skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number
Quantum topology provides various frameworks for defining and computing invariants of manifolds inspired by quantum theory. One such framework of substantial interest in both mathematics and physics is the Turaev-Viro-Barrett-Westbury state sum construction, which uses the data of a spherical fusion category to define topological invariants of triangulated 3-manifolds via tensor network contractions. In this work we analyze the computational complexity of state sum invariants of 3-manifolds derived from Tambara-Yamagami categories. While these categories are the simplest source of state sum invariants beyond finite abelian groups (whose invariants can be computed in polynomial time) their computational complexities are yet to be fully understood. We first establish that the invariants arising from even the smallest Tambara-Yamagami categories are #P-hard to compute, so that one expects the same to be true of the whole family. Our main result is then the existence of a fixed parameter tractable algorithm to compute these 3-manifold invariants, where the parameter is the first Betti number of the 3-manifold with ℤ/2ℤ coefficients. Contrary to other domains of computational topology, such as graphs on surfaces, very few hard problems in 3-manifold topology are known to admit FPT algorithms with a topological parameter. However, such algorithms are of particular interest as their complexity depends only polynomially on the combinatorial representation of the input, regardless of size or combinatorial width. Additionally, in the case of Betti numbers, the parameter itself is computable in polynomial time. Thus while one generally expects quantum invariants to be hard to compute classically, our results suggest that the hardness of computing state sum invariants from Tambara-Yamagami categories arises from classical 3-manifold topology rather than the quantum nature of the algebraic input.  more » « less
Award ID(s):
2330130
PAR ID:
10658277
Author(s) / Creator(s):
; ;
Editor(s):
Aichholzer, Oswin; Wang, Haitao
Publisher / Repository:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Date Published:
Volume:
332
ISSN:
1868-8969
Page Range / eLocation ID:
38:1-38:15
Subject(s) / Keyword(s):
3-manifold quantum invariant fixed parameter tractable algorithm topological parameter Gauss sums topological quantum field theory Mathematics of computing → Geometric topology Theory of computation → Computational geometry Theory of computation → Fixed parameter tractability
Format(s):
Medium: X Size: 15 pages; 927055 bytes Other: application/pdf
Size(s):
15 pages 927055 bytes
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Fefferman, Bill (Ed.)
    We show that for any fixed (2+1)-dimensional TQFT over ℂ of either Turaev-Viro-Barrett-Westbury or Reshetikhin-Turaev type, the problem of (exactly) computing its invariants on closed 3-manifolds is either solvable in polynomial time, or else it is #𝖯-hard to (exactly) contract certain tensors that are built from the TQFT’s fusion category. Our proof is an application of a dichotomy result of Cai and Chen [J. ACM, 2017] concerning weighted constraint satisfaction problems over ℂ. We leave for future work the issue of reinterpreting the conditions of Cai and Chen that distinguish between the two cases (i.e. #𝖯-hard tensor contractions vs. polynomial time invariants) in terms of fusion categories. We expect that with more effort, our reduction can be improved so that one gets a dichotomy directly for TQFTs' invariants of 3-manifolds rather than more general tensors built from TQFTs' fusion categories. 
    more » « less
  2. ; (, Journal für die reine und angewandte Mathematik (Crelles Journal))
    .We show the existence of linear bounds on Wall 𝜌-invariants of PL manifolds, employing a new combinatorial concept of 𝐺-colored polyhedra. As an application, we show how the number of h-cobordism classes of manifolds simple homotopy equivalent to a lens space with 𝑉 simplices and the fundamental group of Z n grows in 𝑉. Furthermore, we count the number of homotopy lens spaces with bounded geometry in 𝑉. Similarly, we give new linear bounds on Cheeger–Gromov 𝜌-invariants of PL manifolds endowed with a faithful representation also. A key idea is to construct a cobordism with a linear complexity whose boundary is π 1 -injectively embedded, using relative hyperbolization. As an application, we study the complexity theory of high-dimensional lens spaces. Lastly, we show the density of 𝜌-invariants over manifolds homotopy equivalent to a given manifold for certain fundamental groups. This implies that the structure set is not finitely generated. 
    more » « less
  3. ; (, Annales scientifiques de lÉcole normale supérieure)
    null (Ed.)
    We establish a relation between the "large r" asymptotics of the Turaev-Viro invariants $$TV_r $$and the Gromov norm of 3-manifolds. We show that for any orientable, compact 3-manifold $$M$$, with (possibly empty) toroidal boundary, $log|TVr(M)|$ is bounded above by a function linear in $$r$$ and whose slope is a positive universal constant times the Gromov norm of $$M$$. The proof combines TQFT techniques, geometric decomposition theory of 3-manifolds and analytical estimates of $6j$-symbols. We obtain topological criteria that can be used to check whether the growth is actually exponential; that is one has $$log|TVr(M)|\geq B r$$, for some $B>0$. We use these criteria to construct infinite families of hyperbolic 3-manifolds whose $SO(3)$- Turaev-Viro invariants grow exponentially. These constructions are essential for the results of article [3] where we make progress on a conjecture of Andersen, Masbaum and Ueno about the geometric properties of surface mapping class groups detected by the quantum representations. We also study the behavior of the Turaev-Viro invariants under cutting and gluing of 3-manifolds along tori. In particular, we show that, like the Gromov norm, the values of the invariants do not increase under Dehn filling and we give applications of this result on the question of the extent to which relations between the invariants TVr and hyperbolic volume are preserved under Dehn filling. Finally we give constructions of 3-manifolds, both with zero and non-zero Gromov norm, for which the Turaev-Viro invariants determine the Gromov norm. 
    more » « less
  4. ; ; (, Journal of Symplectic Geometry)
    It is known that any contact $$3$$-manifold can be obtained by rationally contact Dehn surgery along a Legendrian link $$L$$ in the standard tight contact $$3$$-sphere. We define and study various versions of contact surgery numbers, the minimal number of components of a surgery link $$L$$ describing a given contact $$3$$-manifold under consideration. In the first part of the paper, we relate contact surgery numbers to other invariants in terms of various inequalities. In particular, we show that the contact surgery number of a contact manifold is bounded from above by the topological surgery number of the underlying topological manifold plus three. In the second part, we compute contact surgery numbers of all contact structures on the $$3$$-sphere. Moreover, we completely classify the contact structures with contact surgery number one on $$S^1\times S^2$$, the Poincar\'e homology sphere and the Brieskorn sphere $$\Sigma(2,3,7)$$. We conclude that there exist infinitely many non-isotopic contact structures on each of the above manifolds which cannot be obtained by a single rational contact surgery from the standard tight contact $$3$$-sphere. We further obtain results for the $$3$$-torus and lens spaces. As one ingredient of the proofs of the above results we generalize computations of the homotopical invariants of contact structures to contact surgeries with more general surgery coefficients which might be of independent interest. 
    more » « less
  5. ; ; ; (, Journal of differential geometry)
    We prove the Turaev-Viro invariants volume conjecture for a "universal" class of cusped hyperbolic 3-manifolds that produces all 3-manifolds with empty or toroidal boundary by Dehn filling. This leads to two-sided bounds on the volume of any hyperbolic 3-manifold with empty or toroidal boundary in terms of the growth rate of the Turaev-Viro invariants of the complement of an appropriate link contained in the manifold. We also provide evidence for a conjecture of Andersen, Masbaum and Ueno (AMU conjecture) about certain quantum representations of surface mapping class groups. A key step in our proofs is finding a sharp upper bound on the growth rate of the quantum 6j−symbol evaluated at q=e2πir. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email