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:quant-ph/9812056 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences

Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy

Stephen Fenner, Frederic Green, Steven Thomas Homer, Randall J. Pruim

Published Nov 8, 1999• 80 citations
arXivHTMLPDF

Abstract

It is shown that determining whether a quantum computation has a non–zero probability of accepting is at least as hard as the polynomial–time hierarchy. This hardness result also applies to determining in general whether a given quantum basis state appears with non–zero amplitude in a superposition, or whether a given quantum bit has positive expectation value at the end of a quantum computation. This result is achieved by showing that the complexity class NQP (a quantum analogue of NP) of Adleman, Demarrais and Huang, is equal to the counting class coC=P.

DOI
10.1098/rspa.1999.0485

Related papers

Revisiting a limit on efficient quantum computation

Tarsem S. Purewal

In this paper, we offer an exposition of a theorem originally due to Adleman, Demarrais and Huang that shows that the quantum complexity class BQP (Bounded-error Quantum Polynomial time) is contained in the classical counting class PP (Probabilistic Polynomial time). Our proof follows the one given by Fortnow and Rogers that relates quantum computing to counting complexity classes by way of GapP functions. The contribution of this paper is an exposition of an important result that assumes a minimal background in computational complexity theory and no knowledge of quantum mechanics.

ACM Southeast Regional Conference (ACMSE)•Mar 10, 2006•1 citation

Bounds on the Power of Constant-Depth Quantum Circuits

Fenner, Stephen, Frederic Green, Steven Thomas Homer +1 more

We show that if a language is recognized within certain error bounds by constant-depth quantum circuits over a finite family of gates, then it is computable in (classical) polynomial time. In particular, our results imply EQNC^0 is contained in P, where EQNC^0 is the constant-depth analog of the class EQP. On the other hand, we adapt and extend ideas of Terhal and DiVincenzo (quant-ph/0205133) to show that, for any family F of quantum gates including Hadamard and CNOT gates, computing the acceptance probabilities of depth-five circuits over F is just as hard as computing these probabilities for circuits over F. In particular, this implies that NQNC^0 = NQACC = NQP = coC=P where NQNC^0 is the constant-depth analog of the class NQP. This essentially refutes a conjecture of Green et al. that NQACC is contained in TC^0 (quant-ph/0106017).

arXiv:quant-ph/0312209•Dec 28, 2003•9 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•1 citation

The complexity of parameters for probabilistic and quantum computation

Josef Michael Breutzmann

In this dissertation we study some effects of allowing computational models that use parameters whose own computational complexity has a strong effect on the computational complexity of the languages computable from the model. We show that in the probabilistic and quantum models there are parameter sets that allow one to obtain noncomputable outcomes;In Chapter 3 we define BP[beta]P the BPP class based on a coin with bias [beta]. We then show that if [beta] is BPP-computable then it is the case that BP[beta]P = BPP. We also show that each language L in P/CLog is in BP[beta]P for some [beta]. Hence there are some [beta] from which we can compute noncomputable languages. We also examine the robustness of the class BPP with respect to small variations from fairness in the coin;In Chapter 4 we consider measures that are based on polynomial-time computable sequences of biased coins in which the biases are bounded away from both zero and one (strongly positive P-sequences). We show that such a sequence [vector][beta] generates a measure [mu][vector][beta] equivalent to the uniform measure in the sense that if C is a class of languages closed under positive, polynomial-time, truth-table reductions with queries of linear length then C has [mu][vector][beta]-measure zero if and only if it has measure zero relative to the uniform measure [mu]. The classes P, NP, BPP, P/Poly, PH, and PSPACE are among those to which this result applies. Thus the measures of these much-studied classes are robust with respect to changes of this type in the underlying probability measure;In Chapter 5 we introduce the quantum computation model and the quantum complexity class BQP. We claim that the computational complexity of the amplitudes is a critical factor in determining the languages computable using the quantum model. Using results from chapter 3 we show that the quantum model can also compute noncomputable languages from some amplitude sets. Finally, we determine a restriction on the amplitude set to limit the model to the range of languages implicit in others' typical meaning of the class BQP.

