On the probability of preparing of a uniform superposition by performing a controlled-multiplication and post-selecting $0$

I take as a starting point Watrous’s celebrated paper defining the Quantum Merlin-Arthur (QMA) class. He provides a protocol for Arthur to test whether an element $h$ is not in a group $mathcal{H}$ with generating set $langle g_1,g_2,cdots, g_krangle$. Merlin gives Arthur a quantum state $vertmathcal{H’}rangle$ that is alleged to be a pure state corresponding to the uniform superposition over all elements of $mathcal{H}$:

$$vertmathcal H’rangle = frac{1}{sqrt{|mathcal H|}}sum_{ain
mathcal{H}} |arangle.$$

However, Arthur must test that Merlin really did provide such a state $vertmathcal{H’}rangle$. He does this by initially performing $j$ iterations of a controlled multiplication of $vertmathcal{H’}rangle$ by elements known to be in $mathcal{H}$, and testing that the control register reverts back to $vert 0rangle$ after Hadamarding. Watrous states that as long as we can post-select upon measuring $0$ in the control register, the state $vert mathcal{H’}rangle$ “will in fact be changed (by quantum magic!) to one that is invariant under right multiplication by elements in $mathcal{H}$.”

According to these notes from O’Donnell, it might suffice to uniformly choose $j$ generators $z_i$ from $langle g_1,g_2,cdots, g_krangle$. That is, if initially $vert mathcal{H’}rangle=sum_{ginmathcal{G}}a_gvert grangle$, then upon multiplying by $z_1$ and post-selecting $vert 0rangle$ on the control register for the first of the $j$ iterations, our state is:

$$vert mathcal{H’}rangle=sum_{ginmathcal{G}}a_gvert grangle + a_gvert gz_1rangle;$$

upon multiplying by $z_2$ and post-selecting $vert 0rangle$ on the control register for the second iteration, our state is:

$$vert mathcal{H’}rangle=sum_{ginmathcal{G}}a_gvert grangle + a_gvert gz_1rangle+a_gvert gz_2rangle+a_gvert gz_1z_2rangle;$$

etc.

Indeed, $vert mathcal{H’}rangle$ may initially correspond to a singleton state such as the state $vert e rangle$, where $e$ is the identity of $mathcal{H}$. Our probability of post-selecting $vert 0rangle$ in the control register appears to increase with each iteration – it may start off low, at $frac{1}{2}$, then with “quantum magic,” increase to greater and greater than $frac{1}{2}$ when $vertmathcal{H’}rangle$ includes most elements of $mathcal{H}$, then settle close to $1$ when $vertmathcal{H’}rangle$ is finally right-invariant.

If we did start off with such a singleton state $vertmathcal{H’}rangle=vert erangle$, how many such iterations must we do to be able to post-select a state that is exponentially close to being right-invariant under elements of $mathcal{H}$, and what is our probability of successfully post-selecting such a state?

In his wonderful lecture from 2012 at about the 25 minute mark, Watrous proposes that $j$ should be linear or at best quadratic in $log Vert mathcal{H}Vert$ and mentions that the generators should be “cube generators” having nice properties according to computational group theory.

But in the case of starting off in a singleton state such as $vert erangle$, can we learn anything about the properties of the specific set of generators $langle g_1,g_2,cdots, g_krangle$ by post-selecting to try and build our own uniform superposition?