Polynomial-time quantum algorithm for Graph Isomorphism

Problem

Does the Graph Isomorphism problem admit a polynomial-time quantum algorithm?

Let \(G=(V_G,E_G)\) and \(H=(V_H,E_H)\) be finite simple graphs with \(|V_G|=|V_H|=n\). The graphs are isomorphic if there exists a bijection \(\pi:V_G\to V_H\) satisfying

\begin{equation} \{u,v\}\in E_G \Longleftrightarrow \{\pi(u),\pi(v)\}\in E_H \qquad \forall u,v\in V_G . \tag{1} \end{equation}

The open question is whether there is a bounded-error quantum algorithm running in time polynomial in \(n\) that, given \(G\) and \(H\), decides whether a bijection satisfying (1) exists.

Source

Implicit in Hallgren, Russell, and Ta-Shma (2003), who show that an efficient solution of the relevant non-Abelian hidden subgroup problem would yield an efficient quantum algorithm for Graph Isomorphism [HRT03]. The wording of the question is a contributor formulation of the broader open problem, not a verbatim question attributed to those authors.

Progress

An efficient solution of the non-Abelian hidden subgroup problem over the symmetric-group wreath product would yield an efficient quantum algorithm for Graph Isomorphism, while the direct extension of Abelian Fourier sampling does not suffice [HRT03].
Strong Fourier sampling on a single coset state reveals insufficient information for the hidden subgroup instances relevant to Graph Isomorphism; a coset-state approach must therefore use genuinely multiregister entangled measurements [MRS08].
A broad class of Kuperberg-style quantum sieve algorithms for the symmetric-group formulation cannot run in polynomial time: algorithms in that sieve family require at least \(\exp(\Omega(\sqrt{n}))\) time for the Graph Isomorphism instances [MRS10].

Comment

A successful coset-state approach must use genuinely multiregister entangled measurements, and polynomial-time quantum sieve algorithms are ruled out for the relevant instances. The open problem is not simply to implement the non-Abelian Fourier transform efficiently, but to find a substantially different way to extract and process the hidden symmetry, or a quantum approach to Graph Isomorphism outside this hidden-subgroup framework.

References

[HRT03]: Sean Hallgren, Alexander Russell, and Amnon Ta-Shma, “The Hidden Subgroup Problem and Quantum Computation Using Group Representations,” SIAM Journal on Computing 32, 916–934 (2003).DOI
[MRS08]: Cristopher Moore, Alexander Russell, and Leonard J. Schulman, “The Symmetric Group Defies Strong Fourier Sampling,” SIAM Journal on Computing 37, 1842–1864 (2008).DOI arXiv
[MRS10]: Cristopher Moore, Alexander Russell, and Piotr Šniady, “On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism,” SIAM Journal on Computing 39, 2377–2396 (2010).DOI arXiv

Polynomial-time quantum algorithm for Graph Isomorphism

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems