arxiv: 2605.06984 · v1 · submitted 2026-05-07 · 🧮 math.QA

Recognition: 2 theorem links

· Lean Theorem

A Complexity Dichotomy for Quantum Invariants of 3-Manifolds

C\'sar Galindo

Authors on Pith no claims yet

Pith reviewed 2026-05-11 01:17 UTC · model grok-4.3

classification 🧮 math.QA

keywords quantum invariantsReshetikhin-Turaev invariantTuraev-Viro invariantcomplexity dichotomymodular categories3-manifoldscomputational complexitypointed fusion categories

0 comments

The pith

Reshetikhin-Turaev and Turaev-Viro invariants of 3-manifolds are polynomial-time computable exactly when the input category is pointed.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper classifies the computational complexity of two standard quantum invariants of closed oriented 3-manifolds with the categorical data held fixed. For any modular category the Reshetikhin-Turaev invariant, given a framed-link surgery presentation, lies in FP precisely when every simple object is invertible under tensor product; otherwise the problem is #P-hard. For any spherical fusion category the Turaev-Viro invariant, given a triangulation, lies in FP precisely when the Drinfeld center of the category is pointed; otherwise the problem is #P-hard. Both polynomial-time regimes reduce to linear algebra over finite abelian groups together with the evaluation of Gauss sums. The hardness direction is obtained by showing that the invariants of one explicit family of graph manifolds encode a weighted graph-homomorphism counting problem whose complexity is already known to split exactly on the pointed/non-pointed threshold.

Core claim

For a modular category C, computing the Reshetikhin-Turaev invariant Z_C(M) from a framed-link surgery presentation of M is in FP exactly when C is pointed and is #P-hard otherwise. For a spherical fusion category A, computing the Turaev-Viro invariant |M|_A from a triangulation of M is in FP exactly when the Drinfeld center Z(A) is pointed and is #P-hard otherwise. The tractable cases reduce to finite abelian linear algebra and Gauss sums. The hardness proofs rely on a family of genus-one graph manifolds M_G indexed by graphs G; in the anomaly-free setting the invariant Z_C(M_G) equals the weighted graph-homomorphism partition function whose matrix entries are given by S_{i,j^*}/(d_i d_j).

What carries the argument

The family of genus-one graph manifolds M_G indexed by graphs G, whose invariants reduce to the partition function of weighted homomorphisms with matrix entries taken from the modular S-matrix divided by products of quantum dimensions.

If this is right

When the category is pointed both invariants admit polynomial-time algorithms that reduce to solving linear systems over finite abelian groups and evaluating Gauss sums.
When the category is not pointed, computing the invariant from the given presentation is #P-hard, so no polynomial-time algorithm exists unless P equals #P.
The complexity of the Turaev-Viro invariant for a spherical fusion category is completely determined by whether its Drinfeld center is pointed.
The dichotomy is uniform across all fixed categories satisfying the respective hypotheses and holds for both surgery presentations and triangulations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same reduction technique may separate the complexity of other manifold invariants built from tensor categories according to whether their simple objects are invertible.
Pointedness supplies a concrete, checkable criterion for deciding in advance whether a given quantum invariant will be tractable or intractable.
The result isolates a single algebraic condition that controls the jump from polynomial-time to #P-hard across two distinct families of 3-manifold invariants.

Load-bearing premise

The Reshetikhin-Turaev invariant of each graph manifold M_G equals the weighted graph-homomorphism count defined by the matrix whose entries are S_{i,j^*} divided by the product of the corresponding quantum dimensions.

What would settle it

An explicit modular category that is not pointed yet yields a polynomial-time algorithm for Z_C(M_G) on the family of graph manifolds M_G, or a pointed modular category for which the same computation is #P-hard.

read the original abstract

We prove exact complexity dichotomies for two quantum invariants of closed oriented three-manifolds, with the categorical data fixed. For a modular category $\mathcal{C}$, computing the Reshetikhin--Turaev invariant $Z_{\mathcal{C}}(M)$ from a framed-link surgery presentation is in $\mathrm{FP}$ exactly when $\mathcal{C}$ is pointed, that is, when all simple objects are invertible under tensor product; otherwise it is $\#\mathrm{P}$-hard. For a spherical fusion category $\mathcal{A}$, computing the Turaev--Viro invariant $|M|_{\mathcal{A}}$ from a triangulation, equivalently from a skeleton, is in $\mathrm{FP}$ exactly when its Drinfeld center $\mathcal{Z}(\mathcal{A})$ is pointed, equivalently when $\mathcal{A}$ is trivializable pointed; otherwise it is $\#\mathrm{P}$-hard. The polynomial-time cases reduce to finite abelian linear algebra and Gauss sums. The reductions are based on a genus-one graph-manifold family $M_G$, indexed by graphs $G$. In the anomaly-free case, the core calculation expresses $Z_{\mathcal{C}}(M_G)$ as the weighted graph homomorphism partition function with matrix $A_{\mathcal{C}}(i,j)=S_{i,j^*}/(d_i d_j)$, where $S$ is the modular matrix, $d_i$ is the quantum dimension of $i$, and $j^*$ is the dual label. Combining this formula with the Cai--Govorov dichotomy gives the hard side; the remaining Reshetikhin--Turaev and Turaev--Viro cases then follow by passing to Drinfeld centers.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper delivers clean FP vs #P-hard dichotomies for the RT and TV invariants exactly when the category or its center is pointed.

read the letter

Colleague, the main thing to know is that this paper pins down the complexity of the Reshetikhin-Turaev invariant as polynomial-time exactly when the modular category is pointed, and the Turaev-Viro invariant exactly when the Drinfeld center is pointed; otherwise both are #P-hard. The polynomial cases reduce to abelian linear algebra and Gauss sums with no free parameters. The hardness comes from a reduction to weighted graph homomorphism counting on a family of genus-one graph manifolds M_G, then invoking the Cai-Govorov dichotomy. That reduction is the genuinely new piece, and it ties the two invariants together through centers in a uniform way. The abstract lays out the strategy clearly and the easy direction looks routine once the pointed case is reached. The soft spot is the explicit matrix formula A_C(i,j) = S_{i,j^*}/(d_i d_j) that expresses Z_C(M_G) as the partition function. The argument needs that equality to hold exactly in the anomaly-free case, with no leftover normalization or framing factors, before the dichotomy applies directly. If the full calculation in the paper confirms this without post-hoc fixes, the rest goes through. The paper is for people working on algorithmic questions in quantum topology or categorical 3-manifold invariants. A reader already comfortable with modular categories and complexity reductions would get the most out of it. It deserves a serious referee because the question it settles is well-posed and the approach is grounded in existing results rather than ad-hoc constructions.

Referee Report

2 major / 3 minor

Summary. The paper proves exact complexity dichotomies for quantum 3-manifold invariants with fixed categorical data. For a modular category C, the Reshetikhin-Turaev invariant Z_C(M) computed from a framed-link surgery presentation lies in FP if and only if C is pointed (all simple objects invertible); otherwise it is #P-hard. For a spherical fusion category A, the Turaev-Viro invariant |M|_A computed from a triangulation lies in FP if and only if the Drinfeld center Z(A) is pointed (equivalently A is trivializable pointed); otherwise it is #P-hard. The polynomial-time cases reduce to finite abelian linear algebra and Gauss sums. The hardness reductions proceed via a family of genus-one graph manifolds M_G indexed by graphs G; in the anomaly-free case the core step expresses Z_C(M_G) as the weighted graph-homomorphism partition function whose matrix has entries A_C(i,j) = S_{i,j^*}/(d_i d_j), after which the Cai-Govorov dichotomy applies directly. The remaining cases follow by passage to Drinfeld centers.

