An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number

Delaney, Colleen; Maria, Clément; Samperton, Eric

doi:10.4230/LIPIcs.SoCG.2025.38

An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number

Colleen Delaney

Department of Mathematics, Department of Physics and Astronomy, Purdue University, West Lafayette, IN, USA Clément Maria

INRIA Université Côte d’Azur, Nice, France
FGV/EMAp, Rio de Janeiro, Brazil Eric Samperton

Department of Mathematics, Department of Computer Science, Purdue University, West Lafayette, IN, USA

Abstract

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 $\mathbb{Z}/2\mathbb{Z}$ 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.

Keywords and phrases:

3-manifold, quantum invariant, fixed parameter tractable algorithm, topological parameter, Gauss sums, topological quantum field theory

Funding:

Colleen Delaney: Partially supported through the Simons Collaboration on Global Categorical Symmetries (Simons Foundation Award 888988).

Clément Maria: Partially supported by the ANR project ANR-20-CE48-0007 (AlgoKnot).

Eric Samperton: Partially supported by NSF award DMS-2038020.

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Geometric topology ; Theory of computation

\rightarrow

Computational geometry ; Theory of computation

\rightarrow

Fixed parameter tractability

Editors:

Oswin Aichholzer and Haitao Wang

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Quantum physics – especially quantum field theory – is a profuse source of invariants in low-dimensional topology, and these invariants often provide information about manifolds beyond the reach of classical topology. For example, on one hand, the Alexander polynomial of a knot is determined “classically” (from the first homology of the knot’s universal abelian cover) and infinitely many different knots have trivial Alexander polynomial; on the other hand, the Jones polynomial (the prototypical example of a quantum invariant) has never been shown to be trivial on any non-trivial knot. However, the native paradigm for (approximately) computing quantum invariants is manifestly quantum computational, so that in general one should expect them to be hard to compute on a classical computer [19]. Naturally then we seek to understand the full landscape of the computational complexities of quantum invariants. From the point of view of computational topology we are particularly interested in a middle ground where there may be interesting invariants that are not too hard to compute, and to develop algorithms to compute them as efficiently as possible.

In this work, we investigate the complexity landscape of a specific class of quantum invariants of 3-manifolds, namely, the Turaev-Viro-Barrett-Westbury (TVBW) state sum construction [30, 2]. Unlike other quantum invariants (e.g. Donaldson invariants), the TVBW construction is a priori algorithmically computable, combining a finite amount of algebraic data in the form of a (skeletalized) spherical fusion category $\mathcal{C}$ with a triangulation $\mathfrak{T}$ of a closed, oriented 3-manifold $M$ to generate a complex algebraic number $|M|_{\mathcal{C}}\in\mathbb{C}$ that is an orientation-preserving homeomorphism invariant of $M$ . The invariant $|M|_{\mathcal{C}}$ is defined as the contraction of a certain tensor network built by decorating $\mathfrak{T}$ with the data of $\mathcal{C}$ , and can be formally described via a combinatorial state sum formula. We refer the reader to the full version of this article [8] for a brief review of the TVBW construction (in the case of multiplicity-free, pseudo-unitary spherical categories) and [32] for more background.

As we review at the end of this introduction, it is desirable to understand the computational complexity of evaluating the TVBW invariant $|\cdot|_{\mathcal{C}}$ on a given triangulated 3-manifold

	$\displaystyle\|\cdot\|_{\mathcal{C}}:\{\text{triangulations of closed, oriented % 3-manifolds}\}$	$\displaystyle\to\mathbb{C}$
	$\displaystyle\text{triangulation $\mathfrak{T}$ of }M$	$\displaystyle\mapsto\|M\|_{\mathcal{C}}.$

More precisely, we would like to understand how the computation of these invariants depends on the choice of spherical fusion category $\mathcal{C}$ , since there are countably infinitely many equivalence classes of such categories, and their classification is at least as hard as the classification of finite groups. As usual, we aim to understand the complexity of computing $|M|_{\mathcal{C}}$ as a function of the size of a triangulation $\mathfrak{T}$ used to encode $M$ .

We approach this complexity-theoretic classification problem from the perspective that fusion categories are “quantum” generalizations of (the representation theory of) finite groups. While this perspective has not been made explicitly overt in the computational topology literature, it is common in quantum algebra, where the extent to which a fusion category deviates from a finite group $G$ can be made precise in various ways. For the sake of space, we will not review these notions here, but will note that anyway one cuts it, the simplest spherical fusion categories are of the type $\mathrm{Vec}(A)$ – where $A$ is an abelian group – consisting of $A$ -graded finite-dimensional vector spaces, with a tensor product that comes from the group operation in $A$ . In fact, for any finite group $G$ , the category of $G$ -graded vector spaces $\mathrm{Vec}(G)$ forms a spherical fusion category, but if $G$ is non-abelian, we consider this category to be more “complicated” than $\mathrm{Vec}(A)$ . One reason for this is that $|\cdot|_{\mathrm{Vec}(A)}$ is always polynomial-time computable, whereas $|\cdot|_{\mathrm{Vec}(G)}$ is often $\#P$ -hard for non-abelian groups [21].

Arguably, after $\mathrm{Vec}(A)$ , the next simplest family of fusion categories consists of the Tambara-Yamagami categories $\operatorname{TY}(A,\chi,\nu)$ . Such a category is determined by a finite abelian group $A$ , together with a small amount of additional data: a bicharacter (i.e., a non-degenerate symmetric bilinear pairing) $\chi:A\times A\to U(1)$ , and a choice of square root $\nu=\pm 1/\sqrt{|A|}=\pm|A|^{-1/2}$ [28]. (See [8] for a complete description of these categories using this data.) And yet, in the full version of this article [8], we show that already in the simplest non-trivial case with $A=\mathbb{Z}/2\mathbb{Z}$ , the invariants $|\cdot|_{\operatorname{TY}(\mathbb{Z}/2\mathbb{Z},\chi,-1/\sqrt{2})}$ are $\#P$ -hard to compute. This is more-or-less a restatement of known results about the Turaev-Viro invariant $\operatorname{TV}_{4}$ [14, 23], since $|\cdot|_{\operatorname{TY}(\mathbb{Z}/2\mathbb{Z},\chi,1/\sqrt{2})}=% \operatorname{TV}_{4}(\cdot)$ . However, as we shall explain, our approach offers a conceptual clarification by placing $\operatorname{TV}_{4}$ within the broader taxonomy of spherical fusion categories. In particular, we conjecture that the TVBW state sum invariant of every non-trivial Tambara-Yamagami category $\operatorname{TY}(A,\chi,\nu)$ is $\#\mathsf{P}$ -hard.

Our main result is a parameterized algorithm to compute the TVBW state sum invariants $|M|_{\operatorname{TY}(A,\chi,\nu)}$ associated to Tambara-Yamagami categories, where our parameter is the first $\mathbb{Z}/2\mathbb{Z}$ Betti number $\beta_{1}$ .

Main Result (Informal; see Theorem 4).

Fix an integer $B\geq 0$ and a Tambara-Yamagami category $\operatorname{TY}(A,\chi,\nu)$ . Then there exists a polynomial time algorithm to evaluate $|M|_{\operatorname{TY}(A,\chi,\nu)}$ for triangulated 3-manifolds with $\beta_{1}(M)\leq B$ .

While the hardness of general Tambara-Yamagami invariants is still conjectural, we interpret our main result as showing that any such hardness is explainable by a simple classical topological fact: there exist triangulations $\mathfrak{T}$ of 3-manifolds $M$ with $n$ simplices where $\beta_{1}(M)$ can be as large as $\Theta(n)$ .

Our algorithm succeeds by converting the natively quantum topological computational problem of computing a TVBW state sum invariant of a triangulated 3-manifold – which a priori requires an expensive tensor network contraction – into a sequence of other much more efficient classical computational problems in algebraic number theory and combinatorial-algebraic topology. Prior to our work, to the best of our knowledge, the only published algorithm in 3-manifold topology directly parameterized by an efficiently computable topological quantity (whose value is independent of the presentation of the input) is the algorithm of Maria and Spreer to compute the Turaev-Viro quantum invariant $\operatorname{TV}_{4}$ of 3-manifolds [30] at a 4th root of unity in $O(2^{\beta_{1}}n^{3})$ operations [23].

The technical underpinnings of our algorithm are explained in Section 3; the algorithm itself is precisely described and analyzed in Section 4. At the heart of our algorithm is a (non-obvious!) observation: $|M|_{\operatorname{TY}(A,\chi,\nu)}$ can be identified with a (normalized) sum of $|H^{1}(M,\mathbb{Z}/2\mathbb{Z})|=2^{\beta_{1}}$ many Gauss sums of $\mathbb{Q}/\mathbb{Z}$ -valued quadratic forms on certain finite abelian groups derived from $A$ and the given triangulation of $M$ .

The second and third equalities above follow for a rather general reason: $\operatorname{TY}(A,\chi,\nu)$ possesses the structure of a $\mathbb{Z}/2\mathbb{Z}$ -grading and so by general facts related to homotopy quantum field theory [31], we are able to reduce $|M|_{\operatorname{TY}(A,\chi,\nu)}$ to a sum of $2^{\beta_{1}}$ terms in a manner similar in spirit to [23]. Notably, however, the concept of graded fusion categories is absent from [23], and this structure enables us to analyze the state sum invariant of $M$ directly from any simplicial triangulation, without having to pass to a one-vertex triangulation via the crushing algorithm of Jaco and Rubinstein [12] (as in [23]).

