Quantum proof for the group non-membership problem

Question

Group non-membership problem:

Input: Group elements $g_1,..., g_k$ and $h$ of $G$.

Yes: $h \not\in \langle g_1, ..., g_k\rangle$

No: $h\in \langle g_1, ..., g_k\rangle$

Notation: $\langle g_1, ..., g_k\rangle$ is the subgroup generated by $g_1,...,g_k$.

Quantum proof:

The group non-membership problem is in $\mathsf{QMA}$. The idea is simple: for $\mathcal{H} = \langle g_1, ..., g_k\rangle$, the quantum proof that $h\in \mathcal{H}$ will be the state

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

Questions:

I think the idea of the proof is that if $|h\rangle$ can be shown to be orthogonal to $|\mathcal H\rangle$ then it would imply that that $h \not\in \mathcal{H}$. Otherwise, $h\in \mathcal{H}$. But how exactly are we supposed to assign quantum states (i.e. the $|a\rangle$'s) corresponding to the elements of $\mathcal{H}$? Do we need to assign separate binary strings to all the elements of the group generated by the elements of $G$, such that they can be represented by qubit systems?

And if we do assign such binary strings a priori, wouldn't it be much simpler to directly (classically) check whether the string assigned to $h$ matches with any of the strings corresponding to the elements of $\mathcal{H}$? I can't really see the speed advantage here. Could someone clarify this "quantum" proof?

---

^{Note: All quotes are from John Watrous - Quantum Complexity Theory (Part 2) - CSSQI 2012 (timestamp included).}

Answer 1

I think the idea of the proof is that if $|h\rangle$ can be shown to be orthogonal to $|\mathcal H\rangle$ then it would imply that that $h \not\in \mathcal{H}$. Otherwise, $h\in \mathcal{H}$.

Not really as far as the method shown in the linked video is concerned.

The algorithm described there uses a controlled-unitary operation of the form $$\newcommand{\ketbra}[1]{\lvert #1\rangle\!\langle #1\rvert} \mathcal U_h\equiv\ketbra0\otimes I+\ketbra1\otimes \mathcal M_h,$$ where $\mathcal M_h$ is the unitary that acts on each state $\lvert g\rangle$ representing the group element $g$ by sending this state into the state that represents the group element $hg$: $$\mathcal M_h\lvert g\rangle=\lvert hg\rangle.$$ Then, you can readily verify that $\mathcal M_h\lvert \mathcal H\rangle=\lvert \mathcal H\rangle$ (because $h\mathcal H=\mathcal H$), which I would call the "main idea" here. We are exploiting the fact that, given an arbitrary state $h\in G$, $$h\in\langle g_1,...,g_n\rangle=\mathcal H\Longleftrightarrow \mathcal M_h\lvert \mathcal H\rangle=\lvert \mathcal H\rangle,\\ h\notin\mathcal H\Longleftrightarrow \mathcal M_h\lvert \mathcal H\rangle\perp \lvert \mathcal H\rangle, $$ the latter fact following from the general result of group theory that $xH\cap H=\{\}$ if $x\notin H$ and $H$ is a subgroup of a group $G$.

Having $\mathcal M_h$ as controlled by an additional qubit can then be thought of as just a gimmick to have the first qubit tell us deterministically which one of the two cases are we dealing with.

In the case $h\in\mathcal H$, we have $$\lvert +\rangle\lvert\mathcal H\rangle\xrightarrow[]{\mathcal U_h}\lvert+\rangle\lvert\mathcal H\rangle \xrightarrow[]{H_1}\lvert0\rangle\lvert\mathcal H\rangle,$$ while in the case $h\notin\mathcal H$, we get (ignoring normalization constants) $$ \lvert +\rangle\lvert\mathcal H\rangle\xrightarrow[]{\mathcal U_h}\lvert0\rangle\lvert\mathcal H\rangle+\lvert1\rangle\lvert hH\rangle\xrightarrow[]{H_1} \lvert0\rangle\otimes(\lvert\mathcal H\rangle+\lvert h\mathcal H\rangle) + \lvert1\rangle\otimes(\lvert\mathcal H\rangle-\lvert h\mathcal H\rangle). $$ Now, it doesn't really matter what the exact states in the second register are in the last bit. What matters is that we have something of the form $\lvert0\rangle\lvert a\rangle+\lvert 1\rangle\lvert b\rangle$, with $\langle a\rvert b\rangle=0$. For any state like this, measuring the first qubit gives you equal probabilities of finding $\lvert0\rangle$ and $\lvert1\rangle$. You then just need to repeat the experiment a few times to assess with good probability whether the measurement results on the first qubit are always equal or uniformly distributed.

But how exactly are we supposed to assign quantum states (i.e. the $|a\rangle$'s) corresponding to the elements of $\mathcal{H}$? Do we need to assign separate binary strings to all the elements of the group generated by the elements of $G$, such that they can be represented by qubit systems?

This is a possible way, but really it doesn't matter how you do the encoding for the sake of the algorithm. The only thing that matters is that different group elements must be assigned orthogonal states. After this, you can decide to assign binary strings to each group element and then convert these to qubits, or just use appropriate high-dimensional qudits, or whatever else might be more convenient in the specific use-case.

And if we do assign such binary strings a priori, wouldn't it be much simpler to directly (classically) check whether the string assigned to $h$ matches with any of the strings corresponding to the elements of $\mathcal{H}$? I can't really see the speed advantage here. Could someone clarify this "quantum" proof?

Indeed, if you do know the classical representation of $h$ in the encoding of your choice, then you already essentially have the solution to the problem.

However, this might not be the case. You might only have access to the unitary $\mathcal U_h$. You might have $\lvert h\rangle$ as input (the quantum state, not the classical description of the corresponding group element), and use the state to implement $\mathcal U_h$, and thus using this protocol to figure out whether $h\in \mathcal H$, without even knowing what $h$ actually is.

Answer 2

This result concerns the black-box group model, which is a fairly standard model in computational group theory. It is intended to represent minimal assumptions on the groups we're working with. In the black box group model we assume that each group element has a (unique) string representation of a fixed length, and a black-box performs the group operations for us.

The literal answer to the question of how we assign binary strings to the group elements is therefore that we don't: this is assumed to have already been done. Note that if the length of the binary string representations of the group elements is $n$, then there could be exponentially many (in $n$) different group elements, which is why the simpler classical check is unsatisfactory. The verification procedure here, assuming we're given a quantum proof as described, requires time polynomial in $n$.

To motivate this model, let's consider the specific example of matrix groups. In particular, let us suppose that every group element we're working with is an $N\times N$ matrix with entries in $\mathbb{Z}_p$ (integers modulo $p$) for some large prime number $p$, such that the matrix is invertible modulo $p$. In other words, our group $G$ is the general linear group $\text{GL}(N,p)$.

Now, you can easily represent elements of $\text{GL}(N,p)$ as binary strings of length $n = N^2 \lceil \log(p)\rceil$ by simply encoding each element of $\mathbb{Z}_p$ using binary notation and then concatenating the encodings of the entries together. Knowing this assignment of strings to group elements by itself does not, however, solve the problem: if you had group elements (i.e., matrices) $h$ and $g_1,\ldots,g_k$, and wanted to be convinced that $h\not\in\langle g_1,\ldots,g_k\rangle$, you would still have a lot of work to do, and it would be a very difficult computational task in general.

However, because we can efficiently perform the group operations (multiplication and inversion) on these string encodings, we can easily adapt any method based on the black-box group model by replacing the group oracle with circuits that efficiently perform these group operations. Thus, for this example of $\text{GL}(N,p)$ , there exist quantum proofs that will convince an efficient (i.e., polynomial-time) verifier that $h\not\in\langle g_1,\ldots,g_k\rangle$ when this statement is true and not when it is false.

The appeal of the black-box group model is that this is reasoning extends to many other concrete ways of representing group elements and performing operations. There is, of course, nothing specific about $\text{GL}(N,p)$ or any other group to the result.

Concerning the idea of the method, gIS has already answered this part very well (so let me suggest that you accept that answer if you find it to be helpful).