Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1411.6049 · Quantum Information and Computation

Quantum invariants of 3-manifolds and NP vs #P

Gorjan Alagic, Catharine W. K. Lo

Published Jan 1, 2017• 2 citations
arXivHTMLPDF

Abstract

The computational complexity class #P captures the difficulty of counting the satisfying assignments to a boolean formula. In this work, we use basic tools from quantum computation to give a proof that the SO(3) Witten-Reshetikhin-Turaev (WRT) invariant of 3-manifolds is #P-hard to calculate. We then apply this result to a question about the combinatorics of Heegaard splittings, motivated by analogous work on link diagrams by M. Freedman. We show that, if #P 6⊆ FPNP, then there exist infinitely many Heegaard splittings which cannot be made logarithmically thin by local WRT-preserving moves, except perhaps via a superpolynomial number of steps. We also outline two extensions of the above results. First, adapting a result of Kuperberg, we show that any presentationindependent approximation of WRT is also #P-hard. Second, we sketch out how all of our results can be translated to the setting of triangulations and Turaev-Viro invariants.

DOI
10.26421/qic17.1-2-8

Related papers

Hardness of computation of quantum invariants on 3-manifolds with restricted topology

Henrique Ennes, Clément Maria

Quantum invariants in low-dimensional topology offer a wide variety of valuable invariants about knots and 3-manifolds, presented by explicit formulas that are readily computable. Their computational complexity has been actively studied and is tightly connected to topological quantum computing. In this article, we prove that for any 3-manifold quantum invariant in the Reshetikhin-Turaev model, there is a deterministic polynomial-time algorithm that, given as input an arbitrary closed 3-manifold M, outputs a closed 3-manifold $$M'$$ M ′ with the same quantum invariant, such that $$M'$$ M ′ is hyperbolic, contains no low genus embedded incompressible surface, and is presented by a strongly irreducible Heegaard diagram. Our construction relies on properties of Heegaard splittings and the Hempel distance. At the level of computational complexity, this proves that the hardness of computing a given quantum invariant of 3-manifolds is preserved even when severely restricting the topology and the combinatorics of the input. This positively answers a question raised by Samperton (Samperton 2023).

arXiv:2503.02814•Journal of Applied and Computational Topology•Jun 25, 2026•3 citations

Estimating Turaev-Viro three-manifold invariants is universal for quantum computation

Gorjan Alagic, Stephen P. Jordan, Robert König +1 more

The Turaev-Viro invariants are scalar topological invariants of compact, orientable $3$-manifolds. We give a quantum algorithm for additively approximating Turaev-Viro invariants of a manifold presented by a Heegaard splitting. The algorithm is motivated by the relationship between topological quantum computers and $(2+1)$-dimensional topological quantum field theories. Its accuracy is shown to be nontrivial, as the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer. Thus approximating certain Turaev-Viro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation. This establishes a relation between the task of distinguishing nonhomeomorphic $3$-manifolds and the power of a general quantum computer.

arXiv:1003.0923•Physical Review A•Oct 8, 2010•23 citations

Classical and Quantum Algorithms for Topological Invariants of Torus Bundles

Nelson Abdiel Colón Vargas, Carlos Ortiz Marrero

Computing topological invariants of 3-manifolds is generally intractable, yet specialized algebraic structures can enable efficient algorithms. For Witten-Reshetikhin-Turaev (WRT) invariants of torus bundles, we exploit the non-commutative torus structure to embed the skein algebra of the closed torus into its symmetric subalgebra at roots of unity. This yields a fixed $N^2$-dimensional representation that supports polynomial-time classical computation with $O(N^2)$ space, and a quantum algorithm using only $O(\log N)$ qubits -- an exponential space advantage. We further prove that extracting individual expansion coefficients is #P-complete, yet there is a quantum algorithm that can efficiently approximate these coefficients for a non-negligible fraction of configurations.

quant-pharXiv:2512.19028•Dec 23, 2025•0 citations

Computation of Large Asymptotics of 3-Manifold Quantum Invariants

Clément Maria, Owen Rouillé

Quantum topological invariants have played an important role in computational topology, and they are at the heart of major modern mathematical conjectures. In this article, we study the experimental problem of computing large r values of Turaev-Viro invariants TVr. We base our approach on an optimized backtracking algorithm, consisting of enumerating combinatorial data on a triangulation of a 3-manifold. We design an easily computable parameter to estimate the complexity of the enumeration space, based on lattice point counting in polytopes, and show experimentally its accuracy. We apply this parameter to a preprocessing strategy on the triangulation, and combine it with multi-precision arithmetics in order to compute the Turaev-Viro invariants. We finally study the improvements brought by these optimizations compared to state-of-the-art implementations, and verify experimentally Chen and Yang's volume conjecture on a census of closed 3-manifolds.

