SIAM Journal on Computing

A Full Characterization of Quantum Advice

Scott Aaronson, Andrew Drucker

Published Jan 1, 2014• 11 citations

Abstract

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.

DOI: 10.1137/110856939

Related papers

A full characterization of quantum advice

Scott Aaronson, Andrew Drucker

ACM Symposium on Theory of Computing (STOC)Jun 5, 20106 citations

Even quantum advice is unlikely to solve PP

Justin Yirka

arXiv:2403.09994Theory of ComputingJan 1, 20251 citation

No Size-Preserving Amplification with Quantum Advice

Shih-Han Hung, Han-Hsuan Lin

quant-pharXiv:2610.03377Oct 5, 20260 citations

Uncloneable Quantum Advice

Anne Broadbent, Martti Karvonen, Sébastien Lord

arXiv:2309.05155IACR Communications in CryptologyOct 7, 20243 citations

On classical advice, sampling advice and complexity assumptions for learning separations

Jordi Pérez-Guijarro

arXiv:2408.13880Aug 25, 20240 citations

Quantum Hardness of Learning Shallow Classical Circuits

Srinivasan Arunachalam, Alex B. Grilo, Aarthi Sundaram

arXiv:1903.02840SIAM Journal on ComputingJan 1, 202111 citations

SIAM Journal on Computing

A Full Characterization of Quantum Advice

Scott Aaronson, Andrew Drucker

Published Jan 1, 2014• 11 citations

Publisher

Abstract

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.

DOI: 10.1137/110856939

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

No Size-Preserving Amplification with Quantum Advice

Shih-Han Hung, Han-Hsuan Lin

Marriott and Watrous showed that quantum Merlin--Arthur games admit generic error reduction without increasing witness size [Computational Complexity, 2005]. In this work, we show that this state-size-preserving amplification property does not hold for polynomial-time quantum computation with quantum advice. In particular, we present decision problems for which even a vanishing additive error reduction requires longer advice. More precisely, for every polynomially bounded advice length $m(n)=ω(1)$ and every error bound $\varepsilon(n)$ that stays below $1/2$ by at least an inverse polynomial, there is a positive function $δ$ with $δ(n)=O\bigl(\min\{(\log m/m)^{1/4},\ \sqrt{\log m/m}\,/(1/2-\varepsilon(n))\}\bigr)$ such that $\mathsf{BQP}_{\varepsilon}/\mathsf{q}m \subsetneq \mathsf{BQP}_{\varepsilon + δ}/\mathsf{q}m$ ; for constant $\varepsilon$ the gap is $O(\sqrt{\log m/m})$ . Here, $\mathsf{BQP}_\varepsilon/\mathsf{q}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a polynomial-time quantum algorithm with an $m(n)$ -qubit advice state that only depends on the input length $n$ . We show this by proving a stronger separation $\mathsf{P}_{\varepsilon+δ}/\mathsf{r} m \not\subset \mathsf{BQP}_{\varepsilon}/\mathsf{q} m$ , where $\mathsf{P}_{\varepsilon}/\mathsf{r}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a deterministic polynomial-time algorithm with an $m(n)$ -bit advice string sampled from a distribution that depends only on $n$ .Marriott and Watrous showed that quantum Merlin--Arthur games admit generic error reduction without increasing witness size [Computational Complexity, 2005]. In this work, we show that this state-size-preserving amplification property does not hold for polynomial-time quantum computation with quantum advice. In particular, we present decision problems for which even a vanishing additive error reduction requires longer advice. More precisely, for every polynomially bounded advice length $m(n)=ω(1)$ and every error bound $\varepsilon(n)$ that stays below $1/2$ by at least an inverse polynomial, there is a positive function $δ$ with $δ(n)=O\bigl(\min\{(\log m/m)^{1/4},\ \sqrt{\log m/m}\,/(1/2-\varepsilon(n))\}\bigr)$ such that $\mathsf{BQP}_{\varepsilon}/\mathsf{q}m \subsetneq \mathsf{BQP}_{\varepsilon + δ}/\mathsf{q}m$; for constant $\varepsilon$ the gap is $O(\sqrt{\log m/m})$. Here, $\mathsf{BQP}_\varepsilon/\mathsf{q}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a polynomial-time quantum algorithm with an $m(n)$-qubit advice state that only depends on the input length $n$. We show this by proving a stronger separation $\mathsf{P}_{\varepsilon+δ}/\mathsf{r} m \not\subset \mathsf{BQP}_{\varepsilon}/\mathsf{q} m$, where $\mathsf{P}_{\varepsilon}/\mathsf{r}m$ is the class of languages recognizable with error at most $\varepsilon(n)$ by a deterministic polynomial-time algorithm with an $m(n)$-bit advice string sampled from a distribution that depends only on $n$.

