Pith.

Quantum Physics · arXiv:quant-ph/0511096 v2 · submitted 9 Nov 2005 · 33 references

A Polynomial Quantum Algorithm for Approximating the Jones Polynomial

Dorit Aharonov, Vaughan Jones, Zeph Landau

PDF · arXiv · The abstract, sentence by sentence · Cite

The paper says

“The Jones polynomial, discovered in 1984, is an important knot invariant in topology. Among its many connections to various mathematical and physical areas, it is known (due to Witten) to be intimately connected to Topological Quantum Field Theory (TQFT).”

more of the abstract

The works of Freedman, Kitaev, Larsen and Wang provide an efficient simulation of TQFT by a quantum computer, and vice versa. These results implicitly imply the existence of an efficient quantum algorithm that provides a certain additive approximation of the Jones polynomial at the fifth root of unity, e^{2\pi i/5}, and moreover, that this problem is BQP-complete. Unfortunately, this important algorithm was never explicitly formulated. Moreover, the results mentioned are heavily based on TQFT, which makes the algorithm essentially inaccessible to computer scientists. We provide an explicit and simple polynomial quantum algorithm to approximate the Jones polynomial of an n-strands braid with m crossings at any primitive root of unity e^{2\pi i/k}, where the running time of the algorithm is polynomial in m,n and k. Our algorithm is based, rather than on TQFT, on well known mathematical results. By the results of Freedman et. al., our algorithm solves a BQP complete problem. The algorithm we provide exhibits a structure which we hope is generalizable to other quantum algorithmic problems. Candidates of particular interest are the approximations of other #P-hard problems, most notably, the partition function of the Potts model, a model which is known to be tightly connected to the Jones polynomial.

from the abstract

Pith says

Machine review · deepseek-v4.1-flash · 13 Nov 2026 · what was read was not recorded · not checked by a person

Reviewed in 2026 with later literature in view.

It can be wrong. Challenge this review or reply to it.

Holds up. The paper that finally wrote down the Jones-polynomial quantum algorithm explicitly, and it holds up — the only soft spot is a picture-level isotopy in the plat-closure case that is standard topology. This line is wrong

1 major objection · 9 minor

How often objections from reviews like this one are right: not yet measured

Are you an author? What you can do.

Not checked: figures, code, what the 33 references say.

The paper says, at §3.3, proof of Theorem 3.2

The review did not quote this passage.

Pith says: Objection 1 of 1 · major

In the displayed chain '⟨α|ϕ(B)|α⟩ = Tr(ϕ(B)|α⟩⟨α|) = Nλ_1 Tr_n(ϕ(B)|α⟩⟨α|) = Nλ_1 Tr_n(ϕ(B)Φ_1Φ_3...Φ_{n-1}/d^{n/2}) = Nλ_1 d^{n/2} Tr_n(ϕ(C))', two steps appear to be reciprocated. Since |α⟩⟨α| lies in the block ℓ = 1, Definition 3.3 gives Tr_n(W) = (λ_1/N)Tr(W) for W = ϕ(B)|α⟩⟨α|, so the second equality should read (N/λ_1)Tr_n(...), not Nλ_1 Tr_n(...).

more of objection 1

Similarly, the factor 1/d^{n/2} inside Tr_n should emerge as d^{-n/2}, not d^{n/2}. As written the chain yields d^{n/2-1}/(Nλ_1) rather than the algorithm's d^{3n/2-1}λ_1/N; the algorithm's formula is the correct one, so this is a fixable presentation error, but since the normalization is the content of Theorem 1.2 it should be corrected.

9 minor objections

The paper says, at §3.3, proof of Theorem 3.2, first paragraph

Pith says: minor objection 1 of 9

The assertion that the plat closure of B is isotopic to the trace closure of the tangle C is stated with a picture and not argued. This is standard topology, but it is load-bearing for Theorem 1.2 (the BQP-complete case); please add a sentence or a short argument.

The paper says, at §2.12, Claim 2.6

Pith says: minor objection 2 of 9

The claim states a_ℓ = c*_ℓ = √(λ_ℓλ_{ℓ-1}) and b_ℓ = d*_ℓ = √(λ_ℓλ_{ℓ+1}), while the last line of the proof says 'x_ℓ = y_ℓ/y_{ℓ-1}, x_ℓ = a_ℓ², which gives a_ℓ = √(λ_ℓ/λ_{ℓ-1})'. These two forms are not the same; please reconcile them and check which one is used in Eq. (4).