arXiv:2010.14316•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2021•6 citations

Quantum Computing with Heegaard Splittings of 3-manifolds

Henrique Ennes

Topological quantum field theories (TQFTs) define invariants for closed 3-manifolds that can be directly computed from Heegaard splittings of these spaces, combinatorial representations in which manifolds are described as gluing handlebodies along boundary surfaces. Density properties of representations associated to TQFTs imply that certain approximation schemes of some of these invariants are universal for quantum computing, while other schemes define #P-hard problems. In this thesis, we exploit this connection between quantum computing and TQFT invariants of closed 3-manifolds. First, we establish a compact data structure for Heegaard splittings, which we encode as sets of curves on triangulations of surfaces. In particular, we achieve exponential compression in space with respect to the number of intersections between curves. Even with such a compressed representation, we show, both theoretically and empirically, that several fundamental operations on the Heegaard splitting and on the represented manifold can be achieved in polynomial time on the input. Next, we extend the results on the complexity bounds of approximating TQFT invariants by demonstrating that the problem hardness is preserved even if when the class of manifolds considered is severely restricted. The use of closed 3-manifolds for simulating quantum computing brings us to the Solovay-Kitaev algorithm. While this method is extremely efficient as a function of the target error level in approximating a unitary operator by universal sets of quantum gates, it scales exponentially on the gates' qudits' dimension. We address this bottleneck by proposing a modification in which exponentially scaling is moved to preprocessing step. Finally, we move from the study of implementation error to dealing with external noise. We propose the use of flag devices on top of error detection codes. Through Monte Carlo simulations, we show that these can lead to significant improvements in state-of-the-art methods.

•Sep 29, 2026•0 citations

A polynomial time algorithm to compute quantum invariants of 3-manifolds with bounded first Betti number.

Clément Maria, Jonathan Spreer

In this article, we introduce a fixed parameter tractable algorithm for computing the Turaev-Viro invariants TV4,q, using the dimension of the first homology group of the manifold as parameter. This is, to our knowledge, the first parameterised algorithm in computational 3-manifold topology using a topological parameter. The computation of TV4,q is known to be #P-hard in general; using a topological parameter provides an algorithm polynomial in the size of the input triangulation for the extremely large family of 3-manifolds with first homology group of bounded rank. Our algorithm is easy to implement and running times are comparable with running times to compute integral homology groups for standard libraries of triangulated 3- manifolds. The invariants we can compute this way are powerful: in combination with integral homology and using standard data sets we are able to roughly double the pairs of 3-manifolds we can distinguish. We hope this qualifies TV4,q to be added to the short list of standard properties (such as orientability, connectedness, Betti numbers, etc.) that can be computed ad-hoc when first investigating an unknown triangulation.

