Quantum Walk Approaches to Graph Isomorphism

Overview

Two graphs are isomorphic if one can be turned into the other by relabeling its vertices. Deciding whether two graphs are isomorphic is a famous problem that is neither known to be solvable in polynomial time nor known to be NP-complete. Quantum walk approaches try to use the way a quantum particle spreads across a graph as a fingerprint: isomorphic graphs give identical fingerprints, and different graphs, hopefully, give different ones.

These methods are heuristic. They have shown that quantum walks can distinguish some pairs of graphs that simpler classical invariants cannot, but no quantum algorithm is known to solve graph isomorphism in polynomial time, and the hardest known cases, strongly regular graphs, resist single-particle walks.

The problem it solves

Determining whether two graphs (networks of nodes and edges) are structurally identical, even if drawn differently — a problem with no known efficient classical algorithm for the general case.

History and background

Graph isomorphism has resisted a polynomial-time algorithm for decades. In 2015, Laszlo Babai announced a quasipolynomial-time classical algorithm, running in time n to the power of a polylogarithmic function of n, and corrected a flaw in 2017. In practice, programs such as nauty and Traces solve nearly all instances quickly. For quantum computing, the problem is interesting because it reduces to a hidden subgroup problem over the symmetric group, which is the generalization of the problem Shor's algorithm solves over cyclic groups.

The standard Fourier sampling approach to that hidden subgroup problem fails: Hallgren, Moore, Rötteler, Russell, and Sen showed in 2006, and Moore, Russell, and Schulman in 2008, that coset states on the symmetric group cannot reveal the answer efficiently. Quantum walks were proposed as an alternative. Shiau, Joynt, and Coppersmith studied physically motivated dynamical algorithms in 2005, Douglas and Wang introduced a walk-inspired classical algorithm in 2008, and Gamble and coauthors proposed two-particle walks in 2010. Berry and Wang and later Rudinger and coauthors studied how far multi-particle walks go, finding that they distinguish many but not all difficult pairs.

How it works

Compares the statistical signatures produced by quantum walks evolving on each graph; matching signatures suggest the graphs may be isomorphic, though this is heuristic rather than a guaranteed proof.

A single quantum particle moving on a graph has dynamics determined by the graph's adjacency matrix. The probability of returning to a vertex after a given time depends on the numbers of closed walks of each length, which are related to the eigenvalues of the matrix. If two graphs have different spectra, the walks show different return probabilities, and the graphs are different.

The hard cases are graphs that are not isomorphic but have identical spectra, such as many strongly regular graphs. A single-particle walk cannot tell them apart. But two particles walking together, with the exchange symmetry of bosons or fermions, explore pairs of vertices and see more structure than a single particle can. With three or more particles the walk captures even more structure.

In the language of classical graph theory, the distinguishing power of a k-particle walk is related to the Weisfeiler-Leman refinement procedure of corresponding dimension, which iteratively compares neighborhoods of k-tuples of vertices. This provides a way to say what these methods can and cannot achieve: they are at best as strong as the matching Weisfeiler-Leman test, and some difficult graphs are known to fool it.

Step by step

1. Represent each graph by its adjacency matrix and define a quantum walk, continuous or discrete, on a single particle or on several non-interacting particles.
2. Prepare the walker in an initial state, such as uniform over vertices or pairs of vertices.
3. Evolve the walk for a chosen time, computing the amplitude or probability distribution, which on a quantum computer means simulating the evolution.
4. Extract a signature, for example the sorted list of return probabilities, or the spectrum of the walk's unitary, for each graph.
5. Compare the signatures of the two graphs. If they differ, the graphs are not isomorphic.
6. If they match, increase the number of particles or use a finer signature, since a match does not prove isomorphism.

A worked example

Take two graphs on 16 vertices that are both strongly regular with the same parameters, a classic hard pair. They have the same spectrum, so a single-particle walk gives the same return probabilities. A two-particle fermionic walk, which forbids two particles from occupying the same vertex, produces different dynamics for the two graphs and can distinguish many such pairs.

For some strongly regular pairs, even the two-particle walk gives the same signature, and three-particle walks are needed. The cost of simulating a k-particle walk classically grows like n to the power k, so the quantum advantage, if there is one, would come from simulating many particles efficiently, which has not been shown to separate isomorphic from non-isomorphic graphs in all cases.

Complexity and resources

What hardware it needs

• A quantum computer able to simulate multi-particle walks on graphs of interest, with enough qubits to encode k-tuples of vertices.
• Photonic quantum walk devices and boson-sampling-like hardware can implement some multi-particle walks directly.
• Classical computers handle small cases and are a strong baseline.

Applications

• Research on the complexity of graph isomorphism and on the power of quantum walks.
• Chemical and pattern-matching problems that compare molecular or network structures, if a speedup is found.
• Testing multi-particle quantum walk hardware against hard graph pairs.

Limitations and caveats

• No quantum speedup has been shown, and classical algorithms are very good in practice.
• The methods are heuristic: a failure to distinguish two graphs does not prove they are isomorphic.
• Strongly regular graphs and related families are hard for single-particle walks.
• Babai's quasipolynomial result narrows the room for a large quantum advantage.

Common misconceptions

• Quantum walks do not solve graph isomorphism in polynomial time, as far as anyone knows.
• Graph isomorphism is not known to be NP-complete, so a quantum speedup would not imply speedups for NP-complete problems.
• The classical algorithm of Douglas and Wang is inspired by quantum walks but runs on a classical computer.

How it compares

• Classical refinement algorithms such as Weisfeiler-Leman and the nauty family are practical and strong.
• The hidden subgroup approach over the symmetric group, which generalizes Shor's algorithm, is known to fail in its standard form.
• Quantum walk search gives a quadratic speedup for finding marked vertices, a different problem.

Real-world impact

An active area of quantum algorithms research; since the classical complexity of graph isomorphism itself is unresolved, any quantum speedup claims here remain especially carefully scrutinized.

Why it matters

Graph isomorphism is one of the few natural problems that sits between P and NP-complete, so it is a prime candidate for a quantum advantage that does not rely on NP-completeness. Understanding why quantum walks fall short on it helps clarify what makes problems amenable to quantum speedup.

The research also produced useful connections between quantum walks, boson sampling, and the Weisfeiler-Leman hierarchy, which are interesting in their own right.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Walk Algorithms
• Related algorithm: Quantum PageRank
• Related algorithm: Boson Sampling
• Related algorithm: Quantum Fourier Transform (QFT)

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database