Gapped Clique Homology on Weighted Graphs Is \({\text{QMA}_1}\)-Hard and Contained in QMA
SIAM Journal on Computing · 31.10.2026 · 55 (5) · FOCS24-137-FOCS24-235
DOI: 10.1137/24m1710243 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 02.01.2026. Verfasst von Robbie King und 1 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 59 Literaturangaben. Gefördert von: QFARM, Spanish Ministry of Science and Innovation, SLAC National Accelerator Laboratory.
Abstract (Originalsprache)
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.
Förderung
- QFARM
- Spanish Ministry of Science and Innovation
- SLAC National Accelerator Laboratory
- National Science Foundation
- Simons Foundation
- U.S. Department of Energy
Zitieren
APA
King, R., & Kohler, T. (2026). Gapped Clique Homology on Weighted Graphs Is \({\text{QMA}_1}\)-Hard and Contained in QMA. SIAM Journal on Computing, 55(5), FOCS24-137-FOCS24-235. https://doi.org/10.1137/24m1710243
Vancouver
King R, Kohler T. Gapped Clique Homology on Weighted Graphs Is \({\text{QMA}_1}\)-Hard and Contained in QMA. SIAM Journal on Computing. 2026;55(5):FOCS24-137-FOCS24-235. doi:10.1137/24m1710243
BibTeX
@article{King2026,
author = {King, Robbie and Kohler, Tamara},
title = {Gapped Clique Homology on Weighted Graphs Is \(\textQMA_1\)-Hard and Contained in QMA},
journal = {SIAM Journal on Computing},
year = {2026},
volume = {55},
number = {5},
pages = {FOCS24--137--FOCS24--235},
doi = {10.1137/24m1710243}
}
EUVIMED