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:2503.02814 · Journal of Applied and Computational Topology

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

Henrique Ennes, Clément Maria

Published Jun 25, 2026• 0 citations
arXivHTMLPDF

Abstract

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

DOI
10.1007/s41468-026-00245-z

Related papers

Quantum invariants of 3-manifolds and NP vs #P

Gorjan Alagic, Catharine W. K. Lo

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.

arXiv:1411.6049•Quantum Information and Computation•Jan 1, 2017•1 citation

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

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•15 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

Possible universal quantum algorithms for generalized Turaev-Viro invariants

Mario E. Vélez, Juan Ospina

An emergent trend in quantum computation is the topological quantum computation (TQC). Briefly, TQC results from the application of quantum computation with the aim to solve the problems of quantum topology such as topological invariants for knots and links (Jones polynomials, HOMFLY polynomials, Khovanov polynomials); topological invariants for graphs (Tutte polynomial and Bollobás-Riordan polynomial); topological invariants for 3-manifolds (Reshetiskin-Turaev, Turaev-Viro and Turaer-Viro-Ocneanu invariants) and topological invariants for 4-manifolds( Crane-Yetter invariants). In a few words, TQC is concerned with the formulation of quantum algorithms for the computation of these topological invariants in quantum topology. Given that one of the fundamental achievements of quantum topology was the discovery of strong connections between monoidal categories and 3-dimensional manifolds, in TQC is possible and necessary to exploit such connections with the purpose to formulate universal quantum algorithms for topological invariants of 3-manifolds. In the present work we make an exploration of such possibilities. Specifically we search for universal quantum algorithms for generalized Turaev-Viro invariants of 3-manifolds such as the Turaev-Viro-Ocneanu invariants, the Kashaev-Baseilhac-Benedetti invariants of 3-manifolds with links and the Geer-Kashaev-Turaev invariants of 3-manifolds with a link and a principal bundle. We also look for physical systems (three dimensional topological insulators and three-dimensional gravity) over which implement the resulting universal topological quantum algorithms.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 13, 2011•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•3 citations
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 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.
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.
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.
An emergent trend in quantum computation is the topological quantum computation (TQC). Briefly, TQC results from the application of quantum computation with the aim to solve the problems of quantum topology such as topological invariants for knots and links (Jones polynomials, HOMFLY polynomials, Khovanov polynomials); topological invariants for graphs (Tutte polynomial and Bollobás-Riordan polynomial); topological invariants for 3-manifolds (Reshetiskin-Turaev, Turaev-Viro and Turaer-Viro-Ocneanu invariants) and topological invariants for 4-manifolds( Crane-Yetter invariants). In a few words, TQC is concerned with the formulation of quantum algorithms for the computation of these topological invariants in quantum topology. Given that one of the fundamental achievements of quantum topology was the discovery of strong connections between monoidal categories and 3-dimensional manifolds, in TQC is possible and necessary to exploit such connections with the purpose to formulate universal quantum algorithms for topological invariants of 3-manifolds. In the present work we make an exploration of such possibilities. Specifically we search for universal quantum algorithms for generalized Turaev-Viro invariants of 3-manifolds such as the Turaev-Viro-Ocneanu invariants, the Kashaev-Baseilhac-Benedetti invariants of 3-manifolds with links and the Geer-Kashaev-Turaev invariants of 3-manifolds with a link and a principal bundle. We also look for physical systems (three dimensional topological insulators and three-dimensional gravity) over which implement the resulting universal topological quantum algorithms.
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.