arXiv:2609.28112
Quantum Topological Data Analysis Beyond Betti Numbers: Complexity Hardness $\&$ An Algorithm for Torsion Witness
Nhat A. Nghiem, Dominic W. Berry, Trung V. Phan
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 = \mathrm{Cl}(G)$, we first prove that, for fixed $r$ and prime $p$, deciding whether $H_r(K,\mathbb{Z})$ 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,\mathbb{Z})$ or $H_{r-1}(K,\mathbb{Z})$ contains $p$-torsion for some $p\in 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.
AI Summary
The paper studies torsion in integral homology of graph clique complexes, beyond the free ranks measured by Betti numbers. It addresses the complexity of detecting $p$-torsion and quantum algorithms for witnessing its presence, with motivations including finite-dimensional logical sectors in homological quantum rotor codes. The hardness construction reduces Betti-number nonvanishing on torsion-free clique complexes to torsion detection. Joining a source complex $K$ with a fixed flag triangulation $P$ of a Moore space gives $\widetilde H_{r+2}(K*P;\mathbb Z)\cong(\mathbb Z/p\mathbb Z)^{\beta_r(K)}$ by the Künneth formula, transferring NP-hardness with a two-degree shift. Related formulations involve Bockstein maps, boundary-matrix invariant factors, lattice saturation, and cohomology. The quantum procedure compares homology dimensions across finite fields using $\dim H_r(K;\mathbb F_p)=\beta_r+t_r(p)+t_{r-1}(p)$. It computes boundary ranks through randomized sketches, reversible pseudorandom arithmetic, and amplitude estimation, followed by classical elimination. A detected difference witnesses torsion in degree $r$ or $r-1$; otherwise the output is INCONCLUSIVE. When simplex counts and sketch sizes are polynomial in $n$, the stated runtime is $\widetilde O(|P|p_{\max}^2\sqrt{\binom n{r+1}}\operatorname{poly}(n))$, nearly quadratic in the candidate-simplex count relative to the corresponding enumeration-based classical algorithm. Limitations include missed torsion when tested primes give equal dimensions, dependence on low-rank promises for efficient sketching, and precision sufficient to recover sketch entries exactly. A separate join construction transfers previously studied Betti-estimation speedups to torsion-factor counting on specially structured complexes.
Central claim may not hold: The abstract claims NP-hardness for fixed homological degree r, although p-torsion detection at fixed r is polynomial-time computable by comparing the rational and finite-field ranks of the explicitly enumerable boundary matrix. The proposed dense-regime speedup incorrectly replaces precision δ by sqrt(δ) using only a small-overlap assumption, overlooking the linear error term 2sqrt(x)ε needed to recover the integer sketch entries.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.