OP-3019OpenQuantum information

Graph isomorphism in BQP

Does graph isomorphism on $n$ -vertex graphs admit a uniform polynomial-time bounded-error quantum algorithm?

Source-reported statusAs of 2026-09-04Source & evidence ↓

Read original source ↗ 0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

Does graph isomorphism on $n$ -vertex graphs admit a uniform polynomial-time bounded-error quantum algorithm?

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

Graph isomorphism is in NP, with neither a polynomial-time classical algorithm nor NP-completeness known. Babai's quasipolynomial-time classical algorithm is the comparison baseline, not a proof that a polynomial-time quantum algorithm is unnecessary or impossible.

The hidden-subgroup route uses permutation groups. Hallgren–Moore–Rötteler–Russell–Sen show that extracting useful information from the relevant coset states requires joint measurements on $\Omega(n\log n)$ states, matching an information-theoretic upper bound. This excludes single- and few-register approaches in that model. It does not prove that every sufficiently joint measurement has superpolynomial implementation complexity, or that all quantum approaches fail.

Archival correction (September 2026): Li–Chen withdrew their 2019 claimed polynomial-time quantum algorithm after substantial errors were found. The withdrawal supplies no positive evidence for GI in BQP and does not change the open status. Related: A15.

Progress & source assessment

Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.

References

[1]Hallgren, Moore, Rötteler, Russell & Sen, 'Limitations of quantum coset states for graph isomorphism', J. ACM 57 (2010) link
[2]Babai, 'Graph isomorphism in quasipolynomial time', STOC 2016 link
[3]Li & Chen, 'The quantum algorithm for graph isomorphism problem' (withdrawn; September 2026 notice) link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.