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. 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 f1,...,fm in S, such that each fi is the unique function in S compatible with O(log|S|) input/output constraints.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. 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 f1,...,fm in S, such that each fi is the unique function in S compatible with O(log|S|) input/output constraints.

arXiv:1004.0377Electronic colloquium on computational complexityApr 2, 20100 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.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.

SIAM Journal on ComputingJan 1, 201411 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.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.09994Theory of ComputingJan 1, 20251 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 BQP/qpoly /spl sube/ PP/poly, where 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 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 /spl nsub/ 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 many other applications; for example, it can be used to fix and even improve on a flawed result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a 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.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 /spl sube/ PP/poly, where 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 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 /spl nsub/ 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 many other applications; for example, it can be used to fix and even improve on a flawed result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a 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.

IEEE Conference on Computational Complexity (CCC)Nov 12, 200430 citations

QMA/qpoly \subseteq PSPACE/poly: De-Merlinizing Quantum Protocols

Scott Aaronson

This paper introduces a new technique for removing existential quantifiers over quantum states. Using this technique, we show that there is no way to pack an exponential number of bits into a polynomial-size quantum state, in such a way that the value of any one of those bits can later be proven with the help of a polynomial-size quantum witness. We also show that any problem in QMA with polynomial-size quantum advice, is also in PSPACE with polynomial-size classical advice. This builds on our earlier result that BQP/qpoly sube PP/poly, and offers an intriguing counterpoint to the recent discovery of Raz that QIP/qpoly = ALL. Finally, we show that QCMA/qpoly sube PP/poly and that QMA/rpoly = QMA/polyThis paper introduces a new technique for removing existential quantifiers over quantum states. Using this technique, we show that there is no way to pack an exponential number of bits into a polynomial-size quantum state, in such a way that the value of any one of those bits can later be proven with the help of a polynomial-size quantum witness. We also show that any problem in QMA with polynomial-size quantum advice, is also in PSPACE with polynomial-size classical advice. This builds on our earlier result that BQP/qpoly sube PP/poly, and offers an intriguing counterpoint to the recent discovery of Raz that QIP/qpoly = ALL. Finally, we show that QCMA/qpoly sube PP/poly and that QMA/rpoly = QMA/poly

IEEE Conference on Computational Complexity (CCC)Aug 8, 200618 citations

QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols

Scott Aaronson

This paper introduces a new technique for removing existential quantifiers over quantum states. Using this technique, we show that there is no way to pack an exponential number of bits into a polynomial-size quantum state, in such a way that the value of any one of those bits can later be proven with the help of a polynomial-size quantum witness. We also show that any problem in QMA with polynomial-size quantum advice, is also in PSPACE with polynomial-size classical advice. This builds on our earlier result that BQP/qpoly is contained in PP/poly, and offers an intriguing counterpoint to the recent discovery of Raz that QIP/qpoly = ALL. Finally, we show that QCMA/qpoly is contained in PP/poly and that QMA/rpoly = QMA/poly.This paper introduces a new technique for removing existential quantifiers over quantum states. Using this technique, we show that there is no way to pack an exponential number of bits into a polynomial-size quantum state, in such a way that the value of any one of those bits can later be proven with the help of a polynomial-size quantum witness. We also show that any problem in QMA with polynomial-size quantum advice, is also in PSPACE with polynomial-size classical advice. This builds on our earlier result that BQP/qpoly is contained in PP/poly, and offers an intriguing counterpoint to the recent discovery of Raz that QIP/qpoly = ALL. Finally, we show that QCMA/qpoly is contained in PP/poly and that QMA/rpoly = QMA/poly.

arXiv:quant-ph/0510230Oct 31, 200516 citations

We prove the following surprising result: given any quantum state

\rho

n

qubits, there exists a local Hamiltonian

H

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

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.