What is known about quantum algorithms for graph isomorphism?

Question

Shor's algorithm (for factoring integers) and Grover's algorithm (for searches) are the two most well-known quantum algorithms. I was wondering if there was a similar result in QC that dealt with the Graph Isomorphism problem?

I can't seem to find a consensus online. I've found two references:

• This paper published in the Physical Review gives an algorithm for graph isomorphism, but it seems as if the algorithm doesn't give any complexity bound. It seems to explain that doing so is hard in adiabatic QC (I'm not too familiar with this so I don't know if I'm understanding this right; would also appreciate if someone could clear this up for me).

• In this paper, the authors claim they have found a poly-time quantum algorithm for the problem, though there is no record of review and this paper remains unpublished. I wasn't sure if people had actually reviewed this and determined whether it was correct or not.

Answer 1

Suppose we have two graphs, given by two different adjacency matrices $G_0$ and $G_1$. We wish to know whether the graphs are isomorphic. It's been a folklore result for a long time that if we can find a way permute the adjacency matrices by elements of $\pi\in S_n$ (the symmetric group on $n$ elements) so as to prepare the state:

$$\sum_{b\in\{0,1\},i\in S_n}\vert b\rangle\vert \pi_i(G_b)\rangle$$

then a simple $\mathsf{SWAP}$ test on the first register will tell whether the graphs are isomorphic. However, all the known ways to do this invariably leave garbage qubits around, without a clear way to clean up the garbage.

This naturally leads to a solution to the Graph Isomorphism Problem given a solution to the Hidden Subgroup Problem for the symmetric group. After many years I think the consensus is that there may not be an efficient quantum solution to the Hidden Subgroup Problem for such groups.

Interestingly there are still other questions one can ask about the Graph Isomorphism problem related not so much to its solution ("are these two graphs isomorphic?"), but to its verifiability ("can you show me whether these two graphs are isomorphic?”) For example, Graph Isomorphism is a standard problem admitting a statistical zero-knowledge proof; a famous result of Goldwasser and Sipser shows that the Graph Isomorphism problem is in the so-called $\mathsf{coAM}$ complexity class. We can ask similar questions in the quantum setting.

For example Watrous asked whether a quantum certificate (a $\mathsf{QMA}$ certificate) exists to prove that two graphs are not isomorphic. That is, he asked whether Graph Non-isomorphism is in $\mathsf{QMA}$ - can Merlin provide Arthur a bunch of qubits as a witness to the non-isomorphism of two graphs? We can ask about bounding Graph Non-isomorphism in other, potentially lower complexity classes like $\mathsf{QCMA}$ - Merlin provides a classical certificate to enable a quantum Arthur to verify that two graphs are not isomorphic.

It is noteworthy, all of this conversation about quantum approaches to graph isomorphism may be mooted by Babai's breakthrough of a classical quasipolynomial solution from a couple of years ago.