The bulk of Section 3 is then concerned with explaining and justifying $(\star)$ , and our methods here diverge substantially from [23]. The efficient algorithmic evaluation of quadratic Gauss sums appears to be well-known to experts in algebraic number theory, although we were unable to find specific references for this fact, the closest apparently being [3]; see Section 2.1 and [8] for further discussion.

The general nature of our main result allows us to establish new conceptual insight into the complexity-theoretic landscape of TVBW invariants, a portion of which we summarize in Figure 1. It is known that TVBW 3-manifold invariants are often #P-hard to compute exactly, and sometimes hard even just to approximate [13, 14, 18, 19, 20, 21]; moreover, in many of these cases, it is known that there can be no tractable algorithm in $\beta_{1}$ . Thus the existence of a parametrized algorithm in a topological and efficiently computable parameter for the Tambara-Yamagami invariants is an interesting counterpoint to their expected hardness. This suggests that the hardness of computing the invariants is due to some intrinsic hardness in 3-manifold topology, rather than the Tambara-Yamagami category alone, whose construction is only a small modification of $\mathrm{Vec}(A)$ .

spherical category $\mathcal{C}$	complexity of $\|M\|_{\mathcal{C}}$	FPT in $\beta_{1}$ ?	Reference
$\mathrm{Vec}(A)$ for $A$ abelian	in $\mathsf{fP}$	Yes	well-known, e.g. [20]
$\operatorname{TY}($ $\mathbb{Z}/2\mathbb{Z}$ $,\exp(\pi iab),-1/\sqrt{2})$	$\#\mathsf{P}$ -hard	Yes	[14, 23], long version [8]
$\operatorname{TY}(A,\chi,\nu)$	unknown in general	Yes	this work
$\mathrm{Vec}(G)$ for $G$ non-abelian solvable	unknown	unknown
$\mathrm{Vec}(G)$ for $G$ non-abelian simple	$\#\mathsf{P}$ -complete	No (unless $\mathsf{fP}=\#\mathsf{P})$	[20]
$U_{q}\mathfrak{sl}_{2}$ -mod ( $q$ a non-lattice root of 1)	$\#\mathsf{P}$ -hard	No (unless $\mathsf{fP}=\#\mathsf{P}$ )	[13, 19]

Figure 1: State of the art for computing TVBW invariants based on “simple” spherical fusion categories.

After scrutinizing Figure 1, it seems sensible to expect that there should be a dichotomy theorem for TVBW invariants. A naïve conjecture would be that $|\cdot|_{\mathcal{C}}$ is in $\mathsf{fP}$ if and only if $\mathcal{C}\simeq\mathrm{Vec}(A)$ , and otherwise $|\cdot|_{\mathcal{C}}$ is $\#\mathsf{P}$ -hard. However, this cannot be correct, as there are “twisted” versions of $A$ -graded vector spaces $\mathrm{Vec}(A,\eta)$ , $\eta\in H^{3}(A,U(1))$ , for which $|\cdot|_{\mathrm{Vec}(A,\eta)}$ is also known to be polynomial-time computable. More subtly, if $G$ is any 2-step nilpotent group, then $|M|_{\mathrm{Vec}(G)}=\#\{\pi_{1}(M)\to G\}/\#G$ should also be in $\mathsf{fP}$ .

A systematic understanding of the computational complexity of state sum invariants is significant because they fit into the larger framework of a fully-extended 3D TQFT. Indeed, this connection endows the invariants with important applications to fault-tolerant quantum computation and the characterization of topologically ordered phases of matter, e.g. via topological quantum computing [16, 17, 26, 34], as well as to the developing paradigm of “non-invertible” or “categorical” symmetries and dualities present in quantum field theories and lattice models [1, 6, 9, 10, 29]. Of course, there is plenty of motivation from low-dimensional topology as well, where these invariants can be used in practice to distinguish non-homeomorphic 3-manifolds. TVBW invariants are heuristically strong, with a typical category $\mathcal{C}$ capable of distinguishing “most” pairs of non-homeomorphic manifolds.

2 Background

In this section we introduce the TVBW invariants of 3-manifolds derived from Tambara-Yamagami categories, as well as some of the basic components necessary for our algorithm.

2.1 Elements of algorithmic number theory

Finite abelian groups.

Let $(A,+)$ be a finite abelian group with $|A|$ elements, denoted additively. The fundamental theorem of finitely generated abelian groups shows that $A$ admits a unique primary decomposition of the form:

A\cong\bigoplus_{\text{$p$ prime}}\ \ \bigoplus_{k_{i},n_{i}\,:\,i\in I_{p}}% \left(\mathbb{Z}/p^{k_{i}}\mathbb{Z}\right)^{n_{i}}

for finitely many primes $p$ , and positive integers $k_{i},n_{i}>0$ . For a finite abelian group $A$ , we denote by $d(A)$ the number of non-trivial summands in its primary decomposition. We use $A_{(p)}$ to denote the subgroup elements whose order is a power of $p$ . Hence,

A=\bigoplus_{p\text{ prime}}A_{(p)},\ \ \ \text{ where }A_{(p)}=\bigoplus_{k_{% i},n_{i}\,:\,i\in I_{p}}\left(\mathbb{Z}/p^{k_{i}}\mathbb{Z}\right)^{n_{i}}.

The following is a standard algorithmic result for finite abelian groups, formulated according to our needs in this article; see for example [25, Chap. 1.11].

Theorem 1.

Let $H$ be a finite abelian group presented via a primary decomposition with generators $h_{1},\ldots,h_{d(H)}$ for each of its prime summands. If $G\subseteq H$ is a subgroup of $H$ specified via a set of generators $g_{1},\ldots,g_{d(G)}$ (each of which is encoded by a list of integers $n_{ij}$ such that $g_{i}=\sum_{j}n_{ij}h_{j}$ ), then there exists a polynomial time algorithm using $O(d(|H|)^{3})$ operations in $H$ that finds a presentation of the primary decomposition of $G$ – that is, a new minimal set of generators of $G$ denoted $g^{\prime}_{1},\ldots,g^{\prime}_{d(G)}$ (each of which is, as before, represented by a list of integers $n^{\prime}_{ij}$ such that $g^{\prime}_{i}=\sum_{j}n^{\prime}_{ij}h_{j}$ ) together with relations of the form $(g^{\prime}_{i})^{p_{i}^{k_{i}}}$ for primes $p_{i}$ and positive integers $k_{i}$ .

Pairings and forms on finite abelian groups.

We now quickly review the basics of quadratic forms on finite abelian groups. We refer the reader to [27] for more background.

Let $(A,+)$ be a finite abelian group, denoted additively. A symmetric bilinear pairing $b\colon A\times A\to G$ into the (not necessarily finite) abelian group $(G,+)$ is a map satisfying

b(x,y)=b(y,x),b(x+y,z)=b(x,z)+b(y,z),\text{ and }b(x,y+z)=b(x,y)+b(x,z)\text{ % for all }x,y,z.

A pairing is non-degenerate if for every $x\in A$ , $x\neq 0$ , there exists some $y\in A$ such that $b(x,y)$ is not trivial in $G$ . When the symmetric bilinear pairing takes value in $(G,+)=(\mathbb{Q}/\mathbb{Z},+)$ , where $(\mathbb{Q}/\mathbb{Z},+)$ is the additive group of rational numbers modulo the integers, we call the pair $(A,b)$ a discriminant pairing. For any real number $x\in\mathbb{R}$ , denote by $\mathbf{e}(x)$ the quantity $\exp(2\pi ix)$ . Let $(U(1),\times)$ be the multiplicative group of complex numbers $\{\mathbf{e}(x):x\in\mathbb{R}/\mathbb{Z}\}$ on the unit circle. There is a natural group isomorphism $\mathbb{Q}/\mathbb{Z}\to U(1),x\mapsto\mathbf{e}(x)$ . When a symmetric bilinear pairing $b$ is non-degenerate and takes value in $(U(1),\times)$ , we call it a bicharacter. Note that $(A,b)$ is a non-degenerate discriminant pairing if and only if $(A,\mathbf{e}(b(\cdot,\cdot)))$ is a bicharacter. If $(A,b)$ is a discriminant pairing and $e_{1},\ldots,e_{k}\in A$ , then the Gram matrix of $(e_{1},\ldots,e_{k})$ is the $k\times k$ matrix $\left(b(e_{i},e_{j})\right)_{i,j}$ .

For a map $q\colon A\to G$ , define $\partial q\colon A\times A\to G$ by $\partial q(x,y):=q(x+y)-q(x)-q(y)$ for any $x,y\in A$ . The map $q$ is a (homogeneous) quadratic form if, for any $x\in A$ and $u\in\mathbb{Z}$ , $q(ux)=u^{2}q(x)$ and the map $\partial q$ is bilinear. For a quadratic form $q$ , we call $\partial q$ the bilinear pairing associated to $q$ . A quadratic form $q$ is non-degenerate if the bilinear pairing $\partial q$ is non-degenerate. If $q$ takes value in $\mathbb{Q}/\mathbb{Z}$ , the pair $(A,q)$ is called a pre-metric group, and if moreover $q$ is non-degenerate, $(A,q)$ is a metric group.

Gauss sums on pre-metric groups.

If $\gamma\in\mathbb{Q}/\mathbb{Z}$ , let $\mathbf{e}(\gamma):=\exp(2\pi i\gamma)$ . To every pre-metric group $(G,q)$ we associate a complex number $\Theta(G,q)$ called the Gauss sum:

\Theta(G,q):=\frac{1}{|\sqrt{|G|}|}\sum_{x\in G}\mathbf{e}(q(x)).

