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_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;$$


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 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 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?

  • 1
    $\begingroup$ Per O'Donnell (page 7), $\mathcal{O}(\text{poly}(n))$ iterations are needed where $n$ is the size of the generating set of the group $\mathcal{H}$. It's obvious that the lower bound must be $\Omega(\log_2 ||\mathcal{H'}||)$, as $\log_2 N$ is the minimum size of a generating set of a finite group of size $N$ (cf. this). Whether you begin with some random $g \in \mathcal{H}$ or the identity $e$ does not affect the estimate; every element can be written as $g^{-1}$ times something i.e., there exists a bijection between $\mathcal Hg$ and $\mathcal He$). $\endgroup$ Commented Dec 16, 2019 at 16:25
  • $\begingroup$ [cont.] Presumably, the exact scaling would depend on the specific randomized algorithm you're using to construct the right-invariant group (which, in fact, is the entire group $\mathcal{H}$). Note that O'Donnell uses the term "$\mathcal{H}$-invariant" rather than "right invariant" because if you can right-multiply by any group element you can effectively produce the entire group $\mathcal{H}$. That is, right invariance is achieved only when $\mathcal{H}$ is generated. $\endgroup$ Commented Dec 16, 2019 at 16:36
  • $\begingroup$ @SanchayanDutta thanks for taking the time to understand my question! I think everything you said is true - but I think the speed of being able to post-select an invariant superposition by multiplying by random elements of the generating set could depend on the group and the specific generating set itself. There might be some pathological generating sets that only slowly explore the group, that take a lot longer to build an invariant superposition. Also my knowledge of finite group theory is not strong but I suspect that the more abelian a group is, the easier it could be... $\endgroup$ Commented Dec 16, 2019 at 16:41
  • 2
    $\begingroup$ Yes, the result would very much depend on the specific nature and sizes of the group and the generating sets. Computational group theory is still largely a research topic, and this might even be a good question for Math Overflow or CS Theory SE. I'd encourage you to ask the question in those venues too. $\endgroup$ Commented Dec 16, 2019 at 16:46
  • 1
    $\begingroup$ Check Mark Sapir and O'Donnell's responses on Math Overflow. $\endgroup$ Commented Dec 21, 2019 at 15:12

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.