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

Nhat A. Nghiem, Dominic W. Berry, Trung V. Phan

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.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.

quant-pharXiv:2609.28112Sep 24, 20260 citations

Quantum Computation with Topological Codes

Keisuke Fujii

SpringerBriefs in mathematical physicsJan 1, 201559 citations

Homological Quantum Error Correction with Torsion

S. Novák

Homological quantum error correction uses tools of algebraic topology and homological algebra to derive Calderbank-Shor-Steane quantum error correcting codes from cellulations of topological spaces. This work is an exploration of the relevant topics, a journey from classical error correction, through homology theory, to CSS codes acting on qudit systems. Qudit codes have torsion in their logical spaces. This is interesting to study because it gives us extra logical qudits, of possibly different dimension. Apart from examples and comments on the topic, we prove an original result, the Structure Theorem for the Qudit Logical Space, an application of the Universal Coefficient Theorem from homological algebra, which gives us information about the logical space when torsion is involved, and that improves on a previous result in the literature. Furthermore, this work introduces our own abstracted and restricted version of the general notion of a cell complex, suited exactly to our needs.Homological quantum error correction uses tools of algebraic topology and homological algebra to derive Calderbank-Shor-Steane quantum error correcting codes from cellulations of topological spaces. This work is an exploration of the relevant topics, a journey from classical error correction, through homology theory, to CSS codes acting on qudit systems. Qudit codes have torsion in their logical spaces. This is interesting to study because it gives us extra logical qudits, of possibly different dimension. Apart from examples and comments on the topic, we prove an original result, the Structure Theorem for the Qudit Logical Space, an application of the Universal Coefficient Theorem from homological algebra, which gives us information about the logical space when torsion is involved, and that improves on a previous result in the literature. Furthermore, this work introduces our own abstracted and restricted version of the general notion of a cell complex, suited exactly to our needs.

arXiv:2405.03559May 6, 20240 citations

Quantum Codes and Computation

Sankalpa Khadka

Jan 1, 20120 citations

Homology You Can Run: The Topology of Quantum Codes, from the Logical-Qubit Count to the Phase Transition

The Institute for Applied Ontological Mathematics

