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