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