Our next theorem is one of the central tools in our algorithm for computing the TVBW invariants of Tambara-Yamagami categories.

Theorem 2.

Let $G$ be a finite abelian group presented via a primary decomposition with $d(G)$ summands. If oracle access to a quadratic form $q:G\to\mathbb{Q}/\mathbb{Z}$ is provided, then the Gauss sum $\Theta(G,q)$ can be evaluated in polynomial time using $O(d(G)^{3}\operatorname{poly}(\log|G|))$ operations, $O(d(G)^{2})$ oracle accesses, and $O(d(G)^{2}\operatorname{poly}(\log|G|))$ memory words.

Theorem 2 is seemingly folklore in the algebraic number theory literature, but we were unable to find any references proving it. We understand it as a consequence of a scattered collection of works on pre-metric groups and algorithms. Wall [33] abstractly classifies metric groups by showing how to decompose them into direct sums of elementary pieces; Basak and Johnson [3] later provide an algorithmic formulation of the decomposition theorem and explain that the Gauss sum of a metric group can be computed readily from the decomposition. We have however not found a complexity analysis of this construction anywhere in the literature. The closest we are aware of is [5, Thm. 1.1], which shows that Gauss sums of (not-necessarily-homogeneous) quadratic forms on cyclic groups $\mathbb{Z}/N\mathbb{Z}$ are computable in polynomial time; however, even if $A$ itself is cyclic, the Gauss sums we will need to compute in our algorithm for $|M|_{\operatorname{TY}(A,\chi,\nu)}$ are on non-cyclic pre-metric groups of the form $(A^{n},q)$ . In order to fill this gap, we prove Theorem 2 in the full version of the paper [8] by supplementing the algorithm of [3] with a detailed complexity analysis.

2.2 Combinatorial and algebraic topology

(Co)homology.

Throughout this article we employ the simplicial cohomology of simplicial complexes with $\mathbb{Z}/2\mathbb{Z}$ coefficients. We assume the reader is familiar with the basic definitions (see [11] for an introduction to the topic). The following well-known fact can be understood as an application of Theorem 1.

Theorem 3.

Let $\mathfrak{T}$ be a simplicial complex with $n$ simplices. For any dimension $d=0,1,2,\dots$ , the following can be computed in polynomial time using $O(n^{3})$ operations: a basis of $Z^{d}(\mathfrak{T},\mathbb{Z}/2\mathbb{Z})$ ; a basis of $B^{d}(\mathfrak{T};\mathbb{Z}/2\mathbb{Z})$ ; a set of elements in $Z^{d}(\mathfrak{T};\mathbb{Z}/2\mathbb{Z})$ that represent a basis of $H^{d}(\mathfrak{T};\mathbb{Z}/2\mathbb{Z})$ . In particular, the dimension of each of these spaces can be computed in polynomial time.

Triangulated 3-manifolds.

The most common data type in computational 3-manifold topology is that of a generalized triangulation; e.g., see [24]. However, strictly speaking, the TVBW invariants are only defined for simplicial (or PL) triangulations. It is possible to extend the definition to “polytope decompositions” (including generalized triangulations) [15], but we will not need to work at this level of generality.

Thus, throughout this work, we make the following conventions: a 3-manifold $M$ is always closed and oriented, and presented by a simplicial triangulation, denoted $\mathfrak{T}$ , together with an orientation of $\mathfrak{T}$ . The orientability of $M$ is reflected in the fact that the simplicial homology group $H_{3}(\mathfrak{T};\mathbb{Z})$ is isomorphic to $\mathbb{Z}$ (this can be checked quickly from $\mathfrak{T}$ ), and then an orientation of $\mathfrak{T}$ is encoded by labeling each tetrahedron in $\mathfrak{T}$ with a sign $+1$ or $-1$ in a way that gives rise to a $\{+1,-1\}$ -valued cellular 0-cocycle on the cellulation dual to $\mathfrak{T}$ .

Later, it will also be convenient to decorate each edge of an oriented triangulation with an arbitrarily chosen orientation. We stress that these edge orientations are arbitrary, and have nothing to do with the orientation of the manifold’s tetrahedra. Going forward, by a small abuse of language, if we say triangulation, then we will usually mean an oriented triangulation equipped with such an edge orientation. We denote the set of vertices of $\mathfrak{T}$ by $V$ , the set of edges by $E$ , the set of triangular faces by $F$ , and the set of tetrahedra by $T$ .

2.3 Tambara-Yamagami quantum invariants

The quantum invariants we consider in this article are $\mathbb{C}$ -valued topological invariants of closed 3-manifolds derived from algebraic data (a spherical fusion category) attached to a combinatorial presentation of the 3-manifold (a simplicial triangulation), together with evaluation rules described in the works of Turaev and Viro [30] and Barrett and Westbury [2]. We now give an extremely brief introduction to Tambara-Yamagami quantum invariants, which are the TVBW invariants produced by a particular infinite family of spherical fusion categories called Tambara-Yamagami categories [28]. For the sake of space, here we provide only the details necessary to follow the proofs of our main results. We refer the reader to [8] for the full details of the combinatorial description of spherical fusion categories in general and for Tambara-Yamagami categories in particular, as well as the general construction of TVBW invariants (for unitary and multiplicity-free categories).

Let $(A,+)$ be a finite abelian group with $|A|$ elements, $\chi:A\times A\to U(1)$ a bicharacter on $A$ , and $\nu$ a choice of square root $\nu=\pm 1/\sqrt{|A|}=\pm|A|^{-1/2}$ . The Tambara-Yamagami category $\operatorname{TY}(A,\chi,\nu)$ is an algebraic object which gives rise to the following data:

$\blacksquare$

a set of colors $L\stackrel{{\scriptstyle\text{def}}}{{=}}A\sqcup\{m\}$ (where $m$ is some symbol not in $A$ ), together with a duality operation ^∗ defined by $a^{*}\stackrel{{\scriptstyle\text{def}}}{{=}}-a$ and $m^{*}\stackrel{{\scriptstyle\text{def}}}{{=}}m$ .
$\blacksquare$

scalars $d_{a}$ and $d_{m}$ associated to every color in $L$ called quantum dimensions, as well as the (global) quantum dimension scalar $D$ . These scalars are defined as follows:

$d_{a}\stackrel{{\scriptstyle\text{def}}}{{=}}1\text{ for all }a\in A,\qquad d_% {m}\stackrel{{\scriptstyle\text{def}}}{{=}}+|A|^{1/2},\qquad D\stackrel{{% \scriptstyle\text{def}}}{{=}}\sum_{x\in L}d_{x}^{2}=2|A|.$
$\blacksquare$

a set of admissible triples of colors

$\{(a,b,-a-b),(a,m,m),(m,a,m),(m,m,a):a,b\in A\}\subset L\times L\times L,$
$\blacksquare$

and a system of $\mathbb{C}$ -valued tetrahedron weights defined below.

A coloring $\theta\colon E\to L$ of a triangulation $\mathfrak{T}$ is an assignment of a color to each edge of $\mathfrak{T}$ . Given an edge $e_{0}$ on the boundary of a face $f$ , the orientation of $e_{0}$ determines a direction along which to traverse the three boundary edges of $f$ ; call these edges $e_{0},e_{1}$ and $e_{2}$ , according to the order in which we first see them while doing this traversal. Now associate a triple of colors $(\theta(e_{0}),\theta(e_{1})^{(*)},\theta(e_{2})^{(*)})$ , where $\theta(e_{i})^{(*)}$ means we apply the duality operation ^∗ to the label $\theta(e_{i})$ if the direction of traversal around $f$ disagrees with the orientation of $e_{i}$ . The coloring $\theta$ is called admissible if every such triple associated to an edge-face pair is admissible. The set of admissible colorings is denoted by $\operatorname{Adm}_{L}(\mathfrak{T})$ .

We now describe the tetrahedral weights involved in the definition of the Tambara-Yamagami invariants. Let $\theta$ be a coloring of $\mathfrak{T}$ and let $\theta_{e}:=\theta(e)\in L$ denote the label of an edge $e\in E$ . For each tetrahedron $t\in T$ with edges $e_{1},e_{2},\ldots e_{6}$ and orientation $O(t)\in\{+,-\}$ , we assign a tetrahedral weight $|t|^{O(t)}_{\theta}\in\mathbb{C}$ . If $\theta$ is inadmissible, then $|t|^{O(t)}_{\theta}\stackrel{{\scriptstyle\text{def}}}{{=}}0$ . Otherwise, $\theta$ is admissible and so, as described in [8], takes on one of four possible types; taking $O(t)$ into account we then assign the tetrahedral weights as follows:

\begin{array}[]{cccc}\text{{\boldmath\bf$m$-empty}}&&&\text{{\boldmath\bf$m$-% triangle}}\\ \left|\begin{array}[]{ccccc}a&b&a+b\\ b-c&a+c&c\\ \end{array}\right|^{+}=1&&&\left|\begin{array}[]{ccccc}m&m&a\\ a&a+b&m\\ \end{array}\right|^{+}=d_{m}\\[15.00002pt] \left|\begin{array}[]{ccccc}a&b&a+b\\ c-b&a+c&c\\ \end{array}\right|^{-}=1&&&\left|\begin{array}[]{ccccc}a&b&a+b\\ m&m&m\\ \end{array}\right|^{-}=d_{m}\\[20.00003pt] \text{{\boldmath\bf flat $m$-quad}}&&&\text{{\boldmath\bf crooked $m$-quad}}\\ \left|\begin{array}[]{ccccc}a&m&m\\ b&m&m\\ \end{array}\right|^{+}=d_{m}\chi(a,b)&&&\left|\begin{array}[]{ccccc}m&m&a\\ m&m&b\\ \end{array}\right|^{+}=\nu d_{m}^{2}\overline{\chi(a,b)}\\[15.00002pt] \left|\begin{array}[]{ccccc}a&m&m\\ b&m&m\\ \end{array}\right|^{-}=d_{m}\overline{\chi(a,b)}&&&\left|\begin{array}[]{ccccc% }m&m&a\\ m&m&b\\ \end{array}\right|^{-}=\nu^{-1}d_{m}^{2}\chi(a,b),\\ \end{array}

