Citation: Nicolas Bridges, Eric Samperton, "Towards a complexity-theoretic dichotomy for TQFT invariants", 2025, https://arxiv.org/abs/2503.02945
Web: https://arxiv.org/abs/2503.02945
Tags: Property-F, Tensor-networks, Quantum-advantage
In this fantastic paper, Nicolas Bridges and Eric Samperton prove a separation result for complexity theory in TQFTs. Namely, they prove that the problem of of contracting a tensor network labeled by morphisms in a spherical fusion category/MTC is either #P-hard or polynomial time. Excitingly, they aren't able to give a computable way of determining which of these two cases a given SFC/MTC falls into!
The proof is an application of Cai and Chen' recently discovered dichotomy for weighted constraint satisfaction problems:
> Cai, Jin-Yi, and Xi Chen. "Complexity of counting CSP with complex weights." Journal of the ACM (JACM) 64.3 (2017): 1-39.
It's interesting to conjecture about exactly what their computational complexity divide is. A natural guess is that the divide is exactly the same as Property F - weakly integral categories. However this is wrong, because computing the knot invariants of categories based on non-solvable (and even some solvable non-nilpontent) finite groups is #P hard:
> Kuperberg, Greg, and Eric Samperton. "Computational complexity and 3-manifolds and zombies." Geometry & Topology 22.6 (2018): 3623-3670.
> Kuperberg, Greg, and Eric Samperton. "Coloring invariants of knots and links are often intractable." Algebraic & Geometric Topology 21.3 (2021): 1479-1510.
Maybe the line is the same as the one for hardness of computing the non-abelian hidden subgroup problem, which includes all nilpotent groups but also some solvable non-nilpotent groups:
> https://arxiv.org/abs/quant-ph/0504083
Anyhow, this paper definitively establishes that something "real" is going on. There is an invariant of a finite group, which is whether or not tensor network contraction on D(G) is #P-hard. Figuring out exactly where this line is is now the challenging and interesting open problem.