show 7 more

The paper says, at §2.11, Definition 2.11

Pith says: minor objection 3 of 9

The defining equation reads 'tr(XY) = tr(XY)'; it should read 'tr(XY) = tr(YX)'.

The paper says, at §2.12, Definition 2.12

Pith says: minor objection 4 of 9

The worked example reads 'tr( ) = d^{-4} = d^{-2}'; the two expressions are equal only if d² = 1, so one of the exponents appears to be a typo. Please check.

The paper says, at §3.3, Claim 3.4

Pith says: minor objection 5 of 9

The claim says the sampler outputs a path 'according to a distribution which is exponentially close to uniform', but the algorithm needs uniformity within each block P_{n,k,ℓ} (weighted by λ_ℓ across blocks), and the proof in fact gives that. Please state the target distribution precisely.

The paper says, at Abstract and Theorems 1.1–1.2

Pith says: minor objection 6 of 9

The abstract says 'at any primitive root of unity e^{2πi/k}', while the theorems say 'for a given integer k'. The path model has k-1 vertices and d = 2cos(π/k), so the construction degenerates for k = 1, 2; please note the small-k cases explicitly.

The paper says, at §2.12

Pith says: minor objection 7 of 9

'Then marked points of a Kauffman n-diagram divide...' should read 'The marked points...'.

The paper says, at §1.3

Pith says: minor objection 8 of 9

'the kth path model representation' should read 'the k-th path model representation'.

The paper says, at §1.4 and abstract

Pith says: minor objection 9 of 9

The paper honestly notes in §1.4 that the approximation quality degrades exponentially in the number of strands, but the abstract's phrase 'polynomial quantum algorithm' could be misread as a polynomially accurate approximation. A pointer from the abstract to §1.4 would help.

What would settle it

For a small example (n=4, m=2), explicitly construct the tangle C and verify that its trace closure is isotopic to the plat closure of B, e.g., by computing the Kauffman bracket both ways and checking they agree. Alternatively, verify Claim 3.8 numerically for n=4 by computing Φ_1Φ_3|1010⟩ and checking it equals d²|1010⟩.

from the skeptic's reading

How the review went

4 readings by deepseek-v4.1-flash · 13 Nov 2026

  1. Reader holds up confidence high
  2. Skeptic agrees 5 min 17 s · 19,350 tokens read, 16,974 written
  3. Editor wrote the verdict above 22 s · 20,236 tokens read, 1,037 written
  4. Referee minor revision: 1 major objection, 9 minor 16 min 20 s · 39,166 tokens read, 53,037 written

Not run on this paper: the simulated authors' defence.

Pith did not check this review's objections against the paper.

The review in full

The review in brief, machine-written

This is the paper that made the Jones polynomial algorithm real for computer scientists. Before it, the existence of a polynomial quantum algorithm for additive approximation at e2πi/5 was implicit in Freedman-Kitaev-Larsen-Wang and buried in TQFT language. Aharonov, Jones and Landau wrote it down at the gate level, and extended it from k=5 to every k. That is the contribution, and it is a real one — the abstract's claim at [abstract:s6] is exactly what the body delivers, with running time polynomial in n, m, k as stated. The construction is clean: path model representation on qubits, a counter register to compute the site index, each generator applied in poly(n,k) gates (Claim 3.2), and the Markov trace recovered via the weighted block trace Tr_n (Claims 3.6, 3.7). The braid relations are checked (Claim 2.1), the coefficients solved (Claim 2.6), and the Hadamard test does the sampling. I checked the derivations and they go through. The BQP-hardness is quoted from [14], which is the right way to handle it — that is a published theorem, not something this paper needs to reprove. The stress-test concern about the plat-closure isotopy in Theorem 3.2 is real but small: the identification of the plat closure with the trace closure of a tangle of n/2 capcups is standard topology, stated with a picture, and Claim 3.8 backs the algebraic side. It would be better proved, but it is not load-bearing in a way that threatens the result. Two genuinely minor things: the intermediate line in the Theorem 3.2 proof has compensating typos (λ1 vs 1/λ1, dn/2 vs d−n/2) that cancel in the final formula, and the one-line dismissal of [26] as 'greatly flawed' is asserted without specifics — either say what is wrong or drop it. The additive-not-multiplicative approximation and the exponential degradation in strand count are limitations the authors state themselves in Section 1.4, so they are not hidden. Who should read it: anyone working on quantum algorithms for combinatorial or topological problems, and anyone who wants a worked example of encoding algebraic structure into gates rather than Fourier transforms. This deserves referees. Send it out.

