# A Polynomial Quantum Algorithm for Approximating the Jones Polynomial

@article{Aharonov2008APQ, title={A Polynomial Quantum Algorithm for Approximating the Jones Polynomial}, author={Dorit Aharonov and Vaughan F. R. Jones and Zeph Landau}, journal={Algorithmica}, year={2008}, volume={55}, pages={395-421} }

AbstractThe 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 (
${\sf{TQFT}}$
). The works of Freedman, Kitaev, Larsen and Wang provide an efficient simulation of
${\sf{TQFT}}$
by a quantum computer, and vice versa. These results implicitly imply the existence of an efficient (namely, polynomial… Expand

#### Topics from this paper

#### Paper Mentions

#### 174 Citations

Efficient quantum circuits for approximating the Jones polynomial

- Computer Science, Mathematics
- Quantum Inf. Comput.
- 2008

A new method is proposed for implementing the AJL algorithm, which improves the performance from O (mnlog2 k) to O(mn), where n is the number of strands, m is thenumber of the crossings in a braid and k is a large-degree polynomial. Expand

Quantum Algorithms Beyond the Jones Polynomial

- Mathematics
- 2007

The quantum algorithm of AJL [3] (following the work of Freedman et al. [10]) to approximate the Jones polynomial, is of a new type: rather than using the quantum Fourier transform, it encodes the… Expand

Eciently Computing the Jones Polynomial on a Quantum Computer

- Mathematics
- 2015

These lectures notes are based on the paper “A Polynomial Quantum Algorithm for Approximating the Jones Polynomial” published in 2008 by Dorit Aharanov, Vaughan Jones, and Zeph Landau. The aim of… Expand

The Jones polynomial: quantum algorithms and applications in quantum complexity theory

- Computer Science, Physics
- Quantum Inf. Comput.
- 2008

It is concluded with direct proofs that evaluating the Jones polynomial of the plat closure at most primitive roots of unity is a #P-hard problem, while learning its most significant bit is PP-hard, circumventing the usual route through the TuttePolynomial and graph coloring. Expand

Topological Quantum Information, Khovanov Homology and the Jones Polynomial

- Mathematics, Physics
- 2010

In this paper we give a quantum statistical interpretation for the bracket polynomial state sum and for the Jones polynomial. We use this quantum mechanical interpretation to give a new quantum… Expand

How Hard Is It to Approximate the Jones Polynomial?

- Mathematics, Computer Science
- Theory Comput.
- 2015

Any value-dependent approximation of the Jones polynomial at these non-lattice roots of unity is #P-hard, which follows fairly directly from the universality result and Aaronson's theorem that PostBQP = PP. Expand

Quantum algorithms for virtual Jones polynomials via Thistlethwaite theorems

- Mathematics, Engineering
- Defense + Commercial Sensing
- 2010

Recently a quantum algorithm for the Jones polynomial of virtual links was proposed by Kauffman and Dye via the implementation of the virtual braid group in anyonic topological quantum computation… Expand

Efficient quantum processing of 3-manifold topological invariants

- Computer Science, Physics
- 2007

All the significant quantities - partition functions and observables - of quantum CSW theory can be processed efficiently on a quantum computer, reflecting the intrinsic, field-theoretic solvability of such theory at finite k. Expand

Polynomial Quantum Algorithms for Additive approximations of the Potts model and other Points of the Tutte Plane

- Physics, Mathematics
- 2007

In the first 36 pages of this paper, we provide polynomial quantum algorithms for additive approximations of the Tutte polynomial, at any point in the Tutte plane, for any planar graph. This includes… Expand

Quantum automata, braid group and link polynomials

- Physics, Mathematics
- Quantum Inf. Comput.
- 2007

In this combinatorial framework, families of finite-states and discrete-time quantum automata capable of accepting the language generated by the braid group are implemented, whose transition amplitudes are colored Jones polynomials. Expand

#### References

SHOWING 1-10 OF 77 REFERENCES

The Jones polynomial: quantum algorithms and applications in quantum complexity theory

- Computer Science, Physics
- Quantum Inf. Comput.
- 2008

It is concluded with direct proofs that evaluating the Jones polynomial of the plat closure at most primitive roots of unity is a #P-hard problem, while learning its most significant bit is PP-hard, circumventing the usual route through the TuttePolynomial and graph coloring. Expand

P/NP, and the quantum field computer

- Computer Science, Medicine
- Proc. Natl. Acad. Sci. USA
- 1998

This work proposes that each physical theory supports computational models whose power is limited by the physical theory, and suggests that some physical system whose effective Lagrangian contains a non-Abelian topological term might be manipulated to serve as an analog computer capable of solving NP or even #P-hard problems in polynomial time. Expand

Quantum Computation of Jones' Polynomials

- Mathematics, Physics
- 2002

It is a challenging problem to construct an efficient quantum algorithm which can compute the Jones' polynomial for any knot or link obtained from platting or capping of a $2n$-strand braid. We… Expand

Polynomial Quantum Algorithms for Additive approximations of the Potts model and other Points of the Tutte Plane

- Physics, Mathematics
- 2007

In the first 36 pages of this paper, we provide polynomial quantum algorithms for additive approximations of the Tutte polynomial, at any point in the Tutte plane, for any planar graph. This includes… Expand

The BQP-hardness of approximating the Jones Polynomial

- Computer Science, Physics
- ArXiv
- 2006

The universality proof of Freedman et al (2002) is extended to ks that grow polynomially with the number of strands and crossings in the link, thus extending the BQP-hardness of Jones polynomial approximations to all values to which the AJL algorithm applies, proving that for all those values, the problems are B QP-complete. Expand

Estimating Jones polynomials is a complete problem for one clean qubit

- Computer Science, Physics
- Quantum Inf. Comput.
- 2008

It is shown 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. Expand

Quantum Complexity Theory

- Computer Science
- SIAM J. Comput.
- 1997

This paper gives the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis, and proves that bits of precision suffice to support a step computation. Expand

Topological Quantum Computation

- Mathematics, Physics
- 2001

The theory of quantum computation can be constructed from the abstract study of anyonic systems. In mathematical terms, these are unitary topological modular functors. They underlie the Jones poly-… Expand

Simulation of Topological Field Theories¶by Quantum Computers

- Physics, Mathematics
- 2002

Abstract: Quantum computers will work by evolving a high tensor power of a small (e.g. two) dimensional Hilbert space by local gates, which can be implemented by applying a local Hamiltonian H for a… Expand

Approximate Counting and Quantum Computation

- Computer Science, Mathematics
- Combinatorics, Probability and Computing
- 2005

A form of additive approximation which can be used to simulate a function in BQP is introduced and it is shown that all functions in the classes #P and GapP have such an approximation scheme under certain natural normalizations. Expand