Torsion detection in clique complexes is conditionally QMA1-hard
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 QMA1-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 \emph{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 kth 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 \emph{unweighted} graphs is NP-hard, even under a constant gap promise, and that it is QMA1-hard if mod-$2$ clique homology is.
Related
- Torsion, valley holonomy, and Berry phases of quasiparticles encircling dislocations and defect complexes in graphene
- A Complete Proof of QMA1-Hardness for Weighted Gapped Clique Homology
- Taub-NUT as gravitational dyon with torsion
- Maximally symmetric black holes with torsion in Lovelock gravity
- Multistate Torsion in Zitterbewegung
BibTeX
@misc{wesolowski2026torsion,
title = {{Torsion detection in clique complexes is conditionally $QMA_1$-hard}},
author = {Adam Wesołowski},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14110},
eprint = {2609.14110},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14110},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Torsion detection in clique complexes is conditionally QMA_1-hard
AU - Adam Wesołowski
PY - 2026
DA - 2026/09/22
PB - arXiv
DO - 10.48550/arxiv.2609.14110
UR - https://arxiv.org/abs/2609.14110
AB - 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 \emph{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 kth 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 \emph{unweighted} graphs is NP-hard, even under a constant gap promise, and that it is QMA_1-hard if mod-$2$ clique homology is.
ER -