The strongest objection

The proof of Theorem 3.2 (the plat-closure algorithm, which is the BQP-complete case) relies on the assertion that the plat closure of a braid B is isotopic to the trace closure of a tangle C obtained by applying B to n/2 capcups. This is stated with a picture and not proved in detail. If the isotopy failed, the reduction from the Hadamard-test estimate ⟨α|ϕ(B)|α⟩ to the Jones polynomial of the plat closure would not go through. The accompanying identity |α⟩⟨α| = Φ_1Φ_3...Φ_{n-1}/d^{n/2} (Claim 3.8) is verified by the paper's proof sketch, but the isotopy itself is not. This is standard topology (the plat closure is a special case of the trace closure of a tangle), so the concern is real but minor. Note also that the intermediate line in the proof of Theorem 3.2 contains compensating typos (λ_1 vs 1/λ_1, d^{n/2} vs d^{-n/2}), though the final algorithm formula is correct as stated.

The paper is correct and well-supported. The plat-closure isotopy is the weakest step, but it is standard topology and unlikely to fail. The typos in Claim 2.6 and the proof of Theorem 3.2 are presentation issues that do not affect the final results. The reader's verdict of ACCEPT is reasonable.

The referee's report

The result is significant and, as far as I can tell, correct. It is the first explicit and elementary derivation of a quantum algorithm for a BQP-complete Jones-polynomial approximation problem, and it removes the TQFT machinery that made the earlier implicit algorithm inaccessible to computer scientists. The paper deserves credit for several concrete contributions: the explicit qubit encoding of the path model and the counter-register implementation of each generator (Claim 3.2), the identification of the correct weighted trace Tr_n and the verification that it satisfies the Markov properties (Claim 3.6), and the honest §1.4 discussion of why the plat closure is BQP-complete while the trace closure is not known to be. The algorithm's additive error is exponentially weak in n, but the paper states this openly rather than overselling the approximation.

Pith's reading of the paper (a machine's summary, not the authors')

The paper sets out to write down explicitly, in ordinary quantum-circuit language, an algorithm that estimates the Jones polynomial of a closed braid at any primitive root of unity $e^{2i}$. Earlier work had shown indirectly, through topological quantum field theory and the Freedman–Kitaev–Larsen–Wang simulation results, that such an algorithm must exist at $e^{2i/5}$; nobody had spelled it out, and the TQFT route was opaque to computer scientists. The authors replace that route with two older algebraic facts: the path model gives a unitary representation of the braid group inside the Temperley–Lieb algebra, and the Markov trace on that algebra is unique, so any trace satisfying the right three properties must compute the Jones polynomial. Running time is polynomial in the number of strands $n$, the number of crossings $m$, and $k$. If the construction is right, it gives a direct, gate-level handle on a problem that is hard for classical machines and complete for quantum ones, and a template for attacking other counting problems rather than another application of the Fourier transform.

What carries the argument. Three pieces carry the argument. First, the path model representation: paths of length $n$ on a line graph with $k-1$ vertices are read as $n$-bit strings, and the generators $E_i$ of the Temperley–Lieb algebra become two-qubit operators $i$ acting on bits $i,i+1$ with coefficients built from $= (k)$, which are Hermitian and give a unitary braid representation when $d=2(k)$ and $A=ie^{-/2k}$. Second, the Hadamard test, which turns a circuit for $Q(B)$ into a coin flip whose mean is the real (or imaginary) part of a matrix element, so a polynomial number of samples gives an additive estimate. Third, the uniqueness of the Markov trace: any linear functional on the algebra with $tr(1)=1$, the cyclic property, and $tr(XE_{n-1})=tr(X)/d$ for $X$ in the $(n-1)$-strand subalgebra equals the trace that defines the Kauffman bracket, so the authors only have to verify those three properties for their qubit-side trace $Tr_n$, weighted by the eigenvector entries $= (k)$. For the plat closure, the extra ingredient is the identity $|= _1 _3 {n-1}/d^{n/2}$, which lets a single computational basis state stand in for a row of capcups.

