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:2403.09994 · Theory of Computing

Even quantum advice is unlikely to solve PP

Justin Yirka

Published Jan 1, 2025• 2 citations
arXivHTMLPDF

Abstract

We give a corrected proof that if $\mathsf{PP} \subseteq \mathsf{BQP/qpoly}$ (probabilistic polynomial time can be efficiently simulated by quantum circuits with quantum advice), then the Counting Hierarchy collapses, as originally claimed by Aaronson (CCC'06). This recovers the related unconditional claim that $\mathsf{PP}$ does not have circuits of any fixed-polynomial size $n^k$ even with quantum advice. Our result is based on proving that $\mathsf{YQP^*}$, an oblivious version of $\mathsf{QMA}\cap\mathsf{coQMA}$, is contained in $\mathsf{APP}$, a $\mathsf{PP}$-low subclass of $\mathsf{PP}$ with an arbitrarily small but nonzero promise gap.

DOI
10.4086/toc.2025.v021a007

Related papers

A full characterization of quantum advice

Scott Aaronson, Andrew Drucker

We prove the following surprising result: given any quantum state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of H can be used to simulate rho on all quantum circuits of fixed polynomial size. In terms of complexity classes, this implies that BQP/qpoly is contained in QMA/poly, which supersedes the previous result of Aaronson that BQP/qpoly is contained in PP/poly. Indeed, we can exactly characterize quantum advice, as equivalent in power to untrusted quantum advice combined with trusted classical advice.

ACM Symposium on Theory of Computing (STOC)•Jun 5, 2010•6 citations

A Full Characterization of Quantum Advice

Scott Aaronson, Andrew Drucker

We prove the following surprising result: given any quantum state $\rho$ on $n$ qubits, there exists a local Hamiltonian $H$ on $\operatorname*{poly}(n)$ qubits (e.g., a sum of two-qubit interactions), such that any ground state of $H$ can be used to simulate $\rho$ on all quantum circuits of fixed polynomial size. In terms of complexity classes, this implies that ${BQP/qpoly}\subseteq{QMA/poly}$, which supersedes the previous result of Aaronson that ${BQP/qpoly}\subseteq {PP/poly}$. Indeed, we can exactly characterize quantum advice as equivalent in power to untrusted quantum advice combined with trusted classical advice. Proving our main result requires combining a large number of previous tools---including a result of Alon et al. on learning of real-valued concept classes, a result of Aaronson on the learnability of quantum states, and a result of Aharonov and Regev on “${QMA}_{{+}}$ super-verifiers''---and also creating some new ones. The main new tool is a so-called majority-certificates lemma, which is closely related to boosting in machine learning, and which seems likely to find independent applications. In its simplest version, this lemma says the following. Given any set $S$ of Boolean functions on $n$ variables, any function $f\in S$ can be expressed as the pointwise majority of $m=O(n)$ functions $f_{1},\ldots,f_{m}\in S$, such that each $f_{i}$ is the unique function in $S$ compatible with $O(\log\vert S\vert)$ input/output constraints.

arXiv:1004.0377•SIAM Journal on Computing•Jan 1, 2014•18 citations

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy

Kartik Anand, Kabgyun Jeong, Junseo Lee

We investigate structural properties of quantum proof systems by establishing collapse results that uncover simplifications in their complexity landscape. We extend classical results such as the Karp-Lipton theorem to quantum polynomial hierarchy with quantum proofs and establish uniqueness preservation for quantum-classical probabilistically checkable proof systems. Our main contributions are threefold. First, we prove that restricting quantum-classical PCP systems to uniqueness does not reduce computational power: $\mathsf{UniqueQCPCP} = \mathsf{QCPCP}$ under $\mathsf{BQ}$-operator and randomized reductions, demonstrating robustness similar to the $\mathsf{UniqueQCMA} = \mathsf{QCMA}$ result. Second, we establish a non-uniform quantum analogue of the Karp-Lipton theorem, showing that if $\mathsf{QMA} \subseteq \mathsf{BQP}/\mathsf{qpoly}$, then $\mathsf{QPH} \subseteq \mathsf{QΣ}_2/\mathsf{qpoly}$, extending the classical collapse theorem to quantum complexity with quantum advice. Third, we introduce a consistent variant of the quantum polynomial hierarchy ($\mathsf{CQPH}$) with consistency constraints across interaction rounds while maintaining product-state proofs, proving its unconditional collapse $\mathsf{CQPH} = \mathsf{CQΣ}_2$. This contrasts with prior work on quantum-entangled polynomial hierarchy, showing that consistency rather than entanglement drives the collapse. These results contribute to understanding structural boundaries in quantum complexity theory and the interplay between constraint types in quantum proof systems.

arXiv:2506.19792•Jun 24, 2025•1 citation

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

Limitations of Quantum Advice and One-Way Communication

Scott Aaronson

Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that $\mathsf{BQP/qpoly}\subseteq\mathsf{PP/poly}$, where $\mathsf{BQP/qpoly}$ is the class of problems solvable in quantum polynomial time, given a polynomial-size “quantum advice state” that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which $\mathsf{NP}\not \subset \mathsf{BQP/qpoly}$. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols. A preliminary version of this paper appeared in the 2004 Conference on Computational Complexity (CCC).

arXiv:quant-ph/0402095•Theory of Computing•Jan 1, 2005•157 citations

PDQP/qpoly=ALL

Scott Aaronson

We show that combining two different hypothetical enhancements to quantum computation---namely, quantum advice and non-collapsing measurements---would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable codes.

arXiv:1805.08577•Quantum Information and Computation•Sep 1, 2018•10 citations
We give a corrected proof that if PP⊆BQP/qpoly\mathsf{PP} \subseteq \mathsf{BQP/qpoly}PP⊆BQP/qpoly (probabilistic polynomial time can be efficiently simulated by quantum circuits with quantum advice), then the Counting Hierarchy collapses, as originally claimed by Aaronson (CCC'06). This recovers the related unconditional claim that PP\mathsf{PP}PP does not have circuits of any fixed-polynomial size nkn^knk even with quantum advice. Our result is based on proving that YQP∗\mathsf{YQP^*}YQP∗, an oblivious version of QMA∩coQMA\mathsf{QMA}\cap\mathsf{coQMA}QMA∩coQMA, is contained in APP\mathsf{APP}APP, a PP\mathsf{PP}PP-low subclass of PP\mathsf{PP}PP with an arbitrarily small but nonzero promise gap.
We prove the following surprising result: given any quantum state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of H can be used to simulate rho on all quantum circuits of fixed polynomial size. In terms of complexity classes, this implies that BQP/qpoly is contained in QMA/poly, which supersedes the previous result of Aaronson that BQP/qpoly is contained in PP/poly. Indeed, we can exactly characterize quantum advice, as equivalent in power to untrusted quantum advice combined with trusted classical advice.
We prove the following surprising result: given any quantum state ρ\rhoρ on nnn qubits, there exists a local Hamiltonian HHH on poly⁡(n)\operatorname*{poly}(n)poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of HHH can be used to simulate ρ\rhoρ on all quantum circuits of fixed polynomial size. In terms of complexity classes, this implies that BQP/qpoly⊆QMA/poly{BQP/qpoly}\subseteq{QMA/poly}BQP/qpoly⊆QMA/poly, which supersedes the previous result of Aaronson that BQP/qpoly⊆PP/poly{BQP/qpoly}\subseteq {PP/poly}BQP/qpoly⊆PP/poly. Indeed, we can exactly characterize quantum advice as equivalent in power to untrusted quantum advice combined with trusted classical advice. Proving our main result requires combining a large number of previous tools---including a result of Alon et al. on learning of real-valued concept classes, a result of Aaronson on the learnability of quantum states, and a result of Aharonov and Regev on “QMA+{QMA}_{{+}}QMA+​ super-verifiers''---and also creating some new ones. The main new tool is a so-called majority-certificates lemma, which is closely related to boosting in machine learning, and which seems likely to find independent applications. In its simplest version, this lemma says the following. Given any set SSS of Boolean functions on nnn variables, any function f∈Sf\in Sf∈S can be expressed as the pointwise majority of m=O(n)m=O(n)m=O(n) functions f1,…,fm∈Sf_{1},\ldots,f_{m}\in Sf1​,…,fm​∈S, such that each fif_{i}fi​ is the unique function in SSS compatible with O(log⁡∣S∣)O(\log\vert S\vert)O(log∣S∣) input/output constraints.
We investigate structural properties of quantum proof systems by establishing collapse results that uncover simplifications in their complexity landscape. We extend classical results such as the Karp-Lipton theorem to quantum polynomial hierarchy with quantum proofs and establish uniqueness preservation for quantum-classical probabilistically checkable proof systems. Our main contributions are threefold. First, we prove that restricting quantum-classical PCP systems to uniqueness does not reduce computational power: UniqueQCPCP=QCPCP\mathsf{UniqueQCPCP} = \mathsf{QCPCP}UniqueQCPCP=QCPCP under BQ\mathsf{BQ}BQ-operator and randomized reductions, demonstrating robustness similar to the UniqueQCMA=QCMA\mathsf{UniqueQCMA} = \mathsf{QCMA}UniqueQCMA=QCMA result. Second, we establish a non-uniform quantum analogue of the Karp-Lipton theorem, showing that if QMA⊆BQP/qpoly\mathsf{QMA} \subseteq \mathsf{BQP}/\mathsf{qpoly}QMA⊆BQP/qpoly, then QPH⊆QΣ2/qpoly\mathsf{QPH} \subseteq \mathsf{QΣ}_2/\mathsf{qpoly}QPH⊆QΣ2​/qpoly, extending the classical collapse theorem to quantum complexity with quantum advice. Third, we introduce a consistent variant of the quantum polynomial hierarchy (CQPH\mathsf{CQPH}CQPH) with consistency constraints across interaction rounds while maintaining product-state proofs, proving its unconditional collapse CQPH=CQΣ2\mathsf{CQPH} = \mathsf{CQΣ}_2CQPH=CQΣ2​. This contrasts with prior work on quantum-entangled polynomial hierarchy, showing that consistency rather than entanglement drives the collapse. These results contribute to understanding structural boundaries in quantum complexity theory and the interplay between constraint types in quantum proof systems.
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.
Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly⊆PP/poly\mathsf{BQP/qpoly}\subseteq\mathsf{PP/poly}BQP/qpoly⊆PP/poly, where BQP/qpoly\mathsf{BQP/qpoly}BQP/qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size “quantum advice state” that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP⊄BQP/qpoly\mathsf{NP}\not \subset \mathsf{BQP/qpoly}NP⊂BQP/qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols. A preliminary version of this paper appeared in the 2004 Conference on Computational Complexity (CCC).