Quantum Topological Data Analysis Beyond Betti Numbers: Complexity Hardness & An Algorithm for Torsion Witness
Abstract
Recent advances have revealed an interplay between quantum computing and topological data analysis (TDA). Most quantum TDA has focused on Betti numbers, which characterize the connectivity and ``holes'' of a dataset. Homology, however, contains additional information in the form of torsion: a nontrivial cycle can become trivial after being repeated finitely, revealing global constraints on how cycles combine and wrap around one another. Beyond applications in biomolecular studies, torsion appears in physical settings including homological quantum rotor codes, discrete charges, and gauge sectors. We study torsion from both classical and quantum perspectives. Given a graph G and its clique complex K = Cl(G), we first prove that, for fixed r and prime p, deciding whether Hr(K,ℤ) contains p-torsion is NP-hard. As a corollary, when a homological rotor code is specified by G, deciding whether the code has a finite-dimensional logical sector of a given order is NP-hard. We discuss related problems, including the Bockstein homomorphism, Smith normal form, lattice saturation, and cohomology. Second, for a finite set of primes P, we develop a quantum algorithm that serves as a one-sided torsion witness. For fixed r, it outputs WITNESS or INCONCLUSIVE, i.e. WITNESS certifies that either Hr(K,ℤ) or Hr−1(K,ℤ) contains p-torsion for some p∈ P while INCONCLUSIVE makes no claim about its presence or absence. We identify a regime in which the algorithm achieves a near-quadratic quantum speedup over the corresponding classical algorithm under the same input model. Our NP-hardness result complements recent hardness results for estimating Betti numbers, adding a complexity-theoretic perspective to quantum TDA. Together, these results demonstrate that integral homology, beyond its Betti numbers, can be computationally challenging.
Related
- Near-Optimal Quantum Algorithm and Complexity Analysis for Riccati Problems
- Topological Signatures of Hardness and Structural Order in Network-Forming Materials
- The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem
- On Certifying Source Sampling Hardness in Quantum Generative Modeling
- Hardness of Approximating Quantum Code Distance Beyond √N
BibTeX
@misc{nghiem2026quantum,
title = {{Quantum Topological Data Analysis Beyond Betti Numbers: Complexity Hardness $\&$ An Algorithm for Torsion Witness}},
author = {Nhat A. Nghiem and Dominic W. Berry and Trung V. Phan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.28112},
eprint = {2609.28112},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28112},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Topological Data Analysis Beyond Betti Numbers: Complexity Hardness & An Algorithm for Torsion Witness
AU - Nhat A. Nghiem
AU - Dominic W. Berry
AU - Trung V. Phan
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2609.28112
UR - https://arxiv.org/abs/2609.28112
AB - Recent advances have revealed an interplay between quantum computing and topological data analysis (TDA). Most quantum TDA has focused on Betti numbers, which characterize the connectivity and ``holes'' of a dataset. Homology, however, contains additional information in the form of torsion: a nontrivial cycle can become trivial after being repeated finitely, revealing global constraints on how cycles combine and wrap around one another. Beyond applications in biomolecular studies, torsion appears in physical settings including homological quantum rotor codes, discrete charges, and gauge sectors. We study torsion from both classical and quantum perspectives. Given a graph G and its clique complex K = Cl(G), we first prove that, for fixed r and prime p, deciding whether H_r(K,ℤ) contains p-torsion is NP-hard. As a corollary, when a homological rotor code is specified by G, deciding whether the code has a finite-dimensional logical sector of a given order is NP-hard. We discuss related problems, including the Bockstein homomorphism, Smith normal form, lattice saturation, and cohomology. Second, for a finite set of primes P, we develop a quantum algorithm that serves as a one-sided torsion witness. For fixed r, it outputs WITNESS or INCONCLUSIVE, i.e. WITNESS certifies that either H_r(K,ℤ) or H_r−1(K,ℤ) contains p-torsion for some p∈ P while INCONCLUSIVE makes no claim about its presence or absence. We identify a regime in which the algorithm achieves a near-quadratic quantum speedup over the corresponding classical algorithm under the same input model. Our NP-hardness result complements recent hardness results for estimating Betti numbers, adding a complexity-theoretic perspective to quantum TDA. Together, these results demonstrate that integral homology, beyond its Betti numbers, can be computationally challenging.
ER -