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.
Gapped Clique Homology on Weighted Graphs Is QMA1-Hard and Contained in QMA
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.
Gapped Clique Homology on weighted graphs is QMA1-hard and contained in QMA
We study the complexity of a classic problem in computational topology, the homology problem: given a description of some space X and an integer k, decide if X contains 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. 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 \emph{spectral sequences}. In particular, we exploit a connection between spectral sequences and Hodge theory. 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. Our result provides some suggestion that the quantum TDA algorithm \emph{cannot} be dequantized. More broadly, we hope that our results will open up new possibilities for quantum advantage in topological data analysis.
A Complete Proof of QMA1-Hardness for Weighted Gapped Clique Homology
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.
We study the complexity of a classic problem in computational topology, the homology problem: given a description of some spaceXand an integerk, decide ifXcontains 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 everyk+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.
Unweighted Gapped Clique Homology is QMA1-complete
Deciding whether the clique complex of a given graph has nontrivial homology in a given dimension, under vertex-product weighting and an inverse-polynomial spectral gap promise on the combinatorial Hodge Laplacian, is known to be QMA1-hard and contained in QMA by King and Kohler (FOCS 2024). The vertex weights are essential in the known proof, where they provide the scale separation needed for the spectral gap analysis. We prove that, when every vertex has weight one, the problem remains QMA1g2-hard and is contained in QMA1g2, where QMA1g2 is QMA1 with the universal gate set g2={X,CX,CCX,H⊗H}. The construction replaces weight by expansion: each vertex of the weighted complex is blown up into a clique whose size encodes its weight. The block sizes are chosen so that symmetric averages reproduce the weighted Hodge metric. The symmetric sector therefore carries the weighted Laplacian up to a common scalar factor, while a local averaging argument gives a uniform lower bound on the orthogonal complement to the symmetric sector. Hence the weighted gap analysis transfers to an unweighted clique complex without introducing either additional low-energy states or spurious homology. Containment in QMA1g2 follows from Rudolph's exact linear combination of unitaries simulation of sparse integer clique Laplacians. The result shows that the gap promise, rather than vertex weighting, is the source of the complexity of gapped clique homology.
Torsion detection in clique complexes is conditionally QMA1-hard
Quantum algorithms for topological data analysis compute Betti numbers, the ranks of the homology groups of a simplicial complex, which can be read off from the kernel of a combinatorial Laplacian. Deciding whether a Betti number of a clique complex is nonzero is QMA1-hard, and remains so under a spectral gap promise on vertex-weighted graphs. Integral homology, however, contains information inaccessible to the Laplacian spectrum. A new part that appears in integral homology is \emph{torsion}: cycles that become boundaries only after being traversed several times, as in a projective plane or a Klein bottle. We provide a simple reduction that allows us to establish the first hardness results for the problem of detecting torsion. We attach to an arbitrary clique complex a fixed 31-vertex triangulation of the projective plane. The kth mod-2 Betti number of the input then reappears as 2-torsion two degrees up, while all rational homology disappears and every combinatorial Laplacian acquires a constant spectral gap. We conclude that detecting torsion in clique complexes of \emph{unweighted} graphs is NP-hard, even under a constant gap promise, and that it is QMA1-hard if mod-2 clique homology is.
Topological data analysis (TDA) is a machine learning technique that uses topology to extract patterns from data and has shown the potential to exhibit quantum advantage. A key concept in TDA is persistent homology, which measures the robustness of topological information at different lengthscales. In this paper, we introduce and study the problem of normalized persistence, a practically motivated and easily interpretable version of persistent homology that counts the fraction of holes that persist at different lengthscales. We prove that a variant of normalized persistence is DQC1-hard and contained in BQP, giving evidence of an exponential quantum speedup for TDA under the standard assumption that DQC1⊆BPP. These are the first DQC1-hardness results for clique complexes, making them directly applicable to TDA instances. We also find a close connection between normalized persistence and the complexity of estimating spectral quantities in the low-energy subspace of local Hamiltonians. We study a family of such problems, including a low-energy normalized subtrace and spectral density. We show that these are DQC1-hard for O(1)-local Hamiltonians, strengthening previous results that required log-local interactions. We also introduce a variant of DQC1 with perfect completeness (SDQC1) to characterize the hardness of problems normalized by an exact kernel. This includes normalized persistence for O(1)-local Hamiltonians, which we show is SDQC1-hard.