Estimating Jones polynomials is a complete problem for one clean qubit

MaRDI QIDQ3602386zbMATH OpenFDO

Authors Peter W. Shor, Stephen P. Jordan

Publication date 12 February 2009

Full work available at URL https://arxiv.org/abs/0707.2831

zbMATH Keywords

Jones polynomialone clean qubit

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: It is known that evaluating a certain approximation to the Jones polynomial for the plat closure of a braid is a BQP-complete problem. That is, this problem exactly captures the power of the quantum circuit model. The one clean qubit model is a model of quantum computation in which all but one qubit starts in the maximally mixed state. One clean qubit computers are believed to be strictly weaker than standard quantum computers, but still capable of solving some classically intractable problems. Here we show 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. That is, a one clean qubit computer can approximate these Jones polynomials in time polynomial in both the number of strands and number of crossings, and the problem of simulating a one clean qubit computer is reducible to approximating the Jones polynomial of the trace closure of a braid.

Recommendations

• scientific article; zbMATH DE number 5573021
• The Jones polynomial: quantum algorithms and applications in quantum complexity theory
• A polynomial quantum algorithm for approximating the Jones polynomial
• A polynomial quantum algorithm for approximating the Jones polynomial
• How hard is it to approximate the Jones polynomial?

Cited in

(24)

• Anyons in geometric models of matter
• Quantum knots and the number of knot mosaics
• Growth rate of quantum knot mosaics
• Complexity classes as mathematical axioms. II
• Benchmarking quantum processors with a single qubit
• Quantum circuits cannot control unknown operations
• Approximating the Turaev-Viro Invariant of Mapping Tori is Complete for One Clean Qubit
• The Jones polynomial: quantum algorithms and applications in quantum complexity theory
• scientific article; zbMATH DE number 5573021 (Why is no real title available?)
• On upper bounds for toroidal mosaic numbers
• Power of quantum computation with few clean qubits
• The BQP-hardness of approximating the Jones polynomial
• Period and toroidal knot mosaics
• Enumeration on graph mosaics
• Approximate Counting and Quantum Computation
• The quantum complexity of computing Schatten p-norms
• A polynomial quantum algorithm for approximating the Jones polynomial
• An improved method for quantum matrix multiplication
• Quantum knot mosaics and bounds of the growth constant
• The mixed Hilden braid group and the plat equivalence in handlebodies
• Passing from plat closure to standard closure of braids in \(\mathbb{R}^3\), in handlebodies and in thickened surfaces
• The quantum monadology
• Quantum catalytic space
• Quantum knots and mosaics

This page was built for publication: Estimating Jones polynomials is a complete problem for one clean qubit

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3602386)