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:1805.08577

PDQP/qpoly = ALL

Scott Aaronson

Published May 22, 2018• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1805.08577

Related papers

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.

•May 22, 2018•1 citation

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.

Electronic colloquium on computational complexity•Jan 1, 2018•0 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.

Quantum Information and Computation•Sep 1, 2018•3 citations

PDQP/qpoly = All

AaronsonScott

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 ...

Quantum Information and Computation•Sep 1, 2018•1 citation

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

Even quantum advice is unlikely to solve PP

Justin Yirka

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.

arXiv:2403.09994•Theory of Computing•Jan 1, 2025•1 citation
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.
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 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.