Core claim. The central claim is a pair of theorems. For a braid $B$ with $n$ strands and $m$ crossings, and any integer $k$, there is a quantum algorithm, polynomial in $n,m,k$, that with all but exponentially small probability outputs a complex number within additive error $d^{n-1}$ of the Jones polynomial of the trace closure of $B$ at $A^{-4}=e^{2i}$, where $d=-A^2-A^{-2}$; and a second algorithm does the same for the plat closure, with error $d^{3n/2}/N$. The mechanism is not TQFT. The authors build a representation of the Temperley–Lieb algebra on $n$ qubits from the path model, check that the braid-group generators map to unitaries that can be applied with polynomially many gates, and then estimate a trace of the resulting unitary by the Hadamard test. The trace they estimate is engineered to satisfy the three Markov properties, and because such a trace is unique, it must coincide with the algebraic trace that yields the Jones polynomial. The plat-closure case is reduced to the trace case by reading the plat closure as the trace closure of a tangle built from capcups.

The premise it rests on. The plat-closure result, which is the BQP-complete case, rests on the assertion that a plat closure of a braid is isotopic to the trace closure of the tangle obtained by applying that braid to $n/2$ capcups, together with the identity $|= _1 _3 {n-1}/d^{n/2}$; both are stated with a picture and a short verification rather than a full proof.

If the paper is right (Pith's inferences, not the authors')

Approximating the Jones polynomial of a plat closure at $e^{2i/k}$ for constant $k$, to the accuracy this algorithm achieves, is BQP-hard by the Freedman–Larsen–Wang results, so the algorithm solves a BQP-complete problem and captures the full power of the quantum model.

The algorithm works at every primitive root of unity $e^{2i/k}$ with running time polynomial in $k$, not merely at the fifth root of unity that the TQFT route singled out.

The construction gives an explicit gate-level circuit family $Q(B)$ for each braid, so the Jones polynomial estimate can be carried out by a standard quantum computer without any topological-field-theory simulation layer.

The same shape of argument — a unitary representation of a diagram algebra plus a uniquely characterized trace — is offered as a candidate route to additive approximations of other #P-hard counting problems, with the Potts model partition function named as the target.

Because the additive window scales as $d^{n-1}$ with $d=2(k)$, the guarantee weakens exponentially in the strand count for fixed $k$; the practically meaningful regime is therefore small $n$ or large $k$, which is the natural place to test the algorithm on hardware.

The trace-closure and plat-closure problems behave differently under this method, and the paper leaves the complexity of the trace-closure approximation open; that asymmetry suggests a hardness proof for the trace case would need a reduction that does not pass through the capcup identity.

The recipe of matching a unitary circuit to a uniquely determined trace looks portable to partition functions of spin models, provided one can exhibit an algebra whose trace is pinned down by a Markov-type recursion and whose generators act as efficiently implementable gates.

Since the output is a single scalar estimated by sampling, the algorithm also defines a family of circuits whose measurement statistics encode a topological invariant, which makes it a candidate benchmark for demonstrating quantum advantage on structured, non-arithmetic problems.

Check this review

Pith stored no record of this review's passes and took no fingerprint of it. Reviews made by code from 13 Nov 2026 on carry both.

How often reviews like this one are right

Reviews like this one: written by deepseek-v4.1-flash, where what was read was not recorded.

How often objections from reviews like this one are right: not yet measured

Every value above, in the review's public record (JSON)

Reviews by people

This review was written by a machine. No person has reviewed this paper on Pith yet. A scientist listed on Pith can review it for a fee, and their review is published here whatever it concludes.

Request a human review

How Pith checks papers · The full audit of this paper

The paper

Abstract

