⚛️ quantum physics

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

This paper establishes that deciding the existence of torsion in the integral homology of a clique complex is NP-hard and presents a quantum algorithm that serves as a one-sided torsion witness, achieving a near-quadratic speedup over classical methods while highlighting the computational complexity of integral homology beyond Betti numbers.

Original authors: Nhat A. Nghiem, Dominic W. Berry, Trung V. Phan

Published 2026-09-24

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Nhat A. Nghiem, Dominic W. Berry, Trung V. Phan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Data scientists often treat large, messy datasets as if they were landscapes, searching for the shape of the information hidden within. To do this, they use a field called topological data analysis, which looks for the fundamental holes and loops in a collection of points, much like a geologist might study the tunnels and caverns of a mountain range. For years, the most popular way to map these shapes has been to count the holes, a method that works well for many problems but misses a deeper layer of complexity. Just as a map might show a cave system but fail to reveal that the rock walls are made of a specific type of stone that behaves differently under pressure, standard methods often overlook a subtle feature called torsion. This feature describes a kind of twist in the data where a loop, which seems to go nowhere, actually becomes a closed path only after being traced a specific number of times. This hidden structure is crucial in fields ranging from biology to physics, where it can reveal how molecules fold or how quantum particles are constrained, yet it has remained largely invisible to the tools used to analyze it.

A team of researchers has now tackled this blind spot, investigating both the difficulty of finding these twists and a new way to find them using quantum computers. They began by asking a fundamental question: is it possible to efficiently determine if a dataset contains these torsion features? Their investigation led to a definitive answer regarding the limits of classical computing. They proved that for a specific type of data structure, deciding whether a torsion twist exists is a problem so complex that no known computer algorithm can solve it quickly, no matter how powerful the machine becomes. This finding is significant because it places a hard ceiling on what traditional computers can achieve in this area, suggesting that the task of uncovering these specific topological secrets is inherently difficult. The researchers showed that this difficulty is not just a theoretical curiosity but applies directly to real-world problems, such as determining the capabilities of certain quantum error-correcting codes used to protect information.

Having established that the problem is hard for classical machines, the team turned to quantum computing to see if a different approach could offer an advantage. They developed a new quantum algorithm designed to act as a witness for these torsion features. Unlike a standard detector that might give a definitive yes or no, this new tool operates with a specific kind of caution. If the algorithm runs and finds evidence, it confidently reports that a torsion twist is present in the data. However, if it does not find evidence, it does not claim the twist is absent; instead, it simply states that the result is inconclusive. This one-sided nature is a deliberate design choice that allows the algorithm to run much faster than any known classical method. In scenarios where the data is large and complex, the quantum approach can perform the necessary calculations with a speed that offers a near-quadratic improvement over the best classical alternatives, effectively reducing the time required to search for these hidden structures by a factor proportional to the square root of the input size.

The work connects two distinct worlds: the abstract mathematics of how shapes are built and the practical engineering of quantum machines. By proving that finding these twists is computationally hard, the researchers have clarified the boundaries of what is possible, showing that integral homology—the complete mathematical description of a shape including its twists—is a challenging task for computers. At the same time, by providing a quantum algorithm that can detect these features more efficiently, they have opened a new door for analyzing complex data. This dual result, which combines a proof of difficulty with a demonstration of speed, suggests that while the full picture of topological data is hard to see, quantum computers may be the only tools capable of revealing the most elusive parts of it. The study does not solve every problem in the field, but it successfully identifies a new frontier where quantum advantage is possible, moving the field beyond simple hole-counting to a more complete understanding of the data's shape.

Technical Summary: Quantum Topological Data Analysis Beyond Betti Numbers

1. Problem Statement

Topological Data Analysis (TDA) utilizes tools from algebraic topology to study the shape of data. While recent quantum computing efforts have focused on estimating Betti numbers (which characterize the rank of the free part of homology groups), these metrics capture only a fraction of the topological information. Specifically, Betti numbers are blind to torsion, a structural feature where nontrivial cycles become trivial after being repeated a finite number of times (e.g., a cycle $\gamma$ such that $p\gamma = 0$ for a prime $p$ , but $\gamma \neq 0$ ).

Torsion encodes discrete topological information relevant to physical systems, such as homological quantum rotor codes, discrete charges in gauge theory, and finite logical sectors. The central problem addressed in this work is the computational complexity of detecting $p$ -torsion (torsion of order divisible by a prime $p$ ) in the integral homology group $H_r(K, \mathbb{Z})$ of a clique complex $K = \text{Cl}(G)$ derived from a graph $G$ . Furthermore, the authors investigate whether a quantum algorithm can efficiently detect this structure compared to classical methods.

2. Methodology

Complexity Hardness Proof

The authors establish the computational hardness of detecting $p$ -torsion through a reduction from the problem of estimating Betti numbers, which is known to be NP-hard.

