Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0908.2122 · Combinatorics Probability Computing

Approximate Counting and Quantum Computation

Magnus Bordewich, Michael Hartley Freedman, László Lovász, Dominic J. A. Welsh

Published Oct 11, 2005• 61 citations
arXivHTMLPDF

Abstract

Motivated by the result that an ‘approximate’ evaluation of the Jones polynomial of a braid at a 5th root of unity can be used to simulate the quantum part of any algorithm in the quantum complexity class BQP, and results relating BQP to the counting class GapP, we introduce a form of additive approximation which can be used to simulate a function in BQP. We show that all functions in the classes #P and GapP have such an approximation scheme under certain natural normalizations. However, we are unable to determine whether the particular functions we are motivated by, such as the above evaluation of the Jones polynomial, can be approximated in this way. We close with some open problems motivated by this work.

DOI
10.1017/s0963548305007005

Related papers

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

Paweł Wocjan, Jon Yard

We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum circuits for implementing the unitary Jones-Wenzl representations of the braid group. We use these to provide new quantum algorithms for approximately evaluating a family of specializations of the HOMFLYPT two-variable polynomial of trace closures of braids. We also give algorithms for approximating the Jones polynomial of a general class of closures of braids at roots of unity. Next we provide a self-contained proof of a result of Freedman et al. that any quantum computation can be replaced by an additive approximation of the Jones polynomial, evaluated at almost any primitive root of unity. Our proof encodes two-qubit unitaries into the rectangular representation of the eight-strand braid group. We then give QCMA-complete and PSPACE-complete problems which are based on braids. We conclude 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 Tutte polynomial and graph coloring.

arXiv:quant-ph/0603069•Journal of International Crisis and Risk Communication Research•Mar 8, 2006•18 citations

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

Paweł Wocjan, Jon Yard

We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum circuits for implementing the unitary Jones-Wenzl representations of the braid group. We use these to provide new quantum algorithms for approximately evaluating a family of specializations of the HOMFLYPT two-variable polynomial of trace closures of braids. We also give algorithms for approximating the Jones polynomial of a general class of closures of braids at roots of unity. Next we provide a self-contained proof of a result of Freedman et al.\ that any quantum computation can be replaced by an additive approximation of the Jones polynomial, evaluated at almost any primitive root of unity. Our proof encodes two-qubit unitaries into the rectangular representation of the eight-strand braid group. We then give QCMA-complete and PSPACE-complete problems which are based on braids. We conclude 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 Tutte polynomial and graph coloring.

Quantum Information and Computation•Jan 1, 2008•56 citations

Quantum Approximate Counting with Additive Error: Hardness and Optimality

Mason L. Rhodes, Sam Slezak, Anirban Ch Narayan Chowdhury +1 more

Quantum counting is the task of determining the dimension of the subspace of states that are accepted by a quantum verifier circuit. It is the quantum analog of counting the number of valid solutions to NP problems -- a problem well-studied in theoretical computer science with far-reaching implications in computational complexity. The complexity of solving the class #BQP of quantum counting problems, either exactly or within suitable approximations, is related to the hardness of computing many-body physics quantities arising in algebraic combinatorics. Here, we address the complexity of quantum approximate counting under additive error. First, we show that computing additive approximations to #BQP problems to within an error exponential in the number of witness qubits in the corresponding verifier circuit is as powerful as polynomial-time quantum computation. Next, we show that returning an estimate within error that is any smaller is #BQP-hard. Finally, we show that additive approximations to a restricted class of #BQP problems are equivalent in computational hardness to the class DQC1. Our work parallels results on additively approximating #P and GapP functions.

arXiv:2411.02602•Nov 4, 2024•0 citations

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

We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum circuits for implementing the unitary Jones-Wenzl representations of the braid group. We use these to provide new quantum algorithms for approximately evaluating a family of specializations of the HOMFLYPT two-variable polynomial of trace closures of braids. We also give algorithms for approximating the Jones polynomial of a general class of closures of braids at roots of unity. Next we provide a self-contained proof of a result of Freedman et al. that any quantum computation can be replaced by an additive approximation of the Jones polynomial, evaluated at almost any primitive root of unity. Our proof encodes two-qubit unitaries into the rectangular representation of the eight-strand braid group. We then give QCMA-complete and PSPACE-cornplete problems which are based on braids. We conclude 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 Tutte polynomial and graph coloring.

Journal of International Crisis and Risk Communication Research•Jan 1, 2008•0 citations

Estimating Jones polynomials is a complete problem for one clean qubit