where $a, b, c$ are arbitrary elements in $A$ .

Finally, the Tambara-Yamagami quantum invariant $|M|_{\operatorname{TY}(A,\chi,\nu)}$ of a 3-manifold $M$ with triangulation $\mathfrak{T}$ is defined via the following “state sum formula:”

|M|_{\operatorname{TY}(A,\chi,\nu)}\stackrel{{\scriptstyle\text{def}}}{{=}}% \displaystyle\sum_{\theta\in\operatorname{Adm}_{L}(\mathfrak{T})}\frac{% \displaystyle\prod_{t\in T}|t|_{\theta}^{O(t)}\prod_{e\in E}d_{\theta{e}}}{% \displaystyle\prod_{f\in F}\sqrt{d_{\theta{e_{1}}}d_{\theta{e_{2}}}d_{\theta{e% _{3}}}}\prod_{v\in V}D.}

We note that for a fixed coloring $\theta$ and tetrahedron $t$ , testing its admissibility on $t$ and determining its type can be carried out in constant time. Thus, there is a naïve algorithm to compute $|M|_{\operatorname{TY}(A,\chi,\nu)}$ directly from this definition with running time exponential in the size of $\mathfrak{T}$ . In fact, this is true of $|M|_{\mathcal{C}}$ for any spherical fusion category $\mathcal{C}$ . We now turn to showing that we can do much better when $\mathcal{C}=\operatorname{TY}(A,\chi,\nu)$ if we bound the $\mathbb{Z}/2\mathbb{Z}$ Betti number $\beta_{1}(M)$ .

3 The role of the Betti number in Tambara-Yamagami invariants

We are interested in the following algorithmic problem:

$\operatorname{TY}(A,\chi,\nu)$ -invariant computation
Input: $\mathfrak{T}$ a triangulation of an oriented closed 3-manifold $M$
Output: $\|M\|_{\operatorname{TY}(A,\chi,\nu)}$

Since we are not working uniformly in the data $A,\chi,\nu$ , there is no harm in assuming we have full “explicit” access to it. Our main result is

Theorem 4.

For a fixed Tambara-Yamagami category $\operatorname{TY}(A,\chi,\nu)$ , there is a deterministic algorithm that, given as input a triangulation of an orientable closed 3-manifold $M$ with $n$ tetrahedra, computes the quantum invariant $|M|_{\operatorname{TY}(A,\chi,\nu)}$ in $O(2^{\beta_{1}}n^{3})$ operations and using $O(n^{2})$ memory words.

In this section we expound the ideas introduced in Section 1 that lead to this algorithm; its proof is deferred until Section 4. Hereafter $A,\chi,$ and $\nu$ are fixed.

3.1 Admissible colorings induce simplicial 1-cocycles

We begin by noting that each admissible coloring determines a $\mathbb{Z}/2\mathbb{Z}$ -valued simplicial 1-cocycle. More precisely, consider the function

