The quantum separation axioms of Cui-Freedman-Wang: the BQP-NDQC1 relationship and DQC1-hardness of trace-closure Jones approximation for $r > 6$

Cui, Freedman, and Wang (Quantum Topology 7 (2016) 185-201, 'Complexity classes as mathematical axioms II') proved that, conditional on three quantum complexity-separation conjectures they call axioms - $BQP \not\subseteq NDQC1$, $BQP \not\subseteq NP$, and $BQP \not\subseteq DQC1$ - polynomially bounded sequences of Jones-preserving $\Gamma_r$-Dehn surgery operations cannot effect even linear simplification of link diagrams, sharpening the exponential bounds Freedman obtained in 2009 from classical axioms. The complexity landscape these theorems assume is itself incomplete in the two ways the paper explicitly leaves open. First, the relationship between BQP (universal polynomial-time quantum computation) and NDQC1 - the class the paper introduces, of problems whose classical certificates are verified by a one-clean-qubit DQC1 machine - is open in both directions: not even $BQP \subseteq NDQC1$ is known, and no unrelativized proof of any of the three axioms exists. Second, for integers $r > 6$ the problem of additively approximating $|J(\hat{\beta}_{tr}; r)|/d^n$ (the Jones evaluation of the trace closure of a braid at the $r$-th root of unity, with $d = 2\cos(\pi/r)$) is known to lie in DQC1, but its DQC1-hardness - established at $r = 5$ by Shor and Jordan - has not been established.

Background

Links in the 3-sphere $S^3$ - disjoint unions of embedded circles - are encoded combinatorially by link diagrams, and two diagrams represent the same link exactly when they differ by a finite sequence of Reidemeister moves (local diagram moves). A braid $\beta \in B_n$ on $n$ strands closes into a link in two standard ways: the trace closure (Markov closure, joining strand ends cyclically) and the plat closure (capping adjacent strand pairs of a braid on $2n$ strands). The Jones polynomial is a polynomial invariant of links; evaluating it at a root of unity $\omega_r = e^{2\pi i/r}$ is #P-hard in the exact sense for integers $r \geq 5$ with $r \neq 6$, so the quantum-computation literature studies additive approximation: with $d = 2\cos(\pi/r)$, estimating the normalized value $|J(\hat{\beta}; r)|/d^n$ to additive error $\epsilon$ in time polynomial in the braid index, braid length, and $1/\epsilon$.

BQP is the class of decision problems solvable with bounded error by polynomial-size uniform quantum circuits. DQC1 ('deterministic quantum computation with one clean qubit', introduced by Knill and Laflamme) is the restricted model whose input is a single pure qubit $|0\rangle$ tensored with $n$ maximally mixed qubits, i.e. the density matrix $|0\rangle\langle 0| \otimes I/2^n$; a unitary is applied to all $n+1$ qubits and only the clean qubit is measured. Its flagship task is estimating the normalized trace of a unitary. $DQC1 \subseteq BQP$, the inclusion is widely believed strict, and this has never been proved.

The approximation theory of the Jones polynomial ties these classes to knot theory. By the Aharonov-Jones-Landau algorithm together with the Freedman-Kitaev-Larsen-Wang universality results, additively approximating $|J(\hat{\beta}_{plat}; r)|/d^n$ for $\beta \in B_{2n}$ (plat closure) is BQP-complete for all $r \geq 5$, $r \neq 6$. Shor and Jordan proved that the same approximation for the trace closure at $r = 5$ is complete for DQC1, and Jordan and Wocjan showed the trace-closure problem lies in DQC1 at every admissible $r$. Additive approximation is thus sensitive to the presentation of the link (plat versus trace closure), a phenomenon also analyzed by Kuperberg.

Freedman's earlier paper 'Complexity classes as mathematical axioms' initiated a program converting complexity-separation conjectures into statements about the combinatorics of link diagrams: if a class separation holds, then sequences of local, efficiently describable operations preserving the $\omega_r$-Jones evaluation cannot substantially simplify diagrams. The source paper continues this with quantum separations. Its operations are $\Gamma_r$-Dehn surgeries: Dehn surgery on a knot disjoint from the link, with gluing matrix in the principal congruence subgroup $\Gamma(4r)$ of $SL(2,\mathbb{Z})$, the subgroup of matrices congruent to the identity entrywise modulo $4r$. Via the $SU(2)$ Reshetikhin-Turaev topological quantum field theory (a 3-dimensional TQFT whose partition function on $(S^3, L)$ equals the Jones evaluation), such surgeries preserve $|J(\cdot; r)|$ up to a phase. When the surgered manifold is again $S^3$ one converts back to a link by '$S^3$ recognition': deciding whether a triangulated closed 3-manifold is $S^3$ lies in NP (Schleimer), although no polynomial-time recognition algorithm is known. Sequences of these operations generate an equivalence relation $\equiv_r$ on diagrams together with a cost measure $\operatorname{dist}_r(D, D')$ counting crossings, description bits of the gluing matrices, and Reidemeister moves; the point is that the number of computational steps to pass from $D$ to $D'$ is polynomially bounded in $\operatorname{dist}_r(D, D')$.