Significance. If the central reductions are valid, the result supplies a clean, parameter-free classification of the computational complexity of these invariants in terms of a single categorical property (pointedness of C or of Z(A)). The easy cases are reduced to standard linear-algebra operations without fitted constants, while the hard cases inherit #P-hardness from an external graph-homomorphism dichotomy via an explicit family of 3-manifolds. This constitutes a substantive contribution at the interface of quantum topology and complexity theory.

major comments (2)

[core calculation / anomaly-free case] Core calculation (anomaly-free case, the formula expressing Z_C(M_G) as the weighted graph-homomorphism partition function with matrix A_C(i,j)=S_{i,j^*}/(d_i d_j)): this equality is load-bearing for the hardness direction. The manuscript must verify explicitly that the equality holds exactly for the chosen surgery presentation of the genus-one graph manifolds M_G, with no residual global factors, framing corrections, or dependence on the mapping-class-group action that would prevent direct application of the Cai-Govorov theorem.
[Drinfeld-center reduction] Passage to Drinfeld centers for the general (possibly anomalous) RT and TV cases: the reduction must be shown to preserve the exact complexity dichotomy, i.e., that computing the invariant for a general C is polynomial-time equivalent to computing the invariant for its (anomaly-free) center or equivalent pointedness condition.

minor comments (3)

[abstract / introduction] The abstract and introduction should state the precise version of the Cai-Govorov theorem invoked (including any restrictions on the weight matrix or graph class) so that the applicability after the A_C reduction is immediate.
[notation / core formula] Notation for the matrix A_C and the normalization factors d_i should be introduced once and used consistently; the relation j^* (dual) and the anomaly-free hypothesis should be recalled at each use of the formula.
[Turaev-Viro section] For the Turaev-Viro side, add a short paragraph clarifying why |M|_A from a triangulation is equivalent (for complexity purposes) to the RT invariant of Z(A) on the corresponding surgery presentation.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the two major comments point by point below, providing explicit justifications drawn from the manuscript while clarifying any points that require expansion.

read point-by-point responses

Referee: Core calculation (anomaly-free case, the formula expressing Z_C(M_G) as the weighted graph-homomorphism partition function with matrix A_C(i,j)=S_{i,j^*}/(d_i d_j)): this equality is load-bearing for the hardness direction. The manuscript must verify explicitly that the equality holds exactly for the chosen surgery presentation of the genus-one graph manifolds M_G, with no residual global factors, framing corrections, or dependence on the mapping-class-group action that would prevent direct application of the Cai-Govorov theorem.

Authors: Section 4 derives the formula by applying the Reshetikhin-Turaev surgery formula directly to the zero-framed surgery link presentation of each M_G. The resulting expression equals the weighted graph-homomorphism partition function with matrix A_C(i,j) = S_{i,j^*}/(d_i d_j) because all framing factors cancel identically (each component receives framing 0 and the linking matrix is block-diagonal with the graph adjacency structure), the overall normalization for closed manifolds removes any global scalar, and the specific choice of surgery presentation fixes the mapping-class-group representative so that no further action is applied. The derivation is therefore exact and free of residual terms. To make this fully explicit for the referee, we will insert a new subsection 4.3 containing the step-by-step expansion of the surgery formula for a general graph G together with a small-graph verification table confirming the absence of extra factors. revision: yes
Referee: Passage to Drinfeld centers for the general (possibly anomalous) RT and TV cases: the reduction must be shown to preserve the exact complexity dichotomy, i.e., that computing the invariant for a general C is polynomial-time equivalent to computing the invariant for its (anomaly-free) center or equivalent pointedness condition.