quant-pharXiv:2610.03377Oct 5, 20260 citations

Uncloneable Quantum Advice

Anne Broadbent, Martti Karvonen, Sébastien Lord

The famous no-cloning principle has been shown recently to enable a number of uncloneable cryptographic primitives, including the copy-protection of certain functionalities. Here we address for the first time unkeyed quantum uncloneablity, via the study of a complexity-theoretic tool that enables a computation, but that is natively unkeyed: quantum advice. Remarkably, this is an application of the no-cloning principle in a context where the quantum states of interest are not chosen by a random process. We establish unconditional constructions for promise problems admitting uncloneable quantum advice and, assuming the feasibility of quantum copy-protecting certain functions, for languages with uncloneable advice. Along the way, we note that state complexity classes, introduced by Rosenthal and Yuen (ITCS 2022) — which concern the computational difficulty of synthesizing sequences of quantum states — can be naturally generalized to obtain state cloning complexity classes. We make initial observations on these classes, notably obtaining a result analogous to the existence of undecidable problems. Our proof technique defines and constructs ingenerable sequences of finite bit strings, essentially meaning that they cannot be generated by any uniform circuit family with non-negligible probability. We then prove a generic result showing that the difficulty of accomplishing a computational task on uniformly random inputs implies its difficulty on any fixed, ingenerable sequence. We use this result to derandomize quantum cryptographic games that relate to cloning, and then incorporate a result of Kundu and Tan (arXiv 2022) to obtain uncloneable advice. Applying this two-step process to a monogamy-of-entanglement game yields a promise problem with uncloneable advice, and applying it to the quantum copy-protection of pseudorandom functions with super-logarithmic output lengths yields a language with uncloneable advice.The famous no-cloning principle has been shown recently to enable a number of uncloneable cryptographic primitives, including the copy-protection of certain functionalities. Here we address for the first time unkeyed quantum uncloneablity, via the study of a complexity-theoretic tool that enables a computation, but that is natively unkeyed: quantum advice. Remarkably, this is an application of the no-cloning principle in a context where the quantum states of interest are not chosen by a random process. We establish unconditional constructions for promise problems admitting uncloneable quantum advice and, assuming the feasibility of quantum copy-protecting certain functions, for languages with uncloneable advice. Along the way, we note that state complexity classes, introduced by Rosenthal and Yuen (ITCS 2022) — which concern the computational difficulty of synthesizing sequences of quantum states — can be naturally generalized to obtain state cloning complexity classes. We make initial observations on these classes, notably obtaining a result analogous to the existence of undecidable problems. Our proof technique defines and constructs ingenerable sequences of finite bit strings, essentially meaning that they cannot be generated by any uniform circuit family with non-negligible probability. We then prove a generic result showing that the difficulty of accomplishing a computational task on uniformly random inputs implies its difficulty on any fixed, ingenerable sequence. We use this result to derandomize quantum cryptographic games that relate to cloning, and then incorporate a result of Kundu and Tan (arXiv 2022) to obtain uncloneable advice. Applying this two-step process to a monogamy-of-entanglement game yields a promise problem with uncloneable advice, and applying it to the quantum copy-protection of pseudorandom functions with super-logarithmic output lengths yields a language with uncloneable advice.

arXiv:2309.05155IACR Communications in CryptologyOct 7, 20243 citations

On classical advice, sampling advice and complexity assumptions for learning separations

Jordi Pérez-Guijarro

