Source-linked AI summary
Estimating Jones polynomials is a complete problem for one clean qubit
Peter W. Shor, Stephen P. Jordan
TL;DR
Plat-closure Jones approximation is BQP-hard, but converting to a trace closure may yield insufficient precision to solve that problem. Using the Fibonacci representation, the paper establishes DQC1-completeness for approximating the trace-closure Jones polynomial at a fifth root of unity.
Problem
Although plat-closure Jones approximation is BQP-hard, Alexander’s conversion to a trace closure can increase the strand count enough to make the resulting approximation too imprecise for the original problem.
Source: §2 · p. 6Method
The paper uses the Fibonacci representation to encode a circuit so that the trace-closure Jones polynomial equals the trace of the encoded circuit.
Source: §2 · p. 6, §5 · p. 11Results
At t = e^{i2π/5}, approximating the trace-closure Jones polynomial within ±ε is DQC1-complete for appropriate ε.
Source: §6 · p. 13Takeaways & Limitations
If DQC1 is not contained in P and does not contain all of BQP, trace-closure Jones approximation is neither classically polynomial-time easy nor BQP-hard.
Source: §6 · p. 14The original DQC1 definition assumes classical circuit generation; whether the proofs carry over to the NC1-controlled variant is left unpursued.
Source: §1 · p. 2
Abstract
from arXiv · showhide
It is known that evaluating a certain approximation to the Jones polynomial for the plat closure of a braid is a BQP-complete problem. That is, this problem exactly captures the power of the quantum circuit model. The one clean qubit model is a model of quantum computation in which all but one qubit starts in the maximally mixed state. One clean qubit computers are believed to be strictly weaker than standard quantum computers, but still capable of solving some classically intractable problems. Here we show that evaluating a certain approximation to the Jones polynomial at a fifth root of unity for the trace closure of a braid is a complete problem for the one clean qubit complexity class. That is, a one clean qubit computer can approximate these Jones polynomials in time polynomial in both the number of strands and number of crossings, and the problem of simulating a one clean qubit computer is reducible to approximating the Jones polynomial of the trace closure of a braid.
1 One Clean Qubit
The section defines DQC1 for one-clean-qubit computation and establishes normalized trace estimation as DQC1-complete. It shows how the model estimates traces and how trace estimation captures computations, including circuits that use clean ancillas.
1 One Clean Qubit
- DQC1 uses one pure |0⟩ qubit and n maximally mixed qubits, with polynomial-time decision correctness at least 2/3 and measurements only at computation’s end.The section notes that allowing a logarithmic number of clean qubits, or a single partially polarized qubit, does not change the class.Source: §1 · pp. 1–2
- The stated completeness results assume classical circuit generation; transfer to the NC1-controlled one-clean-qubit model is proposed but not pursued.The authors say they suspect the algorithm and hardness proof carry over to that weaker control model.Source: §1 · p. 2
- A Hadamard test estimates a circuit’s normalized trace by averaging over computational-basis states and measuring the control qubit; controlled-U adds only constant-factor overhead.The figure explains how outcome frequencies estimate the real part of an expectation, while a different control initialization estimates its imaginary part.Source: §1 · p. 2, Figure 1 · p. 2
- To prove trace-estimation hardness, the construction replaces the projectors in the one-clean-qubit measurement expression with CNOT gates in a larger unitary.When a projected qubit is |1⟩, a CNOT flips an extra qubit, making the resulting basis state orthogonal and excluding it from the trace.Source: §1 · pp. 2–3
- Inverse-polynomial-precision trace estimation is DQC1-complete.The section sketches hardness for estimating normalized traces and relates trace estimation to its decision version by binary search.Source: §1 · pp. 2–3
- Circuits using m clean ancillas can be handled by adding m extra qubits and CNOT flags, and constant or logarithmic clean-qubit counts yield the same class as one clean qubit.The construction relates the enlarged unitary’s trace to the original trace by Tr[Ua] = 2^m Tr[U].Source: §1 · p. 3
2 Jones Polynomials
The Jones polynomial is a link invariant, and braids provide discrete representations of links through plat and trace closures. Although approximation for plat closures is BQP-complete, transferring that hardness to trace closures is not immediate; the paper establishes DQC1-completeness for a trace-closure approximation at a fifth root of unity.
2 Jones Polynomials
- The Jones polynomial assigns a Laurent polynomial to an oriented knot or link, and exact evaluation is #P-hard at all but a few special values of t.Its degree grows at most linearly with the number of crossings, but its integer coefficients may be exponentially large.Source: §2 · p. 4
- Plat and trace closures join braid ends in different ways, and every link can be represented using either closure.Alexander’s theorem gives the trace-closure representation; the plat-closure representation follows as a corollary.Source: §2 · p. 5, Figure 5 · p. 5, Figure 6 · p. 5
- A function on braids induces a link invariant under trace closure when it is invariant under both Markov moves.These moves enforce the link-equivalence constraints in the braid representation.Source: §2 · pp. 5–6, Figure 7 · p. 5
- Plat-closure approximation at the specified precision is BQP-complete, while trace-closure approximation was previously known only to lie in BQP.Alexander’s conversion can increase the strand count, making the resulting approximation too imprecise to inherit plat-closure hardness.Source: §2 · p. 6
- At a fifth root of unity, approximating the Jones polynomial of a braid’s trace closure is DQC1-complete.The paper uses the Fibonacci representation to express the polynomial as a trace over the entire Hilbert space rather than a subset of diagonal elements.Source: §2 · p. 6
3 Fibonacci Representation
The Fibonacci representation gives a unitary braid-group representation whose trace yields the Jones polynomial at t = ei2π/5. Its local crossing rules act on constrained p/∗ strings, and a weighted trace over two invariant subspaces yields the polynomial.
3 Fibonacci Representation
- The Fibonacci representation is a unitary representation of the braid group whose trace yields the Jones polynomial at t = ei2π/5.The paper treats its particle labels p and ∗ as formal elements in a procedure based on Temperley-Lieb recoupling theory.Source: §3 · p. 6
- For an n-strand braid, the representation acts on length n + 1 strings of p and ∗ with no adjacent ∗ symbols.The strings span a space of dimension f_(n+3), and the representation maps braid-group elements to unitary transformations.Source: §3 · p. 7, Figure 8 · p. 7
- Each elementary crossing locally mixes strings that differ at the symbol beneath the crossing, with coefficients determined by that symbol and its neighbors.The braid action is computed by applying the local crossing rules to the string labels.Source: §3 · p. 7
- The representation is reducible into four invariant subspaces because its rules leave the leftmost and rightmost symbols unchanged.The paper illustrates the action on the ∗…p subspace.Source: §3 · p. 8
- The Jones polynomial at t = ei2π/5 is a weighted trace of the Fibonacci representation over the ∗…∗ and ∗…p subspaces.The parameter is also expressed using A = e−i3π/5, with t = A−4.Source: §3 · pp. 7–8
4 Computing the Jones Polynomial in DQC1
The algorithm encodes constrained Fibonacci strings as integers so a one-clean-qubit computer can trace-estimate the braid action. It simulates each crossing through locally extracted symbols and accounts for the trace weights with only constant measurement overhead.
4 Computing the Jones Polynomial in DQC1
- Length-n strings over p and ∗ with no adjacent ∗ symbols are in bijection with integers from 0 through f_(n+2) − 1, where f1 = 1, f2 = 1, and f3 = 2; this is the Zeckendorf representation.Source: §4 · p. 8
- The encoding maps the valid strings to at least half of the full 2^b-dimensional bitstring space, enabling trace estimation over a sufficiently large subspace.A direct mapping of p and ∗ symbols to bits would not work because one-clean-qubit trace estimation may not handle exponentially small subspaces.Source: §4 · pp. 8–9
- For each crossing, the algorithm extracts neighboring encoded symbols into ancillas, applies the local three-qubit unitary, and returns the symbols to the encoding.Combining these crossing circuits and performing DQC1 trace estimation approximates the Jones polynomial.Source: §4 · p. 9
- The leftmost symbol can be extracted by comparing its encoded integer with a Fibonacci threshold, then conditionally subtracting that threshold.Integer arithmetic and comparison can be implemented efficiently using NC1 circuits and a constant number of clean ancillas.Source: §4 · p. 9
- Splitting the string encoding into two integers permits extraction of an arbitrary symbol by moving the split, while scaling the trace weights to at most one adds only constant measurement overhead.Moving the split uses addition, subtraction, and comparison; the weights are at least 1/φ after scaling.Source: §4 · p. 10, Figure 10
5 DQC1-hardness of Jones Polynomials
The section proves DQC1-hardness by encoding quantum-circuit computation into Fibonacci-representation braids whose trace closure yields the circuit trace. Efficient gate simulation relies on local symbol movement and carefully controlled encoding and trace weights.
5 DQC1-hardness of Jones Polynomials
- The reduction maps symbol strings to bitstrings and constructs a braid whose Fibonacci representation implements the circuit unitary, making its trace equal the circuit trace.Source: §5 · pp. 10–11
- Equal-size preimages for each bitstring ensure an unbiased trace, while superblocks locate each encoded bit through its first coding block.Source: §5 · p. 11
- Proposition 1 enables polynomial-crossing approximations of independent Fibonacci-representation blocks for k = O(log n); this efficiency is specific to that representation, not density alone.Source: §5 · p. 12
- The inchworm alternates density-enabled moves of centered ∗ symbols between superblocks, then reverses its swaps to shuttle among gate locations.Source: §5 · pp. 12–13
- A constant-probability starting condition is enforced by conditionally flipping an extra encoded qubit when the first two superblocks lack centered ∗ symbols.Source: §5 · p. 12
- Choosing sufficiently large superblocks makes strings without a valid swap segment exponentially unlikely for random strings.Source: §5 · p. 13
- An extra terminal superblock applies a conditional rotation with overlap 1/φ when the last symbol is p, canceling the Jones trace’s weighting.Source: §5 · p. 13
- For appropriate ε, approximating the Jones polynomial of a braid’s trace closure to within ±ε is DQC1-hard.Source: §5 · p. 13
6 Conclusion
The paper establishes DQC1-completeness for approximating the Jones polynomial of a braid’s trace closure at a fifth root of unity. This resolves an open complexity question and yields conditional implications from the authors’ stated beliefs about DQC1.
6 Conclusion
- Approximating the trace-closure Jones polynomial at t = ei2π/5 to within ±ε is DQC1-complete for appropriate ε.Source: §6 · p. 13
- The trace-closure approximation’s complexity was open at precision ±|D^(n−1)|/poly(n,m), and the paper establishes DQC1-completeness for A = e−i3π/5.Source: §6 · p. 13
- If DQC1 is not contained in P and does not contain all of BQP, the approximation is neither classically polynomial-time solvable nor BQP-hard.Source: §6 · p. 14
- The authors identify trace-closure Jones approximation as one of only four known candidates for classically intractable problems solvable on a one-clean-qubit computer.Source: §6 · p. 14
A Jones Polynomials by Fibonacci Representation
The paper identifies a weighted trace of the Fibonacci braid representation with the Jones polynomial at A = e−i3π/5, up to computable factors. It establishes this identification by showing that the representation and trace satisfy the required Temperley-Lieb and Markov-trace properties.
A Jones Polynomials by Fibonacci Representation
- The Jones polynomial at A = e−i3π/5 is obtained from the Fibonacci representation’s weighted trace after multiplying by computable powers of D and (−A).Thus approximating the Jones polynomial reduces to computing this trace.Source: A Jones Polynomials by Fibonacci… · p. 15
- The paper identifies its weighted trace with the Markov trace, whose defining properties uniquely determine the trace map.The proof verifies the needed properties for the Fibonacci representation and its weighted trace.Source: A Jones Polynomials by Fibonacci… · p. 15
- The weighted trace is the ordinary matrix trace on strings ending in ∗ plus φ times the trace on strings ending in p, and it is normalized so f Tr(1) = 1.The two subspaces have dimensions fn−1 and fn, respectively.Source: A Jones Polynomials by Fibonacci… · p. 15
- The Fibonacci representation satisfies the Temperley-Lieb algebra relations, so its trace gives the Jones polynomial at A = e−i3π/5.The proof checks the required generator relations, including that the relevant blocks square to D times themselves.Source: A Jones Polynomials by Fibonacci… · pp. 17–18
B Density of the Fibonacci representation
The Fibonacci braid representation is dense, modulo phase, in the stated special unitary groups. The proof establishes a low-dimensional base case and extends density inductively using the representation’s recursive block structure.
B Density of the Fibonacci representation
- For n = 4, ρ∗∗(B4) is dense modulo phase in SU(2), providing the low-dimensional base case.The proof shows two generator rotations cannot generate a finite subgroup of SO(3).Source: B Density of the Fibonacci… · pp. 18–19
- Because φ(A) and φ(B) rotate about different axes, their generated group is not Ck or Dk; R = φ(A)^5φ(B)^5 has order greater than 5, excluding containment in T, O, or I.Source: B Density of the Fibonacci… · p. 19
- The induction uses the recursive block structure of the representation, with the bridge and decoupling lemmas to obtain density on the larger spaces.The proof identifies subspaces corresponding to lower-dimensional representations and uses generators that mix them.Source: B Density of the Fibonacci… · pp. 18, 20
- The image of the braid group under ρ∗∗ is dense modulo phase in SU(fn−1), and the corresponding ρ∗p image is dense in SU(fn).The proof establishes these density claims for the respective invariant subspaces.Source: B Density of the Fibonacci… · pp. 20–21
C Fibonacci and Path Model Representations
The path model representation at k = 5 corresponds to the Fibonacci representation up to a sign. The sign difference comes from a choice of fourth root and is compensated in the Jones-polynomial factor.
C Fibonacci and Path Model Representations
- For any braid group Bn and root of unity ei2π/k, the path model represents braids as linear operators on formal combinations of n-step ladder paths.The paths start on the bottom rung of a ladder of height k − 1.Source: C Fibonacci and Path Model… · p. 21
- At k = 5, allowed paths correspond bijectively to length n + 1 strings of p and ∗ that start with ∗ and have no adjacent ∗ symbols.The ladder rungs are labeled from top to bottom as ∗, p, p, ∗.Source: C Fibonacci and Path Model… · p. 21
- The k = 5 path model representation equals the paper’s −1 times Fibonacci representation; the sign difference is compensated by (−A)3·writhe.The sign difference results from the different fourth root of t chosen for A in [3].Source: C Fibonacci and Path Model… · p. 21
D Unitaries on Logarithmically Many Strands
The construction approximates arbitrary paired unitaries in Fibonacci-representation subspaces with braids whose crossing counts are polynomial in the number of symbols and log inverse precision. Its recursive step builds general unitaries from a constant number of operations on large subspaces.
D Unitaries on Logarithmically Many Strands
- For k = O(log n), a braid with poly(n, log(1/ǫ)) crossings approximates any specified pair of unitaries in SU(fk+1) and SU(fk) to error ǫ.The proposition also holds symmetrically for ρp∗ rather than ρ∗p.Source: D Unitaries on Logarithmically Many… · p. 21
- At each recursive step, the construction can act on a subspace that is a constant fraction—about 0.62 for large n—of the full fn-dimensional space.The proportion exceeds one half, which the construction uses to assemble arbitrary unitaries from a constant number of steps.Source: D Unitaries on Logarithmically Many… · p. 25
- Any m × m unitary with m divisible by 4 is a product of seven unitaries, each acting on only m/2 basis states.The construction groups two-level row operations so previously eliminated entries remain zero.Source: D Unitaries on Logarithmically Many… · p. 25
- The recursive construction uses a constant number of lower-level and current-level operators, so braids for logarithmically many symbols have polynomially many crossings.Polynomially small base-case precision suffices for polynomial final precision through error propagation.Source: D Unitaries on Logarithmically Many… · p. 27
E Zeckendorf Representation
The appendix defines a Fibonacci-weighted encoding of strings with no adjacent ∗ symbols and proves that the encoding is bijective onto a consecutive range of integers.
E Zeckendorf Representation
- The map z encodes each length-n string by treating ∗ as 1 and p as 0, then summing its symbols weighted by Fibonacci numbers.The passage gives z(s) = sum from i=1 to n of s_i f_(i+1).Source: E Zeckendorf Representation · p. 27
- The induction establishes the bijection by separating strings according to whether they start with p or ∗, which maps them to disjoint consecutive integer ranges.Strings starting with p map to 0 through f_(n+1)−1; those starting with ∗ map to f_(n+1) through f_(n+2)−1.Source: E Zeckendorf Representation · pp. 27–28
- For every n, z maps the allowed strings bijectively to the integers from 0 through f_(n+2)−1.The proof states this range explicitly when combining the two cases for the first symbol.Source: E Zeckendorf Representation · pp. 27–28