Polynomial-time quantum algorithm for Graph Isomorphism
- Field
- Topic
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
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
Reports do not certify correctness or automatically change the problem's status. Progress policy.
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].
Babai’s algorithm gives a general classical upper bound of \(\exp((\log n)^{O(1)})\) time for Graph Isomorphism, and since a quantum computer can run the same classical procedure it also yields a quasipolynomial-time quantum upper bound. This does not settle the present question, which asks for a polynomial-time quantum algorithm [BAB16]. An error in the running-time analysis of the original preprint, pointed out by Helfgott, was repaired by Babai in 2017; the correction is documented on Babai’s announcement page [BABUP].
Anastos, Kwan, and Moore proved a strong smoothed-case result for Graph Isomorphism. For every \(n\)-vertex graph \(G_0\), after a random perturbation obtained by adding and removing only \(O(n)\) edges in expectation, the resulting graph admits a polynomial-time canonical-labelling algorithm with high probability. They also showed that, for every edge probability \(p=p(n)\), a random graph \(G(n,p)\) admits polynomial-time canonical labelling with high probability. These results substantially enlarge the classes of instances known to be efficiently solvable, but do not give a polynomial-time algorithm for worst-case Graph Isomorphism and hence do not resolve the present question [AKM25].
- Reported progress: PR #46.
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).DOIarXiv
- [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).DOIarXiv
- [AKM25]
- Michael Anastos, Matthew Kwan, and Benjamin Moore, “Smoothed Analysis for Graph Isomorphism,” in Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025), 2098–2106 (2025).DOIarXiv
- [BAB16]
- László Babai, “Graph Isomorphism in Quasipolynomial Time,” in Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), 684–697 (2016).DOIarXiv
- [BABUP]
- László Babai, “Graph Isomorphism Update,” January 2017. update.html; upcc-fix.pdf.linklink