The BQP-hardness of approximating the Jones polynomial
From MaRDI portal
Publication:5135831
DOI10.1088/1367-2630/13/3/035019zbMath1448.68244arXivquant-ph/0605181OpenAlexW2119968904MaRDI QIDQ5135831
Publication date: 24 November 2020
Published in: New Journal of Physics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/quant-ph/0605181
Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Knot polynomials (57K14)
Related Items
The complexity of approximating complex-valued Ising and Tutte partition functions ⋮ Topological quantum computation is hyperbolic ⋮ Doubled lattice Chern-Simons-Yang-Mills theories with discrete gauge group ⋮ Unnamed Item ⋮ Quantum algorithms for classical lattice models ⋮ Quantum Fourier transforms and the complexity of link invariants for quantum doubles of finite groups ⋮ A permanent formula for the Jones polynomial ⋮ Topology and Quantum Computing
Cites Work
- Inapproximability of the Tutte polynomial
- State models and the Jones polynomial
- Quantum field theory and the Jones polynomial
- Simulation of topological field theories by quantum computers
- A modular functor which is universal for quantum computation
- Fault-Tolerant Quantum Computation with Constant Error Rate
- Estimating Jones polynomials is a complete problem for one clean qubit
- A polynomial invariant for knots via von Neumann algebras
- P/NP , and the quantum field computer
- On the computational complexity of the Jones and Tutte polynomials
- Topological quantum computation
- Quantum Computation and the Evaluation of Tensor Networks
- Quantum computing, postselection, and probabilistic polynomial-time
- Relations between the ‘percolation’ and ‘colouring’ problem and other graph-theoretical problems associated with regular planar lattices: some exact results for the ‘percolation’ problem
- Approximate Counting and Quantum Computation
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item