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 