ACM-SIAM Symposium on Discrete Algorithms (SODA)•Jan 1, 2017•5 citations
The computational complexity class #P captures the difficulty of counting the satisfying assignments to a boolean formula. In this work, we use basic tools from quantum computation to give a proof that the SO(3) Witten-Reshetikhin-Turaev (WRT) invariant of 3-manifolds is #P-hard to calculate. We then apply this result to a question about the combinatorics of Heegaard splittings, motivated by analogous work on link diagrams by M. Freedman. We show that, if #P 6⊆ FPNP, then there exist infinitely many Heegaard splittings which cannot be made logarithmically thin by local WRT-preserving moves, except perhaps via a superpolynomial number of steps. We also outline two extensions of the above results. First, adapting a result of Kuperberg, we show that any presentationindependent approximation of WRT is also #P-hard. Second, we sketch out how all of our results can be translated to the setting of triangulations and Turaev-Viro invariants.
Quantum invariants in low-dimensional topology offer a wide variety of valuable invariants about knots and 3-manifolds, presented by explicit formulas that are readily computable. Their computational complexity has been actively studied and is tightly connected to topological quantum computing. In this article, we prove that for any 3-manifold quantum invariant in the Reshetikhin-Turaev model, there is a deterministic polynomial-time algorithm that, given as input an arbitrary closed 3-manifold M, outputs a closed 3-manifold M′M'M′ M ′ with the same quantum invariant, such that M′M'M′ M ′ is hyperbolic, contains no low genus embedded incompressible surface, and is presented by a strongly irreducible Heegaard diagram. Our construction relies on properties of Heegaard splittings and the Hempel distance. At the level of computational complexity, this proves that the hardness of computing a given quantum invariant of 3-manifolds is preserved even when severely restricting the topology and the combinatorics of the input. This positively answers a question raised by Samperton (Samperton 2023).
The Turaev-Viro invariants are scalar topological invariants of compact, orientable 333-manifolds. We give a quantum algorithm for additively approximating Turaev-Viro invariants of a manifold presented by a Heegaard splitting. The algorithm is motivated by the relationship between topological quantum computers and (2+1)(2+1)(2+1)-dimensional topological quantum field theories. Its accuracy is shown to be nontrivial, as the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer. Thus approximating certain Turaev-Viro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation. This establishes a relation between the task of distinguishing nonhomeomorphic 333-manifolds and the power of a general quantum computer.
Computing topological invariants of 3-manifolds is generally intractable, yet specialized algebraic structures can enable efficient algorithms. For Witten-Reshetikhin-Turaev (WRT) invariants of torus bundles, we exploit the non-commutative torus structure to embed the skein algebra of the closed torus into its symmetric subalgebra at roots of unity. This yields a fixed N2N^2N2-dimensional representation that supports polynomial-time classical computation with O(N2)O(N^2)O(N2) space, and a quantum algorithm using only O(log⁡N)O(\log N)O(logN) qubits -- an exponential space advantage. We further prove that extracting individual expansion coefficients is #P-complete, yet there is a quantum algorithm that can efficiently approximate these coefficients for a non-negligible fraction of configurations.
Quantum topological invariants have played an important role in computational topology, and they are at the heart of major modern mathematical conjectures. In this article, we study the experimental problem of computing large r values of Turaev-Viro invariants TVr. We base our approach on an optimized backtracking algorithm, consisting of enumerating combinatorial data on a triangulation of a 3-manifold. We design an easily computable parameter to estimate the complexity of the enumeration space, based on lattice point counting in polytopes, and show experimentally its accuracy. We apply this parameter to a preprocessing strategy on the triangulation, and combine it with multi-precision arithmetics in order to compute the Turaev-Viro invariants. We finally study the improvements brought by these optimizations compared to state-of-the-art implementations, and verify experimentally Chen and Yang's volume conjecture on a census of closed 3-manifolds.
Topological quantum field theories (TQFTs) define invariants for closed 3-manifolds that can be directly computed from Heegaard splittings of these spaces, combinatorial representations in which manifolds are described as gluing handlebodies along boundary surfaces. Density properties of representations associated to TQFTs imply that certain approximation schemes of some of these invariants are universal for quantum computing, while other schemes define #P-hard problems. In this thesis, we exploit this connection between quantum computing and TQFT invariants of closed 3-manifolds. First, we establish a compact data structure for Heegaard splittings, which we encode as sets of curves on triangulations of surfaces. In particular, we achieve exponential compression in space with respect to the number of intersections between curves. Even with such a compressed representation, we show, both theoretically and empirically, that several fundamental operations on the Heegaard splitting and on the represented manifold can be achieved in polynomial time on the input. Next, we extend the results on the complexity bounds of approximating TQFT invariants by demonstrating that the problem hardness is preserved even if when the class of manifolds considered is severely restricted. The use of closed 3-manifolds for simulating quantum computing brings us to the Solovay-Kitaev algorithm. While this method is extremely efficient as a function of the target error level in approximating a unitary operator by universal sets of quantum gates, it scales exponentially on the gates' qudits' dimension. We address this bottleneck by proposing a modification in which exponentially scaling is moved to preprocessing step. Finally, we move from the study of implementation error to dealing with external noise. We propose the use of flag devices on top of error detection codes. Through Monte Carlo simulations, we show that these can lead to significant improvements in state-of-the-art methods.
In this article, we introduce a fixed parameter tractable algorithm for computing the Turaev-Viro invariants TV4,q, using the dimension of the first homology group of the manifold as parameter. This is, to our knowledge, the first parameterised algorithm in computational 3-manifold topology using a topological parameter. The computation of TV4,q is known to be #P-hard in general; using a topological parameter provides an algorithm polynomial in the size of the input triangulation for the extremely large family of 3-manifolds with first homology group of bounded rank. Our algorithm is easy to implement and running times are comparable with running times to compute integral homology groups for standard libraries of triangulated 3- manifolds. The invariants we can compute this way are powerful: in combination with integral homology and using standard data sets we are able to roughly double the pairs of 3-manifolds we can distinguish. We hope this qualifies TV4,q to be added to the short list of standard properties (such as orientability, connectedness, Betti numbers, etc.) that can be computed ad-hoc when first investigating an unknown triangulation.