Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$

Understand

We study the complexity of a classic problem in computational topology, the homology problem: given a description of some space $X$ and an integer $k$, decide if $X$ contains a $k$-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.
• We consider clique complexes, motivated by the practical application of topological data analysis (TDA).