A CSS quantum error-correcting code is, on the nose, a length-three chain complex over F2 : the commutation law HZ H⊤ X = 0 that makes the code valid is exactly the condition ∂ 2 = 0 that makes a chain complex. We take this identification literally and show that the entire working theory of a quantum code is one homological object the same engine computes, at scale, and certifies. The number of logical qubits is the first Betti number, k = dim H1 = n − rank HX − rank HZ = b1 ; the code distance is the systole, the shortest non-contractible cycle. We reproduce the published parameters of state-of-the-art codes exactly—the toric and hypergraph-product families and the IBM bivariate-bicycle codes [[72, 12, 6]], [[144, 12, 12]], [[90, 8, 10]]—cross-validated four independent ways and kernelcertified for the small cases in Cubical Agda, on CPU and GPU. The two scale certificates—the Betti count b1 and the rank-derived logical count k—are themselves kernel-proved to be a single first-homology certificate (a DescentCertificate both readings factor through), closed terminally through a fixed-point engine. We then run the code, not just measure it. (i) The Union-Find decoder is the engine's connected-components reduction, and "a logical error occurred" is the engine's coboundary decision (the residual cycle has nonzero winding); decoding the toric code at growing distance recovers the accuracy threshold near 9.5%, and the optimal (maximum-likelihood) threshold near 11% is the engine's two homology sectors competing as the domain-wall free energy of a random-bond Ising model on the Nishimori line. (ii) A code's distance scaling is its Tanner-graph spectral expansion: the second eigenvalue λ2 versus the Ramanujan bound is a computable certificate (Sipser–Spielman), exact on the topological tier where the spectral gap obeys γ d2 → 4π 2 . (iii) The full chain complex carries metachecks—redundancies among the parity checks—and we compute them: the bivariate-bicycle codes have six, the engines of single-shot error correction; the 4-dimensional toric code's homology (1, 4, 6, 4, 1), with k = b2 = 6, is the tensor of four circle complexes. (iv) The logical error-rate prefactor is the multiplicity of the systole, A = 2L for the toric code, which we compute exactly. (v) Finally the engine measures a topological phase transition: as random noise thickens, torus-wrapping "giant" cycles appear in a sharp homological-percolation transition at pc ≈ 0.5 that sharpens with system size—the same homology machinery now detecting when noise spontaneously writes a logical operator. (vi) The engine runs over any coefficients: qudit (Fp ) codes are chain complexes over Fp , and the integral homology, computed by the Smith normal form, exposes torsion—so a code's logical-qudit count can depend on the qudit dimension, an extra logical appearing exactly when p divides a torsion coefficient (reproducing the known homology of the torus, the Moore spaces, the Klein bottle, and RP2 ). We are careful to fence what is not claimed: minimum distance is NP-hard in general and we compute it only on the systolic tier; the giant-cycle transition is the random-cluster one, distinct from the maximum-likelihood decoding threshold of the random-bond Ising model. The thesis is singular and operational: a quantum code's parameters, its decoder, its quality, its higher-dimensional structure, its performance prefactor, and its phase transition are not six theories but one—homology you can run. Published by The Institute for Applied Ontological Mathematics.A CSS quantum error-correcting code is, on the nose, a length-three chain complex over F2 : the commutation law HZ H⊤ X = 0 that makes the code valid is exactly the condition ∂ 2 = 0 that makes a chain complex. We take this identification literally and show that the entire working theory of a quantum code is one homological object the same engine computes, at scale, and certifies. The number of logical qubits is the first Betti number, k = dim H1 = n − rank HX − rank HZ = b1 ; the code distance is the systole, the shortest non-contractible cycle. We reproduce the published parameters of state-of-the-art codes exactly—the toric and hypergraph-product families and the IBM bivariate-bicycle codes [[72, 12, 6]], [[144, 12, 12]], [[90, 8, 10]]—cross-validated four independent ways and kernelcertified for the small cases in Cubical Agda, on CPU and GPU. The two scale certificates—the Betti count b1 and the rank-derived logical count k—are themselves kernel-proved to be a single first-homology certificate (a DescentCertificate both readings factor through), closed terminally through a fixed-point engine. We then run the code, not just measure it. (i) The Union-Find decoder is the engine's connected-components reduction, and "a logical error occurred" is the engine's coboundary decision (the residual cycle has nonzero winding); decoding the toric code at growing distance recovers the accuracy threshold near 9.5%, and the optimal (maximum-likelihood) threshold near 11% is the engine's two homology sectors competing as the domain-wall free energy of a random-bond Ising model on the Nishimori line. (ii) A code's distance scaling is its Tanner-graph spectral expansion: the second eigenvalue λ2 versus the Ramanujan bound is a computable certificate (Sipser–Spielman), exact on the topological tier where the spectral gap obeys γ d2 → 4π 2 . (iii) The full chain complex carries metachecks—redundancies among the parity checks—and we compute them: the bivariate-bicycle codes have six, the engines of single-shot error correction; the 4-dimensional toric code's homology (1, 4, 6, 4, 1), with k = b2 = 6, is the tensor of four circle complexes. (iv) The logical error-rate prefactor is the multiplicity of the systole, A = 2L for the toric code, which we compute exactly. (v) Finally the engine measures a topological phase transition: as random noise thickens, torus-wrapping "giant" cycles appear in a sharp homological-percolation transition at pc ≈ 0.5 that sharpens with system size—the same homology machinery now detecting when noise spontaneously writes a logical operator. (vi) The engine runs over any coefficients: qudit (Fp ) codes are chain complexes over Fp , and the integral homology, computed by the Smith normal form, exposes torsion—so a code's logical-qudit count can depend on the qudit dimension, an extra logical appearing exactly when p divides a torsion coefficient (reproducing the known homology of the torus, the Moore spaces, the Klein bottle, and RP2 ). We are careful to fence what is not claimed: minimum distance is NP-hard in general and we compute it only on the systolic tier; the giant-cycle transition is the random-cluster one, distinct from the maximum-likelihood decoding threshold of the random-bond Ising model. The thesis is singular and operational: a quantum code's parameters, its decoder, its quality, its higher-dimensional structure, its performance prefactor, and its phase transition are not six theories but one—homology you can run. Published by The Institute for Applied Ontological Mathematics.

Oct 11, 20260 citations

Quantum Codes Derived from Cyclic Codes

Giuliano G. La Guardia

arXiv:1705.00239International Journal of Theoretical PhysicsApr 29, 201734 citations

Quantum Topological Data Analysis Beyond Betti Numbers: Complexity Hardness

\&

An Algorithm for Torsion Witness

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})

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.