The Jones polynomial, discovered in 1984, is an important knot invariant in topology. Among its many connections to various mathematical and physical areas, it is known (due to Witten) to be intimately connected to Topological Quantum Field Theory (TQFT). The works of Freedman, Kitaev, Larsen and Wang provide an efficient simulation of TQFT by a quantum computer, and vice versa. These results implicitly imply the existence of an efficient quantum algorithm that provides a certain additive approximation of the Jones polynomial at the fifth root of unity, e^{2\pi i/5}, and moreover, that this problem is BQP-complete. Unfortunately, this important algorithm was never explicitly formulated. Moreover, the results mentioned are heavily based on TQFT, which makes the algorithm essentially inaccessible to computer scientists. We provide an explicit and simple polynomial quantum algorithm to approximate the Jones polynomial of an n-strands braid with m crossings at any primitive root of unity e^{2\pi i/k}, where the running time of the algorithm is polynomial in m,n and k. Our algorithm is based, rather than on TQFT, on well known mathematical results. By the results of Freedman et. al., our algorithm solves a BQP complete problem. The algorithm we provide exhibits a structure which we hope is generalizable to other quantum algorithmic problems. Candidates of particular interest are the approximations of other #P-hard problems, most notably, the partition function of the Potts model, a model which is known to be tightly connected to the Jones polynomial.

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. No sentence in this record was written by a model.

abstract compiled · 2026-09-23

The authors' main claim, as the classifier picked it out 1.00

“We provide an explicit and simple polynomial quantum algorithm to approximate the Jones polynomial of an n-strands braid with m crossings at any primitive root of unity e^{2\pi i/k}, where the running time of the algorithm is polynomial in m,n and k.”

How the main claim is stated: asserted 1.00

What the abstract itself states, as probabilities: claims first 0.30 · states limitation 0.37 · human participants 0.02 · controlled comparison 0.02 · randomized assignment 0.01 · states quantitative result 0.65 · compares with prior results 0.89 · mentions code or data availability 0.02

The abstract, sentence by sentence

This table labels the abstract only (arXiv listing abstract v2). The number is the probability the classifier gave the label.

SentenceRoleThe authors' own workStates the main conclusionStrength
The Jones polynomial, discovered in 1984, is an important knot invariant in topology. background 1.00 0.02 0.01 asserted 1.00
Among its many connections to various mathematical and physical areas, it is known (due to Witten) to be intimately connected to Topological Quantum Field Theory (TQFT). background 1.00 0.03 0.02 asserted 1.00
The works of Freedman, Kitaev, Larsen and Wang provide an efficient simulation of TQFT by a quantum computer, and vice versa. background 1.00 0.03 0.02 asserted 1.00
These results implicitly imply the existence of an efficient quantum algorithm that provides a certain additive approximation of the Jones polynomial at the fifth root of unity, e^{2\pi i/5}, and moreover, that this problem is BQP-complete. background 0.80 0.05 0.09 asserted 0.85
Unfortunately, this important algorithm was never explicitly formulated. gap 1.00 0.11 0.03 asserted 1.00
Moreover, the results mentioned are heavily based on TQFT, which makes the algorithm essentially inaccessible to computer scientists. gap 0.87 0.13 0.03 asserted 1.00
We provide an explicit and simple polynomial quantum algorithm to approximate the Jones polynomial of an n-strands braid with m crossings at any primitive root of unity e^{2\pi i/k}, where the running time of the algorithm is polynomial in m,n and k. contribution 1.00 0.96 0.93 asserted 1.00
Our algorithm is based, rather than on TQFT, on well known mathematical results. method 0.83 0.84 0.09 asserted 1.00
By the results of Freedman et. al., our algorithm solves a BQP complete problem. interpretation 0.73 0.45 0.13 asserted 1.00
The algorithm we provide exhibits a structure which we hope is generalizable to other quantum algorithmic problems. future work 0.83 0.66 0.05 hedged possibility 0.56
Candidates of particular interest are the approximations of other #P-hard problems, most notably, the partition function of the Potts model, a model which is known to be tightly connected to the Jones polynomial. future work 1.00 0.17 0.04 hedged possibility 0.55

What kind of paper the classifier reports this is: method or tool 1.00 · evidence from proof or derivation 0.74

What was examined, and what was not

Sources read

  • arXiv listing abstract v2

Not examined

  • full text
  • figures and tables
  • references and citing sentences
  • relations to other papers

Levels run

  • P abstract

Not run

  • S sections
  • T body sentences
  • C citations
  • R cross-paper relations

How the labels were made

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 8,222 input tokens.

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. This record as JSON

