The computational complexity of simplicial homology has been studied since the question was raised by Kaibel and Pfetsch, and clique homology was later shown to be
QMA1-hard by Crichigno and Kohler. King and Kohler subsequently introduced the weighted, spectrally gapped version considered here and developed a reduction intended to establish the same hardness result in this setting.
We give a complete proof of the hard direction. The earlier King-Kohler argument contains a gap in the analysis of the nontrivially folded local gadgets, so the required topological and spectral properties have to be re-established on the clique complexes actually produced by the reduction. This is not a local repair of the published proof: the argument requires a new analysis of the local topology, the filtered cochain complexes, and the interaction of many overlapping gadgets.
Our proof uses exact finite certificates for the local combinatorial data and relative homology to determine the effect of each gadget on the encoded qubit space. We then prove the finite-dimensional filtered-Hodge statement needed to recover the corresponding rank-one low-energy penalty and derive a quantitative global estimate that transfers the source-Hamiltonian promise gap to the final weighted Hodge Laplacian. Consequently, for fixed efficiently computable
k(n) and inverse-polynomial
γ(n), weighted gapped clique homology is
QMA1(G)-hard. The previously known
QMA-containment argument is logically independent of the gap and remains unaffected.
Abstract. We study the complexity of a classic problem in computational topology, the homology problem: given a description of some space [Formula: see text] and an integer [Formula: see text], decide if [Formula: see text] contains a [Formula: see text]-dimensional hole. The setting and statement of the homology problem are completely classical, yet we find that the complexity is characterized by quantum complexity classes. Our result can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics established by Witten (1982). We consider clique complexes, motivated by the practical application of topological data analysis (TDA). The clique complex of a graph is the simplicial complex formed by declaring every [Formula: see text]-clique in the graph to be a [Formula: see text]-simplex. Our main result is that deciding whether the clique complex of a weighted graph has a hole or not, given a suitable promise on the gap, is [Formula: see text]-hard and contained in QMA. Our main innovation is a technique to lower bound the eigenvalues of the combinatorial Laplacian operator. For this, we invoke a tool from algebraic topology known as spectral sequences. In particular, we exploit a connection between spectral sequences and Hodge theory outlined by Forman (1994). Spectral sequences will play a role analogous to perturbation theory for combinatorial Laplacians. In addition, we develop the simplicial surgery technique used in prior work by Crichigno and Kohler (2022). Our result provides some suggestion that the quantum TDA algorithm due to Lloyd, Garnerone, and Zanardi (2016) cannot be dequantized, although proving this would require studying the complexity of a different problem related to the combinatorial Laplacian of clique complexes.
We study the complexity of a classic problem in computational topology, the homology problem: given a description of some space
Xand an integer
k, decide if
Xcontains a k-dimensional hole. The setting and statement of the homology problem are completely classical, yet we find that the complexity is characterized by quantum complexity classes. Our result can be seen as an aspect of a connection between homology and supersymmetric quantum mechanics [1]. We consider clique complexes, motivated by the practical application of topological data analysis (TDA). The clique complex of a graph is the simplicial complex formed by declaring every
k+1-clique in the graph to be a k-simplex. Our main result is that deciding whether the clique complex of a weighted graph has a hole or not, given a suitable promise on the gap, is QMA1-hard and contained in QMA. Our main innovation is a technique to lower bound the eigenvalues of the combinatorial Laplacian operator. For this, we invoke a tool from algebraic topology known as spectral sequences. In particular, we exploit a connection between spectral sequences and Hodge theory [2]. Spectral sequences will play a role analogous to perturbation theory for combinatorial Lapla-cians. In addition, we develop the simplicial surgery technique used in prior work [3]. Our result provides some suggestion that the quantum TDA algorithm [4] cannot be dequantized. More broadly, we hope that our results will open up new possibilities for quantum advantage in topological data analysis.
We study the complexity of Local Hamiltonian problems under the restriction that every local term is an unweighted occurrence of the same fixed interaction. In the resulting Single-Interaction Hamiltonian (SIH) model, once the interaction is fixed, the Hamiltonian is specified entirely by its ordered interaction hypergraph.
Our main technical tool is an exact compiler that converts any fixed finite alphabet of local interactions into a single interaction. On a designated auxiliary subspace, the compiled Hamiltonian reproduces the source Hamiltonian exactly, while the complete spectrum below a chosen separation scale is preserved with multiplicity. Combined with a finite-alphabet normalization, this gives a universal polynomial-time reduction from
k-Local Hamiltonian to SIH
3k+3 up to a known global energy scale and inverse-polynomial approximation.
Sharper constructions give QMA-completeness of SIH
3 and of geometrically local SIH
8 with bounded degree and interaction range. In the stoquastic setting, we obtain StoqMA-completeness of Stoq-SIH
3 and QMA-completeness of 1-Pinned Stoq-SIH
4. We also establish hardness results for uniformly system-size-dependent interactions and derive single-interaction formulations of the Hamiltonian quantum PCP conjecture, frustration-free, exponentially precise, and guided Local Hamiltonian problems. These results show that independently chosen local matrices and independently tunable coupling strengths are not necessary for a broad range of Hamiltonian-complexity phenomena.
For clique complexes
X1⊆X2, normalized persistence in degree
d is
rank[Hd(X1)→Hd(X2)]/dimHd(X1). Estimating it requires exact endpoint homology and the inclusion-induced map, even with inverse-polynomial endpoint Laplacian gaps. We prove that additive-error
1/24 estimation is hard for
BQP1G2, the perfect-completeness class over the exact gate set
G2={X,CX,CCX,H⊗H}, and hence for
BQP1 over every finite gate set with entries in a cyclotomic field
Q(ζ2k), even for unweighted clique complexes. The main tool is a finite-certificate kernel-transfer theorem. For a fixed palette of weighted clique gadgets satisfying finitely many exactly checkable local conditions, every unit chain
x of the full geometric complex satisfies
dist(x,K)2≤C(tλ2+⟨x,Δx⟩/(gλ26)), where
K is the embedded kernel of the simulated projector Hamiltonian,
g its gap,
t the number of gadgets, and
λ the private vertex weight. Since
λ is chosen independently of
g, the geometric Laplacian has exactly
dimK zero modes and a gap linear in
g above them. Exact fillings identify the endpoint homology with a quotient
V/WA of the register cycle space, and nested term sets induce the natural quotient epimorphisms, so the persistent rank equals the later kernel dimension without any choice of compatible harmonic representatives. A fixed eight-dimensional label register turns a
BQP1G2 verifier into instances with
βd(X1)=8 and normalized persistence
3/4 or
1/8, and an established common-copy blow-up transfers everything to unweighted graphs.
Khovanov homology is a topological knot invariant that categorifies the Jones polynomial, recognizes the unknot, and is conjectured to appear as an observable in
4D supersymmetric Yang--Mills theory. Despite its rich mathematical and physical significance, the computational complexity of Khovanov homology remains largely unknown. To address this challenge, this work initiates the study of efficient quantum algorithms for Khovanov homology. We provide simple proofs that increasingly accurate additive approximations to the ranks of Khovanov homology are DQC1-hard, BQP-hard, and #P-hard, respectively. For the first two approximation regimes, we propose a novel quantum algorithm. Our algorithm is efficient provided the corresponding Hodge Laplacian thermalizes in polynomial time and has a sufficiently large spectral gap, for which we give numerical and analytical evidence. Our approach introduces a pre-thermalization procedure that allows our quantum algorithm to succeed even if the Betti numbers of Khovanov homology are much smaller than the dimensions of the corresponding chain spaces, overcoming a limitation of prior quantum homology algorithms. We introduce novel connections between Khovanov homology and graph theory to derive analytic lower bounds on the spectral gap.