Towards a complexity-theoretic dichotomy for TQFT invariants

• URL: http://arxiv.org/abs/2503.02945v1
• Date: Tue, 04 Mar 2025 19:05:46 GMT
• Title: Towards a complexity-theoretic dichotomy for TQFT invariants
• Authors: Nicolas Bridges, Eric Samperton,
• Abstract summary: We show that for any fixed $(2+1)$-dimensional TQFT over $mathbbC$, the problem of (exactly) computing its invariants on closed 3-manifolds is solvable in time.<n>Our proof is an application of a result of Cai and Chen concerning weighted constraint satisfaction problems over $mathbbC$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that for any fixed $(2+1)$-dimensional TQFT over $\mathbb{C}$ 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 $\#\mathsf{P}$-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 $\mathbb{C}$. We leave for future work the issue of reinterpreting the conditions of Cai and Chen that distinguish between the two cases (i.e. $\#\mathsf{P}$-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 the TQFT's fusion category.

Related papers

• Thirty-six officers, artisanally entangled [0.7826806223782052]
  A perfect tensor of order $d$ is a state of four systems maximally entangled under any bipartition. We present the first human-made order-$6$ perfect tensors. We sketch a formulation of the theory of perfect tensors in terms of quasi-orthogonal decompositions of matrix algebras.
  arXiv  Detail & Related papers  (2025-04-21T19:04:33Z)
• Explicit non-free tensors [3.1593341358400737]
  We prove that non-free tensors exist in $mathbbCn otimes mathbbCn otimes mathbbCn$, where they are not generic. We show that if a tensor $T$ is free, then there is a tensor $S$ in the GL-orbit closure of $T$, whose support is free and whose moment map image is the minimum-norm point of the moment polytope of $T$.
  arXiv  Detail & Related papers  (2025-03-28T17:38:44Z)
• Overcomplete Tensor Decomposition via Koszul-Young Flattenings [63.01248796170617]
  We give a new algorithm for decomposing an $n_times n times n_3$ tensor as the sum of a minimal number of rank-1 terms. We show that an even more general class of degree-$d$s cannot surpass rank $Cn$ for a constant $C = C(d)$.
  arXiv  Detail & Related papers  (2024-11-21T17:41:09Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• Equivalence Between SE(3) Equivariant Networks via Steerable Kernels and Group Convolution [90.67482899242093]
  A wide range of techniques have been proposed in recent years for designing neural networks for 3D data that are equivariant under rotation and translation of the input. We provide an in-depth analysis of both methods and their equivalence and relate the two constructions to multiview convolutional networks. We also derive new TFN non-linearities from our equivalence principle and test them on practical benchmark datasets.
  arXiv  Detail & Related papers  (2022-11-29T03:42:11Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• CFT$_D$ from TQFT$_{D+1}$ via Holographic Tensor Network, and Precision Discretisation of CFT$_2$ [6.375036429666303]
  We show that the path-integral of conformal field theories in $D$ dimensions can be constructed by solving for eigenstates of an RG operator. We also devise and illustrate numerical methods for $D=2,3$ to search for CFT$_D$ as phase transition points between symmetric TQFT$_D$.
  arXiv  Detail & Related papers  (2022-10-21T17:34:14Z)
• Annihilating Entanglement Between Cones [77.34726150561087]
  We show that Lorentz cones are the only cones with a symmetric base for which a certain stronger version of the resilience property is satisfied. Our proof exploits the symmetries of the Lorentz cones and applies two constructions resembling protocols for entanglement distillation.
  arXiv  Detail & Related papers  (2021-10-22T15:02:39Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  We focus on the measurement defined by the decomposition based on Schur-Weyl duality on $n$ qubits. We derive various types of distribution including a kind of central limit when $n$ goes to infinity.
  arXiv  Detail & Related papers  (2021-04-26T15:03:08Z)
• $a\times b=c$ in $2+1$D TQFT [2.982218441172364]
  We study the implications of the anyon fusion equation $atimes b=c$ on global properties of $2+1$D topological quantum field theories (TQFTs) We argue that the appearance of such fusions for non-abelian $a$ and $b$ can also be an indication of zero-form symmetries in a TQFT.
  arXiv  Detail & Related papers  (2020-12-29T10:01:57Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.