DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2025.5

Towards a Complexity-Theoretic Dichotomy for TQFT Invariants

Authors: Nicolas Bridges and Eric Samperton

Published in: LIPIcs, Volume 350, 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)

Abstract

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.

Cite as

Nicolas Bridges and Eric Samperton. Towards a Complexity-Theoretic Dichotomy for TQFT Invariants. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bridges_et_al:LIPIcs.TQC.2025.5,
  author =	{Bridges, Nicolas and Samperton, Eric},
  title =	{{Towards a Complexity-Theoretic Dichotomy for TQFT Invariants}},
  booktitle =	{20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)},
  pages =	{5:1--5:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-392-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{350},
  editor =	{Fefferman, Bill},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2025.5},
  URN =		{urn:nbn:de:0030-drops-240548},
  doi =		{10.4230/LIPIcs.TQC.2025.5},
  annote =	{Keywords: Complexity, topological quantum field theory, dichotomy theorems, constraint satisfaction problems, tensor categories}
}

Search Results

Documents authored by Bridges, Nicolas

Towards a Complexity-Theoretic Dichotomy for TQFT Invariants

Abstract

Cite as

Thanks for your feedback!

Could not send message