© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Quantum Computing with Heegaard Splittings of 3-manifolds

Henrique Ennes

Published Sep 29, 2026• 0 citations

Abstract

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.

Related papers

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

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

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

Topological Quantum Computation and Quantum Compilation

Joren Brunekreef

A central problem in realizing universal quantum computers is dealing with decoherence effects, which can destroy the vulnerable quantum states present in the internal registers. Several schemes have been developed that provide resistance to decoherence, leading to theories of fault-tolerant quantum computation. One such scheme is the theory of topological quantum computation, which encodes qubit states in robust topological properties of certain quantum systems. However, fault-tolerant theories typically only provide a finite set of primitive gates, from which we must then form approximations to arbitrary quantum gates. The Solovay-Kitaev algorithm describes a procedure for accomplishing this, and proves that the number of primitive gates required to approximate an arbitrary gate is only polylogarithmic in the desired degree of accuracy. In this thesis, we first outline the basic theory of quantum computation. Secondly, we describe the general problem of quantum compilation, list several possible strategies for relevant optimizations, and outline a proof of the Solovay-Kitaev theorem. Next, we give an introduction to the theory of topological quantum computation by anyons, with special focus on Fibonacci-anyons. Finally, we list some numerical results of an implementation of the Solovay-Kitaev algorithm when applied to a Fibonacci-anyon model and analyze the performance gains obtained through applications of the proposed optimizations.

•Aug 26, 2014•0 citations

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

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.

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

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.

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.

A central problem in realizing universal quantum computers is dealing with decoherence effects, which can destroy the vulnerable quantum states present in the internal registers. Several schemes have been developed that provide resistance to decoherence, leading to theories of fault-tolerant quantum computation. One such scheme is the theory of topological quantum computation, which encodes qubit states in robust topological properties of certain quantum systems. However, fault-tolerant theories typically only provide a finite set of primitive gates, from which we must then form approximations to arbitrary quantum gates. The Solovay-Kitaev algorithm describes a procedure for accomplishing this, and proves that the number of primitive gates required to approximate an arbitrary gate is only polylogarithmic in the desired degree of accuracy. In this thesis, we first outline the basic theory of quantum computation. Secondly, we describe the general problem of quantum compilation, list several possible strategies for relevant optimizations, and outline a proof of the Solovay-Kitaev theorem. Next, we give an introduction to the theory of topological quantum computation by anyons, with special focus on Fibonacci-anyons. Finally, we list some numerical results of an implementation of the Solovay-Kitaev algorithm when applied to a Fibonacci-anyon model and analyze the performance gains obtained through applications of the proposed optimizations.