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:1003.0923 · Physical Review A

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

Gorjan Alagic, Stephen P. Jordan, Robert König, Ben W. Reichardt

Published Oct 8, 2010• 15 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.82.040302

Related papers

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

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

Quantum algorithms for invariants of triangulated manifolds

Gorjan Alagic, Edgar A. Bering

One of the apparent advantages of quantum computers over their classical counterparts is their ability to efficiently contract tensor networks. In this article, we study some implications of this fact in the case of topological tensor networks. The graph underlying these networks is given by the triangulation of a manifold, and the structure of the tensors ensures that the overall tensor is independent of the choice of internal triangulation. This leads to quantum algorithms for additively approximating certain invariants of triangulated manifolds. We discuss the details of this construction in two specific cases. In the first case, we consider triangulated surfaces, where the triangle tensor is defined by the multiplication operator of a finite group; the resulting invariant has a simple closed-form expression involving the dimensions of the irreducible representations of the group and the Euler characteristic of the surface. In the second case, we consider triangulated 3-manifolds, where the tetrahedral tensor is defined by the so-called Fibonacci anyon model; the resulting invariant is the well-known Turaev-Viro invariant of 3-manifolds.

Quantum Information and Computation•Sep 1, 2012•1 citation

Quantum Algorithms for Invariants of Triangulated Manifolds

Gorjan Alagic, Edgar A. Bering

One of the apparent advantages of quantum computers over their classical counterparts is their ability to efficiently contract tensor networks. In this article, we study some implications of this fact in the case of topological tensor networks. The graph underlying these networks is given by the triangulation of a manifold, and the structure of the tensors ensures that the overall tensor is independent of the choice of internal triangulation. This leads to quantum algorithms for additively approximating certain invariants of triangulated manifolds. We discuss the details of this construction in two specific cases. In the first case, we consider triangulated surfaces, where the triangle tensor is defined by the multiplication operator of a finite group; the resulting invariant has a simple closed-form expression involving the dimensions of the irreducible representations of the group and the Euler characteristic of the surface. In the second case, we consider triangulated 3-manifolds, where the tetrahedral tensor is defined by the so-called Fibonacci anyon model; the resulting invariant is the well-known Turaev-Viro invariant of 3-manifolds.

arXiv:1108.5424•Aug 27, 2011•0 citations

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•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•2 citations
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.
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.
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.
One of the apparent advantages of quantum computers over their classical counterparts is their ability to efficiently contract tensor networks. In this article, we study some implications of this fact in the case of topological tensor networks. The graph underlying these networks is given by the triangulation of a manifold, and the structure of the tensors ensures that the overall tensor is independent of the choice of internal triangulation. This leads to quantum algorithms for additively approximating certain invariants of triangulated manifolds. We discuss the details of this construction in two specific cases. In the first case, we consider triangulated surfaces, where the triangle tensor is defined by the multiplication operator of a finite group; the resulting invariant has a simple closed-form expression involving the dimensions of the irreducible representations of the group and the Euler characteristic of the surface. In the second case, we consider triangulated 3-manifolds, where the tetrahedral tensor is defined by the so-called Fibonacci anyon model; the resulting invariant is the well-known Turaev-Viro invariant of 3-manifolds.
One of the apparent advantages of quantum computers over their classical counterparts is their ability to efficiently contract tensor networks. In this article, we study some implications of this fact in the case of topological tensor networks. The graph underlying these networks is given by the triangulation of a manifold, and the structure of the tensors ensures that the overall tensor is independent of the choice of internal triangulation. This leads to quantum algorithms for additively approximating certain invariants of triangulated manifolds. We discuss the details of this construction in two specific cases. In the first case, we consider triangulated surfaces, where the triangle tensor is defined by the multiplication operator of a finite group; the resulting invariant has a simple closed-form expression involving the dimensions of the irreducible representations of the group and the Euler characteristic of the surface. In the second case, we consider triangulated 3-manifolds, where the tetrahedral tensor is defined by the so-called Fibonacci anyon model; the resulting invariant is the well-known Turaev-Viro invariant of 3-manifolds.
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).
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.