Torsion detection in clique complexes is conditionally QMA 1-hard

Quantum algorithms for topological data analysis compute Betti numbers, the ranks of the homology groups of a simplicial complex, which can be read off from the kernel of a combinatorial Laplacian. Deciding whether a Betti number of a clique complex is nonzero is QMA 1-hard, and remains so under a spectral gap promise on vertex-weighted graphs. Integral homology, however, contains information inaccessible to the Laplacian spectrum. A new part that appears in integral homology is torsion: cycles that become boundaries only after being traversed several times, as in a projective plane or a Klein bottle. We provide a simple reduction that allows us to establish the first hardness results for the problem of detecting torsion. We attach to an arbitrary clique complex a fixed 31-vertex triangulation of the projective plane. The k th mod- 2 Betti number of the input then reappears as 2-torsion two degrees up, while all rational homology disappears and every combinatorial Laplacian acquires a constant spectral gap. We conclude that detecting torsion in clique complexes of unweighted graphs is NP-hard, even under a constant gap promise, and that it is QMA 1-hard if mod- 2 clique homology is.