We tackle 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 20 years ago. We show that
this decision problem is QMA1-hard. Moreover, we show that a version of the
problem satisfying a suitable promise and certain constraints is contained in
QMA. This suggests that the seemingly classical problem may in fact be quantum
mechanical. In fact, we are able to significantly strengthen this by showing
that the problem remains QMA1-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 homological algebra. We discuss potential
implications for the problem of quantum advantage in topological data analysis.