In this paper, we study the relationship between advice in the form of a training set and classical advice. We do this by analyzing the class $\mathsf{BPP/samp}$ and certain variants of it. Specifically, our main result demonstrates that $\mathsf{BPP/samp}$ is a proper subset of the class $\mathsf{P/poly}$ , which implies that advice in the form of a training set is strictly weaker than classical advice. This result remains valid when considering quantum advice and a quantum generalization of the training set. Finally, leveraging the insights from our proofs, we identify both sufficient and necessary complexity-theoretic assumptions for the existence of concept classes that exhibit a quantum learning speed-up. We consider both the worst-case setting, where accurate results are required for all inputs, and the average-case setting.In this paper, we study the relationship between advice in the form of a training set and classical advice. We do this by analyzing the class $\mathsf{BPP/samp}$ and certain variants of it. Specifically, our main result demonstrates that $\mathsf{BPP/samp}$ is a proper subset of the class $\mathsf{P/poly}$, which implies that advice in the form of a training set is strictly weaker than classical advice. This result remains valid when considering quantum advice and a quantum generalization of the training set. Finally, leveraging the insights from our proofs, we identify both sufficient and necessary complexity-theoretic assumptions for the existence of concept classes that exhibit a quantum learning speed-up. We consider both the worst-case setting, where accurate results are required for all inputs, and the average-case setting.

arXiv:2408.13880Aug 25, 20240 citations

Quantum Hardness of Learning Shallow Classical Circuits

Srinivasan Arunachalam, Alex B. Grilo, Aarthi Sundaram

In this paper, we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of probably approximately correct (PAC) learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1. Hardness of PAC learning ${AC}^0$ and ${TC}^0$ under the uniform distribution. Our first result concerns the concept class ${TC}^0$ (resp., ${AC}^0$ ), the class of constant-depth, polynomial-sized circuits with unbounded fan-in majority gates (resp., ${AND}, {OR}, {NOT}$ gates). We show the following: if there exists no quantum (quasi-)polynomial-time algorithm to solve the ring-learning with errors ( ${RLWE}$ ) problem, then there exists no (quasi-)polynomial-time quantum learning algorithm for ${TC}^0$ ; and if there exists no $2^{O(d^{1/\eta})}$ -time quantum algorithm to solve ${RLWE}$ with dimension $d = O(polylog n)$ (for every constant $\eta > 2$ ), then there exists no $O(n^{ \log^{\nu} n} )$ -time quantum learning algorithm for $poly(n)$ -sized ${AC}^0$ circuits (for a constant $\nu>0$ ), matching the classical upper bound of Linial, Mansour and Nisan [J. ACM, 40 (1993), pp. 607--620], where the learning algorithms are under the uniform distribution (even with access to quantum membership queries). The main technique in these results uses an explicit family of pseudorandom functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2. Hardness of learning ${TC}^0_2$ in the PAC setting. Our second result shows that if there exists no quantum polynomial-time algorithm for the ${LWE}$ problem, then there exists no polynomial-time quantum-PAC learning algorithm for the class ${TC}^0_2$ , i.e., depth-2 ${TC}^0$ circuits. The main technique in this result is to establish a connection between the quantum security of public-key encryption schemes and the learnability of a concept class that consists of decryption functions of the cryptosystem. Our results show that quantum resources do not give an exponential improvement to learning constant-depth polynomial-sized neural networks. This also gives a strong (conditional) negative answer to one of the “Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson https://www.scottaaronson.com/writings/qchallenge.html, 2005.In this paper, we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of probably approximately correct (PAC) learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1. Hardness of PAC learning ${AC}^0$ and ${TC}^0$ under the uniform distribution. Our first result concerns the concept class ${TC}^0$ (resp., ${AC}^0$), the class of constant-depth, polynomial-sized circuits with unbounded fan-in majority gates (resp., ${AND}, {OR}, {NOT}$ gates). We show the following: if there exists no quantum (quasi-)polynomial-time algorithm to solve the ring-learning with errors (${RLWE}$) problem, then there exists no (quasi-)polynomial-time quantum learning algorithm for ${TC}^0$; and if there exists no $2^{O(d^{1/\eta})}$-time quantum algorithm to solve ${RLWE}$ with dimension $d = O(polylog n)$ (for every constant $\eta > 2$), then there exists no $O(n^{ \log^{\nu} n} )$-time quantum learning algorithm for $poly(n)$-sized ${AC}^0$ circuits (for a constant $\nu>0$), matching the classical upper bound of Linial, Mansour and Nisan [J. ACM, 40 (1993), pp. 607--620], where the learning algorithms are under the uniform distribution (even with access to quantum membership queries). The main technique in these results uses an explicit family of pseudorandom functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2. Hardness of learning ${TC}^0_2$ in the PAC setting. Our second result shows that if there exists no quantum polynomial-time algorithm for the ${LWE}$ problem, then there exists no polynomial-time quantum-PAC learning algorithm for the class ${TC}^0_2$, i.e., depth-2 ${TC}^0$ circuits. The main technique in this result is to establish a connection between the quantum security of public-key encryption schemes and the learnability of a concept class that consists of decryption functions of the cryptosystem. Our results show that quantum resources do not give an exponential improvement to learning constant-depth polynomial-sized neural networks. This also gives a strong (conditional) negative answer to one of the “Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson https://www.scottaaronson.com/writings/qchallenge.html, 2005.

