{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T12:36:30Z","timestamp":1793277390356,"version":"4.5.0"},"reference-count":59,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","funder":[{"name":"QFARM"},{"name":"Spanish Ministry of Science and Innovation","award":["CEX2019-00904-S"],"award-info":[{"award-number":["CEX2019-00904-S"]}]},{"name":"Spanish Ministry of Science and Innovation","award":["PID2020-113523GB-I0"],"award-info":[{"award-number":["PID2020-113523GB-I0"]}]},{"DOI":"10.13039\/100011664","name":"SLAC National Accelerator Laboratory","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100011664","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["PHY-1125565"],"award-info":[{"award-number":["PHY-1125565"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["828076"],"award-info":[{"award-number":["828076"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0020360"],"award-info":[{"award-number":["DE-SC0020360"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2026,10,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1137\/24m1710243","type":"journal-article","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T08:28:25Z","timestamp":1767342505000},"page":"FOCS24-137-FOCS24-235","source":"Crossref","is-referenced-by-count":3,"title":["Gapped Clique Homology on Weighted Graphs Is \\({\\text{QMA}_1}\\)-Hard and Contained in QMA"],"prefix":"10.1137","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8152-6340","authenticated-orcid":true,"given":"Robbie","family":"King","sequence":"first","affiliation":[{"name":"Department of Computing and Mathematical Sciences, Caltech, Pasadena, CA 91125 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tamara","family":"Kohler","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Stanford University, Stanford, CA 94305 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,1,2]]},"reference":[{"key":"ref1","first-page":"82","volume":"9","author":"Aaronson S.","year":"2009","journal-title":"Quantum Inf. Comput."},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2016.05.003"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293639"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1145\/2491533.2491549"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"D. Aharonov, V. Jones, and Z. Landau, A polynomial quantum algorithm for approximating the Jones polynomial, in Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 427\u2013436.","DOI":"10.1145\/1132516.1132579"},{"key":"ref6","first-page":"1202","volume":"7","author":"Apers S.","year":"2023","journal-title":"Quatnum"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.87.165145"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-006-0150-x"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Exponential improvement in precision for simulating sparse Hamiltonians, in Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, ACM, New York, 2014, pp. 283\u2013292.","DOI":"10.1145\/2591796.2591854"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.5.010319"},{"key":"ref11","unstructured":"F. G. Brand\u00e3o, Entanglement Theory and the Quantum Simulation of Many-Body Physics, PhD thesis, preprint, arXiv:0810.0026, 2008."},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/536\/10552"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.22331\/q-2024-04-30-1325"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1145\/3549524"},{"key":"ref15","first-page":"94","volume-title":"Theory of Quantum Computation, Communication, and Cryptography: 5th Conference, TQC 2010, Leeds, UK, Rev. Selected Papers","author":"Childs A. M.","year":"2010"},{"key":"ref16","first-page":"15","volume":"53","author":"Chow T. Y.","year":"2006","journal-title":"Notices Amer. Math. Soc."},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-024-54118-z"},{"key":"ref18","unstructured":"P. M. Crichigno, Supersymmetry and Quantum Computation, preprint, https:\/\/arxiv.org\/abs\/2011.01239 (2020)."},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1804949115"},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"B. Donald and D. Chang, On the complexity of computing the homology type of a triangulation, in Proceedings of the 32nd Annual Symposium of Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1991, pp. 650\u2013661, https:\/\/doi.org\/10.1109\/SFCS.1991.185432.","DOI":"10.1109\/SFCS.1991.185432"},{"key":"ref21","unstructured":"B. Fefferman and C. Y.Y. Lin, A complete characterization of unitary quantum space, preprint, https:\/\/arxiv.org\/abs\/1604.01384 (2016)."},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.90.120402"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0040-9383(94)90030-2"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1561\/0400000066"},{"key":"ref25","unstructured":"A. Gily\u00e9n, S. Lloyd, and E. Tang, Quantum-Inspired Low-Rank Stochastic Regression with Logarithmic Dependence on the Dimension, preprint, arXiv:1811.04909, 2018."},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s10827-016-0608-6"},{"key":"ref27","unstructured":"T. E. Goldberg, Combinatorial Laplacians of simplicial complexes, Senior thesis, Bard College, Annandale-on-Hudson, NY, 6, 2002."},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/140957056"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"A. Gundert and M. Szedl\u00e1k, Higher dimensional Cheeger inequalities, in Proceedings of the Thirtieth Annual Symposium on Computational Geometry, ACM, New York, 2014, pp. 181\u2013188.","DOI":"10.1145\/2582112.2582118"},{"key":"ref30","unstructured":"S. Gunn and N. Kornerup, Review of a Quantum Algorithm for Betti Numbers, preprint, arXiv:1906.07673, 2019."},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.22331\/q-2022-11-10-855"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.22331\/q-2022-12-07-873"},{"key":"ref33","unstructured":"L. Huijse, A Supersymmetric Model for Lattice Fermions, Ph.D. thesis, Amsterdam University, Amsterdam, 2010."},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/14\/7\/073002"},{"key":"ref35","unstructured":"S. P. Jordan, H. Kobayashi, D. Nagaj, and H. Nishimura, Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems, https:\/\/arxiv.org\/abs\/1111.5306, 2012."},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445226"},{"key":"ref37","unstructured":"A. Y. Kitaev, Quantum Measurements and the Abelian Stabilizer Problem, https:\/\/arxiv.org\/abs\/quant-ph\/9511026, 1995."},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/047"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/107"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms10138"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"ref42","doi-asserted-by":"crossref","unstructured":"A. Lubotzky, High dimensional expanders, in Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, World Scientific, Singapore, 2018, pp. 705\u2013730.","DOI":"10.1142\/9789813272880_0027"},{"key":"ref43","unstructured":"MATHEMATICA, Mathematica Proofs, https:\/\/www.dropbox.com\/sh\/p3nwoqacyj0gl1l\/AADDb6aULOSn7ZChfSsq1NTba?dl=0."},{"key":"ref44","unstructured":"S. McArdle, A. Gily\u00e9n, and M. Berta, A Streamlined Quantum Algorithm for Topological Data Analysis with Exponentially Fewer Qubits, preprint, arXiv:2209.12887, 2022."},{"key":"ref45","series-title":"Cambridge Stud. Adv. Math. 58","volume-title":"A User\u2019s Guide to Spectral Sequences","author":"McCleary J.","year":"2001"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1088\/0034-4885\/75\/2\/022001"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3002-x"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1098\/rsif.2014.0873"},{"key":"ref49","unstructured":"C. Rayudu, Fermionic independent set and Laplacian of an independence complex are QMA-hard, preprint, https:\/\/arxiv.org\/abs\/2411.03230 (2025)."},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.3389\/fncom.2017.00048"},{"key":"ref51","unstructured":"D. Rudolph, Towards a Universal Gateset for \\(\\textsf{QMA}_1\\), preprint, https:\/\/arxiv.org\/abs\/2411.02681 (2025)."},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.4.040349"},{"key":"ref53","first-page":"84","volume":"3","author":"Shi Y.","year":"2003","journal-title":"Quantum Inf. Comput."},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2014.01.002"},{"key":"ref55","doi-asserted-by":"crossref","unstructured":"E. Tang, A quantum-inspired classical algorithm for recommendation systems, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2019, pp. 217\u2013228.","DOI":"10.1145\/3313276.3316310"},{"key":"ref56","unstructured":"S. Ubaru, I. Y. Akhalwaya, M. S. Squillante, K. L. Clarkson, and L. Horesh, Quantum Topological Data Analysis with Linear Depth and Exponential Speedup, preprint, arXiv:2108.02811, 2021."},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-statistics-031017-100045"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.4310\/jdg\/1214437492"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1007\/BF01217730"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1710243","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,29]],"date-time":"2026-10-29T12:07:36Z","timestamp":1793275656000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1710243"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,2]]},"references-count":59,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2026,10,31]]}},"alternative-id":["10.1137\/24M1710243"],"URL":"https:\/\/doi.org\/10.1137\/24m1710243","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,2]]}}}