REVIEW 6 cited by
A Polynomial Quantum Algorithm for Approximating the Jones Polynomial
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
A Polynomial Quantum Algorithm for Approximating the Jones Polynomial
read the original 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.
Forward citations
Cited by 6 Pith papers
-
Hierarchical entanglement transitions and hidden area-law sectors in quantum many-body dynamics
Local quenches in chaotic quantum systems produce a Renyi-index-tuned hierarchy of entanglement transitions, with S_alpha>1 obeying area law while S_alpha<=1 is volume-law, carried by an O(1)-dimensional dominant Schm...
-
Constrained Optimal Polynomials for Quantum Linear System Solvers
Constrained Uniform Polynomial (CUP) and Constrained Adaptive Polynomial (CAP) solvers achieve lower error than standard QSVT and Chebyshev methods in noise-limited regimes by optimizing accuracy versus block-encoding...
-
Nonisothermal global-pressure exactness in fractured multiphase flow with aperture feedback
A new mixed saturation-temperature compatibility condition is derived for exact global-pressure equivalence in nonisothermal multiphase fractured flow, with numerical benchmarks confirming regimes where exactness hold...
-
Nonisothermal global-pressure exactness in fractured multiphase flow with aperture feedback
Constrained optimal polynomials (CUP and CAP) reduce quantum linear system solver errors under noise by jointly optimizing approximation accuracy and block-encoding normalization, outperforming standard QSVT and Cheby...
-
Lower overhead fault-tolerant building blocks for noisy quantum computers
New combinatorial proofs and circuit designs for quantum error correction reduce physical qubit overhead by up to 10x and time overhead by 2-6x for codes including Steane, Golay, and surface codes.
-
A slightly improved upper bound for quantum statistical zero-knowledge
QSZK and its non-interactive variant NIQSZK stay inside QIP(2)∩co-QIP(2), now with an honest prover that runs in quantum linear space and single-exponential time.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.