•Jan 1, 1996•0 citations

Computational Complexity of Some Quantum Theories in $1+1$ Dimensions

Saeed Adel Mehraban

We study the computational complexity of certain integrable quantum theories in 1+1 dimensions. We formalize a model of quantum computation based on these theories. In this model, distinguishable particles start out with known momenta and initial superposition of different configurations. Then the label of these particles are measured at the end. We prove that additive approximation to single amplitudes of these models can be obtained by the one-clean-qubit model, if no initial superpositions are allowed. However, if arbitrary initial states and non-adaptive intermediate measurements are allowed, we show that conditioned on infinite polynomial hierarchy assumption it is hard to sample from the output distribution of these models on a classical randomized computer. A classical analogue of this model is also formalized and its computational power is pinned down within the complexity classes below BPP and NP.

arXiv:1512.09243•Dec 31, 2015•4 citations

Quantum Computability

Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh A. Huang

In this paper some theoretical and (potentially) practical aspects of quantum computing are considered. Using the tools of transcendental number theory it is demonstrated that quantum Turing machines (QTM) with rational amplitudes are sufficient to define the class of bounded error quantum polynomial time (BQP) introduced by Bernstein and Vazirani [Proc. 25th ACM Symposium on Theory of Computation, 1993, pp. 11--20, SIAM J. Comput., 26 (1997), pp. 1277--1339]. On the other hand, if quantum Turing machines are allowed unrestricted amplitudes (i.e., arbitrary complex amplitudes), then the corresponding BQP class has uncountable cardinality and contains sets of all Turing degrees. In contrast, allowing unrestricted amplitudes does not increase the power of computation for error-free quantum polynomial time (EQP). Moreover, with unrestricted amplitudes, BQP is not equal to EQP. The relationship between quantum complexity classes and classical complexity classes is also investigated. It is shown that when quantum Turing machines are restricted to have transition amplitudes which are algebraic numbers, BQP, EQP, and nondeterministic quantum polynomial time (NQP) are all contained in PP, hence in ${\rm P}^{#{\rm P}}$ and PSPACE. A potentially practical issue of designing "machine independent" quantum programs is also addressed. A single ("almost universal") quantum algorithm based on Shor's method for factoring integers is developed which would run correctly on almost all quantum computers, even if the underlying unitary transformations are unknown to the programmer and the device builder.

SIAM Journal on Computing•Oct 1, 1997•266 citations
It is shown that determining whether a quantum computation has a non–zero probability of accepting is at least as hard as the polynomial–time hierarchy. This hardness result also applies to determining in general whether a given quantum basis state appears with non–zero amplitude in a superposition, or whether a given quantum bit has positive expectation value at the end of a quantum computation. This result is achieved by showing that the complexity class NQP (a quantum analogue of NP) of Adleman, Demarrais and Huang, is equal to the counting class coC=P.
In this paper, we offer an exposition of a theorem originally due to Adleman, Demarrais and Huang that shows that the quantum complexity class BQP (Bounded-error Quantum Polynomial time) is contained in the classical counting class PP (Probabilistic Polynomial time). Our proof follows the one given by Fortnow and Rogers that relates quantum computing to counting complexity classes by way of GapP functions. The contribution of this paper is an exposition of an important result that assumes a minimal background in computational complexity theory and no knowledge of quantum mechanics.
We show that if a language is recognized within certain error bounds by constant-depth quantum circuits over a finite family of gates, then it is computable in (classical) polynomial time. In particular, our results imply EQNC^0 is contained in P, where EQNC^0 is the constant-depth analog of the class EQP. On the other hand, we adapt and extend ideas of Terhal and DiVincenzo (quant-ph/0205133) to show that, for any family F of quantum gates including Hadamard and CNOT gates, computing the acceptance probabilities of depth-five circuits over F is just as hard as computing these probabilities for circuits over F. In particular, this implies that NQNC^0 = NQACC = NQP = coC=P where NQNC^0 is the constant-depth analog of the class NQP. This essentially refutes a conjecture of Green et al. that NQACC is contained in TC^0 (quant-ph/0106017).
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.
In this dissertation we study some effects of allowing computational models that use parameters whose own computational complexity has a strong effect on the computational complexity of the languages computable from the model. We show that in the probabilistic and quantum models there are parameter sets that allow one to obtain noncomputable outcomes;In Chapter 3 we define BP[beta]P the BPP class based on a coin with bias [beta]. We then show that if [beta] is BPP-computable then it is the case that BP[beta]P = BPP. We also show that each language L in P/CLog is in BP[beta]P for some [beta]. Hence there are some [beta] from which we can compute noncomputable languages. We also examine the robustness of the class BPP with respect to small variations from fairness in the coin;In Chapter 4 we consider measures that are based on polynomial-time computable sequences of biased coins in which the biases are bounded away from both zero and one (strongly positive P-sequences). We show that such a sequence [vector][beta] generates a measure [mu][vector][beta] equivalent to the uniform measure in the sense that if C is a class of languages closed under positive, polynomial-time, truth-table reductions with queries of linear length then C has [mu][vector][beta]-measure zero if and only if it has measure zero relative to the uniform measure [mu]. The classes P, NP, BPP, P/Poly, PH, and PSPACE are among those to which this result applies. Thus the measures of these much-studied classes are robust with respect to changes of this type in the underlying probability measure;In Chapter 5 we introduce the quantum computation model and the quantum complexity class BQP. We claim that the computational complexity of the amplitudes is a critical factor in determining the languages computable using the quantum model. Using results from chapter 3 we show that the quantum model can also compute noncomputable languages from some amplitude sets. Finally, we determine a restriction on the amplitude set to limit the model to the range of languages implicit in others' typical meaning of the class BQP.
Computational Complexity of Some Quantum Theories in 1+11+11+1 Dimensions
We study the computational complexity of certain integrable quantum theories in 1+1 dimensions. We formalize a model of quantum computation based on these theories. In this model, distinguishable particles start out with known momenta and initial superposition of different configurations. Then the label of these particles are measured at the end. We prove that additive approximation to single amplitudes of these models can be obtained by the one-clean-qubit model, if no initial superpositions are allowed. However, if arbitrary initial states and non-adaptive intermediate measurements are allowed, we show that conditioned on infinite polynomial hierarchy assumption it is hard to sample from the output distribution of these models on a classical randomized computer. A classical analogue of this model is also formalized and its computational power is pinned down within the complexity classes below BPP and NP.
In this paper some theoretical and (potentially) practical aspects of quantum computing are considered. Using the tools of transcendental number theory it is demonstrated that quantum Turing machines (QTM) with rational amplitudes are sufficient to define the class of bounded error quantum polynomial time (BQP) introduced by Bernstein and Vazirani [Proc. 25th ACM Symposium on Theory of Computation, 1993, pp. 11--20, SIAM J. Comput., 26 (1997), pp. 1277--1339]. On the other hand, if quantum Turing machines are allowed unrestricted amplitudes (i.e., arbitrary complex amplitudes), then the corresponding BQP class has uncountable cardinality and contains sets of all Turing degrees. In contrast, allowing unrestricted amplitudes does not increase the power of computation for error-free quantum polynomial time (EQP). Moreover, with unrestricted amplitudes, BQP is not equal to EQP. The relationship between quantum complexity classes and classical complexity classes is also investigated. It is shown that when quantum Turing machines are restricted to have transition amplitudes which are algebraic numbers, BQP, EQP, and nondeterministic quantum polynomial time (NQP) are all contained in PP, hence in ${\rm P}^{#{\rm P}}$ and PSPACE. A potentially practical issue of designing "machine independent" quantum programs is also addressed. A single ("almost universal") quantum algorithm based on Shor's method for factoring integers is developed which would run correctly on almost all quantum computers, even if the underlying unitary transformations are unknown to the programmer and the device builder.