Reduction Strategy: They construct a new complex $K' = K * P$ , where $K$ is the original clique complex and $P$ is a flag triangulation of a specific topological space (Real Projective Space $\mathbb{R}P^2$ for $p=2$ , or a Moore space $M(\mathbb{Z}/p, 1)$ for general prime $p$ ).
Künneth Formula: Using the reduced Künneth homology formula, they demonstrate that the homology of the join $K * P$ $K * P$ relates to the homology of $K$ $K$ via a tensor product with the homology of $P$ $P$ .
- For $P = \mathbb{R}P^2$ , $\tilde{H}_1(P, \mathbb{Z}) \cong \mathbb{Z}/2\mathbb{Z}$ .
- The formula yields $\tilde{H}_{r+2}(K * P, \mathbb{Z}) \cong \tilde{H}_r(K, \mathbb{Z}) \otimes \mathbb{Z}/p\mathbb{Z}$ .
Implication: If $\tilde{H}_r(K, \mathbb{Z})$ has a non-zero rank (i.e., $\beta_r(K) > 0$ ), the resulting group $\tilde{H}_{r+2}(K * P, \mathbb{Z})$ contains $p$ -torsion. Thus, an efficient algorithm for detecting $p$ -torsion would imply an efficient algorithm for determining if $\beta_r(K) > 0$ , proving that $p$ -torsion detection is NP-hard.

Quantum Algorithm: One-Sided Torsion Witness

To address the detection problem, the authors propose a quantum algorithm that functions as a one-sided torsion witness.

Mathematical Insight: The algorithm relies on the Universal Coefficient Theorem, which relates homology over integers to homology over a finite field $\mathbb{F}_p$ :
$\dim H_r(K, \mathbb{F}_p) = \beta_r + t_r(p) + t_{r-1}(p)$
where $\beta_r$ is the Betti number (free rank) and $t_r(p)$ is the count of cyclic summands of order divisible by $p$ . Since $\beta_r$ is invariant across fields, a change in $\dim H_r(K, \mathbb{F}_p)$ when varying $p$ indicates the presence of torsion.
Algorithmic Steps:
1. Rank Estimation: The algorithm estimates the rank of the boundary operators $\partial_r$ and $\partial_{r+1}$ over the finite field $\mathbb{F}_p$ .
2. Quantum Rank Sketching: Instead of classical Gaussian elimination, the algorithm uses a quantum approach to estimate the entries of a "sketch" matrix $M = U \partial_r V$ , where $U$ and $V$ are matrices with entries drawn from an $\epsilon$ -biased distribution.
3. State Preparation: It utilizes block-encoding of the boundary operator, Dicke state preparation, and quantum arithmetic circuits to compute the matrix entries $M_{ij} = U_i^T \partial_r V_j \pmod p$ .
4. Classical Post-Processing: The estimated entries are used to construct the matrix $M$ , which is then classically diagonalized to determine its rank.
5. Witness Output: The algorithm compares the sum of ranks of $\partial_r$ and $\partial_{r+1}$ across different primes $p \in P$ . If the sum changes for some $p$ , it outputs WITNESS, indicating that either $H_r(K, \mathbb{Z})$ or $H_{r-1}(K, \mathbb{Z})$ contains $p$ -torsion for some $p$ ; otherwise, it outputs INCONCLUSIVE.

3. Key Results

Complexity-Theoretic Results

Theorem 1 (NP-Hardness): Determining whether $H_r(K, \mathbb{Z})$ contains $p$ -torsion is NP-hard for a fixed prime $p$ .
Corollaries: This hardness extends to several related problems, including:
- Deciding if a homological quantum rotor code possesses a finite-dimensional logical sector of a specific order.
- Determining if the Bockstein homomorphism is non-zero.
- Deciding if reducing an integer matrix modulo $p$ increases its rank (Smith normal form implications).
- Testing $p$ -saturation of simplicial boundary lattices.
- Detecting $p$ -torsion in integral cohomology.

Algorithmic Results

Theorem 2 (Quantum Speedup): The proposed quantum algorithm outputs a WITNESS or INCONCLUSIVE result.
Complexity Comparison:
- Quantum Complexity: $\tilde{O}\left( |P| p_{\max}^2 \sqrt{\binom{n}{r+1}} \text{poly}(n) \right)$ .
- Classical Complexity: $O\left( |P| \binom{n}{r+1} \text{poly}(n) \log^3(1/\Delta) \right)$ .
Speedup: The quantum algorithm achieves a near-quadratic speedup in the term $\binom{n}{r+1}$ (the number of potential $r$ -simplices) compared to the corresponding classical algorithm under the same input oracle model. This speedup is most effective when the rank of the boundary operator is small or bounded.

4. Significance and Claims

The authors claim that this work significantly expands the scope of Quantum Topological Data Analysis (QTDA) beyond the estimation of Betti numbers to the more complex integral homology structure.

Completeness of Hardness Landscape: By proving the NP-hardness of $p$ -torsion detection, the paper complements existing hardness results for Betti numbers, demonstrating that integral homology as a whole is computationally challenging. This suggests that generic efficient solutions for full integral homology are unlikely.
Physical Relevance: The hardness results provide a complexity-theoretic foundation for physical problems involving discrete topological structures, such as identifying finite logical sectors in homological rotor codes or discrete gauge symmetries in string compactifications.
Quantum Advantage: The paper demonstrates that while full integral homology is hard, specific aspects (like detecting the presence of torsion) can be addressed with a quantum advantage. The proposed algorithm offers a near-quadratic speedup, filling a gap where previous QTDA work focused solely on free parts (Betti numbers) or relied on real-field coefficients that obscure torsion.
Limitations: The authors modestly note that the algorithm is a "one-sided witness" (it cannot definitively prove the absence of torsion if the result is inconclusive) and that whether a speedup beyond quadratic is possible for revealing the full torsion structure remains an open question.