Detecting complex torsion structures in graphs is computationally hard
Torsion detection in clique complexes is conditionally $QMA_1$-hard
Computational Complexity
Summary
Some shapes made from dots and lines have hidden twists called torsion, which are tricky to find. The authors study how hard it is to detect these twists using computers. They show that even deciding if such a twist exists can be very difficult—either hard for classical computers or even for quantum ones, depending on the problem. This means that some deep geometric features in data are complicated to uncover using current algorithmic tools.
What this means in practice
- •For topological data analysts: Identify limits on efficiently detecting torsion features in large network data modeled by clique complexes.
- •For quantum algorithm designers: Understand hardness results guiding the feasibility of quantum algorithms for advanced homology invariants beyond Betti numbers.
A theory result. No direct application yet.
Authors
Adam Wesołowski
Abstract
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 ask how hard it is to detect torsion, and we answer with a simple reduction. 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.