Peter W. Shor, Stephen P. Jordan

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[12, 3, 1]. 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 [20]. 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. 1 One Clean Qubit The one clean qubit model of quantum computation originated as an idealized model of quantum computation on highly mixed initial states, such as appear in NMR implementations[20, 4]. In this model, one is given an initial quantum state consisting of a single qubit in the pure state |0〉, and n qubits in the maximally mixed

Quantum Information and Computation•Sep 1, 2008•91 citations

Estimating Jones polynomials is a complete problem for one clean qubit

Peter W. Shor, Stephen P. Jordan

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.

Quantum Information and Computation•Sep 1, 2008•49 citations
Motivated by the result that an ‘approximate’ evaluation of the Jones polynomial of a braid at a 5th root of unity can be used to simulate the quantum part of any algorithm in the quantum complexity class BQP, and results relating BQP to the counting class GapP, we introduce a form of additive approximation which can be used to simulate a function in BQP. We show that all functions in the classes #P and GapP have such an approximation scheme under certain natural normalizations. However, we are unable to determine whether the particular functions we are motivated by, such as the above evaluation of the Jones polynomial, can be approximated in this way. We close with some open problems motivated by this work.
We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum circuits for implementing the unitary Jones-Wenzl representations of the braid group. We use these to provide new quantum algorithms for approximately evaluating a family of specializations of the HOMFLYPT two-variable polynomial of trace closures of braids. We also give algorithms for approximating the Jones polynomial of a general class of closures of braids at roots of unity. Next we provide a self-contained proof of a result of Freedman et al. that any quantum computation can be replaced by an additive approximation of the Jones polynomial, evaluated at almost any primitive root of unity. Our proof encodes two-qubit unitaries into the rectangular representation of the eight-strand braid group. We then give QCMA-complete and PSPACE-complete problems which are based on braids. We conclude 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 Tutte polynomial and graph coloring.
We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum circuits for implementing the unitary Jones-Wenzl representations of the braid group. We use these to provide new quantum algorithms for approximately evaluating a family of specializations of the HOMFLYPT two-variable polynomial of trace closures of braids. We also give algorithms for approximating the Jones polynomial of a general class of closures of braids at roots of unity. Next we provide a self-contained proof of a result of Freedman et al.\ that any quantum computation can be replaced by an additive approximation of the Jones polynomial, evaluated at almost any primitive root of unity. Our proof encodes two-qubit unitaries into the rectangular representation of the eight-strand braid group. We then give QCMA-complete and PSPACE-complete problems which are based on braids. We conclude 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 Tutte polynomial and graph coloring.
Quantum counting is the task of determining the dimension of the subspace of states that are accepted by a quantum verifier circuit. It is the quantum analog of counting the number of valid solutions to NP problems -- a problem well-studied in theoretical computer science with far-reaching implications in computational complexity. The complexity of solving the class #BQP of quantum counting problems, either exactly or within suitable approximations, is related to the hardness of computing many-body physics quantities arising in algebraic combinatorics. Here, we address the complexity of quantum approximate counting under additive error. First, we show that computing additive approximations to #BQP problems to within an error exponential in the number of witness qubits in the corresponding verifier circuit is as powerful as polynomial-time quantum computation. Next, we show that returning an estimate within error that is any smaller is #BQP-hard. Finally, we show that additive approximations to a restricted class of #BQP problems are equivalent in computational hardness to the class DQC1. Our work parallels results on additively approximating #P and GapP functions.
We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum circuits for implementing the unitary Jones-Wenzl representations of the braid group. We use these to provide new quantum algorithms for approximately evaluating a family of specializations of the HOMFLYPT two-variable polynomial of trace closures of braids. We also give algorithms for approximating the Jones polynomial of a general class of closures of braids at roots of unity. Next we provide a self-contained proof of a result of Freedman et al. that any quantum computation can be replaced by an additive approximation of the Jones polynomial, evaluated at almost any primitive root of unity. Our proof encodes two-qubit unitaries into the rectangular representation of the eight-strand braid group. We then give QCMA-complete and PSPACE-cornplete problems which are based on braids. We conclude 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 Tutte polynomial and graph coloring.
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[12, 3, 1]. 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 [20]. 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. 1 One Clean Qubit The one clean qubit model of quantum computation originated as an idealized model of quantum computation on highly mixed initial states, such as appear in NMR implementations[20, 4]. In this model, one is given an initial quantum state consisting of a single qubit in the pure state |0〉, and n qubits in the maximally mixed
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.