Clique Homology is QMA1-hard

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 QMA 1 -hard and the exact counting version i...

Full description

Saved in:
Bibliographic Details
Published in:Nature communications 2024-11, Vol.15 (1), p.9846
Main Authors: Crichigno, Marcos, Kohler, Tamara
Format: Article
Language:English
Subjects:
639/705/1042
639/766/483
Complexity
Computer applications
Data analysis
Decision making
Hamiltonian functions
Homology
Humanities and Social Sciences
Mental task performance
multidisciplinary
Quantum mechanics
Science
Science (multidisciplinary)
Topology
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 QMA 1 -hard and the exact counting version is # 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 QMA and # 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. The question of the computational complexity of the homology problem is a long-standing open problem in computational topology. Here, the authors show that the decision version of the problem is QMA1-hard and the exact counting version of the problem is #BPQ-hard, and discuss implications for topological data analysis.
ISSN:2041-1723
DOI:10.1038/s41467-024-54118-z