Skip to content
Preprint

Quantum Topological Data Analysis Beyond Betti Numbers: Complexity Hardness $\&$ An Algorithm for Torsion Witness

Sep 2026 · 1 citation · 62 references
Physics

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.

View source

Similar papers

Preprint Sep 2026

Quantum Advantage in Topological Data Analysis via Mayer Homology

Prior work has explored quantum algorithms for topological data analysis (TDA), revealing the possibility of exponential quantum speedups in estimating the ratios of Betti numbers to the dimension of the combinatorial Laplacian. However, this quantity is only non-vanishing and efficient-to-quantumly-estimate when Betti...

Nhat A. Nghiem, R. Babbush, Adam Zalcman et al. · 0 citations
Preprint Sep 2026

Quantum Log-Determinant Methods for Torsion-Sensitive Topological Data Analysis

Betti numbers are central to topological data analysis but fail to capture torsion in integral homology. Torsion can distinguish topological structures with identical Betti numbers, and examples from classical topological data analysis show that it can affect the topology inferred from data. Related torsion-sensitive q...

D. Thanos, Caesnan M. G. Leditto, A. Wesołowski et al. · 1 citation
Sep 2026

Spectral Methods for the Complexity of Planar Graph Homomorphisms

We explore the frontier beyond the recently discovered barrier represented by the \emph{quantum automorphism group} $qut(M)$ in the classification theory of planar graph homomorphisms $PlGH(M)$. We show that analyzing the spectral relations of $M$ can prove \#P-hardness when traditional vertex separation and domain-red...

Ashwin Maran, Jin-Yi Cai, Zhu-Xiao Tang · 0 citations
Preprint Nov 2026

Exploring topological signatures of quantum Fisher information scaling in graph states

Graph states are a versatile resource for quantum metrology, and their quantum Fisher information (QFI) has a closed-form expression in terms of the underlying graph: it counts pairs of vertices with identical neighborhoods. It remains unclear, however, which global structural properties of a graph determine whether it...

Majid Hassani, P. Emonts, Jordi Tura · 0 citations
Preprint Sep 2026

Chern-number estimation: nearly optimal quantum algorithm and provable quantum speedup

Topological phases of matter are characterized by global properties of quantum states beyond conventional local order parameters. The Chern number is a central invariant in this characterization, linking the geometry of quantum states to robust physical observables and making its determination key to understanding quan...

Soichiro Imamura, Shintaro Ae, Kazuki Sakamoto et al. · 1 citation
Preprint Oct 2026

A Complete Proof of $\mathsf{QMA}_1$-Hardness for Weighted Gapped Clique Homology

The computational complexity of simplicial homology has been studied since the question was raised by Kaibel and Pfetsch, and clique homology was later shown to be $\mathsf{QMA}_1$-hard by Crichigno and Kohler. King and Kohler subsequently introduced the weighted, spectrally gapped version considered here and developed...

Tal Barak · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.