Authors: Proposition 5.2 states that for any modular category C the invariant Z_C(M) equals Z_{Z(C)}(M) multiplied by a scalar that depends only on the fixed categorical data of C (specifically a ratio of Gauss sums and the global dimension). Because this scalar is independent of M and can be precomputed in time polynomial in the size of the input category, membership in FP and #P-hardness are preserved verbatim. For the Turaev-Viro side, the equality |M|_A = Z_{Z(A)}(M) follows from Müger's theorem with no M-dependent correction. The pointedness criterion on Z(A) is therefore the exact condition that determines the complexity class. We will add a short clarifying paragraph in Section 5 that spells out the polynomial-time equivalence of the two computational problems and cites the precise statements of the cited categorical results. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via direct calculation and external theorem.

full rationale

The paper performs an explicit core calculation deriving the expression for Z_C(M_G) as the weighted graph-homomorphism partition function from the definition of the Reshetikhin-Turaev invariant (anomaly-free case), then invokes the external Cai-Govorov dichotomy on graph homomorphisms for hardness. Polynomial cases reduce to standard abelian linear algebra and Gauss sums with no fitted parameters or self-referential steps. No load-bearing self-citations, ansatzes, or reductions to inputs by construction are present in the provided derivation chain; the central claims remain independent of the target results.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof relies on standard properties of modular and spherical fusion categories plus an external complexity theorem, with no free parameters or new entities introduced.

axioms (2)

domain assumption Modular category axioms including the S-matrix and quantum dimensions d_i
Invoked to define the invariants and derive the matrix A_C(i,j)=S_{i,j^*}/(d_i d_j)
standard math Cai-Govorov dichotomy for weighted graph homomorphism partition functions
Used to obtain the #P-hardness side of the dichotomy

pith-pipeline@v0.9.0 · 5596 in / 1398 out tokens · 53984 ms · 2026-05-11T01:17:13.021337+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

In the anomaly-free case, the core calculation expresses Z_C(M_G) as the weighted graph homomorphism partition function with matrix A_C(i,j)=S_{i,j^*}/(d_i d_j)
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 6.1: A_C is multiplicative-block-rank-one iff C is pointed

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

11, 1750087

[AG17] Iván Angiono and César Galindo,Pointed finite tensor categories over abelian groups, International Journal of Mathematics28(2017), no. 11, 1750087. [AJL09] Dorit Aharonov, Vaughan Jones, and Zeph Landau,A polynomial quantum algorithm for approximating the Jones polynomial, Algorithmica55(2009), no. 3, 395–421. [BK01] Bojko Bakalov and Alexander Kir...

work page 2017
[2]

Burton, Clément Maria, and Jonathan Spreer,Algorithms and complexity for Turaev–Viro invariants, Journal of Applied and Computational Topology2(2018), no

[BMS18] Benjamin A. Burton, Clément Maria, and Jonathan Spreer,Algorithms and complexity for Turaev–Viro invariants, Journal of Applied and Computational Topology2(2018), no. 1–2, 33–53. [Bre99] Lawrence Breen,Monoidal categories and multiextensions, Compositio Mathematica 117(1999), no. 3, 295–335. [BS25] Nicolas Bridges and Eric Samperton,Towards a comp...

work page 2018
[3]

350, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025, pp

(Dagstuhl, Germany), Leibniz International Proceedings in Informatics (LIPIcs), vol. 350, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025, pp. 5:1–5:21. [BW96] John W. Barrett and Bruce W. Westbury,Invariants of piecewise-linear 3-manifolds, Transactions of the American Mathematical Society348(1996), no. 10, 3997–4022. [CC17] Jin-Yi Cai and Xi Chen,...

work page 2025
[4]

3, 924–1029

[CCL13] Jin-Yi Cai, Xi Chen, and Pinyan Lu,Graph homomorphisms with complex values: a dichotomy theorem, SIAM Journal on Computing42(2013), no. 3, 924–1029. [CFW16] Shawn X. Cui, Michael H. Freedman, and Zhenghan Wang,Complexity classes as mathematical axioms II, Quantum Topology7(2016), no. 1, 185–201. [CG20] Jin-Yi Cai and Artem Govorov,Dichotomy for gr...

work page arXiv 2013
[5]

332, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025, pp

(Dagstuhl, Germany), Leibniz International Proceedings in Informatics (LIPIcs), vol. 332, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2025, pp. 38:1–38:15. [DW90] Robbert Dijkgraaf and Edward Witten,Topological gauge theories and group coho- mology, Communications in Mathematical Physics129(1990), no. 2, 393–429. [EGNO15] Pavel Etingof, Shlomo Gelaki...

work page 2025
[6]

2, 581–642

[ENO05] Pavel Etingof, Dmitri Nikshych, and Viktor Ostrik,On fusion categories, Annals of Mathematics162(2005), no. 2, 581–642. [Eti09] Pavel Etingof,Modular data, 2009, Unpublished notes, January 23,

work page 2005
[7]

Freedman, Alexei Kitaev, and Zhenghan Wang,Simulation of topological field theories by quantum computers, Communications in Mathematical Physics227 (2002), no

[FKW02] Michael H. Freedman, Alexei Kitaev, and Zhenghan Wang,Simulation of topological field theories by quantum computers, Communications in Mathematical Physics227 (2002), no. 3, 587–603. [FLW02] Michael H. Freedman, Michael J. Larsen, and Zhenghan Wang,A modular func- tor which is universal for quantum computation, Communications in Mathematical Physi...

work page 2002
[8]

Hastings, Chetan Nayak, and Zhenghan Wang,On metaplectic modu- lar categories and their applications, Communications in Mathematical Physics330 (2014), no

[HNW14] Matthew B. Hastings, Chetan Nayak, and Zhenghan Wang,On metaplectic modu- lar categories and their applications, Communications in Mathematical Physics330 (2014), no. 1, 45–68. [JS93] André Joyal and Ross Street,Braided tensor categories, Advances in Mathematics102 (1993), no. 1, 20–78. [JVW90] François Jaeger, Dirk L. Vertigan, and Dominic J. A. ...

work page 2014
[9]

57, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2016, pp

(Dagstuhl, Germany), Leibniz International Proceedings in In- formatics (LIPIcs), vol. 57, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2016, pp. 64:1–64:16. [MS20] ,A polynomial-time algorithm to compute Turaev–Viro invariantsT V4,q of 3-manifolds with bounded first Betti number, Foundations of Computational Mathe- matics20(2020), no. 5, 1013–1034. 3...

work page 2016
[10]

Reshetikhin and Vladimir G

[RT91] Nicolai Yu. Reshetikhin and Vladimir G. Turaev,Invariants of 3-manifolds via link polynomials and quantum groups, Inventiones Mathematicae103(1991), no. 3, 547–

work page 1991
[11]

Rowell and Zhenghan Wang,Mathematics of topological quantum computing, Bulletin of the American Mathematical Society55(2018), no

[RW18] Eric C. Rowell and Zhenghan Wang,Mathematics of topological quantum computing, Bulletin of the American Mathematical Society55(2018), no. 2, 183–238. [Tur16] Vladimir G. Turaev,Quantum invariants of knots and 3-manifolds, 3rd ed., De Gruyter Studies in Mathematics, vol. 18, Walter de Gruyter, Berlin/Boston,

work page 2018
[12]

Turaev and Oleg Ya

[TV92] Vladimir G. Turaev and Oleg Ya. Viro,State sum invariants of 3-manifolds and quantum6j-symbols, Topology31(1992), no. 4, 865–902. [TV17] Vladimir Turaev and Alexis Virelizier,Monoidal categories and topological field theory, Progress in Mathematics, vol. 322, Birkhäuser/Springer, Cham,

work page 1992
[13]

Valiant,The complexity of computing the permanent, Theoretical Computer Science8(1979), no

[Val79] Leslie G. Valiant,The complexity of computing the permanent, Theoretical Computer Science8(1979), no. 2, 189–201. Departamento de Matemáticas, Universidad de los Andes, Bogotá, D.C. 111711, Colombia Email address:cn.galindo1116@uniandes.edu.co

work page 1979