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 