Clique Homology is QMA 1 -hard.

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 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 seem

SUBMITTER: Crichigno M 

PROVIDER: S-EPMC11561080 | biostudies-literature | 2024 Nov

REPOSITORIES: biostudies-literature