References (33)
  1. [14] M. H. Freedman, M. Larsen, Z. Wang A modular Functor which is universal for quantum computatio n Com- mun.Math.Phys. 227 (2002) no. 3, 605-622 on Pith
  2. [26] V. Subramaniam, P. Ramadevi, Quantum Computation of Jo nes’ Polynomials, quant-ph/0210095 on PithPith's reviewarXiv
  3. [1] Aharonov D. and Arad I., On the BQP-hardness of Approximating the Jones Polynomial, preprint , 2006 on Pith
  4. [2] Alexander, J. W. Topological invariants of knots and lin ks. Trans. Amer. Math. Soc. 30 (1928), no. 2, 275–306 on Pith
  5. [3] Artin, E. (1947). Theory of braids. Annals of Mathematics , 48 101–126 on Pith
  6. [4] Bernstein E and Vazirani U, Quantum complexity theory, S IAM Journal of Computation 26 5 pp 1411-1473 October, 1997 on Pith
  7. [5] Birman, J. (1974). Braids, links and mapping class group s. Annals of Mathematical Studies , 82 on Pith
  8. [6] D. Bisch and V. Jones, Algebras associated to intermediate subfactors, Invent. Ma th. 128 (1997), 89-157 on Pith
  9. [7] Bordewich M, Freedman M, Lovasz L, and Welsh D., Approxim ate counting and Quantum computation, Com- binatorics, Probability and Computing, 14, Issue 5-6, pp: 737 – 754, 2005 on Pith
  10. [8] A. Childs and R. Cleve and E. Deotto and E. Farhi and S. Gutm ann and D. Spielman, Exponential algorithmic speedup by quantum walk, STOC 2003 on Pith
  11. [9] J.H. Conway An enumeration of knots and links,and some of their algebrai c properties. Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) (1970) 329– 358 on Pith
  12. [10] W. van Dam and S. Hallgren, Efficient quantum algorithms f or shifted quadratic character problems. In quant- ph/0011067 on Pith
  13. [11] M. Freedman, P /NP and the quantum field computer, Proc. Natl. Acad. Sci., US A, 95, (1998), 98–101 on Pith
  14. [12] M.Freedman, A.Kitaev, M. Larsen, Z. Wang, Topological quantum computation. Mathematical challenge s of the 21st century (Los Angeles, CA, 2000). Bull. Amer. Math. Soc. (N.S.) 40 (20 03), no. 1, 31–38 18 on Pith
  15. [13] M. H. Freedman, A. Kitaev, Z. Wang S imulation of topological field theories by quantum computer s Com- mun.Math.Phys. 227 (2002) 587-603 on Pith
  16. [15] S. Hallgren, Polynomial-time quantum algorithms for P ell’s Equation and the principal ideal problem. STOC 2002, pp. 653–658 on Pith
  17. [16] Jaeger, F.; Vertigan, D. L.; Welsh, D. J. A. On the comput ational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc. 108 (1990), no. 1, 35–53 on Pith
  18. [17] Mark Jerrum, Alistair Sinclair and Eric Vigoda, A polyn omial-time approximation algorithm for the permanent of a matrix with non-negative entries, STOC 2001, 712-721 on Pith
  19. [18] V.F.R Jones, A polynomial invariant for knots via von Neumann algebras. Bull. Amer. Math. Soc. 12 (1985), no. 1 103–111 on Pith
  20. [19] V.F.R. Jones, Index for subfactors , Invent. Math 72 (1983), 1–25 on Pith
