---
abstract: |
    We prove the following surprising result: given any quantum state $\rho$ on $n$ qubits, there exists a local Hamiltonian $H$ on $\operatorname*{poly}\left(
    n\right)  $ 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 $\mathsf{BQP/qpoly}\subseteq\mathsf{QMA/poly}$, which supersedes the previous result of Aaronson that $\mathsf{BQP/qpoly}\subseteq\mathsf{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 ‘$\mathsf{QMA}_{\mathsf{+}}$ 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\left(
    n\right)  $ functions $f_{1},\ldots,f_{m}\in S$, such that each $f_{i}$ is the unique function in $S$ compatible with $O\left(  \log\left\vert S\right\vert
    \right)  $ input/output constraints.
author:
- |
    Scott Aaronson[^1]\
    MIT
- |
    Andrew Drucker[^2]\
    MIT
bibliography:
- 'thesis.bib'
title: A Full Characterization of Quantum Advice
---

Introduction\[INTRO\]
=====================

> *How much classical information is needed to specify a quantum state of* $n$ *qubits?*

This question has inspired a rich and varied set of responses, in part because it can be interpreted in many ways.  If we want to specify a quantum state $\rho$ *exactly*, then of course the answer is ‘an infinite amount,’ since amplitudes in quantum mechanics are continuous.  A natural compromise is to try to specify $\rho$ *approximately*, i.e., to give a description which yields a state $\widetilde{\rho}$ whose statistical behavior is close to that of $\rho$ under every measurement. (This statement is captured by the requirement that $\rho$ and $\widetilde{\rho}$ are close under the so-called *trace distance* metric.)  But it is not hard to see that even for this task, we still need to use an exponential (in $n$) number of classical bits.

This fact can be viewed as a disappointment, but also as an opportunity, since it raises the prospect that we might be able to encode massive amounts of information in physically compact quantum states: for example, we might hope to store $2^{n}$ classical bits in $n$ qubits.  But an obvious practical requirement is that we be able to retrieve the information reliably, and this rules out the hope of significant ‘quantum compression’ of classical strings, as shown by a landmark result of Holevo [@holevo] from 1973.  Consider a sender Alice and a recipient Bob, with a one-way quantum channel between them.  Then Holevo’s Theorem says that, if Alice wants to encode an $n$-bit classical string $x$ into an $m$-qubit quantum state $\rho_{x}$, in such a way that Bob can retrieve $x$ (with probability $2/3$, say) by measuring $\rho_{x}$, then Alice must take $m\geq n-O\left(  1\right)  $ (or $m\geq
n/2-O\left(  1\right)  $, if Alice and Bob share entanglement).  In other words, for this communication task, quantum states offer essentially no advantage over classical strings. In 1999, Ambainis et al. [@antv] generalized Holevo’s result as follows: even if Bob wants to learn only a *single bit* $x_{i}$ of $x=x_{1}\ldots x_{n}$ (for some $i\in\left[
n\right]  $ unknown to Alice), and is willing to destroy the state $\rho_{x}$ in the process of learning that bit, Alice still needs to send $m=\Omega
\left(  n\right)  $ qubits for Bob to succeed with high probability.

These results say that the exponential descriptive complexity of quantum states cannot be effectively harnessed for classical data storage, but they do not bound the number of practically meaningful ‘degrees of freedom’ in a quantum state used for purposes other than storing data.  For example, a quantum state could be useful for computation, or it could be a physical system worthy of study in its own right.  The question then becomes, what useful information *can* we give about an $n$-qubit state using a ‘reasonable’ number (say, $\operatorname*{poly}\left(  n\right)  $) of classical bits?

One approach to this question is to identify special subclasses of quantum states for which a faithful approximation can be specified using only $\operatorname*{poly}\left(  n\right)  $ bits.  This has been done, for example, with matrix product states [@vidal] and ‘tree states’ [@aar:mlin].  A second approach is to try to describe an *arbitrary* $n$-qubit state $\rho$ concisely, in such a way that the state $\widetilde{\rho}$ recovered from the description is close to $\rho$ with respect to some natural subclass of *measurements*.  This has been done for specific classes like the ‘pretty good measurements’ of Hausladen and Wootters [@hausladen].  A more ambitious goal in this vein, explored by Aaronson in two previous works [@aar:adv; @aar:learn] and continued in the present paper, is to give a description of an $n$-qubit state $\rho$ which yields a state $\widetilde{\rho}$ that behaves approximately like $\rho$ with respect to all (binary) measurements performable by quantum circuits of ‘reasonable’ size—say, of size at most $n^c$, for some fixed $c > 0$. Then if $c$ is taken large enough, $\widetilde{\rho}$ is arguably ‘just as good’ as $\rho$ for practical purposes.

Certainly we can achieve this goal using $2^{n^{c + O(1)}}$ bits: simply give approximations to the measurement statistics for every size-$n^c$ circuit.  However, the results of Holevo [@holevo] and Ambainis et al. [@antv] suggest that a much more succinct description might be possible.  This hope was realized by Aaronson [@aar:adv], who gave a description scheme in which an $n$-qubit state can be specified using $\operatorname*{poly}\left(n\right)$ classical bits. There is a significant catch in Aaronson’s result, though: the encoder Alice and decoder Bob both need to invest exponential amounts of computation.

In a subsequent paper [@aar:learn], Aaronson gave a closely-related result which significantly reduces the computational requirements: now Alice can generate her message in polynomial time (for fixed $c$).  Also, while Bob cannot necessarily construct the state $\widetilde{\rho}$ efficiently on his own, if he is presented with such a state (by an untrusted prover, say), Bob can *verify* the state in polynomial time.  The catch in this result is a weakened approximation guarantee: Bob cannot use $\widetilde{\rho}$ to predict the outcomes of *all* the measurements defined by size-$n^c$ circuits, but only *most* of them (with respect to a samplable distribution used by Alice in the encoding process).  Aaronson [@aar:adv; @aar:learn] conjectured that the tradeoff between this result and the previous one revealed an inherent limit to quantum compression.

Our Quantum Information Result
------------------------------

The main result of this paper is that Aaronson’s conjecture was false: one really can get the best of both worlds, and simulate an arbitrary quantum state $\rho$ on all small circuits, using a different state $\widetilde{\rho
}$ that is easy to recognize.  Indeed, we can even take $\widetilde{\rho}$ to be the *ground state of a local Hamiltonian*: that is, the unique pure state $\widetilde{\rho}=\left\vert \psi\right\rangle \left\langle
\psi\right\vert $ on $\operatorname*{poly}\left(  n\right)  $ qubits that is compatible with $\operatorname*{poly}\left(  n\right)  $ local constraints, each involving a constant number of qubits.  In a sense, then, this paper completes a ‘trilogy’ of which [@aar:adv; @aar:learn] were the first two installments.

Here is a formal statement of our result.

\[mainthm0\] Let $c, \varepsilon>0$, and let $\rho$ be any $n$-qubit quantum state.  Then there exists a $2$-local Hamiltonian $H$ on $\operatorname*{poly}\left(n, \frac{1}{\varepsilon}  \right)  $ qubits with unique ground state $\left\vert \psi\right\rangle \left\langle
\psi\right\vert$, and a transformation $C\longrightarrow C^{\prime}$ of quantum circuits, computable in time $\operatorname*{poly}\left( n, 1 / \varepsilon  \right)$ given $H$, such that the following holds: $\left\vert C^{\prime}\left(  \left\vert \psi\right\rangle \left\langle \psi\right\vert \right)  -C\left(  \rho\right)  \right\vert \leq\varepsilon$ for any measurement $C$ definable by a quantum circuit of size $n^c$.  (Here $C\left(  \rho\right)$ is the probability that $C$ accepts $\rho$.)

In other words, the ground states of local Hamiltonians are ‘universal quantum states’ in a very non-obvious sense.  For example, suppose you own a quantum software store, which sells quantum states $\rho
$ that can be fed as input to quantum computers.  Then our result says that *ground states of local Hamiltonians are the only kind of state you ever need to stock*.  What makes this surprising is that being a good piece of quantum software might entail satisfying an exponential number of constraints: for example, if $\rho$ is supposed to help a customer’s quantum computer $Q$ evaluate some Boolean function $f:\left\{  0,1\right\}  ^{n}\rightarrow\left\{  0,1\right\}  $, then $Q\left(  \rho , x \right)
$ should output $f\left(  x\right)  $ for *every* input $x\in\left\{
0,1\right\}  ^{n}$.  By contrast, any $k$-local Hamiltonian $H$ can be described as a set of at most ${\binom{n }{k}} = O(n^{k})$ constraints.

One can also interpret Theorem \[mainthm0\] as a statement about communication over quantum channels.  Suppose Alice (who is computationally unbounded) has a classical description of an $n$-qubit state $\rho$.  She would like to describe $\rho$ to Bob (who is computationally bounded), at least well enough for Bob to be able to *simulate* $\rho$ on all quantum circuits of some fixed polynomial size.  However, Alice cannot just send $\rho$ to Bob, since her quantum communication channel is noisy and there is a chance that $\rho$ might get corrupted along the way.   Nor can she send a faithful classical description of $\rho$, since that would require an exponential number of bits. Our result provides an alternative: Alice can send a different quantum state $\sigma$, of $\operatorname*{poly}(n)$ qubits, together with a $\operatorname*{poly}(n)$-bit classical string $x$. Then, Bob can use $x$ to *verify* that $\sigma$ can be used to accurately simulate $\rho$ on all small measurements.

We believe Theorem \[mainthm0\] makes a significant contribution to the study of the effective information content of quantum states.  It does, however, leave open whether a quantum state of $n$ qubits can be efficiently encoded *and* decoded in polynomial time, in a way that is ‘good enough’ to preserve the measurement statistics of measurements defined by circuits of fixed polynomial size.  This remains an important problem for future work.

Impact on Quantum Complexity Theory\[MOTIVATION\]
-------------------------------------------------

The questions addressed in this paper, and our results, are naturally phrased and proved in terms of complexity classes.  In recent years, researchers have defined quantum complexity classes as a way to study the ‘useful information’ embodied in quantum states. One approach is to study the power of nonuniform *quantum advice*.  The class $\mathsf{BQP/qpoly}$, defined by Nishimura and Yamakami [@ny], consists of all languages decidable in polynomial time by a quantum computer, with the help of a $\operatorname*{poly}\left(  n\right) $-qubit advice state that depends only on the input length $n$. This class is analogous to the classical class $\mathsf{P/poly}$. To understand the role of quantum information in determining the power of $\mathsf{BQP/qpoly}$, a useful benchmark of comparison is the class $\mathsf{BQP/poly}$ of decision problems efficiently solvable by a quantum computer with $\operatorname*{poly}\left(  n\right) $ bits of *classical* advice. It is open whether $\mathsf{BQP/qpoly} =
\mathsf{BQP/poly}$.

A second approach studies the power of quantum *proof systems*, by analogy with the classical class $\mathsf{NP}$.  Kitaev (unpublished, 1999) defined the complexity class now called $\mathsf{QMA}$, for ‘Quantum Merlin-Arthur’. This is the class of decision problems for which a ‘yes’ answer can be proved by exhibiting a *quantum witness state* (or *quantum proof*) $\left\vert \psi\right\rangle $, on $\operatorname*{poly}\left(  n\right)  $ qubits, which is then checked by a skeptical polynomial-time quantum verifier. A natural benchmark class is $\mathsf{QCMA}$ (for ‘Quantum Classical Merlin-Arthur’), defined by Aharonov and Naveh [@an]. This is the class of decision problems for which a ‘yes’ answer can be checked by a *quantum* verifier who receives a *classical* witness.  Here the natural open question is whether $\mathsf{QMA} = \mathsf{QCMA}$.

In this paper we prove a new upper bound on $\mathsf{BQP/qpoly}$:

\[mainthm1\]$\mathsf{BQP/qpoly}\subseteq\mathsf{QMA/poly}$.

Previously Aaronson showed in [@aar:adv] that $\mathsf{BQP/qpoly}
\subseteq\mathsf{PP/poly}$, and showed in [@aar:learn] that $\mathsf{BQP/qpoly}$ is contained in the ‘heuristic’ class $\mathsf{HeurQMA/poly}$.  Theorem \[mainthm1\] supersedes both of these earlier results.

Theorem \[mainthm1\] says that one can always replace polynomial-size quantum advice by polynomial-size *classical* advice, together with a polynomial-size quantum *witness* (or equivalently, *untrusted* quantum advice).  Indeed, we can *characterize* the class $\mathsf{BQP/qpoly}$, as equal to the subclass of $\mathsf{QMA/poly}$ in which the quantum witness state $\left\vert \psi_{n}\right\rangle $ can only depend on the input length $n$.[^3]

Using Theorem \[mainthm1\], we also obtain several other results for quantum complexity theory:

1.  Without loss of generality, every quantum advice state can be taken to be the ground state of some local Hamiltonian $H$.  (This essentially follows by combining our $\mathsf{BQP/qpoly}\subseteq\mathsf{QMA/poly}$ result with the result of Kitaev that <span style="font-variant:small-caps;">Local Hamiltonians</span> is $\mathsf{QMA}$-complete.)

2.  It is open whether for every local Hamiltonian $H$ on $n$ qubits, there exists a quantum circuit of size $\operatorname*{poly}\left(  n\right) $ that prepares a ground state of $H$. It is easy to show that an affirmative answer would imply $\mathsf{QMA}=\mathsf{QCMA}$. As a consequence of Theorem \[mainthm1\], we can show that an affirmative answer would also imply $\mathsf{BQP/qpoly}=\mathsf{BQP/poly}$—thereby establishing a previously-unknown connection between quantum proofs and quantum advice.

3.  We generalize Theorem \[mainthm1\] to show that $\mathsf{QCMA/qpoly}\subseteq\mathsf{QMA/poly}$.

4.  We also use our new characterization of $\mathsf{BQP/qpoly}$ to prove a quantum analogue of the Karp-Lipton Theorem [@kl].  Recall that the Karp-Lipton Theorem says that if $\mathsf{NP}\subset\mathsf{P/poly}$, then the polynomial hierarchy collapses to the second level.  Our ‘Quantum Karp-Lipton Theorem’ says that if $\mathsf{NP}\subset\mathsf{BQP/qpoly}$ (that is, $\mathsf{NP}$-complete problems are efficiently solvable with the help of quantum advice), then $\mathsf{\Pi
    }_{\mathsf{2}}^{\mathsf{P}}\subseteq\mathsf{QMA}^{\mathsf{P{}romiseQMA}}$.  As far as we know, this is the first nontrivial result to derive unlikely consequences from a hypothesis about quantum machines being able to solve $\mathsf{NP}$-complete problems in polynomial time.

Finally, using our result, we are able to explain a previously-mysterious aspect of a 2000 paper of Watrous [@watrous].  Watrous gave the best-known example of a problem in $\mathsf{QMA}$ that is not *obviously* in $\mathsf{QCMA}$—that is, for which quantum proofs actually seem to help.[^4]  This problem is called <span style="font-variant:small-caps;">Group Non-Membership</span>, and is defined as follows: Arthur is given a finite *black-box group* $G$ and a subgroup $H\leq
G$ (specified by their generators), as well as an element $x\in G$.  His task is to verify that $x\notin H$.  It is known that, as a black-box problem, this problem is not in $\mathsf{MA}$.  But Watrous showed that <span style="font-variant:small-caps;">Group Non-Membership</span> is in $\mathsf{QMA}$, since Merlin can always persuade Arthur that $x\notin H$ by giving him the following quantum proof:$$\left\vert H\right\rangle =\frac{1}{\sqrt{\left\vert H\right\vert }}\sum_{h\in
H}\left\vert h\right\rangle .$$ Arthur’s verification procedure consists of two tests.  In the first test, Arthur *assumes* that Merlin sent $\left\vert H\right\rangle $, and then uses $\left\vert H\right\rangle $ to decide whether $x\in H$.  The test is a simple, beautiful illustration of the power of quantum algorithms.  The second test in Watrous’s protocol confirms that Merlin really sent $\left\vert H\right\rangle
$ or at least, a state which is ‘equivalent’ for purposes of the first test.  This second test and its analysis are considerably more involved, and seem less ‘natural’.  So the question arises: can the second test be omitted?

Using our results, we find that a slightly weaker version of Watrous’s second test can be derived in an almost *automatic* way from his first test, as follows. If we assume that the black-box group $H = H_n$ is fixed for each input length, then <span style="font-variant:small-caps;">Group Non-Membership</span> is in $\mathsf{BQP/qpoly}$, by letting $\left\vert H_n\right\rangle$ as above be the trusted advice for length $n$ and using Watrous’ first test as the $\mathsf{BQP/qpoly}$ algorithm. Then Theorem \[mainthm1\] (which can be readily adapted to the black-box setting) tells us that Group Non-Membership is in $\mathsf{QMA/poly}$ as well.

Proof Overview\[TECHNIQUES\]
----------------------------

We now give an overview of the proof Theorem \[mainthm1\], that $\mathsf{BQP/qpoly}\subseteq\mathsf{QMA/poly}$.  As we will explain, our proof rests on a new idea we call the ‘majority-certificates’ technique, which is not specifically quantum and which seems likely to find other applications.

We begin with a language $L\in\mathsf{BQP/qpoly}$ and, for $n>0$, a $\operatorname*{poly}(n)$-size quantum circuit $Q\left(  x,  \xi \right)  $ that computes $L(x)$ with high probability when given the ‘correct’ advice state $\xi
=\rho_{n}$ on $\operatorname*{poly}\left(  n\right)
$ qubits.  The challenge, then, is to force Merlin to supply a witness state $\rho'$ that behaves like $\rho_{n}$ on every input $x\in\left\{  0,1\right\}  ^{n}$.

Every potential advice state $\xi$ defines a function $f_{\xi}:\left\{  0,1\right\}
^{n}\rightarrow\left[  0,1\right]  $, by $f_{\xi}(x):=\Pr\left[  Q\left(  x, \xi \right)
=1\right]  $.  For each such $\xi$, let $\widehat{f}_{\xi}(x):=\left[  f_{\xi }(x)\geq1/2\right]  $ be the Boolean function obtained by rounding $f_{\xi}$.  As a simplification, suppose that Merlin is restricted to sending an advice state $\xi$ for which $f_{\xi
}(x)\notin\left(  1/3,2/3\right)  $: that is, an advice state which renders a ‘clear opinion’ about every input $x$.  (This simplification helps to explain the main ideas, but does not follow the actual proof.)  Let $S$ be the set of all Boolean functions $f:\left\{  0,1\right\}  ^{n}\rightarrow\left\{
0,1\right\}  $ that are expressible as $\widehat{f}_{\xi }$ for some such advice state $\xi
$.  Then $S$ includes the ‘target function’ $f^{\ast}:=L_{n}$ (the restriction of $L$ to inputs of length $n$), as well as a potentially-large number of other functions.  However, we claim $S$ is not *too* large: $\left\vert S\right\vert \leq2^{\operatorname*{poly}\left(  n\right)  }$.  This bound on the ‘effective information content’ of quantum states was derived previously by Aaronson [@aar:adv; @aar:learn], building on the work of Ambainis et al. [@antv].

One might initially hope that, just by virtue of the size bound on $S$, we could find some set of $\operatorname*{poly}(n)$ values$$\left(  x_{1},f^{\ast}\left(  x_{1}\right)  \right)  ,\ldots,\left(
x_{k},f^{\ast}\left(  x_{t}\right)  \right)$$ which *isolate* $f^{\ast}$ in $S$—that is, which differentiate $f^{\ast}$ from all other members of $S$.  In that case, the trusted classical advice could simply specify those values, as ‘tests’ for Arthur to perform on the quantum state sent by Merlin.  Alas, this hope is unfounded in general.  For consider the case where $f^{\ast}$ is the identically-zero function, and $S$ consists of $f^{\ast}$ along with the ‘point function’ $f_{y}$ (which equals $1$ on $y$ and $0$ elsewhere), for all $y\in\left\{
0,1\right\}  ^{n}$.  Then $f^{\ast}$ can only be isolated in $S$ by specifying its value at *every* point!

Luckily, this counterexample leads us to a key observation.  Although $f$ is not isolatable in $S$ by a small number of values, each point function $f_{y}$ *can* be isolated (by its value at $y$), and moreover, $f_{y}$ is quite ‘close’ to $f$.  In fact, if we choose any three distinct strings $x,y,z$, then $f^{\ast}=\operatorname*{MAJ}\left(  f_{x},f_{y},f_{z}\right)  $.  (Of course if $f^{\ast}$ were the identically-zero function, it could be easily specified with classical advice!  But $f^{\ast}$ could have been any function in this example.)

This suggests a new, more indirect approach to our general problem: we try to express $f$ as the pointwise majority vote $$f^{\ast}\left(  x\right)  \equiv\operatorname*{MAJ}\left(  f_{1}\left(
x\right)  ,\ldots,f_{m}\left(  x\right)  \right)  ,$$ of a small number ($m=O\left(  n\right)  $, say) of *other* functions $f_{1},\ldots,f_{m}$ in $S$, where each $f_{i}$ is isolatable in $S$ by specifying at most $k=O\left(  \log\left\vert S\right\vert \right)  $ of its values.  Indeed, we will show this can *always* be done.  We call this key result the *majority-certificates lemma*; we will say more about its proof and its relation to earlier work in Section \[MAJCERDISCUSSION\].

With this lemma in hand, we can solve our (artificially simplified) problem: in the $\mathsf{QMA/poly}$ protocol for $L$, we use certificates which isolate $f_{1},\ldots,f_{m}\in S$ as above as the classical advice for Arthur.  Arthur requests from Merlin each of the $m$ states $\xi_1, \ldots, \xi_m$ such that $f_{i}=f_{\xi_i}$, and verifies that he receives appropriate states by checking them against the certificates.  This involves multiple measurements of each $\xi_i
$—and an immediate difficulty is that, since measurements are irreversible in quantum mechanics, the process of verifying the witness state might also destroy it.   However, we get around this difficulty by appealing to a result of Aharonov and Regev [@ar].  This result essentially says that a $\mathsf{QMA}$ protocol in which Arthur is granted the (physically unrealistic) ability to perform ‘non-destructive measurements’ on his witness state, can be efficiently simulated by an ordinary $\mathsf{QMA}$ protocol.

To build intuition, we will begin (in Section \[MAJCER\]) by proving the majority-certificates lemma for Boolean functions, as described above.  However, to remove the artificial simplification we made and prove Theorem \[mainthm1\], we will need to generalize the lemma substantially, to a statement about possibly-infinite sets of real-valued functions $f:\left\{
0,1\right\}  ^{n}\rightarrow\left[  0,1\right]  $.  In the general version, the hypothesis that $S$ is finite and not too large gets replaced by a more subtle assumption: namely, an upper bound on the so-called *fat-shattering dimension* of $S$.  To prove our generalization, we use powerful results of Alon et al. [@abch] and Bartlett and Long [@bartlettlong] on the learnability of real-valued functions.  We then use a bound on the fat-shattering dimension of real-valued functions defined by quantum states (from Aaronson [@aar:learn], building on Ambainis et al. [@antv]). Figure \[yqpflow\] shows the overall dependency structure of the proof.

\[ptb\]

[yqpflow2.eps]{}

Majority-Certificates Lemma in Context\[MAJCERDISCUSSION\]
----------------------------------------------------------

The majority-certificates lemma is closely related to the seminal notion of *boosting* [@schapire] from computational learning theory.  Boosting is a broad topic with a vast literature, but a common ‘generic’ form of the boosting problem is as follows: we want to learn some target function $f^{\ast}$, given sample data of the form $\left(  x,f^{\ast}\left(  x\right)
\right)  $.  We assume we have a *weak learning algorithm* $A^{f^{\ast},\mathcal{D}}$, with the property that, for any probability distribution $\mathcal{D}$ over inputs $x$, with high probability $A$ finds a hypothesis $f\in\mathcal{F}$ which predicts $f^{\ast
}\left(  x\right)  $ ‘reasonably well’ when $x\sim\mathcal{D}$.  The task is to ‘boost’ this weak learner into a *strong* learner $B^{f^{\ast}}$.  The strong learner should output a collection of functions $f_{1},\ldots,f_{m}\in\mathcal{F}$, such that a (possibly-weighted) majority vote over $f_{1}\left(  x\right)  ,\ldots,f_{m}\left(  x\right)  $ predicts $f^{\ast}\left(  x\right)  $ ‘extremely well.’  It turns out [@schapire; @fs_adaboost] that this goal can be achieved in a very general setting.

Our majority-certificates lemma has strengths and weaknesses compared to boosting.  Our assumptions are much milder than those of boosting: rather than needing a weak learner, we assume only that the hypothesis class $S$ is ‘not too large.’  Also, we represent our target function $f^{\ast}$ *exactly* by $\operatorname*{MAJ}\left(
f_{1},\ldots,f_{m}\right)  $, not just approximately.  On the other hand, we do not give an efficient algorithm to *find* our majority-representation. Also, the $f_{i}$’s are not ‘explicitly given’: we only give a way to *recognize* each $f_{i}$, under the assumption that the function purporting to be $f_{i}$ is in fact drawn from the original hypothesis class.

The proof of our lemma also has similarities to boosting.  As an analogue of a ‘weak learner’, we show that for every distribution $\mathcal{D}$, there exists a function $f\in S$ which agrees with the target function $f^{\ast}$ on most $x\sim\mathcal{D}$, *and* which is isolatable in $S$ by specifying $O(\log|S|)$ queries.  Using the Minimax Theorem, we then nonconstructively ‘boost’ this fact into the desired majority-representation of $f^{\ast}$.  We note that Nisan used the Minimax Theorem for boosting in a similar way, in his alternative proof of Impagliazzo’s ‘hard-core set theorem’ (see [@imp_hardcore]).

The majority-certificates lemma is also reminiscent of Bshouty et al.’s algorithm [@bshouty], for learning small circuits in the complexity class $\mathsf{ZPP}^{\mathsf{NP}}$.  Our lemma lacks the algorithmic component of this earlier work, but unlike Bshouty et al., we do not require the functions being learned to come with any succinct labels (such as circuit descriptions).

Organization of the Paper
-------------------------

In Section \[MAJCER\], we prove the Boolean majority-certificates-lemma. In Section \[REALMAJ\], we give our real-valued generalization of this lemma, and in Section \[QADV\] we use it to prove Theorem \[mainthm1\], and state some consequences for quantum complexity theory. Theorem \[mainthm0\] is proved in Section \[LOCALHAM\]. Section \[NERD\] contains some further results for quantum complexity, and the Appendices provide some additional applications of and perspectives on the majority-certificates lemma.

The Majority-Certificates Lemma\[MAJCER\]
=========================================

A *Boolean concept class* is a family of sets $\left\{  S_{n}\right\}
_{n\geq1}$, where each $S_{n}$ consists of Boolean functions $f:\left\{
0,1\right\}  ^{n}\rightarrow\left\{  0,1\right\}  $ on $n$ variables.  Abusing notation, we will often use $S$ to refer directly to a set of Boolean functions on $n$ variables, with the quantification over $n$ being understood.

By a *certificate*, we mean a partial Boolean function $C:\left\{
0,1\right\}  ^{n}\rightarrow\left\{  0,1,\ast\right\}  $.  The *size* of $C$, denoted $\left\vert C\right\vert $, is the number of inputs $x$ such that $C\left(  x\right)  \in\left\{  0,1\right\}  $.  A Boolean function $f:\left\{  0,1\right\}  ^{n}\rightarrow\left\{  0,1\right\}  $ is *consistent* with $C$ if $f\left(  x\right)  =C\left(  x\right)
$ whenever $C\left(  x\right)  \in\left\{  0,1\right\}  $.  Given a set $S$ of Boolean functions and a certificate $C$, let $S\left[  C\right]  $ be the set of all functions $f\in S$ that are consistent with $C$.  Say that a function $f\in S$ is *isolated in* $S$ by the certificate $C$ if $S\left[  C\right]  =\left\{  f\right\}  $.

We now prove a lemma that represents one of the main tools of this paper.

\[Majority-Certificates Lemma\]\[majcer\]Let $S$ be a set of Boolean functions $f:\left\{  0,1\right\}  ^{n}\rightarrow\left\{  0,1\right\}  $, and let $f^{\ast}\in S$.  Then there exist $m=O\left(  n\right)  $ certificates $C_{1},\ldots,C_{m}$, each of size $k=O\left(  \log\left\vert S\right\vert
\right)  $, and functions $f_{1}, \ldots, f_{m} \in S$, such that

1.  $S\left[  C_{i}\right]  = \{f_{i}\}$ all $i\in\left[  m\right]  $;

2.  $\operatorname*{MAJ}\left(  f_{1}\left(  x\right)  ,\ldots
    ,f_{m}\left(  x\right)  \right)  =f^{\ast}\left(  x\right)  $ for all $x\in\left\{  0,1\right\}  ^{n}$.

Our proof of Lemma \[majcer\] relies on the following claim.

\[heurpart\] Let $\mathcal{D}$ be any distribution over inputs $x\in\{0,1\}^{n}$. Then there exists a function $f\in S$ such that

-   $f$ is isolatable in $S$ by a certificate $C$ of size $k=O\left(
    \log\left\vert S\right\vert \right)  $;

-   $\Pr_{x\sim\mathcal{D}}[f(x)\neq f^{\ast}(x)]\leq\frac{1}{10}$.

Lemma \[majcer\] follows from Claim \[heurpart\] by a boosting-type argument, as follows. Consider a two-player game where:

-   Alice chooses a certificate $C$ of size $k$ that isolates some $f\in S$, and

-   Bob simultaneously chooses an input $x\in\left\{  0,1\right\}  ^{n}$.

Alice wins the game if $f\left(  x\right)  =f^{\ast}\left(  x\right)  $. Claim \[heurpart\] tells us that for every mixed strategy of Bob (i.e., distribution $\mathcal{D}$ over inputs), there exists a pure strategy of Alice that succeeds with probability at least $0.9$ against $\mathcal{D}$.  Then by the Minimax Theorem, there exists a mixed strategy for Alice—that is, a probability distribution $\mathcal{C}$ over certificates—that allows her to win with probability at least $0.9$ against *every* pure strategy of Bob.

Now suppose we draw $C_{1},\ldots,C_{m}$ independently from $\mathcal{C}$, isolating functions $f_{1},\ldots,f_{m}$ in $S$. Fix an input $x\in\left\{
0,1\right\}  ^{n}$; then by the success of Alice’s strategy against $x$, and applying a Chernoff bound,$$\Pr_{f_{1},\ldots,f_{m}\sim\pi}\left[  \operatorname*{MAJ}\left(  f_{1}\left(
x\right)  ,\ldots,f_{m}\left(  x\right)  \right)  \neq f^{\ast}(x)\right]
<\frac{1}{2^{n}},$$ provided we choose $m=O\left(  n\right)  $ suitably.  But by the union bound, this means there must be a *fixed* choice of $C_{1},\ldots
,C_{m}$ such that $\operatorname*{MAJ}\left(  f_{1},\ldots,f_{m}\right)
\equiv f^{\ast}(x)$, where each $f_{i}$ is isolated in $S$ by $C_{i}$. This proves Lemma \[majcer\], modulo the Claim.

\[Proof of Claim \[heurpart\]\]By symmetry, we can assume without loss of generality that $f^{\ast}$ is the identically-zero function.  Given the mixed strategy $\mathcal{D}$ of Bob, we construct the certificate $C$ as follows.  Initially $C$ is empty: that is, $C\left(  x\right)  =\ast$ for all $x\in\left\{  0,1\right\}  ^{n}$.  In the first stage, we draw $t=O\left(
\log\left\vert S\right\vert \right)  $ inputs $x_{1},\ldots,x_{t}$ independently from $\mathcal{D}$.  For any $f:\{0,1\}^{n}\rightarrow
\{0,1\}$, let$$w_{f}:=\Pr_{x\sim\mathcal{D}}\left[  f\left(  x\right)  =1\right]  .$$ Now suppose $f$ is such that $w_{f}>0.1$.  Then$$\Pr_{x_{1},\ldots,x_{t}\sim\mathcal{D}}\left[  f\left(  x_{1}\right)
=0\wedge\cdots\wedge f\left(  x_{t}\right)  =0\right]  <0.9^{t}\leq\frac
{1}{\left\vert S\right\vert },$$ provided $t\geq\log_{10/9}\left\vert S\right\vert $.  So by the union bound, there must be a *fixed* choice of $x_{1},\ldots,x_{t}$ that kills off every $f\in S$ such that $w_{f}>0.1$—that is, such that $f\left(
x_{1}\right)  =\cdots=f\left(  x_{t}\right)  =0$ implies $w_{f}\leq0.1$.  Fix that $x_{1},\ldots,x_{t}$, and set $C\left(  x_{i}\right)  :=0$ for all $i\in\left[  t\right]  $.

In the second stage, our goal is just to isolate some *particular* function $f\in S\left[  C\right]  $.  We do this recursively as follows.  If $\left\vert S\left[  C\right]  \right\vert =1$ then we are done.  Otherwise, there exists an input $x$ such that $f\left(  x\right)  =0$ for some $f\in
S\left[  C\right]  $ and $f\left(  x\right)  =1$ for other $f\in S\left[
C\right]  $.  If setting $C\left(  x\right)  :=0$ decreases $\left\vert
S\left[  C\right]  \right\vert $ by at least a factor of $2$, then set $C\left(  x\right)  :=0$; otherwise set $C\left(  x\right)  :=1$.  Since $S\left[  C\right]  $ can halve in size at most $\log_{2}\left\vert
S\right\vert $ times, this procedure terminates after at most $\log
_{2}\left\vert S\right\vert $ steps with $\left\vert S\left[  C\right]
\right\vert =1$.

The end result is a certificate $C$ of size $O\left(  \log\left\vert
S\right\vert \right)  $, which isolates a function $f$ in $S$ for which $w_{f}\leq1/10$.  We have therefore found a pure strategy for Alice that fails with probability at most $1/10$ against $\mathcal{D}$, as desired.

Extension to Real Functions\[REALMAJ\]
======================================

In this section, we extend the majority-certificates lemma from Boolean functions to real-valued functions $f:\left\{  0,1\right\}  ^{n}\rightarrow\left[  0,1\right]  $.  We will need this extension for the application to quantum advice in Section \[QADV\].  In proving our extension we will have to confront several new difficulties.  Firstly, the concept classes $S$ that we want to consider can now contain a *continuum* of functions—so Lemma \[majcer\], which assumed that $S$ was finite and constructed certificates of size $O\left(  \log\left\vert
S\right\vert \right)  $, is not going to work.  In Section \[LEARNBACK\], we review notions from computational learning theory, including fat-shattering dimension and $\varepsilon$-covers, which (combined with results of Alon et al. [@abch] and Bartlett and Long [@bartlettlong]) can be used to get around this difficulty.  Secondly, it is no longer enough to isolate a function $f_{i}\in S$ that we are interested in; instead we will need to ‘safely’ isolate $f_{i}$, which roughly speaking means that (i) $f_{i}$ is consistent with some certificate $C$, and (ii) any $f\in S$ that is even *approximately* consistent with $C$ is close to $f_{i}$.  In Section \[SAFEWINNOW\], we prove a ‘safe winnowing lemma’ that can be used for this purpose.  Finally, in Section \[THELEMMA\], we put the pieces together to prove a real-valued majority-certificates lemma.

Background from Learning Theory\[LEARNBACK\]
--------------------------------------------

A *p-concept class* $S$ is a family of functions $f:\left\{
0,1\right\}  ^{n}\rightarrow\left[  0,1\right]  $ (as usual, quantification over all $n$ is understood).  Given functions $f,g:\left\{  0,1\right\}
^{n}\rightarrow\left[  0,1\right]  $ and a subset of inputs $X\subseteq
\left\{  0,1\right\}  ^{n}$, we will be interested in three measures of the distance between $f$ and $g$ restricted to $X$:$$\begin{aligned}
\Delta_{\infty}\left(  f,g\right)  \left[  X\right]   &  :=\max_{x\in
X}\left\vert f\left(  x\right)  -g\left(  x\right)  \right\vert ,\\
\Delta_{2}\left(  f,g\right)  \left[  X\right]   &  :=\sqrt{\sum_{x\in
X}\left(  f\left(  x\right)  -g\left(  x\right)  \right)  ^{2}},\\
\Delta_{1}\left(  f,g\right)  \left[  X\right]   &  :=\sum_{x\in X}\left\vert
f\left(  x\right)  -g\left(  x\right)  \right\vert .\end{aligned}$$ For convenience, we define $\Delta_{\infty}\left(  f,g\right)  :=\Delta
_{\infty}\left(  f,g\right)  \left[  \left\{  0,1\right\}  ^{n}\right]  $, and similarly for $\Delta_{2}\left(  f,g\right)  $ and $\Delta_{1}\left(
f,g\right)  $.  Also, given a distribution $\mathcal{D}$ over $\left\{
0,1\right\}  ^{n}$, define$$\Delta_{1}\left(  f,g\right)  \left\langle \mathcal{D}\right\rangle
:=\operatorname*{E}_{x\sim\mathcal{D}}\left[  \left\vert f\left(  x\right)
-g\left(  x\right)  \right\vert \right]  .$$ Finally we will need the notions of coverability and fat-shattering dimension.

\[Coverability\]Let $S$ be a p-concept class.  The subset $C\subseteq S$ is an $\varepsilon$-cover for $S$ if for all $f\in S$, there exists a $g\in
C$ such that $\Delta_{\infty}\left(  f,g\right)  \leq\varepsilon$.  We say $S$ is coverable if for all $\varepsilon>0$, there exists an $\varepsilon
$-cover for $S$ of size $2^{\operatorname*{poly}\left(  n,1/\varepsilon
\right)  }$.

\[Fat-Shattering Dimension\]Let $S$ be a p-concept class and $\varepsilon>0$ be a real number.  We say the set $A\subseteq\left\{  0,1\right\}  ^{n}$ is $\varepsilon$-shattered by $S$ if there exists a function $r:A\rightarrow
\left[  0,1\right]  $ such that for all $2^{\left\vert A\right\vert }$ Boolean functions $g:A\rightarrow\left\{  0,1\right\}  $, there exists a p-concept $f\in S$ such that for all $x\in A$, we have $f\left(  x\right)
\leq r\left(  x\right)  -\varepsilon$ whenever $g\left(  x\right)  =0$ and $f\left(  x\right)  \geq r\left(  x\right)  +\varepsilon$ whenever $g\left(
x\right)  =1$.  Then the $\varepsilon$-fat-*shattering dimension* of $S$, or $\operatorname*{fat}_{\varepsilon}\left(  S\right)  $, is the size of the largest set $\varepsilon$-shattered by $S$.  We say $S$ is bounded-dimensional if $\operatorname*{fat}_{\varepsilon}\left(  S\right)
\leq\operatorname*{poly}\left(  n,1/\varepsilon\right)  $ for all $\varepsilon>0$.

The following central result was shown by Alon et al. [@abch] (see also [@tewari]).

\[[@abch]\]\[coverthm\]Every p-concept class $S$ has an $\varepsilon
$-cover of size $\exp\left[  O\left(  \left(  n+\log1/\varepsilon\right)
\operatorname*{fat}_{\varepsilon/4}\left(  S\right)  \right)  \right]  $.  So in particular, if $S$ is bounded-dimensional then $S$ is coverable.

Building on the work of Alon et al. [@abch], Bartlett and Long [@bartlettlong] then proved the following:

\[[@bartlettlong]\]\[blthm\]Let $S$ be a p-concept class and $\mathcal{D}$ be a distribution over $\left\{  0,1\right\}  ^{n}$.  Fix an $f:\left\{  0,1\right\}  ^{n}\rightarrow\left[  0,1\right]  $ (not necessarily in $S$) and an error parameter $\alpha>0$.  Suppose we form a set $X\subseteq\left\{  0,1\right\}  ^{n}$ by choosing $m$ inputs independently with replacement from $\mathcal{D}$.  Then there exists a positive constant $K$ such that, with probability at least $1-\delta$ over $X$, any hypothesis $h\in S$ that minimizes $\Delta_{1}\left(  h,f\right)
\left[  X\right]  $ also satisfies$$\Delta_{1}\left(  h,f\right)  \left\langle \mathcal{D}\right\rangle \leq
\alpha+\inf_{g\in S}\Delta_{1}\left(  g,f\right)  \left\langle \mathcal{D}\right\rangle ,$$ provided$$m\geq\frac{K}{\alpha^{2}}\left(  \operatorname*{fat}\nolimits_{\alpha
/5}\left(  S\right)  \log^{2}\frac{1}{\alpha}+\log\frac{1}{\delta}\right)  .$$

Theorem \[blthm\] has the following corollary, which is similar to Corollary 2.4 of Aaronson [@aar:learn], but more directly suited to our purposes here.[^5]

\[occamcor\]Let $S$ be a p-concept class and $\mathcal{D}$ be a distribution over $\left\{  0,1\right\}  ^{n}$.  Fix an $f\in S$ and an error parameter $\varepsilon>0$.  Suppose we form a set $X\subseteq\left\{
0,1\right\}  ^{n}$ by choosing $m$ inputs independently with replacement from $\mathcal{D}$.  Then there exists a positive constant $K$ such that, with probability at least $1-\delta$ over $X$, any hypothesis $h\in S$ that satisfies $\Delta_{\infty}\left(  h,f\right)  \left[  X\right]  \leq
\varepsilon$ also satisfies $\Delta_{1}\left(  h,f\right)  \left\langle
\mathcal{D}\right\rangle \leq11\varepsilon$, provided$$m\geq\frac{K}{\varepsilon^{2}}\left(  \operatorname*{fat}\nolimits_{\varepsilon}\left(  S\right)  \log^{2}\frac{1}{\varepsilon}+\log\frac{1}{\delta}\right)  .$$

Let $S^{\ast}$ be the p-concept class consisting of all functions $g:\left\{
0,1\right\}  ^{n}\rightarrow\left[  0,1\right]  $ for which there exists an $f\in S$ such that $\Delta_{\infty}\left(  g,f\right)  \leq\varepsilon$.  Fix an $f\in S$ and a distribution $\mathcal{D}$, and let $X$ be chosen as in the statement of the corollary.  Suppose we choose a hypothesis $h\in
S$ such that $\Delta_{\infty}\left(  h,f\right)  \left[  X\right]
\leq\varepsilon$.  Then there exists a function $g\in S^{\ast}$ such that $g\left(  x\right)  =h\left(  x\right)  $ for all $x\in X$.  This $g$ is simply obtained by setting $g\left(  x\right)  :=h\left(  x\right)  $ if $x\in X$ and $g\left(  x\right)  :=f\left(  x\right)  $ otherwise.  In particular, note that $\Delta_{1}\left(  h,g\right)  \left[  X\right]  =0$, which means that $h$ minimizes the functional $\Delta_{1}\left(  h,g\right)
\left[  X\right]  $ over all hypotheses in $S$ (and indeed in $S^{\ast}$).  By Theorem \[blthm\], this implies that with probability at least $1-\delta$ over $X$,$$\Delta_{1}\left(  h,g\right)  \left\langle \mathcal{D}\right\rangle \leq
\alpha+\inf_{u\in S^{\ast}}\Delta_{1}\left(  u,g\right)  \left\langle
\mathcal{D}\right\rangle =\alpha$$ for all $\alpha>0$, provided we take$$m\geq\frac{K}{\alpha^{2}}\left(  \operatorname*{fat}\nolimits_{\alpha
/5}\left(  S^{\ast}\right)  \log^{2}\frac{1}{\alpha}+\log\frac{1}{\delta
}\right)  .$$ Here we have used the fact that $g\in S^{\ast}$, and hence$$\inf_{u\in S^{\ast}}\Delta_{1}\left(  u,g\right)  \left\langle \mathcal{D}\right\rangle =0.$$ So by the triangle inequality,$$\begin{aligned}
\Delta_{1}\left(  h,f\right)  \left\langle \mathcal{D}\right\rangle  &
\leq\Delta_{1}\left(  h,g\right)  \left\langle \mathcal{D}\right\rangle
+\Delta_{1}\left(  g,f\right)  \left\langle \mathcal{D}\right\rangle \\
&  \leq\alpha+\Delta_{\infty}\left(  g,f\right) \\
&  \leq\alpha+\varepsilon.\end{aligned}$$ Next, we claim that $\operatorname*{fat}\nolimits_{\alpha/5}\left(  S^{\ast
}\right)  \leq\operatorname*{fat}\nolimits_{\alpha/5-\varepsilon}\left(
S\right)  $.  The reason is simply that, if a given set $\beta$-fat-shatters $S^{\ast}$, then it must also $\left(  \beta-\varepsilon
\right)  $-fat-shatter $S$ by the triangle inequality.  Setting $\alpha:=10\varepsilon$ now yields the desired statement.

The Safe Winnowing Lemma\[SAFEWINNOW\]
--------------------------------------

To prove the real-valued majority-certificates lemma, the first step is to prove a so-called ‘safe winnowing lemma.’  This lemma says intuitively that, given any set $S$ of real-valued functions with a small $\varepsilon$-cover (or equivalently, with polynomially-bounded fat-shattering dimension), it is possible to find a set of $k=\operatorname*{poly}\left(  n\right)  $ constraints $\left\vert f\left(
x_{1}\right)  -a_{1}\right\vert \leq\epsilon$, …, $\left\vert f\left(
x_{k}\right)  -a_{k}\right\vert \leq\epsilon$ that are *essentially* compatible with one and only one function $f\in S$.  Here ‘essentially’ means that (i) any function that satisfies the constraints is close to $f$ in $L_{\infty}$-norm, and (ii) $f$ itself not only satisfies the constraints, but does so with a ‘margin to spare.’

\[Safe Winnowing Lemma\]\[linfwinnow\]Let $S$ be a set of functions $f:\left\{  0,1\right\}  ^{n}\rightarrow\left[  0,1\right]  $.  Fix a function $f^{\ast}\in S$ and subset $Y\subseteq\left\{  0,1\right\}  ^{n}$.  For some parameter $\varepsilon>0$, let $C$ be a finite $\varepsilon$-cover for $S$.  Then there exists an $f\in S$, as well as a subset $Z\subseteq
\left\{  0,1\right\}  ^{n}$ of size at most $k=\log_{2}\left\vert
C\right\vert $, such that:

1.  Every $g\in S$ that satisfies $\Delta_{\infty}\left(  f,g\right)
    \left[  Y\cup Z\right]  \leq\frac{\varepsilon}{5k}$ also satisfies $\Delta_{\infty}\left(  f,g\right)  \leq3\varepsilon$.

2.  $\Delta_{\infty}\left(  f,f^{\ast}\right)  \left[  Y\right]
    \leq\varepsilon/5$.

Let $\delta:=\frac{\varepsilon}{5k}$.  We construct $\left(  f,Z\right)
$ by an iterative procedure.  Initially let $S_{0}:=S$, let $f_{0}:=f^{\ast
}$, and let $Z_{0}:=Y$.  We will form new sets $S_{1},S_{2},\ldots$ by repeatedly adding constraints of the form $f\left(  x\right)  \leq\alpha$ or $f\left(  x\right)  \geq\alpha$ for various $x,\alpha$, maintaining the invariant that $f_{t}\in S_{t}$.  At iteration $t$, suppose there exists a function $g\in S_{t-1}$ such that $\Delta_{\infty}\left(  f_{t-1},g\right)
\left[  Y\cup Z_{t-1}\right]  \leq\delta$, but nevertheless $\left\vert
f_{t-1}\left(  z_{t}\right)  -g\left(  z_{t}\right)  \right\vert
>3\varepsilon$ for some input $z_{t}$.  Then first set $Z_{t}:=Z_{t-1}\cup\left\{  z_{t}\right\}  $ (i.e., add $z_{t}$ into our set of inputs, if it is not already there).  Let $v:=\frac{1}{2}\left[  f_{t-1}\left(
z_{t}\right)  +g\left(  z_{t}\right)  \right]  $, let $A$ be the set of all functions $h\in S_{t-1}$ such that $h\left(  z_{t}\right)  <v$, and let $B$ be the set of all $h\in S_{t-1}$ such that $h\left(  z_{t}\right)  \geq
v$.  Also, for any given set $M$, let $M^{\Diamond}:=M\cap C$.  Then clearly $\min\left\{  \left\vert A^{\Diamond}\right\vert ,\left\vert B^{\Diamond
}\right\vert \right\}  \leq\left\vert S_{t-1}^{\Diamond}\right\vert /2$.  If $\left\vert A^{\Diamond}\right\vert <\left\vert B^{\Diamond}\right\vert $, then set $S_{t}:=A$; otherwise set $S_{t}:=B$.  Then set $f_{t}:=f_{t-1}$ if $f_{t-1}\in S_{t}$ and $f_{t}:=g$ otherwise.  Since $\left\vert
S_{t}^{\Diamond}\right\vert $ can halve at most $k=\log_{2}\left\vert
C\right\vert $ times, it is clear that after $T\leq k$ iterations we have $\left\vert S_{T}^{\Diamond}\right\vert \leq1$.  Set $f:=f_{T}$ and $Z:=Z_{T}$.  Then by the triangle inequality,$$\Delta_{\infty}\left(  f,f^{\ast}\right)  \left[  Y\right]  \leq T\delta
\leq\frac{\varepsilon}{5},$$ and also$$\left\vert f\left(  z_{t}\right)  -f_{t}\left(  z_{t}\right)  \right\vert
\leq\left(  T-t\right)  \delta<\frac{\varepsilon}{5}$$ for all $t\in\left[  T\right]  $.  So suppose by contradiction that there still exists a function $g\in S_{T}$ such that $\Delta_{\infty}\left(
f,g\right)  \left[  Y\cup Z\right]  \leq\delta$ but $\left\vert f\left(
x\right)  -g\left(  x\right)  \right\vert >3\varepsilon$ for some $x$, and consider functions $p,q\in C$ in the cover such that $\Delta_{\infty}\left(
f,p\right)  \leq\varepsilon$ and $\Delta_{\infty}\left(  g,q\right)
\leq\varepsilon$.  Then $p,q\in S_{T}^{\Diamond}$ but $p\neq q$, which contradicts the fact that $\left\vert S_{T}^{\Diamond}\right\vert \leq1$.  Also notice that for all $g\in S$, if $\Delta_{\infty}\left(  f,g\right)
\left[  Y\cup Z\right]  \leq\delta$ then $g\in S_{T}$.  Thus $\Delta
_{\infty}\left(  f,g\right)  \left[  Y\cup Z\right]  \leq\delta$ implies $\Delta_{\infty}\left(  f,g\right)  \leq3\varepsilon$ as desired.

Note that Lemma \[linfwinnow\] is still interesting in the special case $Y=\varnothing$, in which case $f^{\ast}$ is irrelevant, and the problem reduces to finding a $Z$ such that every $g\in S$ that satisfies $\Delta_{\infty}\left(  f,g\right)  \left[  Z\right]  \leq\frac{\varepsilon
}{5k}$ also satisfies $\Delta_{\infty}\left(  f,g\right)  \leq3\varepsilon$.  In Appendix \[WINNOW\], we will develop the theory of ‘winnowability’ of p-concept classes for its own sake.  We show there that the condition $\Delta_{\infty}\left(  f,g\right)  \left[
Z\right]  =O\left(  \varepsilon/k\right)  $ can be improved to $\Delta
_{1}\left(  f,g\right)  \left[  Z\right]  =O\left(  \varepsilon\right)  $.  On the other hand, the proof becomes more involved, and we no longer know how to incorporate $f^{\ast}$ and $Y$.  We also show that the condition $\Delta_{\infty}\left(  f,g\right)  \left[  Z\right]  =O\left(  \varepsilon
/k\right)  $ *cannot* be improved to $\Delta_{\infty}\left(
f,g\right)  \left[  Z\right]  =O\left(  \varepsilon\right)  $ or even $\Delta_{2}\left(  f,g\right)  \left[  Z\right]  =O\left(  \varepsilon\right)
$.

The Real-Valued Majority-Certificates Lemma\[THELEMMA\]
-------------------------------------------------------

We are finally ready to generalize Lemma \[majcer\] to the case of real-valued functions.

\[Real Majority-Certificates\]\[realmajcer\]Let $S$ be a p-concept class, let $f^{\ast}\in S$, and let $\varepsilon>0$.  Then for some $m=O\left(
n/\varepsilon^{2}\right)  $, there exist functions $f_{1},\ldots,f_{m}\in S$, sets $X_{1},\ldots,X_{m}\subseteq\left\{  0,1\right\}  ^{n}$ each of size $k=O\left(  \left(  n+\frac{\log^{2}1/\varepsilon}{\varepsilon^{2}}\right)
\operatorname*{fat}\nolimits_{\varepsilon/48}\left(  S\right)  \right)  $, and an $\alpha=\Omega\left(  \frac{\varepsilon}{\left(  n+\log1/\varepsilon
\right)  \operatorname*{fat}\nolimits_{\varepsilon/48}\left(  S\right)
}\right)  $ for which the following holds.  All $g_{1},\ldots,g_{m}\in
S$ that satisfy $\Delta_{\infty}\left(  f_{i},g_{i}\right)  \left[
X_{i}\right]  \leq\alpha$ for $i\in\left[  m\right]  $ also satisfy $\Delta_{\infty}\left(  f^{\ast},g\right)  \leq\varepsilon$, where$$g\left(  x\right)  :=\frac{g_{1}\left(  x\right)  +\cdots+g_{m}\left(
x\right)  }{m}.$$

Let$$\begin{aligned}
\beta &  :=\frac{\varepsilon}{48},\\
t  &  :=C\left(  n+\log\frac{1}{\beta}\right)  \operatorname*{fat}\nolimits_{\beta}\left(  S\right)  ,\\
\alpha &  :=\frac{0.4\beta}{t},\end{aligned}$$ where $C$ is a suitably large constant.  Also, let $S_{\operatorname*{fin}}$ be a finite $\alpha$-cover for $S$: that is, a finite subset $S_{\operatorname*{fin}}\subseteq S$ such that for all $f\in S$, there exists a $g\in S_{\operatorname*{fin}}$ such that $\Delta_{\infty}\left(
f,g\right)  \leq\alpha$.[^6]  Given $f$ and $X$, let $S\left[  f,X\right]  $ be the set of all $g\in S$ such that $\Delta_{\infty}\left(  f,g\right)  \left[
X\right]  \leq\alpha$.

Now consider a two-player game where Alice chooses a function $f\in
S_{\operatorname*{fin}}$ and a set $X\subseteq\left\{  0,1\right\}  ^{n}$ of size $k$, and Bob simultaneously chooses an input $x\in\left\{  0,1\right\}
^{n}$.  Alice’s *penalty* in this game (the number she is trying to minimize) equals$$\sup_{g\in S\left[  f,X\right]  }\left\vert f^{\ast}\left(  x\right)
-g\left(  x\right)  \right\vert .$$ We claim that there exists a mixed strategy for Alice—that is, a probability distribution $\mathcal{P}$ over $\left(  f,X\right)  $ pairs—that gives her an expected penalty of at most $\varepsilon/2$ against every pure strategy of Bob.

Let us see why the lemma follows from this claim.  Fix an input $x\in\left\{
0,1\right\}  ^{n}$, and suppose Alice draws $\left(  f_{1},X_{1}\right)
,\ldots,\left(  f_{m},X_{m}\right)  $ independently from $\mathcal{P}$.  Then for all $i\in\left[  m\right]  $,$$\operatorname*{E}_{\left(  f_{i},X_{i}\right)  \sim\mathcal{P}}\left[
\sup_{g\in S\left[  f,X\right]  }\left\vert f^{\ast}\left(  x\right)
-g\left(  x\right)  \right\vert \right]  \leq\frac{\varepsilon}{2}.$$ Thus, letting $z_{1},\ldots,z_{m}$ be independent random variables in $\left[  0,1\right]  $, each with expectation at most $\varepsilon/2$, the expression$$\Pr_{\left(  f_{1},X_{1}\right)  ,\ldots,\left(  f_{m},X_{m}\right)
\sim\mathcal{P}}\left[  \exists g_{1}\in S\left[  f_{1},X_{1}\right]
,\ldots,g_{m}\in S\left[  f_{m},X_{m}\right]  ~:~\left\vert f^{\ast}\left(
x\right)  -\frac{g_{1}\left(  x\right)  +\cdots+g_{m}\left(  x\right)  }{m}\right\vert >\varepsilon\right]$$ is at most $\Pr\left[  z_{1}+\cdots z_{m}>\varepsilon m\right]  $ by the triangle inequality.  This, in turn, is less than$$2\exp\left(  -\frac{2\left(  \varepsilon m\right)  ^{2}}{m}\right)  <2^{-n}$$ by Hoeffding’s inequality, provided we choose $m=O\left(  n/\varepsilon
^{2}\right)  $ suitably.  By the union bound, this means that there must be a fixed choice of $f_{1},\ldots,f_{m}$ and $X_{1},\ldots,X_{m}$ such that$$\left\vert f^{\ast}\left(  x\right)  -\frac{g_{1}\left(  x\right)
+\cdots+g_{m}\left(  x\right)  }{m}\right\vert \leq\varepsilon$$ for all $g_{1}\in S\left[  f_{1},X_{1}\right]  ,\ldots,g_{m}\in S\left[
f_{m},X_{m}\right]  $ and all inputs $x\in\left\{  0,1\right\}  ^{n}$ simultaneously, as desired.

We now prove the claim.  By the Minimax Theorem, our task is equivalent to the following: given any mixed strategy $\mathcal{D}$ of Bob, find a *pure* strategy of Alice that achieves a penalty of at most $\varepsilon/2$ against $\mathcal{D}$.  In other words, given any distribution $\mathcal{D}$ over inputs $x\in\left\{  0,1\right\}  ^{n}$, we want a fixed function $f\in S_{\operatorname*{fin}}$, and a set $X\subseteq
\left\{  0,1\right\}  ^{n}$ of size $k$, such that$$\operatorname*{E}_{x\sim\mathcal{D}}\left[  \sup_{g\in S\left[  f,X\right]
}\left\vert f^{\ast}\left(  x\right)  -g\left(  x\right)  \right\vert \right]
\leq\frac{\varepsilon}{2}.$$ We construct this $\left(  f,X\right)  $ pair as follows.

In the first stage, we let $Y$ be a set, of size at most$$M:=\frac{K}{\beta^{2}}\left(  \operatorname*{fat}\nolimits_{\beta}\left(
S\right)  \log^{2}\frac{1}{\beta}+\log\frac{1}{\delta}\right)  ,$$ formed by choosing $M$ inputs independently with replacement from $\mathcal{D}$.  Here $\beta=\varepsilon/48$ as defined earlier, $\delta=1/2$, and $K$ is the constant from Corollary \[occamcor\].  Then by Corollary \[occamcor\], with probability at least $1-\delta=1/2$ over the choice of $Y$, any $g\in S$ that satisfies $\Delta_{\infty}\left(  f^{\ast},g\right)
\left[  Y\right]  \leq\beta$ also satisfies $\Delta_{1}\left(  f^{\ast
},g\right)  \left\langle \mathcal{D}\right\rangle \leq11\beta$.  So there must be a *fixed* choice of $Y$ with that property.  Fix that $Y$, and let $S^{\prime}$ be the set of all $g\in S$ such that $\Delta_{\infty
}\left(  f^{\ast},g\right)  \left[  Y\right]  \leq\beta$.

In the second stage, our goal is just to winnow $S^{\prime}$ down to a particular function $f$.  More precisely, we want to find an $f\in S^{\prime
}\cap S_{\operatorname*{fin}}$, and a set $X\subseteq\left\{  0,1\right\}
^{n}$ containing $Y$, such that any $g\in S$ that satisfies $\Delta_{\infty
}\left(  f,g\right)  \left[  X\right]  \leq\alpha$ also satisfies $\Delta_{\infty}\left(  f,g\right)  \leq11\beta$.

We find this $\left(  f,X\right)  $ pair as follows.  By Theorem \[coverthm\], the class $S^{\prime}$ has a $4\beta$-cover of size$$N=\exp\left[  O\left(  \left(  n+\log\frac{1}{4\beta}\right)
\operatorname*{fat}\nolimits_{\beta}\left(  S^{\prime}\right)  \right)
\right]  \leq\exp\left[  O\left(  \left(  n+\log\frac{1}{\beta}\right)
\operatorname*{fat}\nolimits_{\beta}\left(  S\right)  \right)  \right]  .$$ Let $t:=\log_{2}N$.  Then by Lemma \[linfwinnow\], there exists a function $u\in S^{\prime}$, as well as a subset $Z\subseteq\left\{  0,1\right\}  ^{n}$ of size at most $t$, such that:

1.  $\Delta_{\infty}\left(  u,f^{\ast}\right)  \left[  Y\right]
    \leq0.8\beta$.

2.  Every $g\in S^{\prime}$ that satisfies $\Delta_{\infty}\left(
    u,g\right)  \left[  Y\cup Z\right]  \leq\frac{0.8\beta}{t}$ also satisfies $\Delta_{\infty}\left(  u,g\right)  \leq12\beta$.

Let $X:=Y\cup Z$, and observe that$$\begin{aligned}
\left\vert X\right\vert  &  =O\left(  \frac{1}{\beta^{2}}\operatorname*{fat}\nolimits_{\beta}\left(  S\right)  \log^{2}\frac{1}{\beta}+\left(  n+\log
\frac{1}{\beta}\right)  \operatorname*{fat}\nolimits_{\beta}\left(  S\right)
\right) \\
&  =O\left(  \left(  n+\frac{\log^{2}1/\varepsilon}{\varepsilon^{2}}\right)
\operatorname*{fat}\nolimits_{\varepsilon/48}\left(  S\right)  \right)\end{aligned}$$ as desired.  Now let $f$ be a function in $S_{\operatorname*{fin}}$ such that $\Delta_{\infty}\left(  f,u\right)  \leq\alpha$.  Let us check that $f$ has the properties we want.  First,$$\begin{aligned}
\Delta_{\infty}\left(  f^{\ast},f\right)  \left[  Y\right]   &  \leq
\Delta_{\infty}\left(  f^{\ast},u\right)  \left[  Y\right]  +\Delta_{\infty
}\left(  u,f\right)  \left[  Y\right] \\
&  \leq0.8\beta+\alpha\\
&  <0.9\beta,\end{aligned}$$ hence $f\in S^{\prime}$ as desired.  Next, any $g\in S$ that satisfies $\Delta_{\infty}\left(  f,g\right)  \left[  X\right]  \leq\alpha$ also satisfies$$\begin{aligned}
\Delta_{\infty}\left(  f^{\ast},g\right)  \left[  Y\right]   &  \leq
\Delta_{\infty}\left(  f^{\ast},f\right)  \left[  Y\right]  +\Delta_{\infty
}\left(  f,g\right)  \left[  Y\right] \\
&  \leq0.9\beta+\alpha\\
&  <\beta,\end{aligned}$$ hence $g\in S^{\prime}$, hence $\Delta_{1}\left(  f^{\ast},g\right)
\left\langle \mathcal{D}\right\rangle \leq11\beta$.  So any $g\in S$ that satisfies $\Delta_{\infty}\left(  f,g\right)  \left[  X\right]  \leq\alpha
$ satisfies$$\begin{aligned}
\Delta_{\infty}\left(  u,g\right)  \left[  Z\right]   &  \leq\Delta_{\infty
}\left(  u,f\right)  \left[  Z\right]  +\Delta_{\infty}\left(  f,g\right)
\left[  Z\right] \\
&  \leq2\alpha\\
&  =\frac{0.8\beta}{t},\end{aligned}$$ hence $\Delta_{\infty}\left(  u,g\right)  \leq12\beta$ (since such a $g$ must belong to $S^{\prime}$), hence$$\begin{aligned}
\Delta_{\infty}\left(  f,g\right)   &  \leq\Delta_{\infty}\left(  f,u\right)
+\Delta_{\infty}\left(  u,g\right) \\
&  \leq\alpha+12\beta\\
&  \leq13\beta.\end{aligned}$$ To conclude,$$\begin{aligned}
\operatorname*{E}_{x\sim\mathcal{D}}\left[  \sup_{g\in S\left[  f,X\right]
}\left\vert f^{\ast}\left(  x\right)  -g\left(  x\right)  \right\vert \right]
&  \leq\Delta_{1}\left(  f^{\ast},f\right)  \left\langle \mathcal{D}\right\rangle +\sup_{g\in S\left[  f,X\right]  }\Delta_{\infty}\left(
f,g\right) \\
&  \leq11\beta+13\beta\\
&  =\frac{\varepsilon}{2}$$ as desired.  This proves the claim and hence the lemma.

Application to Quantum Advice\[QADV\]
=====================================

In this section, we use the real-valued majority-certificates lemma to prove Theorems \[mainthm0\] and \[mainthm1\], as well as several other results.

Bestiary of Quantum Complexity Classes\[QCC\]
---------------------------------------------

Given a language $L\subseteq\left\{  0,1\right\}  ^{\ast}$, let $L:\left\{
0,1\right\}  ^{\ast}\rightarrow\left\{  0,1\right\}  $ be the characteristic function of $L$.  We now give a formal definition of the class $\mathsf{BQP/qpoly}$.

A language $L$ is in $\mathsf{BQP/qpoly}$ if there exists a polynomial-time quantum algorithm $A$ and polynomial $p$ such that for all $n$, there exists an advice state $\rho_{n}$ on $p\left(  n\right)  $ qubits such that $A\left(  x,\rho_{n}\right)  $ outputs $L\left(  x\right)  $ with probability $\geq2/3$ for all $x\in\left\{  0,1\right\}  ^{n}$.

Closely related to quantum advice are *quantum proofs*.  We now recall the definition of $\mathsf{QMA}$ (Quantum Merlin-Arthur), a quantum version of $\mathsf{NP}$.

A language $L$ is in $\mathsf{QMA}$ if there exists a polynomial-time quantum algorithm $A$ and polynomial $p$ such that for all $x\in\left\{
0,1\right\}  ^{n}$:

1.  If $x\in L$ then there exists a witness $\rho_{x}$ on $p\left(
    n\right)  $ qubits such that $A\left(  x,\rho_{x}\right)  $ accepts with probability $\geq2/3$.

2.  If $x\notin L$ then $A\left(  x,\rho\right)  $ accepts with probability $\leq1/3$ for all $\rho$.

We will actually need a generalization of $\mathsf{QMA}$, which was called $\mathsf{QMA}_{\mathsf{+}}$ by Aharonov and Regev [@ar:quantum].[^7]

A language $L$ is in $\mathsf{QMA}_{\mathsf{+}}$ if there exists a polynomial-time algorithm $A$, which takes $x\in\left\{  0,1\right\}  ^{n}$ as input and produces quantum circuits $C_{x,1},\ldots,C_{x,m}$ and rational numbers $r_{x,1},\ldots,r_{x,m}$ as output, as well as polynomials $p,q$ such that for all $x\in\left\{  0,1\right\}  ^{n}$:

1.  If $x\in L$ then there exists a witness $\rho_{x}$ on $p\left(
    n\right)  $ qubits such that $\left\vert \Pr\left[  C_{x,i}\left(  \rho
    _{x}\right)  \text{ accepts}\right]  -r_{x,i}\right\vert \leq1/q\left(
    n\right)  $ for all $i\in\left[  m\right]  $.

2.  If $x\notin L$ then for all $\rho$, there exists an $i\in\left[
    m\right]  $ such that $\left\vert \Pr\left[  C_{x,i}\left(  \rho\right)
    \text{ accepts}\right]  -r_{x,i}\right\vert >5/q\left(  n\right)  $.

Aharonov and Regev [@ar:quantum] made the following extremely useful observation, which we prove for completeness.

\[[@ar]\]\[qmaplusthm\]$\mathsf{QMA}_{\mathsf{+}}=\mathsf{QMA}$.

$\mathsf{QMA}\subseteq\mathsf{QMA}_{\mathsf{+}}$ is obvious.  For the other direction, let $L\in\mathsf{QMA}_{\mathsf{+}}$, and fix an input $x\in\left\{
0,1\right\}  ^{n}$, quantum circuits $C_{x,1},\ldots,C_{x,m}$, rational numbers $r_{x,1},\ldots,r_{x,m}$, and polynomials $p,q$.  Then consider the following $\mathsf{QMA}$ verification procedure.  Given a witness state $\sigma$ on $K=O\left(  q\left(  n\right)  ^{2}\log q\left(  n\right)
\right)  $ registers:

1.  Choose $i\in\left[  m\right]  $ uniformly at random.

2.  For $k:=1$ to $K$, apply $C_{x,i}$ to the $k^{th}$ register of $\sigma$.

3.  If the fraction $\alpha$ of invocations that accepted satisfies $\left\vert \alpha-r_{x,i}\right\vert \leq2/q\left(  n\right)  $, then accept.  Otherwise reject.

Let $P_{i}\left(  \sigma\right)  $ be the probability that the above procedure accepts, conditioned on choosing $i\in\left[  m\right]  $ in step (i).

Completeness is easy: an honest Merlin can send Arthur the product state $\rho_{x}^{\otimes K}$.  Then provided we take $K$ sufficiently large, $P_{i}\left(  \rho_{x}^{\otimes K}\right)  <1/q\left(  n\right)  ^{2}$ for all $i\in\left[  m\right]  $ by a Chernoff bound.

In the soundness case, suppose by way of contradiction that there exists a state $\sigma$ such that$$\operatorname*{E}_{i\in\left[  m\right]  }\left[  P_{i}\left(  \sigma\right)
\right]  <\frac{2}{q\left(  n\right)  ^{2}}.$$ Then by Markov’s inequality, $P_{i}\left(  \sigma\right)  <2/q\left(
n\right)  $ for each *particular* $i\in\left[  m\right]  $.  Now let $\sigma_{k}$ be the $k^{th}$ register of $\sigma$, and let $\rho:=\frac
{1}{K}\left(  \sigma_{1}+\cdots+\sigma_{K}\right)  $.  Then by linearity of expectation,$$\begin{aligned}
\left\vert \Pr\left[  C_{x,i}\left(  \rho\right)  \text{ accepts}\right]
-r_{x,i}\right\vert  &  =\left\vert \operatorname*{E}_{k\in\left[  K\right]
}\left[  \Pr\left[  C_{x,i}\left(  \sigma_{k}\right)  \text{ accepts}\right]
\right]  -r_{x,i}\right\vert \\
&  \leq\frac{2}{q\left(  n\right)  }+P_{i}\left(  \sigma\right) \\
&  \leq\frac{4}{q\left(  n\right)  },\end{aligned}$$ which contradicts the assumption that there exists an $i\in\left[  m\right]
$ such that$$\left\vert \Pr\left[  C_{x,i}\left(  \rho\right)  \text{ accepts}\right]
-r_{x,i}\right\vert >\frac{5}{q\left(  n\right)  }.$$ The theorem now reduces to the standard fact that $\mathsf{QMA}$ protocols can be amplified to any desired $1/\operatorname*{poly}\left(  n\right)
$ soundness gap.

To state our results, it will be helpful to have the further notion of *untrusted advice*, which is like advice in that it depends only on the input length $n$, but like a witness in that it cannot be trusted.  This notion has been studied before: Chakaravarthy and Roy [@chakaravarthy] and Fortnow and Santhanam [@fortnowsanthanam] defined the complexity class $\mathsf{ONP}$ (‘Oblivious $\mathsf{NP}$’), which is like $\mathsf{NP}$ except that the witness can depend only on the input length.  Independently, Aaronson [@aar:learn] defined the complexity class $\mathsf{YP}$,[^8] which is easily seen to equal $\mathsf{ONP}\cap\mathsf{coONP}$.  We will adopt the ‘$\mathsf{Y}$’ notation in this paper, because it is much easier to write $\mathsf{YQP/poly}$ (for example) than $\mathsf{OQMA/poly}\cap\mathsf{coOQMA/poly}$.

We now give a formal definition of $\mathsf{YP}$, as well as a slight variant called $\mathsf{YP}^{\mathsf{\ast}}$.

A language $L$ is in $\mathsf{YP}$ if there exist polynomial-time algorithms $A,B$ and a polynomial $p$ such that:

1.  For all $n$, there exists an advice string $y_{n}\in\left\{
    0,1\right\}  ^{p\left(  n\right)  }$ such that $A\left(  x,y_{n}\right)
    =1$ for all $x\in\left\{  0,1\right\}  ^{n}$.

2.  If $A\left(  x,y\right)  =1$, then $B\left(  x,y\right)  =L\left(
    x\right)  $.

$L$ is in $\mathsf{YP}^{\mathsf{\ast}}$ if moreover $A$ ignores $x$, depending only on $y$.

Clearly $\mathsf{P}\subseteq\mathsf{YP}^{\mathsf{\ast}}\subseteq
\mathsf{YP}\subseteq\mathsf{P/poly}\cap\mathsf{NP}\cap\mathsf{coNP}$.  Also, Aaronson [@aar:learn] showed that $\mathsf{ZPP}\subseteq\mathsf{YP}$.  We will be interested in the natural quantum analogues of $\mathsf{YP}$ and $\mathsf{YP}^{\mathsf{\ast}}$:

A language $L$ is in $\mathsf{YQP}$ if there exist polynomial-time quantum algorithms $A,B$ and a polynomial $p$ such that:

1.  For all $n$, there exists an advice state $\rho_{n}$ on $p\left(
    n\right)  $ qubits such that $A\left(  x,\rho_{n}\right)  $ accepts with probability $\geq2/3$ for all $x\in\left\{  0,1\right\}  ^{n}$.

2.  If $A\left(  x,\rho\right)  $ accepts with probability $\geq1/3$, then $B\left(  x,\rho\right)  $ outputs $L\left(  x\right)  $ with probability $\geq2/3$.

$L$ is in $\mathsf{YQP}^{\mathsf{\ast}}$ if moreover $A$ ignores $x$, depending only on $\rho$.

Clearly $\mathsf{BQP}\subseteq\mathsf{YQP}^{\mathsf{\ast}}\subseteq
\mathsf{YQP}\subseteq\mathsf{BQP/qpoly}\cap\mathsf{QMA}\cap\mathsf{coQMA}$.  By direct analogy to $\mathsf{QMA}_{\mathsf{+}}$, we can define the following generalizations of $\mathsf{YQP}$ and $\mathsf{YQP}^{\mathsf{\ast}}$:

A language $L$ is in $\mathsf{YQP}_{\mathsf{+}}$ if there exists a polynomial-time algorithm $A$, which takes $x\in\left\{  0,1\right\}  ^{n}$ as input and produces quantum circuits $C_{x,1},\ldots,C_{x,m}$ and rational numbers $r_{x,1},\ldots,r_{x,m}$ as output; a polynomial-time quantum algorithm $B$; and polynomials $p,q$ such that:

1.  For all $n$, there exists an advice state $\rho_{n}$ on $p\left(
    n\right)  $ qubits such that $\left\vert \Pr\left[  C_{x,i}\left(  \rho
    _{n}\right)  \text{ accepts}\right]  -r_{x,i}\right\vert \leq1/q\left(
    n\right)  $ for all $i\in\left[  m\right]  $ and $x\in\left\{  0,1\right\}
    ^{n}$.

2.  If $\left\vert \Pr\left[  C_{x,i}\left(  \rho\right)  \text{
    accepts}\right]  -r_{x,i}\right\vert \leq5/q\left(  n\right)  $ for all $i\in\left[  m\right]  $, then $B\left(  x,\rho\right)  $ outputs $L\left(
    x\right)  $ with probability $\geq2/3$.

$L$ is in $\mathsf{YQP}_{\mathsf{+}}^{\mathsf{\ast}}$ if moreover $A$ ignores $x$.

Then we have the following direct counterpart to Theorem \[qmaplusthm\]:

\[yqpplusthm\]$\mathsf{YQP}_{\mathsf{+}}=\mathsf{YQP}$ and $\mathsf{YQP}_{\mathsf{+}}^{\mathsf{\ast}}=\mathsf{YQP}^{\mathsf{\ast}}$.

For $\mathsf{YQP}\subseteq\mathsf{YQP}_{\mathsf{+}}$ and $\mathsf{YQP}^{\mathsf{\ast}}\subseteq\mathsf{YQP}_{\mathsf{+}}^{\mathsf{\ast}}$, we simply take $m=1$ and take $q\left(  n\right)  $ to be a constant.  For $\mathsf{YQP}_{\mathsf{+}}\subseteq\mathsf{YQP}$, the simulation procedure is essentially the same as in the proof of Theorem \[qmaplusthm\].  Namely, let $L\in\mathsf{YQP}_{\mathsf{+}}$, and fix an input $x\in\left\{
0,1\right\}  ^{n}$, quantum circuits $C_{x,1},\ldots,C_{x,m}$ generated by an algorithm $A$, rational numbers $r_{x,1},\ldots,r_{x,m}$, polynomials $p,q$, and an algorithm $B$.  Then given a witness state $\sigma$ on $K=O\left(
q\left(  n\right)  ^{2}\log q\left(  n\right)  \right)  $ registers, the $\mathsf{YQP}$ algorithm $A^{\prime}$ does the following:

1.  Choose $i\in\left[  m\right]  $ uniformly at random.

2.  For $k:=1$ to $K$, apply $C_{x,i}$ to the $k^{th}$ register of $\sigma$.

3.  If the fraction $\alpha$ of invocations that accepted satisfies $\left\vert \alpha-r_{x,i}\right\vert \leq2/q\left(  n\right)  $, then accept.  Otherwise reject.

Likewise, let $\sigma_{k}$ be the $k^{th}$ register of $\sigma$.  Then the $\mathsf{YQP}$ algorithm $B^{\prime}$ chooses $k\in\left[  K\right]  $ uniformly at random, runs $B\left(  x,\sigma_{k}\right)  $, and outputs the result.  One can check that conditions (i) and (ii) in the definition of $\mathsf{YQP}$ are both satisfied, albeit with $1-1/q\left(  n\right)  ^{2}$ and $1-2/q\left(  n\right)  ^{2}$ in place of $2/3$ and $1/3$ (which is not an important difference, because of amplification).  The proof of $\mathsf{YQP}_{\mathsf{+}}^{\mathsf{\ast}}\subseteq\mathsf{YQP}^{\mathsf{\ast
}}$ is the same, except that both $A$ and $A^{\prime}$ ignore the input $x$ when generating the $C_{x,i}$’s and $r_{x,i}$’s.

Characterizing Quantum Advice\[YQPSEC\]
---------------------------------------

Fix a polynomial-size quantum circuit $Q$.  For a given advice state $\rho$, let $f_{\rho}\left(  x\right)  :=\Pr\left[  Q\text{ accepts }x,\rho\right]  $.  Let $S$ be the p-concept class consisting of $f_{\rho}$ for all $p\left(
n\right)  $-qubit mixed states $\rho$.  Then Aaronson [@aar:learn] proved the following.

\[[@aar:learn]\]\[qlearn\]$\operatorname*{fat}\nolimits_{\gamma}\left(
S\right)  =O\left(  p\left(  n\right)  /\gamma^{2}\right)  .$

We now prove the following characterization of $\mathsf{BQP/qpoly}$, which immediately implies (and strengthens) Theorem \[mainthm1\]:

\[yqpthm\]$\mathsf{BQP/qpoly}=\mathsf{YQP/poly}$.

One direction ($\mathsf{YQP/poly}\subseteq\mathsf{BQP/qpoly}$) is obvious, since untrusted quantum advice and trusted classical advice can both be simulated by trusted quantum advice.  We prove that $\mathsf{BQP/qpoly}\subseteq\mathsf{YQP/poly}$.  It suffices to show that $\mathsf{BQP/qpoly}\subseteq\mathsf{YQP}_{\mathsf{+}}\mathsf{/poly}$, since $\mathsf{YQP}=\mathsf{YQP}_{\mathsf{+}}$ by Theorem \[yqpplusthm\].  Let $L\in
\mathsf{BQP/qpoly}$, let $Q$ be a quantum algorithm that decides $L$ with completeness and soundness errors $1/5$, and let $x\in\left\{  0,1\right\}
^{n}$ be the input.  Also, let $f_{\xi}\left(  z\right)  :=\Pr\left[
Q\left(  z,\xi\right)  \text{ accepts}\right]  $, where $\xi$ is a $p\left(
n\right)  $-qubit quantum advice state for $Q$.  Then by definition, there exists a ‘true’ advice state $\rho_{n}$ such that$$\left\vert f_{\rho_{n}}\left(  z\right)  -L\left(  z\right)  \right\vert
\leq0.2$$ for all $z\in\left\{  0,1\right\}  ^{n}$.  Let $S$ be the p-concept class consisting of $f_{\xi}$ for all $p\left(  n\right)  $-qubit mixed states $\xi$.  Then Theorem \[qlearn\] implies that $\operatorname*{fat}\nolimits_{\gamma}\left(  S\right)  =O\left(  p\left(  n\right)  /\gamma
^{2}\right)  $ for all $\gamma>0$.  Set $\gamma:=1/480$.  Then by Lemma \[realmajcer\], for some $m=O\left(  n\right)  $, there exist $p\left(
n\right)  $-qubit mixed states $\rho\left[  1\right]  ,\ldots,\rho\left[
m\right]  $, sets $X_{1},\ldots,X_{m}\subseteq\left\{  0,1\right\}  ^{n}$ each of size $k=O\left(  n\cdot p\left(  n\right)  \right)  $, and an $\alpha=\Omega\left(  \frac{1}{n\cdot p\left(  n\right)  }\right)  $ for which the following holds:

-   *All* $p\left(  n\right)  $*-qubit states* $\sigma\left[  1\right]  ,\ldots,\sigma\left[  m\right]  $* that satisfy* $\Delta_{\infty}\left(  f_{\rho\left[  i\right]  },f_{\sigma\left[
    i\right]  }\right)  \left[  X_{i}\right]  \leq5\alpha$* for* $i\in\left[  m\right]  $* also satisfy* $\Delta_{\infty}\left(
    f_{\rho_{n}},f_{\sigma}\right)  \leq0.1$*, where* $\sigma:=\frac{1}{m}\left(  \sigma\left[  1\right]  +\cdots+\sigma\left[  m\right]  \right)
    $*.*

Our $\mathsf{YQP}_{\mathsf{+}}\mathsf{/poly}$ simulation is now the following.  The classical $\mathsf{/poly}$ advice encodes the sets $X_{1},\ldots,X_{m}$, as well as a rational approximation $r_{i,z}$ to $f_{\rho\left[  i\right]  }\left(  z\right)  $ for each $i\in\left[
m\right]  $ and $z\in X_{i}$.  The untrusted quantum advice $\rho
_{n}^{\prime}$ consists of $m$ registers of $p\left(  n\right)  $ qubits each; in the honest case, $\rho_{n}^{\prime}$ is simply $\rho\left[
1\right]  \otimes\cdots\otimes\rho\left[  m\right]  $.  Let $\sigma\left[
i\right]  $ be the $i^{th}$ register of $\rho_{n}^{\prime}$.  Then given the advice, the $\mathsf{YQP}_{\mathsf{+}}$ machine $A$ outputs a circuit $C_{i,z}$ that runs $Q\left(  z,\sigma\left[  i\right]  \right)  $ and outputs the result, for each $i\in\left[  m\right]  $ and $z\in X_{i}$.  The machine $B$ chooses $i\in\left[  m\right]  $ uniformly at random, then runs $Q\left(  x,\sigma\left[  i\right]  \right)  $ and outputs the result.

We are interested in the difference between $\Pr\left[  C_{i,z}\left(
\rho_{n}^{\prime}\right)  \text{ accepts}\right]  $ and $r_{i,z}$.  In the honest case,$$\Pr\left[  C_{i,z}\left(  \rho_{n}^{\prime}\right)  \text{ accepts}\right]
=\Pr\left[  Q\left(  z,\rho\left[  i\right]  \right)  \text{ accepts}\right]
=f_{\rho\left[  i\right]  }\left(  z\right)$$ for all $i,z$.  Moreover, we can easily arrange each $r_{i,z}$ to be within $\alpha$ of $f_{\rho\left[  i\right]  }\left(  z\right)  $, by using $O\left(  \log n\right)  $ bits to specify each $r_{i,z}$.  For the soundness case, suppose$$\left\vert \Pr\left[  C_{i,z}\left(  \rho_{n}^{\prime}\right)  \text{
accepts}\right]  -r_{i,z}\right\vert \leq5\alpha$$ for all $i\in\left[  m\right]  $ and $z\in X_{i}$.  Then by (\*), we have $\Delta_{\infty}\left(  f_{\rho_{n}},f_{\sigma}\right)  \leq0.1$.  Notice that by linearity of expectation,$$\Pr\left[  B\text{ accepts}\right]  =\operatorname*{E}_{i\in\left[  m\right]
}\left[  \Pr\left[  Q\left(  x,\sigma\left[  i\right]  \right)  \text{
accepts}\right]  \right]  =f_{\sigma}\left(  x\right)  ,$$ and that this holds regardless of what entanglement might be present among the $m$ registers $\sigma\left[  1\right]  ,\ldots,\sigma\left[  m\right]  $.  Hence$$\begin{aligned}
\left\vert \Pr\left[  B\text{ accepts}\right]  -L\left(  x\right)
\right\vert  &  \leq\left\vert \Pr\left[  B\text{ accepts}\right]
-f_{\rho_{n}}\left(  x\right)  \right\vert +\left\vert f_{\rho_{n}}\left(
x\right)  -L\left(  x\right)  \right\vert \\
&  \leq0.1+0.2\end{aligned}$$ which is less than $1/3$ as desired, and $L\in\mathsf{YQP}_{\mathsf{+}}\mathsf{/poly}=\mathsf{YQP/poly}$.

Theorem \[yqpthm\] actually yields the stronger result that $\mathsf{BQP/qpoly}\subseteq\mathsf{YQP}^{\mathsf{\ast}}\mathsf{/poly}$, since the machine $A$ had no dependence on the input $x$.  We therefore have $\mathsf{BQP/qpoly}=\mathsf{YQP^{\mathsf{\ast}}/poly}=\mathsf{YQP/poly}$: the two definitions of $\mathsf{YQP}$ collapse in the presence of polynomial-size classical advice.  Since we never needed the assumption that the $\mathsf{BQP/qpoly}$ machine computes a *language* (i.e., a total Boolean function), another strengthening we can easily observe is $\mathsf{P{}romiseBQP/qpoly}=\mathsf{P{}romiseYQP/poly}$.

If we prefer, we can interpret Theorem \[yqpthm\] as a statement about quantum communication protocols rather than quantum complexity classes.  The following theorem makes this connection more precise.

\[channelthm\]Suppose that Alice, who is computationally unbounded, has a classical description of an $n$-qubit quantum state $\rho$.  She wants to send $\rho$ to Bob, who is limited to $\mathsf{BQP}$ computations.  Alice has at her disposal a noiseless one-way classical channel to Bob, as well as a noisy one-way quantum channel.  Then for all $m$ and $\varepsilon>0$, there exists a protocol whereby

1.  Alice sends Bob a classical string $y$ of $\operatorname*{poly}\left(  n,m,1/\varepsilon\right)  $ bits, as well as a state $\sigma$ of $\operatorname*{poly}\left(  n,m,1/\varepsilon\right)  $ qubits.

2.  Bob receives $y$ together with a possibly-corrupted version $\widetilde{\sigma}$ of $\sigma$.

3.  If $\widetilde{\sigma}=\sigma$, then for any measurement $E$ performed by a circuit with at most $m$ gates, Bob can perform another measurement $f_{y}\left(  E\right)  $ on $\widetilde{\sigma}$, and then output a number $\beta\in\left[  0,1\right]  $ such that $\left\vert
    \beta-\operatorname*{Tr}\left(  E\rho\right)  \right\vert \leq\varepsilon$ with $1-1/\exp\left(  n\right)  $ probability.  Here $f_{y}\left(  E\right)
    $ can be computed in polynomial time given $y$ together with a description of $E$.

4.  For every $\widetilde{\sigma}$ and every such measurement $E$, with $1-1/\exp\left(  n\right)  $ probability Bob outputs either ‘FAIL’ or else a $\beta\in\left[  0,1\right]  $ such that $\left\vert \beta
    -\operatorname*{Tr}\left(  E\rho\right)  \right\vert \leq\varepsilon$.

This is just a direct translation of Theorem \[yqpthm\] to the communication setting.  The string $y$ plays the role of the trusted classical advice, the state $\widetilde{\sigma}$ plays the role of the untrusted quantum advice, the measurement $E$ plays the role of the input $x\in\left\{  0,1\right\}  ^{n}$, and Bob plays the role of the verifier.  To get $1-1/\exp\left(  n\right)  $ success probability, we amplify the protocol $O\left(  n\right)  $ times, which just makes $y$ and $\widetilde{\sigma}$ polynomially longer.

The Complexity of Preparing Quantum Advice States\[LOCALHAM\]
-------------------------------------------------------------

If we combine Theorem \[yqpthm\] with known $\mathsf{QMA}$-completeness results, we can obtain a striking consequence for quantum complexity theory.  Namely, *the preparation of quantum advice states can always be reduced to the preparation of ground states of local Hamiltonians*—despite the fact that quantum advice states involve an exponential number of constraints, while ground states of local Hamiltonians involve only a polynomial number. * *In particular, if ground states of local Hamiltonians can be prepared by polynomial-size circuits, then we have not only ** $\mathsf{QMA}=\mathsf{QCMA}$, but also $\mathsf{BQP/qpoly}=\mathsf{BQP/poly}$.  The following theorem makes this connection precise.

\[localthm\]Let $Q$ be a polynomial-size quantum circuit that takes an advice state $\rho_{n}$.  Then there exists another polynomial-size quantum circuit $Q^{\prime}$ with the following property.  For all $n$ and $\varepsilon>0$, there exists a $2$-local Hamiltonian $H$ on $\operatorname*{poly}\left(  n,1/\varepsilon\right)  $ qubits, such that for all ground states $\left\vert \phi\right\rangle $ of $H$ and inputs $x\in\left\{  0,1\right\}  ^{n}$,$$\left\vert \Pr\left[  Q^{\prime}\text{ accepts }x,\left\vert \phi\right\rangle
\right]  -\Pr\left[  Q\text{ accepts }x,\rho_{n}\right]  \right\vert
\leq\varepsilon.$$ Furthermore, $Q^{\prime}$ can be efficiently generated given $Q$ together with a description of $H$.

Kempe, Kitaev, and Regev [@kkr] proved that the <span style="font-variant:small-caps;">2-Local Hamiltonians</span> problem is $\mathsf{QMA}$-complete.  Furthermore, examining their proof, we find that it yields the following stronger result.  Let $V$ be a $\mathsf{QMA}$ verification procedure with completeness and soundness errors $\delta$.  Then there exists a $2$-local Hamiltonian $H$, as well as a polynomial-time ‘recovery procedure’ $R$, such that if $\left\vert \phi\right\rangle
$ is any ground state of $H$, then with $\Omega\left(  1/\operatorname*{poly}\left(  n\right)  \right)  $ probability, $R\left(  \left\vert \phi
\right\rangle \right)  $ outputs a state $\left\vert \varphi\right\rangle
$ such that $\Pr\left[  V\text{ accepts }\left\vert \varphi\right\rangle
\right]  \geq1-\delta$.  To prove the stronger result: consider a ground state of $H$, which Kempe et al. show to be a *history state* of the form$$\left\vert \phi\right\rangle =\frac{1}{\sqrt{T}}\sum_{t=1}^{T}\left\vert
t\right\rangle \left\vert \phi_{t}\right\rangle .$$ Then $R$ can simply measure the clock register $\left\vert t\right\rangle $, postselect on obtaining the outcome $t=1$, and then retrieve $\left\vert
\varphi\right\rangle $ from the computation register $\left\vert \phi
_{1}\right\rangle $.

Indeed, we can strengthen the above result further, to increase $R$’s success probability from $\Omega\left(  1/\operatorname*{poly}\left(  n\right)
\right)  $ to $1-\delta$.  To do so, we simply increase the number of steps $T$ by a $1/\delta$ factor, then put additional terms in $H$, to impose the constraint that the computation should do nothing for the first $\left(
1-\delta\right)  T$ steps (leaving $\left\vert \phi_{1}\right\rangle
$ unchanged), and only apply $V$ during the final $\delta T$ steps.

Now let $Q$ be a polynomial-size quantum circuit that takes advice state $\rho_{n}$, and let $\left(  A,B\right)  $ be the $\mathsf{YQP/poly}$ checking algorithm (with error parameter $\delta$) from Theorem \[yqpthm\].  Then by the above, there exists a $2$-local Hamiltonian $H$ on $\operatorname*{poly}\left(  n,1/\delta\right)  $ qubits, as well as a polynomial-time algorithm $R$, such that

1.  If $\left\vert \phi\right\rangle $ is any ground state of $H$, then with at least $1-\delta$ probability, $R\left(  \left\vert
    \phi\right\rangle \right)  $ outputs a state $\left\vert \varphi\right\rangle
    $ such that $\Pr\left[  A\text{ accepts }\left\vert \varphi\right\rangle
    \right]  \geq1-\delta$.

2.  This $\left\vert \varphi\right\rangle $ satisfies $\left\vert
    B_{\varphi}\left(  x\right)  -Q_{\rho_{n}}\left(  x\right)  \right\vert
    \leq\delta$ for all $x\in\left\{  0,1\right\}  ^{n}$, where $B_{\varphi
    }\left(  x\right)  :=\Pr\left[  B\text{ accepts }x,\left\vert \varphi
    \right\rangle \right]  $ and $Q_{\rho_{n}}\left(  x\right)  :=\Pr\left[
    Q\text{ accepts }x,\rho_{n}\right]  $.

We can now combine $R$ and $B$ into a single algorithm $Q^{\prime}$, such that $\left\vert Q_{\phi}^{\prime}\left(  x\right)  -Q_{\rho_{n}}\left(  x\right)
\right\vert \leq2\delta$ for all $x\in\left\{  0,1\right\}  ^{n}$.  Setting $\delta:=\varepsilon/2$ then yields the corollary.

Let us make two remarks about Theorem \[localthm\].  First, as a ‘free byproduct,’ we get that$$\left\vert \Pr\left[  Q^{\prime}\text{ accepts }x,\left\vert \phi\right\rangle
\right]  -\Pr\left[  Q\text{ accepts }x,\rho_{n}\right]  \right\vert
\leq2\varepsilon$$ for all $\left\vert \phi\right\rangle $ that are $\varepsilon$*-close* in trace distance to a ground state of $H$.  Second, there is nothing special here about <span style="font-variant:small-caps;">2-Local Hamiltonians</span>.  So far as we know, *all* existing $\mathsf{QMA}$-completeness reductions have the property we needed for Theorem \[localthm\]: namely, the property that any ground state of the new instance can be transformed into a $\mathsf{QMA}$ witness for the original instance, with $\Omega\left(
1/\operatorname*{poly}\left(  n\right)  \right)  $ success probability.  As one example, Aharonov et al. [@agik] showed that even finding the ground state energy of a nearest-neighbor Hamiltonian on the line is $\mathsf{QMA}$-complete, provided the line is composed of qudits with $d\geq12$.  We can combine their result with Theorem \[yqpthm\] to show that for all $L\in\mathsf{BQP/qpoly}$, there exists a nearest-neighbor qudit Hamiltonian $H$ on the line, such that any ground state of $H$ is a valid quantum advice state for $L$.

Fix $c, \varepsilon > 0$, and let $\rho$ be the $n$-qubit state in Theorem \[mainthm0\]. Let $Q(C, \xi)$ be an efficiently constructible polynomial-size quantum circuit that takes a description of a quantum measurement circuit $C$ of size $n^c$, as well as a quantum state $\xi$ of $n$ qubits, and that outputs the measurement result $C(\xi)$.

Fix $\rho_n := \rho$. Let $H$ be the 2-local Hamiltonian given by Theorem \[localthm\], with ground state $\left\vert \psi\right\rangle$, and let $Q'(C, \xi)$ be the circuit in Theorem \[localthm\], which is efficiently constructible given $Q$ and $H$. Then, if we define the measurement $C'$ as $C'(\xi) := Q'(C, \xi)$, we have $$\left|C'\left(  \left\vert \psi\right\rangle \left\langle \psi\right\vert \right) - C(\rho) \right|  = \left| Q'\left(C, \left\vert \psi\right\rangle \left\langle \psi\right\vert \right) - Q(C, \rho) \right|  \leq \varepsilon.$$

Further Implications for Quantum Complexity Theory\[NERD\]
==========================================================

In this section, we use the $\mathsf{BQP/qpoly}=\mathsf{YQP/poly}$ theorem to harvest two more results about quantum complexity classes.  The first is an ‘exchange theorem’ stating that $\mathsf{QCMA/qpoly}\subseteq\mathsf{QMA/poly}$: in other words, *one can always simulate quantum advice together with a classical witness by classical advice together with a quantum witness*.  This is a straightforward generalization of Theorem \[yqpthm\].  The second result is a ‘Quantum Karp-Lipton Theorem,’ which states that if $\mathsf{NP}\subset\mathsf{BQP/qpoly}$ (that is, $\mathsf{NP}$-complete problems are efficiently solvable by quantum computers with quantum advice), then $\mathsf{\Pi}_{\mathsf{2}}^{\mathsf{P}}\subseteq
\mathsf{QMA}^{\mathsf{P{}romiseQMA}}$, which one can think of as ‘almost as bad’ as a collapse of the polynomial hierarchy.  This result makes essential use of Theorem \[yqpthm\], and is a good illustration of how that theorem can be applied in quantum complexity theory.

\[Exchange Theorem\]\[qcmaqpoly\]$\mathsf{QCMA/qpoly}\subseteq
\mathsf{QMA/poly}$.

The proof is almost the same as that of Theorem \[yqpthm\].  Let $L\in\mathsf{QCMA/qpoly}$.  Then there exists a polynomial-time quantum verifier $Q$, a family of polynomial-size advice states $\left\{  \rho
_{n}\right\}  _{n}$, and a polynomial $p$ such that for all inputs $x\in\left\{  0,1\right\}  ^{n}$:

-   $x\in L\implies\exists w\in\left\{  0,1\right\}  ^{p\left(  n\right)
    }~\Pr\left[  Q\left(  x,w,\rho_{n}\right)  \text{ accepts}\right]  \geq2/3.$

-   $x\notin L\implies\forall w\in\left\{  0,1\right\}  ^{p\left(  n\right)
    }~\Pr\left[  Q\left(  x,w,\rho_{n}\right)  \text{ accepts}\right]  \leq1/3.$

Now consider the following promise problem: given $x$ and $w$ as input, as well as a constant $c\in\left[  0,1\right]  $, decide whether $\Pr\left[
Q\left(  x,w,\rho_{n}\right)  \text{ accepts}\right]  $ is at most $c-1/10$ or at least $c+1/10$, promised that one of these is the case.  (Equivalently, *estimate* the probability within an additive error $\pm1/10$.)  This problem is clearly in $\mathsf{P{}romiseBQP/qpoly}$, since we can take $\rho_{n}$ as the advice.  So by Theorem \[yqpthm\], the problem is in $\mathsf{P{}romiseYQP/poly}$ as well.

We claim this implies $L\in\mathsf{QMA/poly}$.  For our $\mathsf{QMA/poly}$ verifier can take the $\mathsf{P{}romiseYQP/poly}$ advice string $a_{n}$ as its advice, and a state of the form $\sigma\otimes\left\vert w\right\rangle
\left\langle w\right\vert $ as its witness.  It can then do the following:

1.  Using $a_{n}$, check that $\sigma$ is a valid witness for the $\mathsf{P{}romiseYQP/poly}$ protocol, and reject if not.

2.  Using $\sigma$, check that $\Pr\left[  Q\left(  x,w,\rho
    _{n}\right)  \text{ accepts}\right]  \geq2/3$ (under the promise that it is either at least $2/3$ or at most $1/3$).

Indeed, let $\mathsf{YQ}$$\mathsf{QCMA}$ denote the complexity class where a $\mathsf{BQP}$ verifier receives a classical witness that depends on the input, as well as a quantum witness that depends only on the input size $n$.  Then we can *characterize* $\mathsf{QCMA/qpoly}$ as equal to $\mathsf{YQ}$$\mathsf{QCMA/poly}$, similarly to how we characterized $\mathsf{BQP/qpoly}$ as equal to $\mathsf{YQP/poly}$.

\[ptb\]

[yqpnew.eps]{}

We now use Theorem \[yqpthm\] to prove an analogue of the Karp-Lipton Theorem for quantum advice.

\[Quantum Karp-Lipton Theorem\]\[qkl\]If $\mathsf{NP}\subset
\mathsf{BQP/qpoly}$, then $\mathsf{\Pi}_{\mathsf{2}}^{\mathsf{P}}\subseteq\mathsf{QMA}^{\mathsf{P{}romiseQMA}}$.

By Theorem \[yqpthm\], the hypothesis implies $\mathsf{NP}\subset
\mathsf{YQP/poly}=\mathsf{YQP^{\mathsf{\ast}}/poly}$.  So let $Q$ be a $\mathsf{YQP^{\mathsf{\ast}}/poly}$ algorithm to decide $SAT$, which takes an input $x$, a trusted advice string $a$, and an untrusted advice state $\rho$.  Let $a^{\ast}$ be the correct value of the advice string.

Now consider an arbitrary language $L\in\mathsf{\Pi}_{\mathsf{2}}^{\mathsf{P}}$, which is defined by a polynomial-time predicate $R\left(  x,y,z\right)
$ like so:

-   $x\in L\Longleftrightarrow\forall y\exists z~R\left(  x,y,z\right)  $.

Using $Q$, we can create a pair of quantum algorithms $Q_{1}\left(
a,\rho\right)  $, $Q_{2}\left(  \rho,x,y\right)  $ with the following properties:

-   There exists a $\rho\ $such that $\Pr\left[  Q_{1}\left(  a^{\ast
    },\rho\right)  \text{ accepts}\right]  \geq2/3$.

-   If $\Pr\left[  Q_{1}\left(  a^{\ast},\rho\right)  \text{
    accepts}\right]  \geq1/3$, then for all $x,y$ pairs, $\Pr\left[  Q_{2}\left(
    \rho,x,y\right)  \text{ accepts}\right]  \geq2/3$ if there exists a $z$ such that $R\left(  x,y,z\right)  $ holds, and $\Pr\left[  Q_{2}\left(
    \rho,x,y\right)  \text{ accepts}\right]  \leq1/3$ otherwise.

Using standard amplification and $\mathsf{NP}$ self-reducibility, we can then strengthen property (P2) to the following, for some quantum algorithm $Q_{2}^{\prime}\left(  \rho,x,y\right)  $:

-   If $\Pr\left[  Q_{1}\left(  a^{\ast},\rho\right)  \text{
    accepts}\right]  \geq1/3$, then for all $x,y$ pairs, $Q_{2}^{\prime}\left(
    \rho,x,y\right)  $ *outputs* a $z$ such that $R\left(  x,y,z\right)  $ holds with probability at least $2/3$, whenever such a $z$ exists.

Now let $U\left(  a,\rho,x,y\right)  $ be a quantum algorithm that does one of the following, both with equal probability:

-   Runs $Q_{1}\left(  a,\rho\right)  $, and accepts if and only if it rejects.

-   Runs $Q_{2}^{\prime}\left(  \rho,x,y\right)  $, and accepts if and only if $R\left(  x,y,Q_{2}^{\prime}\left(  \rho,x,y\right)  \right)  $ holds.

Then we claim that

-   $x\in L\Longrightarrow\exists a,\rho\left[  \Pr\left[
    Q_{1}\left(  a,\rho\right)  \text{ accepts}\right]  \geq2/3\right]
    \wedge\left[  \forall\sigma,y~\Pr\left[  U\left(  a,\sigma,x,y\right)  \text{
    accepts}\right]  \geq1/3\right]  $.

-   $x\notin L\Longrightarrow\forall a,\rho\left[  \Pr\left[
    Q_{1}\left(  a,\rho\right)  \text{ accepts}\right]  \leq1/2\right]
    \vee\left[  \exists\sigma,y~\Pr\left[  U\left(  a,\sigma,x,y\right)  \text{
    accepts}\right]  \leq1/4\right]  $.

It is clear that this claim implies $L\in\mathsf{QMA}^{\mathsf{P{}romiseQMA}}$.  (The crucial point here is that $U$ does *not* take the existentially-quantified advice state $\rho$ as input—and therefore, the $\mathsf{QMA}$ machine does not need to pass a quantum state to the $\mathsf{P{}romiseQMA}$ oracle, which would be illegal.  This is why we needed the $\mathsf{BQP/qpoly}=\mathsf{YQP^{\mathsf{\ast}}/poly}$ theorem for this result.)

We now prove the claim.  First suppose $x\in L$.  Then there exists an advice string $a=a^{\ast}$ with the following properties:

-   There exists a $\rho$ such that $\Pr\left[  Q_{1}\left(
    a,\rho\right)  \text{ accepts}\right]  \geq2/3$.  (By (P1).)

-   For all $\sigma,y$ pairs, either $\Pr\left[  Q_{1}\left(
    a,\sigma\right)  \text{ rejects}\right]  \geq2/3$, or $\Pr\left[  R\left(
    x,y,Q_{2}^{\prime}\left(  \sigma,x,y\right)  \right)  \text{ holds}\right]
    \geq2/3$.  (By (P2’) and  $x\in L$.)

By (B2), we have $\forall\sigma,y~\Pr\left[  U\left(  a,\sigma,x,y\right)
\text{ accepts}\right]  \geq1/3$.  This proves (A1).

Next suppose $x\notin L$.  Then given an advice string $a$, suppose there exists a $\rho$ such that $\Pr\left[  Q_{1}\left(  a,\rho\right)  \text{
accepts}\right]  >1/2$.  Set $\sigma:=\rho$, and choose a $y$ for which there is *no* $z$ such that $R\left(  x,y,z\right)  $ holds.  Then

-   $\Pr\left[  Q_{1}\left(  a,\sigma\right)  \text{ rejects}\right]  <1/2$.  (By assumption.)

-   $\Pr\left[  R\left(  x,y,Q_{2}^{\prime}\left(  \sigma,x,y\right)
    \right)  \text{ holds}\right]  =0$.  (By $x\notin L$.)

Combining these, $\Pr\left[  U\left(  a,\sigma,x,y\right)  \text{
accepts}\right]  <1/4$.  This proves (A2), and hence the claim, and hence the lemma.

Previously, Aaronson [@aar:subtle] showed that if $\mathsf{PP}\subset
\mathsf{BQP/qpoly}$, then the counting hierarchy $\mathsf{CH}$ collapses.  However, he had been unable to show that $\mathsf{NP}\subset
\mathsf{BQP/qpoly}$ would have unlikely consequences in the uniform world.

Open Problems\[OPEN\]
=====================

One open problem is simply to find more applications of the majority-certificates lemma, which seems likely to have uses outside of quantum complexity theory; we mention one application (to ‘untrusted oracles’) in Appendix \[UORACLE\]. Can we improve the parameters of the majority-certificates lemma (the size of the certificates or the number $O\left(  n\right)  $ of certificates), or alternatively, show that the current parameters are essentially optimal?  Also, can we prove the real-valued majority-certificates lemma with an error tolerance $\alpha$ that depends only on the desired accuracy $\varepsilon$ of the final approximation, not on $n$ or the fat-shattering dimension of $S$?

On the quantum complexity side, we mention several questions.  First, in Theorem \[localthm\], is the polynomial blowup in the number of qubits unavoidable?  Could one hope for a way to simulate an $n$-qubit advice state by the ground state of $n$-qubit local Hamiltonian, or would that have implausible complexity consequences?  Second, can we use the ideas in this paper to prove any upper bound on the class $\mathsf{QMA/qpoly}$ better than the $\mathsf{PSPACE/poly}$ upper bound shown by Aaronson [@aar:qmaqpoly]?  Third, if $\mathsf{NP}\subset\mathsf{BQP/qpoly}$, then does $\mathsf{QMA}^{\mathsf{P{}romiseQMA}}$ contain not just $\mathsf{\Pi}_{\mathsf{2}}^{\mathsf{P}}$ but the entire polynomial hierarchy? Finally, is $\mathsf{BQP/qpoly} = \mathsf{BQP/poly}$?

Acknowledgments
===============

We thank Sanjeev Arora, Kai-Min Chung, Avinatan Hassidim, John Watrous, and Colin Zheng for helpful discussions, and the anonymous reviewers for their comments.

Appendix: Untrusted Oracles\[UORACLE\]
======================================

In this appendix, we give an interesting consequence of the majority-certificates lemma for classical complexity theory.

When we give a machine an oracle, normally we assume the oracle can be trusted.  But it is also natural to consider *untrusted* oracles, which are nevertheless restricted in their computational power.  We formalize this notion as follows:

\[Untrusted Oracles\]Let $\mathcal{C}$ and $\mathcal{D}$ be complexity classes.  Also, given a family $a=\left\{  a_{n}\right\}  _{n\geq1}$ of $p\left(  n\right)  $-bit advice strings and a machine $V$, let $V\left[
a\right]  $ be the language decided by $V$ given $a$ as advice.  Then $\mathcal{C}^{\mathsf{Untrusted}\text{-}\mathcal{D}}$ is the class of languages $L$ for which there exists a $\mathcal{C}$ machine $U$, a $\mathcal{D}$ machine $V$, and a polynomial $p$ such that for all $n$:

1.  There exist $p\left(  n\right)  $-bit advice strings $a_{1},\ldots,a_{m}$ such that $U^{V\left[  a_{1}\right]  ,\ldots,V\left[
    a_{m}\right]  }$ decides $L$.

2.  $U^{V\left[  a_{1}\right]  ,\ldots,V\left[  a_{m}\right]  }\left(
    x\right)  $ outputs either $L\left(  x\right)  $ or ‘FAIL’, for all inputs $x\in\left\{  0,1\right\}  ^{n}$ and all $p\left(  n\right)  $-bit advice strings $a_{1},\ldots,a_{m}$.

We can now state the consequence.

\[untrustedthm\]Let $\mathcal{C}$ be a uniform syntactic complexity class, such as $\mathsf{P}$, $\mathsf{NP}$, or $\mathsf{EXP}$.  Then $\mathcal{C}\mathsf{/poly}\subseteq\left(  \mathsf{AC}^{0}\right)  ^{\mathsf{Untrusted}\text{-}\mathcal{C}}$.

Let $V$ be a $\mathcal{C}\mathsf{/poly}$ machine that uses a family $a=\left\{  a_{n}\right\}  _{n\geq1}$ of $p\left(  n\right)  $-bit advice strings.  Fix an input length $n$, and let $f_{w}\left(  x\right)  $ be the output of $V$ on input $x$ and advice string $w\in\left\{  0,1\right\}
^{p\left(  n\right)  }$.  Then $S=\left\{  f_{w}\right\}  _{w\in\left\{
0,1\right\}  ^{p\left(  n\right)  }}$ is a Boolean concept class of size $\left\vert S\right\vert \leq2^{\operatorname*{poly}\left(  n\right)  }$.  So by Lemma \[majcer\], there exist $m=O\left(  n\right)  $ polynomial-size certificates $C_{1},\ldots,C_{m}$, which isolate functions $f_{1},\ldots
,f_{m}\in S$ respectively such that $\operatorname*{MAJ}\left(  f_{1},\ldots,f_{m}\right)  =f_{a_{n}}$.  Now, we can easily modify the proof of Lemma \[majcer\] to ensure not only that $\operatorname*{MAJ}\left(
f_{1},\ldots,f_{m}\right)  =f^{\ast}$, but also that$$\begin{aligned}
f_{a_{n}}\left(  x\right)   &  =1\Longrightarrow f_{1}\left(  x\right)
+\cdots+f_{m}\left(  x\right)  \geq\frac{2m}{3},\\
f_{a_{n}}\left(  x\right)   &  =0\Longrightarrow f_{1}\left(  x\right)
+\cdots+f_{m}\left(  x\right)  \leq\frac{m}{3}$$ for all inputs $x$.  To do so, we simply take $m=O\left(  n\right)
$ sufficiently large and redo the Chernoff bound.  Furthermore, it is known that <span style="font-variant:small-caps;">Approximate Majority</span>—that is, <span style="font-variant:small-caps;">Majority</span> where the fraction of $1$’s in the input is bounded away from $1/2$ by a constant—can be computed by polynomial-size depth-$3$ circuits, so in particular, in $\mathsf{AC}^{0}$ (see Viola [@viola:maj] for example).

By hardwiring the certificates $C_{1},\ldots,C_{m}$ into the $\mathsf{AC}^{0}$ circuit, we can produce an $\mathsf{AC}^{0}$ circuit that first checks whether $f_{i}$ is consistent with $C_{i}$ for all $i\in\left[
m\right]  $, outputs ‘FAIL’ if not, and otherwise outputs $U^{f_{1},\ldots,f_{m}}\left(  x\right)  =f_{a_{n}}\left(
x\right)  $.

If $\mathcal{C}$ is a semantic complexity class, such as $\mathsf{BPP}$ or $\mathsf{UP}$, the difficulty is that there might be a $\mathcal{C}\mathsf{/poly}$ machine $M$ and advice string $w$ for which the function $f_{w}$ is undefined (since $M$ need not decide a language for every $w$).  However, if we force the $\mathsf{Untrusted-}\mathcal{C}$ oracle to restrict itself to $w$ for which $f_{w}$ *is* defined, then Theorem \[untrustedthm\] goes through for semantic classes as well.  Using the *real*-valued majority-certificates lemma that we develop in Section \[REALMAJ\], it is possible to remove the assumption that $f_{w}$ is defined for all $w$ for semantic classes such as $\mathsf{BPP}$.

Appendix: Isolatability and Learnability\[ISOLNLEARN\]
======================================================

The following definition abstracts a key notion from the majority-certificates lemma.

\[Majority-Isolatability\]A Boolean concept class $S$ *is majority-isolatable if for every* $f\in S$*, there exist* $m=\operatorname*{poly}\left(  n\right)  $* certificates* $C_{1},\ldots,C_{m}$*, each of size* $\operatorname*{poly}\left(
n\right)  $*, such that*

1.  $S\left[  C_{i}\right]  $ is nonempty for all $i\in\left[
    m\right]  $, and

2.  if $f_{i}\in S\left[  C_{i}\right]  $ for all $i\in\left[
    m\right]  $, then $\operatorname*{MAJ}\left(  f_{1},\ldots,f_{m}\right)  =f$, where $\operatorname*{MAJ}$ denotes pointwise majority.

We now show that the majority-isolatability of a Boolean concept class $S$ is equivalent to a large number of other properties of $S$—including having singly-exponential cardinality, having polynomial VC-dimension, being PAC-learnable using $\operatorname*{poly}\left(  n\right)  $ samples, and being ‘winnowable.’  While we do not need this equivalence theorem elsewhere in the paper, it might be of interest anyway.  Note that the equivalence theorem is easily seen to break down for concept classes with infinite input domains.

\[VC-dimension\]We say a Boolean concept class $S$ *shatters* the set $A\subseteq\left\{  0,1\right\}  ^{n}$ if for all $2^{\left\vert A\right\vert
}$ functions $g:A\rightarrow\left\{  0,1\right\}  $, there exists an $f\in
S$ whose restriction to $A$ equals $g$.  Then the VC-dimension of $S$, or $\operatorname*{VCdim}\left(  S\right)  $, is the size of the largest set shattered by $S$.

Given a distribution $\mathcal{D}$ over $\left\{  0,1\right\}  ^{n}$, we say the Boolean functions $f,g:\left\{  0,1\right\}  ^{n}\rightarrow\left\{
0,1\right\}  $ are $\left(  \mathcal{D},\varepsilon\right)  $*-close* if$$\Pr_{x\sim\mathcal{D}}\left[  g\left(  x\right)  =f\left(  x\right)  \right]
\geq1-\varepsilon.$$

\[Learnability\]$S$ is learnable if for all $f\in S$, distributions $\mathcal{D}$, and $\varepsilon,\delta>0$, there exists an $m=\operatorname*{poly}\left(  n,1/\varepsilon,\log1/\delta\right)  $ such that with probability at least $1-\delta$ over sample points $x_{1},\ldots,x_{m}$ drawn independently from $\mathcal{D}$, every $g\in
S$ satisfying $g\left(  x_{1}\right)  =f\left(  x_{1}\right)  ,\ldots
,g\left(  x_{m}\right)  =f\left(  x_{m}\right)  $ is $\left(  \mathcal{D},\varepsilon\right)  $-close to $f$.

We can also define ‘approximability,’ which is like learnability except that the choice of training examples can be nondeterministic:

\[Approximability\]$S$ is approximable if for all $f\in S$ and distributions $\mathcal{D}$, there exists a certificate $C$ of size $\operatorname*{poly}\left(  n,1/\varepsilon\right)  $ such that every $g\in S\left[  C\right]  $ is $\left(  \mathcal{D},\varepsilon\right)  $-close to $f$.

Finally, let us call attention to a notion that implicitly played a major role in the proof of Lemma \[majcer\].

\[Winnowability\]$S$ is winnowable if for all nonempty subsets $S^{\prime
}\subseteq S$, there exists a certificate $C$ of size $\operatorname*{poly}\left(  n\right)  $ such that $\left\vert S^{\prime}\left[  C\right]
\right\vert =1$.

We can now prove the equivalence theorem.

\[equivthm\]Let $S$ be a Boolean concept class.  Then $\left\vert
S\right\vert \leq2^{\operatorname*{poly}\left(  n\right)  }$ iff $\operatorname*{VCdim}\left(  S\right)  \leq\operatorname*{poly}\left(
n\right)  $ iff $S$ is learnable iff $S$ is approximable iff $S$ is majority-isolatable iff $S$ is winnowable.

$\left\vert S\right\vert \leq2^{\operatorname*{poly}\left(  n\right)
}\Longrightarrow\operatorname*{VCdim}\left(  S\right)  \leq
\operatorname*{poly}\left(  n\right)  $ follows from the trivial upper bound $\operatorname*{VCdim}\left(  S\right)  \leq\log_{2}\left\vert S\right\vert $.

$\operatorname*{VCdim}\left(  S\right)  \leq\operatorname*{poly}\left(
n\right)  \Longrightarrow\left\vert S\right\vert \leq2^{\operatorname*{poly}\left(  n\right)  }$ is Sauer’s Lemma [@sauer], which implies the relation $\left\vert S\right\vert \leq2^{n\operatorname*{VCdim}\left(  S\right)  }$.

$\left\vert S\right\vert \leq2^{\operatorname*{poly}\left(  n\right)
}\Longrightarrow$**Learnable** was proved by Valiant [@valiant:pac].

**Learnable**$\Longrightarrow$**Approximable** is immediate, and **Approximable**$\Longrightarrow\operatorname*{VCdim}\left(  S\right)
\leq\operatorname*{poly}\left(  n\right)  $ follows from a counting argument (see Blumer et al. [@behw] for details).

$\left\vert S\right\vert \leq2^{\operatorname*{poly}\left(  n\right)
}\Longrightarrow$**Majority-Isolatable** was the content of Lemma \[majcer\].

**Majority-Isolatable**$\Longrightarrow\left\vert S\right\vert
\leq2^{\operatorname*{poly}\left(  n\right)  }$ follows from another counting argument: if $S$ is majority-isolatable, then every $f\in S$ is uniquely determined by $\operatorname*{poly}\left(  n\right)  $ certificates $C_{1},\ldots,C_{m}$, each of which can be specified using $\operatorname*{poly}\left(  n\right)  $ bits.

For $\left\vert S\right\vert \leq2^{\operatorname*{poly}\left(  n\right)
}\Longrightarrow$**Winnowable**, let $S^{\prime}\subseteq S$.  Then as in the proof of Lemma \[majcer\], we can use binary search to winnow $S^{\prime}$ down to a single function $f\in S^{\prime}$, which yields a certificate of size at most $\log_{2}\left\vert S^{\prime}\right\vert \leq
\log_{2}\left\vert S\right\vert $.

For **Winnowable**$\Longrightarrow\left\vert S\right\vert \leq
2^{\operatorname*{poly}\left(  n\right)  }$, we prove the contrapositive.  Suppose $\left\vert S\right\vert \geq2^{t\left(  n\right)  }$ for some superpolynomial function $t\left(  n\right)  $ (at least, for infinitely many $n$).  Then define a subset $S^{\prime}\subseteq S$ by the following iterative procedure.  Initially $S^{\prime}=S$.  Then so long as there exists a certificate $C$ of size at most $t\left(  n\right)  /\left(
2n+2\right)  $ such that $\left\vert S^{\prime}\left[  C\right]  \right\vert
=1$, remove the function $f\in S^{\prime}\left[  C\right]  $ from $S^{\prime}$, halting only when no more such ‘isolating certificates’ can be found.

The number of certificates of size $k$ is at most $2^{\left(  n+1\right)  k}$, and a given certificate $C$ can only be chosen once, since thereafter $S^{\prime}\left[  C\right]  $ is empty.  So when the above procedure halts, we are left with a set $S^{\prime}$ such that $\left\vert S^{\prime
}\right\vert \geq2^{t\left(  n\right)  }-2^{\left(  n+1\right)  t\left(
n\right)  /\left(  2n+2\right)  }>0$.  Furthermore, for every function $f$ remaining in $S^{\prime}$, there can be no polynomial-size certificate $C$ such that $S^{\prime}\left[  C\right]  =\left\{  f\right\}  $—for if there were, then we would already have eliminated $f$ in the process of forming $S^{\prime}$.  Hence $S$ is not winnowable.

Appendix: Winnowing of p-Concept Classes\[WINNOW\]
==================================================

In this appendix, we look more closely at the problem solved by Lemma \[linfwinnow\] (the ‘Safe Winnowing Lemma’), and ask in what senses it is possible to winnow a p-concept class down to ‘essentially’ just one function.  The answer turns out to be interesting, even though we do not need it for our quantum complexity applications.

We first give a definition that abstracts part of what Lemma \[linfwinnow\] was trying to accomplish.

\[Winnowability\]A p-concept class $S$ is $L_{1}$-winnowable if the following holds.  For all nonempty subsets $S^{\prime}\subseteq S$ and $\varepsilon>0$, there exists a function $f\in S^{\prime}$, a set $X\subseteq\left\{
0,1\right\}  ^{n}$ of size $\operatorname*{poly}\left(  n,1/\varepsilon
\right)  $, and a $\delta=\operatorname*{poly}\left(  \varepsilon\right)
$ such that every $g\in S^{\prime}$ that satisfies $\Delta_{1}\left(
f,g\right)  \left[  X\right]  \leq\delta$ also satisfies $\Delta_{\infty
}\left(  f,g\right)  \leq\varepsilon$.  Likewise, $S$ is $L_{2}$-winnowable if $\Delta_{2}\left(  f,g\right)  \left[  X\right]  \leq\delta
$ implies $\Delta_{\infty}\left(  f,g\right)  \leq\varepsilon$, and $L_{\infty}$-winnowable if $\Delta_{\infty}\left(  f,g\right)  \left[
X\right]  \leq\delta$ implies $\Delta_{\infty}\left(  f,g\right)
\leq\varepsilon$.

Clearly $L_{\infty}$-winnowability implies $L_{2}$-winnowability implies $L_{1}$-winnowability.  The following lemma will imply that every set of functions with a small cover is $L_{1}$-winnowable.

\[$L_{1}$-Winnowing Lemma\]\[l1lem\]Let $S$ be a set of functions $f:\left\{  0,1\right\}  ^{n}\rightarrow\left[  0,1\right]  $.  For some parameter $\varepsilon>0$, let $C$ be a finite $\varepsilon$-cover for $S$.  Then there exists an $f\in S$, as well as a subset $X\subseteq\left\{
0,1\right\}  ^{n}$ of size $O\left(  \frac{1}{\varepsilon}\log\left\vert
C\right\vert \right)  $, such that every $g\in S$ that satisfies $\Delta
_{1}\left(  f,g\right)  \left[  X\right]  \leq0.4\varepsilon$ also satisfies $\Delta_{\infty}\left(  f,g\right)  \leq2\varepsilon$.

We will consider functions $P:S\rightarrow\left[  0,1\right]  $, which we think of as assigning a probability weight $P\left(  g\right)  $ to each function $g\in S$.  In particular, given an $f\in S$ and a subset of inputs $X\subseteq\left\{  0,1\right\}  ^{n}$, define$$P_{f,X}\left(  g\right)  :=\exp\left(  -\Delta_{1}\left(  f,g\right)  \left[
X\right]  \right)  .$$ Clearly $P_{f,X}\left(  f\right)  =1$.  Our goal will be to find $f\in
S$ and $X\subseteq\left\{  0,1\right\}  ^{n}$, with $\left\vert X\right\vert
=O\left(  \frac{1}{\varepsilon}\log\left\vert C\right\vert \right)  $, such that every $g\in S$ that satisfies $P_{f,X}\left(  g\right)  \geq
e^{-0.4\varepsilon}$ also satisfies $\Delta_{\infty}\left(  f,g\right)
\leq2\varepsilon$.  Supposing we have found such an $\left(  f,X\right)
$ pair, the lemma is proved.

Consider the progress measure$$M_{f,X}:=\sum_{h\in C}P_{f,X}\left(  h\right)  .$$ Clearly $M_{f,X}\leq\left\vert C\right\vert $ for all $\left(  f,X\right)  $.  We claim, furthermore, that $M_{f,X}\geq\exp\left(  -\varepsilon\left\vert
X\right\vert \right)  $ for all $\left(  f,X\right)  $.  For since $C$ is an $\varepsilon$-cover for $S$, there always exists an $h\in C$ such that $\Delta_{1}\left(  f,h\right)  \left[  X\right]  \leq\varepsilon\left\vert
X\right\vert $, and that $h$ alone contributes at least $\exp\left(
-\varepsilon\left\vert X\right\vert \right)  $ to $M_{f,X}$.

We will construct $\left(  f,X\right)  $ by an iterative process.  Initially $f$ is arbitrary and $X$ is the empty set, so $P_{f,X}\left(  g\right)
=1$ for all $g$, and $M_{f,X}=\left\vert C\right\vert $.  Now, suppose there exists a $g\in S$ such that $P_{f,X}\left(  g\right)  \geq e^{-0.4\varepsilon
}$, as well as an input $y$ such that $\left\vert f\left(  y\right)  -g\left(
y\right)  \right\vert >2\varepsilon$.  As a first step, let $Y:=X\cup\left\{
y\right\}  $ (that is, add $y$ into our set of inputs).  Then the crucial claim is that either $M_{f,Y}$ or $M_{g,Y}$ is a $1-\Omega\left(
\varepsilon\right)  $ factor smaller than $M_{f,X}$.  This means in particular that, by replacing $X$ with $Y$ (increasing $\left\vert
X\right\vert $ by $1$), and possibly also replacing $f$ with $g$, we can decrease $M_{f,X}$ by a $1-\Omega\left(  \varepsilon\right)  $ factor compared to its previous value.  Since $\exp\left(  -\varepsilon\left\vert
X\right\vert \right)  \leq M_{f,X}\leq\left\vert C\right\vert $, it is clear that $M_{f,X}$ can decrease in this way at most$$O\left(  \log_{1+\varepsilon}\frac{\left\vert C\right\vert }{\exp\left(
-\varepsilon\left\vert X\right\vert \right)  }\right)$$ times.  Setting the above expression equal to $\left\vert X\right\vert $ and solving, we find that the process must terminate when $\left\vert X\right\vert
=O\left(  \frac{1}{\varepsilon}\log\left\vert C\right\vert \right)  $, returning an $\left(  f,X\right)  $ pair with the properties we want.

We now prove the crucial claim.  The first step is to show that either$$M_{f,Y}=\sum_{h\in C}P_{f,X}\left(  h\right)  e^{-\left\vert f\left(
y\right)  -h\left(  y\right)  \right\vert }$$ or else$$M^{\prime}:=\sum_{h\in C}P_{f,X}\left(  h\right)  e^{-\left\vert g\left(
y\right)  -h\left(  y\right)  \right\vert }$$ is at most$$\frac{1+e^{-\varepsilon}}{2}M_{f,X}.$$ For since $\left\vert f\left(  y\right)  -g\left(  y\right)  \right\vert
>2\varepsilon$, either $\left\vert f\left(  y\right)  -h\left(  y\right)
\right\vert >\varepsilon$ or $\left\vert g\left(  y\right)  -h\left(
y\right)  \right\vert >\varepsilon$ by the triangle inequality.  So for every $y$, either $e^{-\left\vert f\left(  y\right)  -h\left(  y\right)  \right\vert
}<e^{-\varepsilon}$ or $e^{-\left\vert g\left(  y\right)  -h\left(  y\right)
\right\vert }<e^{-\varepsilon}$.  This in turn means that either $M_{f,Y}$ or $M^{\prime}$ must have at least half its terms (as weighted by the $P_{f,X}\left(  h\right)  $’s) shrunk by an $e^{-\varepsilon}$ factor.

If $M_{f,Y}<\frac{1+e^{-\varepsilon}}{2}M_{f,X}$ then we are done.  So suppose instead that $M^{\prime}<\frac{1+e^{-\varepsilon}}{2}M_{f,X}$.  Then$$\begin{aligned}
M_{g,Y}  &  =\sum_{h\in C}P_{g,X}\left(  h\right)  e^{-\left\vert g\left(
y\right)  -h\left(  y\right)  \right\vert }\\
&  \leq M^{\prime}\max_{h\in C}\frac{P_{g,X}\left(  h\right)  }{P_{f,X}\left(
h\right)  }\\
&  =M^{\prime}\max_{h\in C}\frac{\exp\left(  -\Delta_{1}\left(  g,h\right)
\left[  X\right]  \right)  }{\exp\left(  -\Delta_{1}\left(  f,h\right)
\left[  X\right]  \right)  }\\
&  \leq M^{\prime}\exp\left(  \Delta_{1}\left(  f,g\right)  \left[  X\right]
\right) \\
&  =\frac{M^{\prime}}{P_{f,X}\left(  g\right)  }\\
&  <\frac{\frac{1+e^{-\varepsilon}}{2}M_{f,X}}{e^{-0.4\varepsilon}}\\
&  <\left(  1-\frac{\varepsilon}{20}\right)  M_{f,X}$$ and we are done.

Recall that $S$ is *coverable* if for all $\varepsilon>0$, there exists an $\varepsilon$-cover for $S$ of size $2^{\operatorname*{poly}\left(
n,1/\varepsilon\right)  }$.  We can now prove the following equivalence theorem.

\[l1winnowthm\]A p-concept class $S$ is coverable if and only if it is $L_{1}$-winnowable.

For **Coverable**$\Longrightarrow$**L**$_{1}$**-Winnowable**: fix a subset $S^{\prime}\subseteq S$ and an $\varepsilon>0$.  Let $C$ be an $\varepsilon/2$-cover for $S^{\prime}$ of size $2^{\operatorname*{poly}\left(  n,1/\varepsilon\right)  }$.  Then by Lemma \[l1lem\], there exists an $f\in S^{\prime}$, as well as a subset $X\subseteq\left\{  0,1\right\}
^{n}$ of size $O\left(  \frac{1}{\varepsilon}\log\left\vert C\right\vert
\right)  =\operatorname*{poly}\left(  n,1/\varepsilon\right)  $, such that every $g\in S^{\prime}$ that satisfies $\Delta_{1}\left(  f,g\right)  \left[
X\right]  \leq\varepsilon/5$ also satisfies $\Delta_{\infty}\left(
f,g\right)  \leq\varepsilon$.

For **L**$_{1}$-**Winnowable**$\Longrightarrow$**Coverable**, we prove the contrapositive.  Suppose there exists a function $t\left(
n,1/\varepsilon\right)  $, superpolynomial in either $n$ or $1/\varepsilon$, such that $S$ has no $\varepsilon$-cover of size $2^{t\left(  n,1/\varepsilon
\right)  }$ (at least, for infinitely many $n$ or $1/\varepsilon$).  Let $p=\operatorname*{poly}\left(  n,1/\varepsilon\right)  $ and $\delta
=\operatorname*{poly}\left(  \varepsilon\right)  $.  Given a function $f$ and subset $X\subseteq\left\{  0,1\right\}  ^{n}$, let $L\left[  f,X\right]  $ be the set of all functions $g$ such that $\Delta_{1}\left(  f,g\right)  \left[
X\right]  \leq\delta$.  Then our goal is to construct a subset $S^{\prime
}\subseteq S$ for which there is no pair $\left(  f,X\right)  $ such that

-   $f\in S^{\prime}$,

-   $X\subseteq\left\{  0,1\right\}  ^{n}$ is a set of inputs with $\left\vert X\right\vert =p$, and

-   $g\in S^{\prime}\cap L\left[  f,X\right]  $ implies $\Delta_{\infty
    }\left(  f,g\right)  \leq\varepsilon$.

Let $W:=\left\lceil 2p/\delta\right\rceil $.  Also, call a set $B$ of functions $f:\left\{  0,1\right\}  ^{n}\rightarrow\left[  0,1\right]  $ a *sliver* if there exists a set $X\subseteq\left\{  0,1\right\}  ^{n}$ with $\left\vert X\right\vert =p$, as well a function $a:X\rightarrow
\left[  W\right]  $, such that$$f\in B\Longleftrightarrow f\left(  x\right)  \in\left[  \frac{a\left(
x\right)  -1}{W},\frac{a\left(  x\right)  }{W}\right]  ~\forall x\in X.$$ Then define a subset $S^{\prime}\subseteq S$ by the following iterative procedure.  Initially $S^{\prime}=S$.  Then so long as there exists a sliver $B$ such that $S^{\prime}\cap B$ is nonempty, together with a function $f_{B}\in S$ such that$$g\in S^{\prime}\cap B\Longrightarrow\Delta_{\infty}\left(  f_{B},g\right)
\leq\varepsilon,$$ remove $B$ from $S^{\prime}$ (that is, set $S^{\prime}:=S^{\prime}\setminus
B$).  Halt only when no more such slivers $B$ can be found.

As a first observation, the total number of slivers is at most $\left(
2^{n}W\right)  ^{p}=2^{\operatorname*{poly}\left(  n,1/\varepsilon\right)  }$.  Thus, the above procedure must halt after at most $2^{\operatorname*{poly}\left(  n,1/\varepsilon\right)  }$ iterations.

As a consequence, we claim that $S^{\prime}$ must be nonempty after the procedure has halted.  For suppose not.  Then the sequence of functions $f_{B}$ chosen by the procedure would form an $\varepsilon$-cover for $S$ of size $2^{\operatorname*{poly}\left(  n,1/\varepsilon\right)  }$—since for all $g\in S$, we would simply need to find a sliver $B$ containing $g$ that was removed by the procedure; then $f_{B}$ would satisfy $\Delta_{\infty}\left(  f_{B},g\right)  \leq\varepsilon$.  But this contradicts the assumption that no such $\varepsilon$-cover exists.

Finally, we claim that once the procedure halts, there can be no $f\in
S^{\prime}$ and set $X$ of $p$ inputs such that $\Delta_{\infty}\left(
f,g\right)  \leq\varepsilon$ for all $g\in S^{\prime}\cap L\left[
f,X\right]  $.  For suppose to the contrary that such an $\left(  f,X\right)
$ pair existed.  It is not hard to see that for every $\left(  f,X\right)
$, there exists a sliver $B$ that contains $f$ and is contained in $L\left[
f,X\right]  $.  But then $S^{\prime}\cap B$ would be nonempty, and $\left(
B,f\right)  $ would satisfy the condition $g\in S^{\prime}\cap
B\Longrightarrow\Delta_{\infty}\left(  f,g\right)  \leq\varepsilon$.  So $B$ (or some other sliver containing $f$) would already have been eliminated in the process of forming $S^{\prime}$.

A natural question is whether Lemma \[l1lem\] and Theorem \[l1winnowthm\] would also hold with $L_{2}$-winnowability or $L_{\infty}$-winnowability in place of $L_{1}$-winnowability.  The next theorem shows, somewhat surprisingly, that the use of the $L_{1}$ norm was essential.

\[l2no\]There exists a p-concept class $S$ that is coverable, but not $L_{2}$-winnowable or $L_{\infty}$-winnowable.

We prove a stronger statement: there exists a *finite* p-concept class $S$, of size $\left\vert S\right\vert \leq2^{\operatorname*{poly}\left(
n\right)  }$, that is not $L_{2}$-winnowable (and as a direct consequence, not $L_{\infty}$-winnowable either).  To prove this, it suffices to find a set $S$ with $\left\vert S\right\vert \leq2^{\operatorname*{poly}\left(  n\right)
}$, as well as a constant $\varepsilon>0$, for which the following holds.  For all $f\in S$, subsets $X\subseteq\left\{  0,1\right\}  ^{n}$ of size less than $2^{n}-n^{2}$, and constants $\delta$ depending on $\varepsilon$, there exists a $g\in S$ such that $\Delta_{2}\left(  f,g\right)  \left[
X\right]  \leq\delta$ but $\Delta_{\infty}\left(  f,g\right)  >\varepsilon
$ (at least, for all sufficiently large $n$).

Let $\varepsilon$ be any constant in $\left(  0,1\right)  $, and let $S$ be the class of all functions $f:\left\{  0,1\right\}  ^{n}\rightarrow\left[
0,1\right]  $ of the form$$f\left(  x\right)  =\frac{a_{x}}{n},$$ where the $a_{x}$’s are nonnegative integers satisfying$$\sum_{x\in\left\{  0,1\right\}  ^{n}}a_{x}=n^{2}.$$ Then clearly $\left\vert S\right\vert \leq\left(  2^{n}\right)  ^{n^{2}}$, since we can form any $f\in S$ by starting from the identically-$0$ function, then choosing $n^{2}$ inputs $x$ (with repetition) on which to increment $f$ by $1/n$.

Now let $f\in S$, and let $X\subseteq\left\{  0,1\right\}  ^{n}$ have size $\left\vert X\right\vert <2^{n}-n^{2}$.  Then we can ‘corrupt’ $f$ to create a new function $g\in S$ as follows.  Let $Z$ be a set of $n$ inputs $x\in\left\{  0,1\right\}  ^{n}$ on which $f\left(  x\right)  >0$ (note that such a $Z$ must exist, since $\sum
_{x}f\left(  x\right)  =n$ but $f\left(  x\right)  \leq1$ for all $x$).  By the pigeonhole principle, there exists a $y\in\left\{  0,1\right\}
^{n}\setminus X$ such that $f\left(  y\right)  =0$.  Fix that $y$, and define$$g\left(  x\right)  :=\left\{
\begin{array}
[c]{cc}1 & \text{if }x=y\\
f\left(  x\right)  -1/n & \text{if }x\in Z\\
f\left(  x\right)  & \text{otherwise.}\end{array}
\right.$$ Clearly $g\in S$ and$$\Delta_{2}\left(  f,g\right)  \left[  X\right]  =\sqrt{\sum_{x\in Z\cap
X}\frac{1}{n^{2}}}\leq\frac{1}{\sqrt{n}}.$$ On the other hand, we have $f\left(  y\right)  =0$ and $g\left(  y\right)
=1$, so $\Delta_{\infty}\left(  f,g\right)  =1$.  Therefore $S$ is not $L_{2}$-winnowable.

[^1]: Email: aaronson@csail.mit.edu.   This material is based upon work supported by the National Science Foundation under Grant No. 0844626.  Also supported by a DARPA YFA grant, a Sloan Fellowship, and the Keck Foundation.

[^2]: Email: adrucker@mit.edu.  This work was done while the author was supported by an Akamai Presidential Graduate Fellowship.

[^3]: We call this restricted class $\mathsf{YQP/poly}$; in another notation it would be $\mathsf{OQMA/poly}\cap\mathsf{coOQMA/poly}$ (where the $\mathsf{O}$ stands for ‘oblivious’).

[^4]: Aaronson and Kuperberg [@ak], however, give evidence that this problem might be in $\mathsf{QCMA}$, under conjectures related to the Classification of Finite Simple Groups.

[^5]: It would also be possible to apply the bound from [@aar:learn] ‘off-the-shelf,’ but at the cost of a worse dependence on $1/\varepsilon$.

[^6]: We will need $S_{\operatorname*{fin}}$ for the technical reason that the basic Minimax Theorem only works with finite strategy spaces.

[^7]: Aharonov and Regev actually defined $\mathsf{QMA}_{\mathsf{+}}$ in a slightly more general way.  However, the definition below is all we need; note that all these classes turn out to equal $\mathsf{QMA}$ anyway.

[^8]: $\mathsf{YP}$ stands for ‘Yoda Polynomial-Time,’ a nomenclature that seems to make neither more nor less sense than ‘Arthur-Merlin.’
