The BQP-hardness of approximating the Jones Polynomial

Abstract

A celebrated important result due to Freedman, Larsen and Wang states that providing additive approximations of the Jones polynomial at the k'th root of unity, for constant k=5 and k>6, is BQP-hard. Together with the algorithmic results of Freedman et al and Aharonov et al, this gives perhaps the most natural BQP-complete problem known today and motivates further study of the topic. In this paper we focus on the universality proof; we extend the universality result of Freedman et al to k's 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 for which the AJL algorithm applies, proving that for all those values, the problems are BQP-complete. As a side benefit, we derive a fairly elementary proof of the Freedman et al density result, without referring to advanced results from Lie algebra representation theory, making this important result accessible to computer science audience. We make use of two general lemmas we prove, the Bridge lemma and the Decoupling lemma, which provide tools for establishing density of subgroups in SU(n). Those tools seem to be of independent interest in more general contexts of proving quantum universality. Our result also implies a completely classical statement, that the_multiplicative_ approximations of the Jones polynomial, at exactly the same values, are #P-hard, via a recent result due to Kuperberg. Since the first publication of those results in their preliminary form (arXiv:quant-ph/0605181v2), the methods we present here were used in several other contexts. This paper is an improved and extended version of the original results, and also includes discussions of the developments since then.

36 pages, 8 figures. A much improved and revised version, updated to Feb 2011, which includes discussions and implications of related results published after the original 2006 version of this paper

References in corpus (10)

• The BQP-hardness of approximating the Jones Polynomial
• Inapproximability of the Tutte polynomial
• How hard is it to approximate the Jones polynomial?
• Trading inverses for an irrep in the Solovay-Kitaev theorem
• Several natural BQP-Complete problems
• The Jones polynomial: quantum algorithms and applications in quantum complexity theory
• Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation
• On an implementation of the Solovay-Kitaev algorithm
• Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete
• A PromiseBQP-complete String Rewriting Problem

Cited by in corpus (25)

• Quantum algorithm for solving linear systems of equations
• Quantum algorithms for algebraic problems
• Verification of quantum computation: An overview of existing approaches
• The BQP-hardness of approximating the Jones Polynomial
• Interactive Proofs For Quantum Computations
• How hard is it to approximate the Jones polynomial?
• Trading inverses for an irrep in the Solovay-Kitaev theorem
• The quantum FFT can be classically simulated
• Quantum Computation Beyond the Circuit Model
• Quantum algorithms for classical lattice models
• A quantum algorithm for additive approximation of Ising partition functions
• BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs
• $q$ - Deformed Spin Networks, Knot Polynomials and Anyonic Topological Quantum Computation
• Quantum Fourier Transforms and the Complexity of Link Invariants for Quantum Doubles of Finite Groups
• Quantizing Knots and Beyond
• Approximating the Turaev-Viro Invariant of Mapping Tori is Complete for One Clean Qubit
• A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs
• Doubled Lattice Chern-Simons-Yang-Mills Theories with Discrete Gauge Group
• Universal quantum computation using Ising anyons from a non-semisimple Topological Quantum Field Theory
• Computational quantum-classical boundary of complex and noisy quantum systems
• Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete
• Quantum Algorithms for the Jones Polynomial
• Computational complexity and 3-manifolds and zombies
• On the degeneracy of $SU(3{)}_k$ topological phases
• Topological quantum computation is hyperbolic