The paper's Theorem 4 states, for each $r \geq 5$, $r \neq 6$: for all positive $\alpha, \beta$ there exists a link diagram $D$ such that no $r$-equivalent diagram $D'$ that is the trace closure of a braid can satisfy $g(D') \leq g(D) + \alpha(\log g(D) + \log c(D))$ unless $\operatorname{dist}_r(D, D') > (g(D)c(D))^{\beta}$, where $g$ denotes girth (the maximum number of strands met by a vertical line) and $c$ the crossing number. Theorem 5 keeps the same distance alternative but drops both the trace-closure restriction and the additive $g(D)$ term, concluding $g(D') > \alpha(\log g(D) + \log c(D))$ for every $r$-equivalent $D'$. Theorem 6 is instead a non-existence statement: no polynomial-time DQC1 algorithm solves the problem $Q(r, \alpha)$ of computing, from a link diagram $D$, a braid $\beta$ whose trace closure $\hat{\beta}_{tr}$ has the same $\omega_r$-Jones evaluation as $D$ and girth $g(\hat{\beta}_{tr}) \leq g(D) + \alpha(\log g(D) + \log c(D))$. Theorem 4 rests on Axiom 1 ($BQP \not\subseteq NDQC1$), Theorem 5 on Axiom 2 ($BQP \not\subseteq NP$), and Theorem 6 on Axiom 3 ($BQP \not\subseteq DQC1$); the failure of each theorem would contradict its axiom.

Problem Statement

Determine the quantum complexity landscape that the conditional diagram-simplification theorems of Cui-Freedman-Wang presuppose, along the two axes the paper itself leaves open: the complexity classification of the Jones-evaluation problems and complexity classes that Theorems 4-6 of the source take as axioms and upper bounds. The two axes are logically independent.

(1) The separation axioms and the BQP-NDQC1 relationship. With DQC1 defined as the class of problems solvable in polynomial time by a one-clean-qubit machine (initial density matrix $|0\rangle\langle 0| \otimes I/2^n$, unitary evolution, measurement of the clean qubit, bounded error) and NDQC1 defined exactly as in Definition 3 of the source (yes-instances admit polynomial-length classical certificates accepted by a DQC1 verifier with probability $> 2/3$; no-instances are rejected with probability $> 2/3$ for every certificate of the specified length), determine whether $BQP \subseteq NDQC1$ or $BQP \not\subseteq NDQC1$ (Axiom 1 of the source). Since Axiom 1 implies them, also determine the truth of the weaker axioms $BQP \not\subseteq NP$ (Axiom 2) and $BQP \not\subseteq DQC1$ (Axiom 3), each currently neither proved nor refuted in the unrelativized setting. Either outcome - a containment proof or a separation proof - resolves the question for that axiom.

(2) DQC1-hardness of trace-closure Jones approximation for $r > 6$. For each integer $r \geq 5$ with $r \neq 6$, let $\omega_r = e^{2\pi i/r}$, $d = 2\cos(\pi/r)$, and for a braid $\beta \in B_n$ of length $m$ let $\hat{\beta}_{tr}$ be its trace closure. Consider the problem of additively approximating $|J(\hat{\beta}_{tr}; r)|/d^n$ to error $\epsilon$ in time $\operatorname{poly}(n, m, 1/\epsilon)$ - known to lie in DQC1 for every such $r$ and to be DQC1-complete at $r = 5$. For a specified integer $r > 6$ - or uniformly for all $r > 6$ - either establish DQC1-hardness by a polynomial-time reduction from a DQC1-complete problem (which, with the known containment, yields DQC1-completeness), or establish, in the unrelativized setting, a definitive negative or structural result showing that the natural hardness statement fails (for example, that the trace-closure problem is not DQC1-hard). A relativized barrier result - for instance an oracle world in which the hardness statement fails - does not by itself settle the unrelativized question.

References

1. Shawn X. Cui, Michael H. Freedman, Zhenghan Wang, 'Complexity classes as mathematical axioms II', Quantum Topology 7 (2016), 185-201, DOI 10.4171/qt/75, arXiv:1305.6076, https://doi.org/10.4171/qt/75
2. Michael H. Freedman, 'Complexity classes as mathematical axioms', Annals of Mathematics (2) 170 (2009), no. 2, 995-1002, DOI 10.4007/annals.2009.170.995, https://doi.org/10.4007/annals.2009.170.995
3. Peter W. Shor, Stephen P. Jordan, 'Estimating Jones polynomials is a complete problem for one clean qubit', Quantum Information & Computation 8 (2008), no. 8-9, 681-714, DOI 10.26421/qic8.8-9-1, arXiv:0707.2831, https://arxiv.org/abs/0707.2831
4. Stephen P. Jordan, Pawel Wocjan, 'Estimating Jones and HOMFLY polynomials with one clean qubit', Quantum Information & Computation 9 (2009), no. 3-4, 264-289, DOI 10.26421/qic9.3-4-6, arXiv:0807.4688, https://arxiv.org/abs/0807.4688
5. Dorit Aharonov, Vaughan Jones, Zeph Landau, 'A polynomial quantum algorithm for approximating the Jones polynomial', Algorithmica 55 (2009), no. 3, 395-421, DOI 10.1007/s00453-008-9168-0, arXiv:quant-ph/0511096, https://arxiv.org/abs/quant-ph/0511096
6. Greg Kuperberg, 'How hard is it to approximate the Jones polynomial?', Theory of Computing 11 (2015), article 6, 183-219, DOI 10.4086/toc.2015.v011a006, arXiv:0908.0512, https://arxiv.org/abs/0908.0512
7. E. Knill, R. Laflamme, 'Power of One Bit of Quantum Information', Physical Review Letters 81 (1998), no. 25, 5672-5675, DOI 10.1103/PhysRevLett.81.5672, https://doi.org/10.1103/PhysRevLett.81.5672
8. Saul Schleimer, 'Sphere recognition lies in NP', in Low-dimensional and symplectic topology, Proceedings of Symposia in Pure Mathematics 82, American Mathematical Society (2011), 183-213, DOI 10.1090/pspum/082/2768660, arXiv:math/0407047, https://arxiv.org/abs/math/0407047
9. Gorjan Alagic, Catharine Lo, 'Quantum invariants of 3-manifolds and NP vs #P', Quantum Information & Computation 17 (2017), no. 1-2, 125-146, DOI 10.26421/qic17.1-2-8, arXiv:1411.6049, https://arxiv.org/abs/1411.6049
10. Eric C. Rowell, Zhenghan Wang, 'Mathematics of Topological Quantum Computing', Bulletin of the American Mathematical Society 55 (2018), no. 2, 183-238, DOI 10.1090/bull/1605, arXiv:1705.06206, https://arxiv.org/abs/1705.06206
11. Alexander Schmidhuber, Michele Reilly, Paolo Zanardi, Seth Lloyd, Aaron Lauda, 'A quantum algorithm for Khovanov homology', arXiv:2501.12378 (2025), https://arxiv.org/abs/2501.12378
12. Tuomas Laakkonen, Enrico Rinaldi, Chris N. Self, Eli Chertkov, Matthew DeCross, David Hayes, Brian Neyenhuis, Marcello Benedetti, Konstantinos Meichanetzidis, 'End-to-End Quantum Algorithms for the Jones Polynomial', PRX Quantum 7 (2026), no. 2, 020355, DOI 10.1103/jgv8-l3j1, arXiv:2503.05625, https://arxiv.org/abs/2503.05625
13. Uma Girish, 'Fourier Spectrum of Noisy Quantum Algorithms', arXiv:2510.06385 (2025), https://arxiv.org/abs/2510.06385
14. Colleen Delaney, Calvin McPhail-Snyder, 'Zesting and the relative complexity of Reshetikhin-Turaev invariants', arXiv:2608.02795 (2026), https://arxiv.org/abs/2608.02795
15. Zhengfeng Ji, Tongyang Li, Changpeng Shao, Xinzhao Wang, Yuxin Zhang, 'DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians', arXiv:2604.01519 (2026), https://arxiv.org/abs/2604.01519