Clique Homology is $${{\mathsf{QMA}}}_{1}$$ QMA 1 -hard

Marcos Crichigno () and Tamara Kohler ()
Additional contact information
Marcos Crichigno: Imperial College London
Tamara Kohler: Instituto de Ciencias Matemáticas

Nature Communications, 2024, vol. 15, issue 1, 1-10

Abstract: Abstract We address the long-standing question of the computational complexity of determining homology groups of simplicial complexes, a fundamental task in computational topology, posed by Kaibel and Pfetsch over twenty years ago. We show that decision problem is $${{\mathsf{QMA}}}_{1}$$ QMA 1 -hard and the exact counting version is $$\#{\mathsf{BQP}}$$ # BQP -hard. In fact, we strengthen this by showing that the problems remains hard in the case of clique complexes, a family of simplicial complexes specified by a graph which is relevant to the problem of topological data analysis. The proof combines a number of techniques from Hamiltonian complexity and algebraic topology. As we discuss, a version of the problems satisfying a suitable promise and certain constraints is contained in $${\mathsf{QMA}}$$ QMA and $$\#{\mathsf{BQP}}$$ # BQP , respectively. This suggests that the seemingly classical problem may in fact be quantum mechanical. We discuss potential implications for the problem of quantum advantage in topological data analysis.

Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.nature.com/articles/s41467-024-54118-z Abstract (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:natcom:v:15:y:2024:i:1:d:10.1038_s41467-024-54118-z

Ordering information: This journal article can be ordered from
https://www.nature.com/ncomms/

DOI: 10.1038/s41467-024-54118-z

Access Statistics for this article

Nature Communications is currently edited by Nathalie Le Bot, Enda Bergin and Fiona Gillespie

More articles in Nature Communications from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().