Clique Homology is $${{\mathsf{QMA}}}_{1}$$-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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub><mml:mrow><mml:mi>QMA</mml:mi></mml:mrow> <mml:mrow><mml:mn>1</mml:mn></mml:mrow> </mml:msub> </mml:math> -hard and the exact counting version is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>#</mml:mi> <mml:mi>BQP</mml:mi></mml:math> -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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>QMA</mml:mi></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>#</mml:mi> <mml:mi>BQP</mml:mi></mml:math> , 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.