- #1
- 24,775
- 792
http://arxiv.org/abs/quant-ph/0511096
A Polynomial Quantum Algorithm for Approximating the Jones Polynomial
Dorit Aharonov, Vaughan Jones, Zeph Landau
26 pages
"The Jones polynmial, discovered in 1984, is an important knot invariant in topology, which is 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, and moreover, that this problem is BQP-complete. Unfortunately, this important algorithm was never explicitly formulated. Moreover, the results of Freedman et. al are heavily based on deep knowledge of TQFT, which makes the algorithm essentially inaccessible for computer scientists.
We provide an explicit and simple polynomial algorithm to approximate the Jones polynomial of an n strands braid with m crossings at the primitive k'th root of unity, for any k, where the running time of the algorithm is polynomial in m,n and k. Our algorithm does not use TQFT at all. 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. A candidate of particular interest is the approximation of the partition function of the Potts model."
John Baez is inviting grad students to join him at UC Riverside for research in QUANTUM MATHEMATICS, remarks Peter Woit
in some approaches to Quantum Gravity the quantum states of the gravitational field are knots---just an idle thought. does gravity, in other words quantum spacetime geometry, connect to this at all?
A Polynomial Quantum Algorithm for Approximating the Jones Polynomial
Dorit Aharonov, Vaughan Jones, Zeph Landau
26 pages
"The Jones polynmial, discovered in 1984, is an important knot invariant in topology, which is 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, and moreover, that this problem is BQP-complete. Unfortunately, this important algorithm was never explicitly formulated. Moreover, the results of Freedman et. al are heavily based on deep knowledge of TQFT, which makes the algorithm essentially inaccessible for computer scientists.
We provide an explicit and simple polynomial algorithm to approximate the Jones polynomial of an n strands braid with m crossings at the primitive k'th root of unity, for any k, where the running time of the algorithm is polynomial in m,n and k. Our algorithm does not use TQFT at all. 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. A candidate of particular interest is the approximation of the partition function of the Potts model."
John Baez is inviting grad students to join him at UC Riverside for research in QUANTUM MATHEMATICS, remarks Peter Woit
in some approaches to Quantum Gravity the quantum states of the gravitational field are knots---just an idle thought. does gravity, in other words quantum spacetime geometry, connect to this at all?
Last edited: