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

Question

I take as a starting point Watrous's celebrated paper (arXiv) 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_k\rangle$. Merlin gives Arthur a quantum state $\vert\mathcal{H'}\rangle$ that is alleged to be a pure state corresponding to the uniform superposition over all elements of $\mathcal{H}$:

$$\vert\mathcal H'\rangle = \frac{1}{\sqrt{|\mathcal H|}}\sum_{a\in \mathcal{H}} |a\rangle.$$

However, Arthur must test that Merlin really did provide such a state $\vert\mathcal{H'}\rangle$. He does this by initially performing $j$ iterations of a controlled multiplication of $\vert\mathcal{H'}\rangle$ by elements known to be in $\mathcal{H}$, and testing that the control register reverts back to $\vert 0\rangle$ 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_k\rangle$. That is, if initially $\vert \mathcal{H'}\rangle=\sum_{g\in\mathcal{G}}a_g\vert g\rangle$, then upon multiplying by $z_1$ and post-selecting $\vert 0\rangle$ on the control register for the first of the $j$ iterations, our state is:

$$\vert \mathcal{H'}\rangle=\sum_{g\in\mathcal{G}}a_g\vert g\rangle + a_g\vert gz_1\rangle;$$

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

$$\vert \mathcal{H'}\rangle=\sum_{g\in\mathcal{G}}a_g\vert g\rangle + a_g\vert gz_1\rangle+a_g\vert gz_2\rangle+a_g\vert gz_1z_2\rangle;$$

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 0\rangle$ 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 $\vert\mathcal{H'}\rangle$ includes most elements of $\mathcal{H}$, then settle close to $1$ when $\vert\mathcal{H'}\rangle$ is finally right-invariant.

If we did start off with such a singleton state $\vert\mathcal{H'}\rangle=\vert e\rangle$, 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, 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 e\rangle$, can we learn anything about the properties of the specific set of generators $\langle g_1,g_2,\cdots, g_k\rangle$ by post-selecting to try and build our own uniform superposition?

Answer 1

CW from self-answer, and also because this is more of an extended comment than an answer.

Let $A$ be the adjacency matrix of the Cayley graph of our group $\mathcal{H}$ of order $N$. Notice that $A$ is square-hermitian. Further let $\mathbb{I}_N$ be the $N\times N$ identity matrix.

It occurs to me that I am, in a sense, asking to prepare the ground state $E_0$ of $A$ - i.e. the uniform superposition over all elements of $\mathcal{H}$ - by doing an initially very slow, very lazy random walk along $A$.

That is, it feels like $E_0$ of $A$ is adiabatically evolved, with an "initial Hamiltonian" being $\mathbb{I}_N+\epsilon A$ which acts on $\vert e\rangle$, and a "final Hamiltonian" being $A$ itself.

A defining paper on adiabatic state preparation appears to be Aharanov and Ta-Shma. I believe the speed at which one could prepare $A$ by such an evolution is indeed given by spectral properties of $A$, or rather of $\mathbb{I}_N+\epsilon A$.

Post-selection may be a bit of a red-herring. If post-selection doesn't work out one could just lower $\epsilon$, and make the walk lazier. What seems to be more important is that the system appears to stay in some ground state, as the adiabatic theorem implies.