arXiv:1903.02840SIAM Journal on ComputingJan 1, 202111 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}

{QMA}_{{+}}

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.

m(n)=ω(1)

and every error bound

\varepsilon(n)

that stays below

1/2

by at least an inverse polynomial, there is a positive function

δ

with

δ(n)=O\bigl(\min\{(\log m/m)^{1/4},\ \sqrt{\log m/m}\,/(1/2-\varepsilon(n))\}\bigr)

such that

\mathsf{BQP}_{\varepsilon}/\mathsf{q}m \subsetneq \mathsf{BQP}_{\varepsilon + δ}/\mathsf{q}m

; for constant

\varepsilon

the gap is

O(\sqrt{\log m/m})

. Here,

\mathsf{BQP}_\varepsilon/\mathsf{q}m

is the class of languages recognizable with error at most

\varepsilon(n)

by a polynomial-time quantum algorithm with an

m(n)

-qubit advice state that only depends on the input length

n

. We show this by proving a stronger separation

\mathsf{P}_{\varepsilon+δ}/\mathsf{r} m \not\subset \mathsf{BQP}_{\varepsilon}/\mathsf{q} m

, where

\mathsf{P}_{\varepsilon}/\mathsf{r}m

is the class of languages recognizable with error at most

\varepsilon(n)

by a deterministic polynomial-time algorithm with an

m(n)

-bit advice string sampled from a distribution that depends only on

n

In this paper, we study the relationship between advice in the form of a training set and classical advice. We do this by analyzing the class

\mathsf{BPP/samp}

and certain variants of it. Specifically, our main result demonstrates that

\mathsf{BPP/samp}

is a proper subset of the class

\mathsf{P/poly}

, which implies that advice in the form of a training set is strictly weaker than classical advice. This result remains valid when considering quantum advice and a quantum generalization of the training set. Finally, leveraging the insights from our proofs, we identify both sufficient and necessary complexity-theoretic assumptions for the existence of concept classes that exhibit a quantum learning speed-up. We consider both the worst-case setting, where accurate results are required for all inputs, and the average-case setting.

{AC}^0

and

{TC}^0

under the uniform distribution. Our first result concerns the concept class

{TC}^0

(resp.,

{AC}^0

), the class of constant-depth, polynomial-sized circuits with unbounded fan-in majority gates (resp.,

{AND}, {OR}, {NOT}

gates). We show the following: if there exists no quantum (quasi-)polynomial-time algorithm to solve the ring-learning with errors (

{RLWE}

) problem, then there exists no (quasi-)polynomial-time quantum learning algorithm for

{TC}^0

; and if there exists no

2^{O(d^{1/\eta})}

-time quantum algorithm to solve

{RLWE}

with dimension

d = O(polylog n)

(for every constant

\eta > 2

), then there exists no

O(n^{ \log^{\nu} n} )

-time quantum learning algorithm for

poly(n)

-sized

{AC}^0

circuits (for a constant

\nu>0

), matching the classical upper bound of Linial, Mansour and Nisan [J. ACM, 40 (1993), pp. 607--620], where the learning algorithms are under the uniform distribution (even with access to quantum membership queries). The main technique in these results uses an explicit family of pseudorandom functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2. Hardness of learning

{TC}^0_2

in the PAC setting. Our second result shows that if there exists no quantum polynomial-time algorithm for the

{LWE}

problem, then there exists no polynomial-time quantum-PAC learning algorithm for the class

{TC}^0_2

, i.e., depth-2

{TC}^0

circuits. The main technique in this result is to establish a connection between the quantum security of public-key encryption schemes and the learnability of a concept class that consists of decryption functions of the cryptosystem. Our results show that quantum resources do not give an exponential improvement to learning constant-depth polynomial-sized neural networks. This also gives a strong (conditional) negative answer to one of the “Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson https://www.scottaaronson.com/writings/qchallenge.html, 2005.