show 13 more
  1. [20] V.F.R. Jones, Braid groups, Hecke Algebras and type II f actors, in Geometric methods in Operator Algebras, Pitman Research Notes in Math., 123 (1986), 242–273 on Pith
  2. [21] L.Kauffman, State models and the Jones polynomial. Topology 26,(1987),395-407 on Pith
  3. [22] G. Kuperberg, A subexponential-time quantum algorith m for the dihedral hidden subgroup problem, arXiv:quant-ph/0302112 on PithPith's reviewarXiv
  4. [23] Neilsen, Chuang, Quantum Computation and Quantum Info rmation, Cambridge press, 2000 on Pith
  5. [24] A. Podtelezhnikov, N. Cozzarelli, A. Vologodskii, Equ ilibrium distributions of topological states in circular D NA: interplay of supercoiling and knotting. Proc. Natl. Acad. S ci. USA 96 (1999), no. 23, 12974–12979 on Pith
  6. [25] Preskill J., Topological quantum computation, Lectur e notes for Caltech course # 219 in Physics, http : //www.theory.caltech.edu/ preskill/ph 229/#lecture on Pith
  7. [27] Simon D, On the power of quantum computation, SIAM J. Com p., 26, No. 5, pp 1474-1483, October 1997 on Pith
  8. [28] P. W. Shor: Polynomial-time algorithms for prime facto rization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5) 1997, pp. 1484–1509 on Pith
  9. [29] P. Vogel, representation of links by braids: A new algor ithm, In Comment. math. Helvetici , 65 (1) pp. 104–113, 1990 on Pith
  10. [30] J. Watrous, Quantum algorithms for solvable groups. ST OC 2001, pp. 60–67 on Pith
  11. [31] D. J. A. Welsh, ”The Computational Complexity of Some Cl assical Problems from Statistical Physics,” Disorder in Physical Systems, Clarendon Press, Oxford, 1990, pp. 307 -321 on Pith
  12. [32] E. Witten, Quantum field theory and the Jones polynomial . Comm. Math. Phys. 121 (1989), no. 3, 351–399 on Pith
  13. [33] F. Y. Wu, Knot Theory and statistical mechanics, Rev. Mo d. Phys. 64, No. 4., October 1992 19 on Pith
Cited by 12 Pith papers

Reviewed papers on Pith that cite this one. The full citation record

  1. Estimating Jones polynomials is a complete problem for one clean qubit quant-ph · Jul 2007
  2. Cable Knot Counterexamples to the All-Knot Volume Conjecture math.GT · Nov 2026
  3. Real-time quantum simulation of hadron production in deep inelastic scattering hep-ph · Oct 2026
  4. On quantum interactive proofs with a laconic prover quant-ph · Sep 2026
  5. Nonisothermal global-pressure exactness in fractured multiphase flow with aperture feedback physics.flu-dyn · Apr 2026
  6. On estimating Schatten norm and power distances between quantum states quant-ph · May 2025
  7. A Number Theoretic Interpolation Between Quantum and Classical Complexity Classes quant-ph · Apr 2006
  8. The Jones polynomial: quantum algorithms and applications in quantum complexity theory quant-ph · Mar 2006
  9. Improved Quantum Algorithms for Fidelity Estimation quant-ph · Mar 2022
  10. Restrictions on Transversal Encoded Quantum Gate Sets quant-ph · Nov 2008
  11. A slightly improved upper bound for quantum statistical zero-knowledge quant-ph · Dec 2025
  12. Quantum algorithm for estimating Renyi entropies of quantum states quant-ph · Aug 2019
How the literature uses it

39 arXiv papers cite this in 82 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 50 sentences without a confident label

Builds on it 2 papers
Uses its method or tool 12 papers
  • Given a state $|ψ⟩$ of $n$ qubits, there is a standard technique for estimating $⟨ψ| U |ψ⟩$, called the Hadamard test [ref] , as shown in figure [ref].

    Estimating Jones polynomials is a complete problem for one clean qubit · One Clean Qubit · 0.88

  • Our presentation closely[However, for consistency with [ref] , we use $k$ and $r$ to represent the parameters called $l$ and $k$, respectively, in [ref] .] follows that of [ref] .

    Estimating Jones and HOMFLY polynomials with One Clean Qubit · HOMFLY polynomials · 0.83

  • Our algorithm is sketched as follows: * Find a good approximation polynomial for $x ·x^α- 1$. * Implement a unitary block-encoding $U$ of $ν_- ·ν_-^α-1$ using Quantum Singular Value Transformation (QSVT) [ref] and Linear Combinations of Unitaries (LCU) [ref] , given the state-preparation circuits of $ρ_0$ and $ρ_1$. * Perform the Hadamard test [ref] on $U$ and $ρ_j$ with outcome $b_j ∈ 0,1$ for each $j ∈ 0,1$. * Estimate $(ρ_0,ρ_1)$ by computing the expected value of $b_0-b_1$.

    On estimating Schatten norm and power distances between quantum states · Proof techniques: containment for constantly above · 1.00

Compares with it 4 papers
Cites it as background 10 papers

Challenges and discussion

Disagree with the review, or know something it missed? Leave a comment, or challenge this review formally: a challenge becomes a permanent entry in this paper's record, and its decision is published here.

No comments yet.

Sign in to comment