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.

  • $\begingroup$ One reason this is a very good question is that both factoring and graph isomorphism are NP-intermediate. $\endgroup$ – Adam Zalcman Feb 10 at 1:57
  • $\begingroup$ *likely NP-intermediate, under the assumption that P$\ne$NP. $\endgroup$ – Mark S Mar 27 at 14:23

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.

  • $\begingroup$ Regarding the Hidden Subgroup Problem, I suppose the type of groups for which we think there may not be an efficient quantum HSP solver are the non-abelian groups? $\endgroup$ – Adam Zalcman Feb 10 at 1:59
  • 1
    $\begingroup$ With some exceptions I think that’s the consensus. HSP for the Heisenberg group is efficient, but I think it’s because the Heisenberg group is close to abelian... $\endgroup$ – Mark S Feb 10 at 2:09
  • 1
    $\begingroup$ @AdamZalcman You might enjoy this presentation by Christopher Moore on quantum algorithms for graph isomorphism, and their relation to the HSP for the symmetric group. I'll have to watch it again but he explains why HSP for $S_n$ may be hard; something about characters of the group being too close together. $\endgroup$ – Mark S Mar 27 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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