\phi\colon\operatorname{Adm}_{L}(\mathfrak{T})\to C^{1}(\mathfrak{T},\mathbb{Z% }/2\mathbb{Z}),\ \ \ \ \phi(\theta)(e)=\left\{\begin{array}[]{ll}1&\text{if }% \theta(e)=m\\ 0&\text{otherwise}\\ \end{array}\right.

(1)

that assigns to an admissible coloring of $\mathfrak{T}$ a $\mathbb{Z}/2\mathbb{Z}$ -valued simplicial 1-cochain of the triangulation (that is, a function $E\to\mathbb{Z}/2\mathbb{Z}$ ).

Lemma 5.

For any admissible coloring $\theta$ of a triangulation $\mathfrak{T}$ , $\phi(\theta)$ is a 1-cocycle.

In the case of $\operatorname{TY}(\mathbb{Z}/2\mathbb{Z},\exp(i\pi ab),-1/\sqrt{2})=% \operatorname{TV}_{4}$ , this lemma was proved in [4, 22] and used in the algorithm of [23]. It can be proved easily in the general case by examining the definition of admissible triples in $\operatorname{TY}(A,\chi,\nu)$ – the calculation boils down to the simple observation that in any admissible coloring, the number of edges around any face of $\mathfrak{T}$ colored by $m$ is either 0 or 2. More conceptually, this lemma follows from the fact that $\operatorname{TY}(A,\chi,\nu)$ is a spherical $\mathbb{Z}/2\mathbb{Z}$ -graded fusion category, and a similar result holds for any spherical $G$ -graded fusion category, cf. [31].

3.2 The partial state sum at a 1-cocycle

Fix a 1-cocycle $\alpha\in Z^{1}(\mathfrak{T},\mathbb{Z}/2\mathbb{Z})$ and consider the partial state sum at $\alpha$ , defined by only summing over the admissible labelings associated to $\alpha$ :

|\mathfrak{T},\alpha|_{\operatorname{TY}(A,\chi,\nu)}\stackrel{{\scriptstyle% \text{def}}}{{=}}\displaystyle\sum_{\theta\in\phi^{-1}(\alpha)}\frac{% \displaystyle\prod_{t\in T}|t|^{O(t)}_{\theta}\prod_{e\in E}d_{\theta{e}}}{% \displaystyle\prod_{f\in F}\sqrt{d_{\theta{e_{1}}}d_{\theta{e_{2}}}d_{\theta{e% _{3}}}}\prod_{v\in V}D}.

By definition, all admissible colorings of $\phi^{-1}(\alpha)$ have the same set of edges colored by the object $m$ . We partition $E$ , $F$ , and $T$ , such that for every coloring in $\phi^{-1}(\alpha)$ :

1.

$E=E_{\emptyset}\sqcup E_{{\small\bullet}}$ where $E_{\emptyset}$ is the set of edges colored by an element of $A$ , and $E_{{\small\bullet}}$ is the set of edges colored by $m$ ,
2.

$F=F_{\emptyset}\sqcup F_{\bullet\bullet}$ where $F_{\emptyset}$ is the set of faces whose edges are colored exclusively by elements of $A$ , and $F_{\bullet\bullet}$ is the set of faces with exactly two edges colored by $m$ ,
3.

$T=T_{\emptyset}\sqcup T_{\triangle}\sqcup T_{\boxplus}\sqcup T_{\boxminus}% \sqcup T_{\mathrel{\ooalign{\raise 0.75346pt\hbox{\hskip 0.42677pt$% \scriptscriptstyle+$}\cr\hss$\diamond$\hss}}}\sqcup T_{\mathrel{\ooalign{% \raise 0.75346pt\hbox{\hskip 0.42677pt$\scriptscriptstyle-$}\cr\hss$\diamond$% \hss}}}$ , where $T_{\emptyset}$ is the set of $m$ -empty faces, $T_{\triangle}$ is the set of $m$ -triangles, $T_{\boxplus}$ and $T_{\boxminus}$ are respectively the set of positively and negatively oriented flat $m$ -quads, and $T_{\mathrel{\ooalign{\raise 0.75346pt\hbox{\hskip 0.42677pt$\scriptscriptstyle% +$}\cr\hss$\diamond$\hss}}}$ and $T_{\mathrel{\ooalign{\raise 0.75346pt\hbox{\hskip 0.42677pt$\scriptscriptstyle% -$}\cr\hss$\diamond$\hss}}}$ are respectively the set of positively and negatively oriented crooked $m$ -quads (see end of Section 2.3 for conventions).

Replacing $|t|^{O(t)}_{\theta}$ by the appropriate values and factorizing, we now rewrite the partial state sum at the 1-cocycle $\alpha$ .

For an admissible coloring $\theta$ and an $m$ -quad tetrahedron $t$ in $\theta$ (either flat or crooked), define $\chi_{\theta(t)}$ to be the value $\chi(a,b)$ where $a, b$ are the colors in $\theta$ assigned to the two opposite edges not colored by $m$ in the (flat or crooked) $m$ -quad tetrahedron $t$ . One can then check:

|\mathfrak{T},\alpha|_{\operatorname{TY}(A,\chi,\nu)}=D^{-|V|}\cdot d_{m}^{C_{% \alpha}}\cdot\nu^{|T_{\mathrel{\ooalign{\raise 0.48436pt\hbox{\hskip 0.42677pt% $\scriptscriptstyle+$}\cr\hss$\diamond$\hss}}}|-|T_{\mathrel{\ooalign{\raise 0% .48436pt\hbox{\hskip 0.42677pt$\scriptscriptstyle-$}\cr\hss$\diamond$\hss}}}|}% \sum_{\theta\in\phi^{-1}(\alpha)}\left(\prod_{t\in T_{\boxplus}}{\chi_{\theta(% t)}}\cdot\prod_{t\in T_{\boxminus}}\overline{\chi_{\theta(t)}}\cdot\prod_{t\in T% _{\mathrel{\ooalign{\raise 0.48436pt\hbox{\hskip 0.42677pt$\scriptscriptstyle+% $}\cr\hss$\diamond$\hss}}}}\overline{\chi_{\theta(t)}}\cdot\prod_{t\in T_{% \mathrel{\ooalign{\raise 0.48436pt\hbox{\hskip 0.42677pt$\scriptscriptstyle-$}% \cr\hss$\diamond$\hss}}}}{\chi_{\theta(t)}}\right)

(2)

where $C_{\alpha}=|E_{{\small\bullet}}|-|F_{\bullet\bullet}|+|T_{\boxplus}|+|T_{% \boxminus}|+2|T_{\mathrel{\ooalign{\raise 0.75346pt\hbox{\hskip 0.42677pt$% \scriptscriptstyle+$}\cr\hss$\diamond$\hss}}}|+2|T_{\mathrel{\ooalign{\raise 0% .75346pt\hbox{\hskip 0.42677pt$\scriptscriptstyle-$}\cr\hss$\diamond$\hss}}}|$ .

In Section 3.4 we prove:

Theorem 6.

Fix a category $\operatorname{TY}(A,\chi,\nu)$ . Let $e_{1},\ldots,e_{|E|}$ be an arbitrary ordering of the edges of $\mathfrak{T}$ . For any collections $\mathcal{P},\mathcal{Q}$ of pairs of indices $(i,j)$ , $1\leq i,j\leq|E|$ , with potentially repeated pairs, such that $|\mathcal{P}|,|\mathcal{Q}|\in O(n)$ , there is an algorithm to evaluate the sum:

\sum_{\theta\in\phi^{-1}(\alpha)}\prod_{(i,j)\in\mathcal{P}}\chi(\theta_{e_{i}% },\theta_{e_{j}})\prod_{(r,s)\in\mathcal{Q}}\overline{\chi(\theta_{e_{r}},% \theta_{e_{s}})}

(3)

in $O(n^{3})$ operations, using $O(n^{2})$ memory words.

Using the theorem, we arrive at a key step towards our main result.

Corollary 7.

Fix a category $\operatorname{TY}(A,\chi,\nu)$ . Given as input a 3-manifold triangulation $\mathfrak{T}$ with $n$ tetrahedra, and a 1-cocycle $\alpha$ in $\mathfrak{T}$ , the sum (2) can be evaluated in $O(n^{3})$ operations, using $O(n^{2})$ memory words.

Proof.

By definition of the projection $\phi$ (Equation (1)), the 1-cocycle $\alpha$ gives a description of the edges colored by the object $m$ in all admissible colorings of $\phi^{-1}(\alpha)$ . Additionally, the multiplicative constant $D^{-|V|}\cdot d_{m}^{C_{\alpha}}\cdot\nu^{|T_{\mathrel{\ooalign{\raise 0.5382% pt\hbox{\hskip 0.42677pt$\scriptscriptstyle+$}\cr\hss$\diamond$\hss}}}|-|T_{% \mathrel{\ooalign{\raise 0.5382pt\hbox{\hskip 0.42677pt$\scriptscriptstyle-$}% \cr\hss$\diamond$\hss}}}|}$ in front of the sum (Equation (2)) depends exclusively on the set of edges colored by $m$ . In consequence, the multiplicative constant can be evaluated in linear time by checking the set of $m$ -colored edges of each tetrahedron. Using the notations of Theorem 6, we consider the pairs $\mathcal{P}$ (resp. $\mathcal{Q}$ ) of indices $(i,j)$ of opposite edges $(e_{i},e_{j})$ not colored by $m$ in tetrahedra of type $T_{\boxplus}\sqcup T_{\mathrel{\ooalign{\raise 0.75346pt\hbox{\hskip 0.42677pt% $\scriptscriptstyle-$}\cr\hss$\diamond$\hss}}}$ (resp. $T_{\boxminus}\sqcup T_{\mathrel{\ooalign{\raise 0.75346pt\hbox{\hskip 0.42677% pt$\scriptscriptstyle+$}\cr\hss$\diamond$\hss}}}$ ), in order to evaluate the sum $\sum_{\theta\in\phi^{-1}(\alpha)}\left(\prod_{t\in T_{\boxplus}}{\chi_{\theta(% t)}}\cdot\prod_{t\in T_{\boxminus}}\overline{\chi_{\theta(t)}}\cdot\prod_{t\in T% _{\mathrel{\ooalign{\raise 0.5382pt\hbox{\hskip 0.42677pt$\scriptscriptstyle+$% }\cr\hss$\diamond$\hss}}}}\overline{\chi_{\theta(t)}}\cdot\prod_{t\in T_{% \mathrel{\ooalign{\raise 0.5382pt\hbox{\hskip 0.42677pt$\scriptscriptstyle-$}% \cr\hss$\diamond$\hss}}}}{\chi_{\theta(t)}}\right)$ in cubic time. $\hfill\blacktriangleleft$

3.3 Efficiently characterizing colorings over a 1-cocycle

For a given 1-cocycle $\alpha\in Z^{1}(\mathfrak{T};\mathbb{Z}/2\mathbb{Z})$ , we now characterize the set $\phi^{-1}(\alpha)\subseteq\operatorname{Adm}(\mathfrak{T})$ . Recall that $E_{\emptyset}$ is the set of edges not colored by $m$ and $F_{\emptyset}$ is the set of faces with no edge colored by $m$ .

Lemma 8.

If the finite abelian group $A$ is given by its primary decomposition with $d(A)$ summands, and the triangulation $\mathfrak{T}$ has $n=|\mathfrak{T}|$ tetrahedra, then the set $\phi^{-1}(\alpha)$ is in bijection with the elements of a finite abelian group $G$ with $O(d(A)n)$ generators.

Proof.

Fix an arbitrary orientation of the edges of the triangulation. The admissibility constraints for colorings in a Tambara-Yamagami category imply that the set $\phi^{-1}(\alpha)$ is in bijection with the set of assignments $\theta\colon E_{\emptyset}\to A$ satisfying the following linear equations: for any $m$ -empty face with edges $e_{1},e_{2},e_{3}$ ,

\varepsilon_{1}\theta(e_{1})+\varepsilon_{2}\theta(e_{2})+\varepsilon_{3}% \theta(e_{3})=0,

where $\varepsilon_{i}\in\{\pm 1\}$ depending whether the orientations of edges $e_{1},e_{2},e_{3}$ agree or not with an arbitrarily chosen orientation of the triangular face. Consider the group homomorphism $\lambda\colon A^{|E_{\emptyset}|}\to A^{|F_{\emptyset}|}$ where the $|F_{\emptyset}|$ -many values are the relations $\varepsilon_{1}\theta(e_{1})+\varepsilon_{2}\theta(e_{2})+\varepsilon_{3}% \theta(e_{3})$ above. The set $\phi^{-1}(\alpha)$ is in bijection with the kernel of this application. Because $A^{|E_{\emptyset}|}$ is a finite abelian group with $d(A)|E_{\emptyset}|$ summands in its primary decomposition, with $|E_{\emptyset}|\leq|E|\in O(n)$ , then $\ker\lambda$ is a finite abelian group with $O(d(A)n)$ generators. $\hfill\blacktriangleleft$

Additionally, a minimal family of generators $(y_{1},\ldots,y_{\ell}),y_{i}\in A^{|E_{\emptyset}|}$ , for $\ker\lambda$ can be computed in polynomial time.

Lemma 9.

For a fixed abelian group $A$ , with the notations above, a minimal family of generators for $\ker\lambda$ can be computed in $O(n^{3})$ operations, using $O(n^{2})$ memory words.

Proof.

The proof is standard linear algebra over $\mathbb{Z}$ using Smith normal form, see the proof of [8, Lemma 3.0] for details. $\hfill\blacktriangleleft$

In conclusion, any generator of the kernel $\ker\lambda\subseteq A^{|E_{\emptyset}|}$ can be interpreted as an assignment of colors to the empty edges of the triangulation $E_{\emptyset}\to A$ . For a fixed 1-cocycle $\alpha$ of the triangulation, any admissible coloring in $\phi^{-1}(\alpha)$ can be expressed as a sum (with integer coefficients) of elements of the kernel (where the sum of colors is edge-wise) following the rule of addition in $A$ .

3.4 Partial state sums are (normalized) Gauss sums

The goal of this subsection is to prove Theorem 6. Consider a finite abelian group $(A,+)$ with $d:=d(A)$ generators $x_{1},\ldots,x_{d}$ for the summands of its primary decomposition, its product $A^{k}$ with generators $(x_{ij})_{i=1\ldots d,j=1\ldots k}$ , and a subgroup $(G,+)$ with $g:=d(G)$ .

For a group element $y\in G$ , we express $y=\sum_{i,j}n_{ij}(y)x_{ij}$ , for integer coefficients $n_{ij}(y)$ , in the set of generators for $A^{k}$ . We also write $y^{(j)}:=\sum_{i=1\ldots d}n_{ij}(y)x_{i}\in A$ for the projection of $y$ into the $j$ -th component of the product $A^{k}$ .

Let $\mathcal{P},\mathcal{Q}$ be arbitrary sets of pairs of indices $(i,j)$ , with $1\leq i,j\leq k$ , and possible multiplicities $p_{ij}\geq 1$ for the pair $(i,j)\in\mathcal{P}$ , and $q_{ij}$ for the pair $(i,j)\in\mathcal{Q}$ . Consider the product:

\psi\colon G\to U(1),\ \ \ \ y\mapsto\displaystyle\prod_{(i,j)\in\mathcal{P}}% \chi(y^{(i)},y^{(j)})^{p_{ij}}\prod_{(r,s)\in\mathcal{Q}}\chi(y^{(r)},y^{(s)})% ^{-q_{rs}}.

(4)

and define the complex valued sum:

\Omega(\mathcal{P},\mathcal{Q}):=\displaystyle\frac{1}{|\sqrt{|G|}|}\sum_{y\in G% }\psi(y).

(5)

Lemma 10.

The sum $\Omega(\mathcal{P},\mathcal{Q})$ in Equation (5) is a quadratic Gauss sum over $G$ , i.e., there exists a quadratic form $q\colon G\to\mathbb{Q}/\mathbb{Z}$ s.t.,

\Omega(\mathcal{P},\mathcal{Q})=\Theta(G,q)=\displaystyle\frac{1}{|\sqrt{|G|}|% }\sum_{x\in G}\mathbf{e}(q(x)).

Proof.

Define the pairing $b\colon A\times A\to\mathbb{Q}/\mathbb{Z}$ satisfying, for any $x,y\in A$ , the equality $\chi(x,y)=\mathbf{e}(b(x,y))$ . The map $b$ is a bilinear pairing. This follows from the definition of a bicharacter. For any $x,y,z\in A$ ,

\chi(x+y,z)=\mathbf{e}(b(x+y,z))=\chi(x,z)\chi(y,z)=\mathbf{e}(b(x,z)+b(y,z)),

and in consequence $b(x+y,z)=b(x,z)+b(y,z)\mod\mathbb{Z}$ . By symmetry of $\chi$ , bilinearity follows. Define $q\colon G\to\mathbb{Q}/\mathbb{Z}$ by:

q(y):=\sum_{(i,j)\in\mathcal{P}}p_{ij}\cdot b(y^{(i)},y^{(j)})-\sum_{(r,s)\in% \mathcal{Q}}q_{rs}\cdot b(y^{(r)},y^{(s)}),

such that $\left|\sqrt{|G|}\right|\Omega(\mathcal{P},\mathcal{Q})=\sum_{x\in G}\mathbf{e}% (q(x))$ . The map $q$ is a quadratic form. Indeed, first notice that, for any integer $u$ , $q(uy)=u^{2}q(y)$ follows from the fact that $b(uy^{(i)},uy^{(j)})=u^{2}b(y^{(i)},y^{(j)})$ . Second, the form $\partial q:(y,y^{\prime})\mapsto q(y+y^{\prime})-q(y)-q(y^{\prime})$ is bilinear, as it can be expressed as a sum of evaluations of the bilinear pairing $b$ on $(y^{(i)},y^{\prime(j)})$ for some $i, j$ . $\hfill\blacktriangleleft$

Proof of Theorem 6.

Using the notation of Theorem 6, we identify the following sum on the triangulation:

\sum_{\theta\in\phi^{-1}(\alpha)}\prod_{(i,j)\in\mathcal{P}}\chi(\theta_{e_{i}% },\theta_{e_{j}})\prod_{(r,s)\in\mathcal{Q}}\overline{\chi(\theta_{e_{r}},% \theta_{e_{s}})}

(6)

with the quantity $\left|\sqrt{|G|}\right|\Omega(\mathcal{P},\mathcal{Q})$ in Equation (5), where the group $G$ is the subgroup $\ker\lambda$ of the product $A^{|E_{\emptyset}|}$ , whose presentation we identify in polynomial time via Lemma 9. The pairs of indices $\mathcal{P}$ and $\mathcal{Q}$ represent indices of edges in Equation (6), and particular copies of $A$ in the product $A^{|E_{\emptyset}|}$ in Equation (4), with a natural correspondence induced by the fact that copies of $A$ in $A^{|E_{\emptyset}|}$ are in bijection with edges not colored by $m$ (once the 1-cocycle $\alpha$ is fixed). The order of the finite group $G=\ker\lambda$ can be evaluated by finding the primary decomposition of $G$ , which can be done in polynomial time (Theorem 1). Let $q$ be the quadratic form defined in the proof of Theorem 10. We can compute the Gram matrix of a minimal family of generators of $\ker\lambda$ (computed in Lemma 9) for the discriminant pairing $(G,\partial q)$ by evaluating $\partial q$ , and compute the Gauss sum $\Omega(\mathcal{P},\mathcal{Q})$ in polynomial time (by virtue of Theorem 2), with the expected complexity. $\hfill\blacktriangleleft$

3.5 Cohomologous 1-cocycles have equal partial state sums

The tools introduced so far in this section would only be enough to construct a parameterized algorithm in terms of the number of 1-cocycles $Z^{1}(\mathfrak{T};\mathbb{Z}/2\mathbb{Z})$ . The final ingredient necessary to further reduce the parameter to $\beta_{1}(M)$ follows from a general statement about TVBW invariants of spherical $G$ -graded fusion categories (for any finite group $G$ ) first described by Turaev and Virelizier [31, Thm. 7.1], specialized to our situation: $\operatorname{TY}(A,\chi,\nu)$ is a spherical $\mathbb{Z}/2\mathbb{Z}$ -graded fusion category.

Theorem 11 (special case of Thm. 7.1 in [31]).

If $\alpha$ and $\beta$ are cohomologous elements of the group of cocycles $Z^{1}(\mathfrak{T};\mathbb{Z}/2\mathbb{Z})$ , then $|\mathfrak{T},\alpha|_{\operatorname{TY}(A,\chi,\nu)}=|\mathfrak{T},\beta|_{% \operatorname{TY}(A,\chi,\nu)}$ .

4 Fixed parameter tractable algorithm in the first Betti number

Fix the data of $\operatorname{TY}(A,\chi,\nu)$ . Given as input an arbitrary triangulation $\mathfrak{T}$ of a closed oriented 3-manifold $M$ , our algorithm to compute the TVBW invariant $|M|_{\operatorname{TY}(A,\chi,\nu)}$ is as follows:

1.

Compute a set of 1-cocycles $\{\alpha_{1},\ldots,\alpha_{\beta_{1}}\}\subset Z^{1}(\mathfrak{T},\mathbb{Z}/% 2\mathbb{Z})$ such that $\{[\alpha_{1}],\ldots,[\alpha_{\beta_{1}}]\}$ forms a basis of the 1-cohomology vector space $H^{1}(\mathfrak{T},\mathbb{Z}/2\mathbb{Z})$ .

Compute a basis for $B^{1}(\mathfrak{T},\mathbb{Z}/2\mathbb{Z})$ ; the cardinality $\#B^{1}(\mathfrak{T},\mathbb{Z}/2\mathbb{Z})$ of the set of 1-coboundaries is equal to $2^{\dim B^{1}(\mathfrak{T},\mathbb{Z}/2\mathbb{Z})}$ . [Theorem 3]
2.

For each of the $2^{\beta_{1}}$ distinct 1-cohomology classes $[\alpha]$ of $H^{1}(\mathfrak{T},\mathbb{Z}/2\mathbb{Z})$ , construct a representative $\alpha\in Z^{1}(\mathfrak{T},\mathbb{Z}/2\mathbb{Z})$ by enumerating all $2^{\beta_{1}}$ $\mathbb{Z}/2\mathbb{Z}$ -combinations of elements in $\{\alpha_{1},\ldots,\alpha_{\beta_{1}}\}$ , i.e., all $\alpha=\varepsilon_{1}\alpha_{1}+\ldots+\varepsilon_{\beta_{1}}\alpha_{\beta_{% 1}}$ , for $\varepsilon_{i}\in\mathbb{Z}/2\mathbb{Z}$ .
Now, for each such $\alpha$ , apply Corollary 7 to compute the partial state sum $|\mathfrak{T},\alpha|_{\operatorname{TY}(A,\chi,\nu)}$ , with the following steps:
1. (a)
  
  Compute a minimal family of generators for $\ker\lambda=\langle x_{1},\ldots,x_{g}\rangle$ , [Lemma 9]
2. (b)
  
  Compute the primary decomposition of $\ker\lambda$ with generators $\ker\lambda=\langle x^{\prime}_{1},\ldots,x^{\prime}_{g}\rangle$ for the summands, [Theorem 1]
3. (c)
  
  Compute the Gram matrix of $x^{\prime}_{1},\ldots,x^{\prime}_{g}$ for the pre-metric form $(\ker\lambda,q)$ , by evaluating $\partial q$ on all pairs $(x^{\prime}_{i},x^{\prime}_{j})$ . [defined in Lemma 10]
4. (d)
  
  Evaluate the Gauss sum of $(\ker\lambda,q)$ , [Theorem 2]
  
  and multiply by $\left|\sqrt{|G|}\right|$ . [proof of Theorem 6]
  
  Normalize to get the state sum $|\mathfrak{T},\alpha|_{\operatorname{TY}(A,\chi,\nu)}$ , with multiplicative factor as in Equation (2). [Corollary 7]
3.

Sum over all $\alpha$ :

$|M|_{\operatorname{TY}(A,\chi,\nu)}=\sum_{\begin{array}[]{c}\alpha=\varepsilon% _{1}\alpha_{1}+\ldots\varepsilon_{\beta_{1}}\alpha_{\beta_{1}}\\ \text{with }\varepsilon_{i}\in\mathbb{Z}/2\mathbb{Z},\text{ and s.t.,}\\ \langle[\alpha_{1}],\ldots,[\alpha_{\beta_{1}}]\rangle=H^{1}(\mathfrak{T},% \mathbb{Z}/2\mathbb{Z})\\ \end{array}}\#B^{1}(\mathfrak{T},\mathbb{Z}/2\mathbb{Z})\cdot|\mathfrak{T},% \alpha|_{\operatorname{TY}(A,\chi,\nu)}.$

Our main Theorem 4 follows readily from the following:

Theorem 12.

Fix a Tambara-Yamagami category $\operatorname{TY}(A,\chi,\nu)$ . Given a triangulation $\mathfrak{T}$ of a closed 3-manifold $M$ with $n$ tetrahedra, the above algorithm computes $|M|_{\operatorname{TY}(A,\chi,\nu)}$ in $O(2^{\beta_{1}}n^{3})$ operations and using $O(n^{2})$ memory words.

Proof.

Computing a basis for $B^{1}(\mathfrak{T},\mathbb{Z}/2\mathbb{Z})$ , as well as a set of generators $\{\alpha_{1},\ldots,\alpha_{\beta_{1}}\}$ whose cohomology classes form a basis of $H^{1}(\mathfrak{T},\mathbb{Z}/2\mathbb{Z})$ , in step (1) is a standard procedure in computer algebra (Theorem 3), done by normalizing a $O(n)\times O(n)$ matrix with $\mathbb{Z}/2\mathbb{Z}$ coefficients. This can be done in $O(n^{3})$ operations in $\mathbb{Z}/2\mathbb{Z}$ with Gaussian eliminations, where an arithmetic operation in $\mathbb{Z}/2\mathbb{Z}$ has constant complexity.

Given the 1-cocycles $\{\alpha_{1},\ldots,\alpha_{\beta_{1}}\}$ , we can enumerate every combination $\alpha=\varepsilon_{1}\alpha_{1}+\ldots+\varepsilon_{\beta_{1}}\alpha_{\beta_{% 1}}$ in (amortized) $O(n)$ operations per $\alpha$ . Indeed, enumerating all $\{\varepsilon_{1},\ldots,\varepsilon_{\beta_{1}}\}$ is akin to incrementing a $\beta_{1}$ -bits binary counter from $0\ldots 0$ to $1\ldots 1$ , which induces an (amortized) change of $O(1)$ bits per increment [7, Chapter 16]. The 1-cocycles are represented by formal sums of $O(n)$ edges, and computing the sum of two 1-cocycles takes $O(n)$ operations.

For each $\alpha$ as above, we compute the partial state sum using Corollary 7 in polynomial time. Specifically, step (2a) is solved by computing a Smith normal form, together with transformation matrices, of a particular $O(d(A)n)\times O(d(A)n)$ -integer matrix, which has complexity $O(n^{3})$ (Lemma 9) with (modular) Gaussian eliminations, once $A$ is fixed.

We can read-off the generators $x_{1},\ldots,x_{g}$ of $\ker\lambda$ from the transformation matrices, and compute the generators $x^{\prime}_{1},\ldots,x^{\prime}_{g}$ of step (2b) by computing the primary decomposition of the subgroup $\ker\lambda$ (Theorem 1). Computing the Gram matrix in step (2c) is done by evaluating the bilinear pairing $\partial q$ , defined in Lemma 10, on all pairs $(x^{\prime}_{i},x^{\prime}_{j})$ . The quadratic form $q$ is defined as a sum of $O(n)$ terms of the form $b(x^{\prime}_{i},x^{\prime}_{j})$ , and the overall Gram matrix can be computed in $O(g^{2}n)$ operations. Recall that we have an oracle access to the function $b(\cdot,\cdot)$ (see beginning of Section 3). By Theorem 2, the Gauss sum of $(\ker\lambda,q)$ can be evaluated from the Gram matrix of $x^{\prime}_{1},\ldots,x^{\prime}_{g}$ in $O(g^{3})$ operations in $\mathbb{Q}/\mathbb{Z}$ , where the arithmetic complexity of operations in $\mathbb{Q}/\mathbb{Z}$ depend solely on the maximal order of an element of $A$ (independently of the size of the Gram matrix). See the full version [8] for details.

Finally, the invariant $|M|_{\operatorname{TY}(A,\chi,\nu)}$ computed in step (3) is the sum of $2^{\beta_{1}}$ complex numbers represented with a constant number of memory words each for a fixed group $A$ (with $\beta_{1}\leq n$ ). In consequence, the overall complexity of the algorithm, knowing $g\in O(d(A)n)$ and considering $d(A),|A|$ constant for a fixed group $A$ , is $O(2^{\beta_{1}}n^{3})$ . The memory complexity is bounded by the size of the matrices, which is $O(n^{2})$ , since we have a fixed $A$ (coefficients are represented with a constant number of memory words, and $d(A)$ is a constant). $\hfill\blacktriangleleft$

References

[1] David Aasen, Roger S. K. Mong, and Paul Fendley. Topological defects on the lattice: I. The Ising model. J. Phys. A, 49(35):354001, 46, 2016. doi:10.1088/1751-8113/49/35/354001.
[2] John W. Barrett and Bruce W. Westbury. Invariants of piecewise-linear $3$ -manifolds. Trans. Amer. Math. Soc., 348(10):3997–4022, 1996. doi:10.1090/S0002-9947-96-01660-1.
[3] Tathagata Basak and Ryan Johnson. Indicators of Tambara-Yamagami categories and Gauss sums. Algebra & Number theory, 9(8):1793–1823, 2015.
[4] Benjamin A. Burton, Clément Maria, and Jonathan Spreer. Algorithms and complexity for Turaev-Viro invariants. J. Appl. Comput. Topol., 2(1-2):33–53, 2018. doi:10.1007/S41468-018-0016-2.
[5] Jin-Yi Cai, Xi Chen, Richard Lipton, and Pinyan Lu. On tractable exponential sums. In Frontiers in Algorithmics: 4th International Workshop, FAW 2010, Wuhan, China, August 11-13, 2010. Proceedings 4, pages 148–159. Springer, 2010. doi:10.1007/978-3-642-14553-7_16.
[6] Yichul Choi, Ho Tat Lam, and Shu-Heng Shao. Noninvertible Global Symmetries in the Standard Model. Phys. Rev. Lett., 129:161601, October 2022. doi:10.1103/PhysRevLett.129.161601.
[7] Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson. Introduction to Algorithms. McGraw-Hill Higher Education, 4th edition, 2001.
[8] Colleen Delaney, Clément Maria, and Eric Samperton. An algorithm for Tambara-Yamagami quantum invariants of 3-manifolds, parameterized by the first Betti number. CoRR, abs/2311.08514, 2023. doi:10.48550/arXiv.2311.08514.
[9] Daniel S. Freed, Gregory W. Moore, and Constantin Teleman. Topological symmetry in quantum field theory, 2023. arXiv:2209.07471.
[10] Daniel S. Freed and Constantin Teleman. Topological dualities in the Ising model. Geom. Topol., 26(5):1907–1984, 2022. doi:10.2140/gt.2022.26.1907.
[11] Allan Hatcher. Algebraic Topology. Cambridge University Press, 1 edition, 2002.
[12] William Jaco and J. Hyam Rubinstein. 0-efficient triangulations of 3-manifolds. J. Differential Geom., 65(1):61–168, 2003.
[13] F. Jaeger, D. L. Vertigan, and D. J. A. Welsh. On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc., 108(1):35–53, 1990. doi:10.1017/S0305004100068936.
[14] Robion Kirby and Paul Melvin. Local surgery formulas for quantum invariants and the Arf invariant. Geometry & Topology Monographs, 7:213–233, 2004.
[15] Alexander Kirillov Jr and Benjamin Balsam. Turaev-Viro invariants as an extended TQFT. arXiv preprint, 2010. arXiv:1004.1533.
[16] A. Yu. Kitaev. Fault-tolerant quantum computation by anyons. Ann. Physics, 303(1):2–30, 2003. doi:10.1016/S0003-4916(02)00018-0.
[17] Robert Koenig, Greg Kuperberg, and Ben W. Reichardt. Quantum computation with Turaev-Viro codes. Ann. Physics, 325(12):2707–2749, 2010. doi:10.1016/j.aop.2010.08.001.
[18] Hari Krovi and Alexander Russell. Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups. Comm. Math. Phys., 334(2):743–777, 2015. doi:10.1007/s00220-014-2285-5.
[19] Greg Kuperberg. How hard is it to approximate the Jones polynomial? Theory Comput., 11:183–219, 2015. doi:10.4086/toc.2015.v011a006.
[20] Greg Kuperberg and Eric Samperton. Computational complexity and 3-manifolds and zombies. Geom. Topol., 22(6):3623–3670, 2018. doi:10.2140/gt.2018.22.3623.
[21] Greg Kuperberg and Eric Samperton. Coloring invariants of knots and links are often intractable. Algebr. Geom. Topol., 21(3):1479–1510, 2021. doi:10.2140/agt.2021.21.1479.
[22] Clément Maria and Jonathan Spreer. Admissible colourings of 3-manifold triangulations for Turaev-Viro type invariants. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 64:1–64:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPICS.ESA.2016.64.
[23] Clément Maria and Jonathan Spreer. A polynomial-time algorithm to compute Turaev-Viro invariants TV4,q of 3-manifolds with bounded first Betti number. Found. Comput. Math., 20(5):1013–1034, 2020. doi:10.1007/s10208-019-09438-8.
[24] Sergei Matveev. Algorithmic Topology and Classification of 3-Manifolds. Springer, 9 edition, 2003.
[25] James R. Munkres. Elements of algebraic topology. CRC Press, 1 edition, 1984.
[26] Eric C. Rowell and Zhenghan Wang. Mathematics of topological quantum computing. Bull. Amer. Math. Soc. (N.S.), 55(2):183–238, 2018. doi:10.1090/bull/1605.
[27] Winfried Scharlau. Quadratic and Hermitian Forms. Grundlehren der mathematischen Wissenschaften. Springer, 1985.
[28] Daisuke Tambara and Shigeru Yamagami. Tensor Categories with Fusion Rules of Self-Duality for Finite Abelian Groups. Journal of Algebra, 209:692–707, 1998.
[29] Ryan Thorngren and Yifan Wang. Fusion category symmetry I: anomaly in-flow and gapped phases. arXiv preprint, 2019. arXiv:1912.02817.
[30] V. G. Turaev and O. Ya. Viro. State sum invariants of $3$ -manifolds and quantum $6j$ -symbols. Topology, 31(4):865–902, 1992. doi:10.1016/0040-9383(92)90015-A.
[31] Vladimir Turaev and Alexis Virelizier. On 3-dimensional homotopy quantum field theory, i. International Journal of Mathematics, 23(09):1250094, 2012.
[32] Vladimir G. Turaev. Quantum invariants of knots and 3-manifolds, volume 18 of De Gruyter Studies in Mathematics. De Gruyter, Berlin, third edition, 2016. doi:10.1515/9783110435221.
[33] Charles T C Wall. Quadratic forms on finite groups and related topics. Topology, 2:281–298, 1963.
[34] Zhenghan Wang. Topological quantum computation, volume 112 of CBMS Regional Conference Series in Mathematics. Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2010. doi:10.1090/cbms/112.

[bib.bib1] [1] David Aasen, Roger S. K. Mong, and Paul Fendley. Topological defects on the lattice: I. The Ising model. J. Phys. A, 49(35):354001, 46, 2016. doi:10.1088/1751-8113/49/35/354001.

[bib.bib2] [2] John W. Barrett and Bruce W. Westbury. Invariants of piecewise-linear $3$ -manifolds. Trans. Amer. Math. Soc., 348(10):3997–4022, 1996. doi:10.1090/S0002-9947-96-01660-1.

[bib.bib3] [3] Tathagata Basak and Ryan Johnson. Indicators of Tambara-Yamagami categories and Gauss sums. Algebra & Number theory, 9(8):1793–1823, 2015.

[bib.bib4] [4] Benjamin A. Burton, Clément Maria, and Jonathan Spreer. Algorithms and complexity for Turaev-Viro invariants. J. Appl. Comput. Topol., 2(1-2):33–53, 2018. doi:10.1007/S41468-018-0016-2.

[bib.bib5] [5] Jin-Yi Cai, Xi Chen, Richard Lipton, and Pinyan Lu. On tractable exponential sums. In Frontiers in Algorithmics: 4th International Workshop, FAW 2010, Wuhan, China, August 11-13, 2010. Proceedings 4, pages 148–159. Springer, 2010. doi:10.1007/978-3-642-14553-7_16.

[bib.bib6] [6] Yichul Choi, Ho Tat Lam, and Shu-Heng Shao. Noninvertible Global Symmetries in the Standard Model. Phys. Rev. Lett., 129:161601, October 2022. doi:10.1103/PhysRevLett.129.161601.

[bib.bib7] [7] Thomas H. Cormen, Clifford Stein, Ronald L. Rivest, and Charles E. Leiserson. Introduction to Algorithms. McGraw-Hill Higher Education, 4th edition, 2001.

[bib.bib8] [8] Colleen Delaney, Clément Maria, and Eric Samperton. An algorithm for Tambara-Yamagami quantum invariants of 3-manifolds, parameterized by the first Betti number. CoRR, abs/2311.08514, 2023. doi:10.48550/arXiv.2311.08514.

[bib.bib9] [9] Daniel S. Freed, Gregory W. Moore, and Constantin Teleman. Topological symmetry in quantum field theory, 2023. arXiv:2209.07471.

[bib.bib10] [10] Daniel S. Freed and Constantin Teleman. Topological dualities in the Ising model. Geom. Topol., 26(5):1907–1984, 2022. doi:10.2140/gt.2022.26.1907.

[bib.bib11] [11] Allan Hatcher. Algebraic Topology. Cambridge University Press, 1 edition, 2002.

[bib.bib12] [12] William Jaco and J. Hyam Rubinstein. 0-efficient triangulations of 3-manifolds. J. Differential Geom., 65(1):61–168, 2003.

[bib.bib13] [13] F. Jaeger, D. L. Vertigan, and D. J. A. Welsh. On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc., 108(1):35–53, 1990. doi:10.1017/S0305004100068936.

[bib.bib14] [14] Robion Kirby and Paul Melvin. Local surgery formulas for quantum invariants and the Arf invariant. Geometry & Topology Monographs, 7:213–233, 2004.

[bib.bib15] [15] Alexander Kirillov Jr and Benjamin Balsam. Turaev-Viro invariants as an extended TQFT. arXiv preprint, 2010. arXiv:1004.1533.

[bib.bib16] [16] A. Yu. Kitaev. Fault-tolerant quantum computation by anyons. Ann. Physics, 303(1):2–30, 2003. doi:10.1016/S0003-4916(02)00018-0.

[bib.bib17] [17] Robert Koenig, Greg Kuperberg, and Ben W. Reichardt. Quantum computation with Turaev-Viro codes. Ann. Physics, 325(12):2707–2749, 2010. doi:10.1016/j.aop.2010.08.001.

[bib.bib18] [18] Hari Krovi and Alexander Russell. Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups. Comm. Math. Phys., 334(2):743–777, 2015. doi:10.1007/s00220-014-2285-5.

[bib.bib19] [19] Greg Kuperberg. How hard is it to approximate the Jones polynomial? Theory Comput., 11:183–219, 2015. doi:10.4086/toc.2015.v011a006.

[bib.bib20] [20] Greg Kuperberg and Eric Samperton. Computational complexity and 3-manifolds and zombies. Geom. Topol., 22(6):3623–3670, 2018. doi:10.2140/gt.2018.22.3623.

[bib.bib21] [21] Greg Kuperberg and Eric Samperton. Coloring invariants of knots and links are often intractable. Algebr. Geom. Topol., 21(3):1479–1510, 2021. doi:10.2140/agt.2021.21.1479.

[bib.bib22] [22] Clément Maria and Jonathan Spreer. Admissible colourings of 3-manifold triangulations for Turaev-Viro type invariants. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 64:1–64:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPICS.ESA.2016.64.

[bib.bib23] [23] Clément Maria and Jonathan Spreer. A polynomial-time algorithm to compute Turaev-Viro invariants TV4,q of 3-manifolds with bounded first Betti number. Found. Comput. Math., 20(5):1013–1034, 2020. doi:10.1007/s10208-019-09438-8.

[bib.bib24] [24] Sergei Matveev. Algorithmic Topology and Classification of 3-Manifolds. Springer, 9 edition, 2003.

[bib.bib25] [25] James R. Munkres. Elements of algebraic topology. CRC Press, 1 edition, 1984.

[bib.bib26] [26] Eric C. Rowell and Zhenghan Wang. Mathematics of topological quantum computing. Bull. Amer. Math. Soc. (N.S.), 55(2):183–238, 2018. doi:10.1090/bull/1605.

[bib.bib27] [27] Winfried Scharlau. Quadratic and Hermitian Forms. Grundlehren der mathematischen Wissenschaften. Springer, 1985.

[bib.bib28] [28] Daisuke Tambara and Shigeru Yamagami. Tensor Categories with Fusion Rules of Self-Duality for Finite Abelian Groups. Journal of Algebra, 209:692–707, 1998.

[bib.bib29] [29] Ryan Thorngren and Yifan Wang. Fusion category symmetry I: anomaly in-flow and gapped phases. arXiv preprint, 2019. arXiv:1912.02817.

[bib.bib30] [30] V. G. Turaev and O. Ya. Viro. State sum invariants of $3$ -manifolds and quantum $6j$ -symbols. Topology, 31(4):865–902, 1992. doi:10.1016/0040-9383(92)90015-A.

[bib.bib31] [31] Vladimir Turaev and Alexis Virelizier. On 3-dimensional homotopy quantum field theory, i. International Journal of Mathematics, 23(09):1250094, 2012.

[bib.bib32] [32] Vladimir G. Turaev. Quantum invariants of knots and 3-manifolds, volume 18 of De Gruyter Studies in Mathematics. De Gruyter, Berlin, third edition, 2016. doi:10.1515/9783110435221.

[bib.bib33] [33] Charles T C Wall. Quadratic forms on finite groups and related topics. Topology, 2:281–298, 1963.

[bib.bib34] [34] Zhenghan Wang. Topological quantum computation, volume 112 of CBMS Regional Conference Series in Mathematics. Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2010. doi:10.1090/cbms/112.

An Algorithm for Tambara-Yamagami Quantum Invariants of 3-Manifolds, Parameterized by the First Betti Number

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Main Result (Informal; see Theorem 4).

2 Background

2.1 Elements of algorithmic number theory

Finite abelian groups.

Theorem 1.

Pairings and forms on finite abelian groups.

Gauss sums on pre-metric groups.

Theorem 2.

2.2 Combinatorial and algebraic topology

(Co)homology.

Theorem 3.

Triangulated 3-manifolds.

2.3 Tambara-Yamagami quantum invariants

3 The role of the Betti number in Tambara-Yamagami invariants

Theorem 4.

3.1 Admissible colorings induce simplicial 1-cocycles

Lemma 5.

3.2 The partial state sum at a 1-cocycle

Theorem 6.

Corollary 7.

Proof.

3.3 Efficiently characterizing colorings over a 1-cocycle

Lemma 8.

Proof.

Lemma 9.

Proof.

3.4 Partial state sums are (normalized) Gauss sums

Lemma 10.

Proof.

Proof of Theorem 6.

3.5 Cohomologous 1-cocycles have equal partial state sums

Theorem 11 (special case of Thm. 7.1 in [31]).

4 Fixed parameter tractable algorithm in the first Betti number

Theorem 12.

Proof.

References