Understanding how to solve group isomorphism given the state $\sum_{\pi \in S_n} |\pi(G) \rangle$

Question

Let $G=([n],E)$ be an undirected graph, which is represented by a $n \choose 2$ bit string, by indicating for each $i < j$ if $(i,j) \in E$. And let $| G \rangle$ be the $n \choose 2$ qubit state that corresponds to the graph $G$.

Let $S_n$ be the set of all permutations on $n$ elements, and $\pi(G)$ is the graph obtained by renaming all $v \in E$ to $\pi(v)$, and where $(i,j)$ is an edge in $G$ if and only if $(\pi(i),\pi(j))$ is an edge in $\pi(G)$.

Assuming we have the state $$c\sum_{\pi \in S_n} |\pi(G) \rangle$$ where $c$ is a normalization constant, how can it help so solve the graph isomorphism problem (given 2 graphs $G,H$ - find out if they are isomorphic).

My initial thought was to measure, since we get an isomorphic graph $\pi(G)$, but the probability to get $H$ if it's isomorphic is very low, and if it's not isomorphic then we need to check every output, and it doesn't help much.

From other quantum algorithms I've seen, the QFT seems like a possible approach but I'm not sure how to use it here.

Help would be appreciated.

Answer 1

There are several pretty standard approaches to "solving" graph isomorphism given access to uniform superpositions over all the permutations of particular graphs (untensored with garbage). For brevity I slightly abuse notation and let $|\pi(G)\rangle$ and $|\pi(H)\rangle$ correspond to the uniform superpositions thereof.

1. One approach, if you are handed a register $|\psi\rangle$ for $|\pi(G)\rangle$ and a separate register $|\phi\rangle$ for $|\pi(H)\rangle$, would be to do a SWAP test by having a control register initialized as $|+\rangle$ act to control a swap of $|\psi\rangle$ with $|\phi\rangle$; measuring the control in the Hadamard basis lets you compute the inner product.

2. If you are given circuits $U$ and $V$ to prepare the uniform superpositions from, say, the all-zero's ket $|00\cdots 0\rangle$ for $|\pi(G)\rangle$ and $|\pi(H)\rangle$ respectively, again untensored with garbage, you can perform a Hadamard test by having a control register $|+\rangle$ act on the all-zero's ket to execute $U$ into $|\pi(G)\rangle$ if the control is $|0\rangle$, and to execute $V$ into $|\pi(H)\rangle$ if the control is $|1\rangle$; again measuring the control in the Hadamard basis gives you the inner product.

3. A third approach, similar to the second, can be done when you have a circuit $U$ to prepare $|\pi(G)\rangle$ from $|00\cdots 0\rangle$, and another backwards circuit $V^\dagger$ that maps $|\pi(H)\rangle$ back to $|00\cdots 0\rangle$. Simply execute $V^\dagger U|00\cdots 0\rangle$ to confirm that $V^\dagger U$ reverts back to the all-zero's ket.

Of note of course is that we don't know of any way to build such circuits $U$ or $V$ or $V^\dagger$ without adding leftover garbage that can't be uncomputed.