Quantum Walk Algorithms

Overview

A quantum walk is the quantum counterpart of a random walk. A classical random walker moves to a random neighbor at each step and spreads out slowly, with a typical distance that grows like the square root of the number of steps. A quantum walker moves in superposition of directions and interferes with itself, so its distance can grow in proportion to the number of steps, which is quadratically faster.

Quantum walks are a versatile framework for algorithm design. They give an exponential speedup on one carefully built graph problem, optimal quadratic speedups for searching and for element distinctness, and a universal model of quantum computation. Many algorithms that look unrelated, including Grover search, can be viewed as quantum walks.

The problem it solves

Searching or traversing a large graph or network structure to find a target node or path.

History and background

Quantum walks were introduced in the early 1990s, with Aharonov, Davidovich, and Zagury's 1993 paper on discrete quantum random walks. Edward Farhi and Sam Gutmann defined the continuous-time quantum walk in 1998. In 2003, Andrew Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel Spielman showed a problem, traversing a pair of glued binary trees, where a quantum walk is exponentially faster than any classical algorithm.

Also in 2003, Neil Shenvi, Julia Kempe, and Birgitta Whaley described a quantum walk search on the hypercube, and Childs and Goldstone extended this to spatial search on lattices in 2004. Andris Ambainis found a quantum walk algorithm for element distinctness with N to the two-thirds queries in 2004, and Mario Szegedy gave a framework that converts classical Markov chains to quantum walks. In 2009 Childs showed that continuous-time quantum walks are universal for quantum computation.

How it works

Exploits quantum superposition and interference to spread probability across a graph differently than a classical random walk, in some cases reaching target nodes quadratically faster.

In a classical walk, probabilities spread out through diffusion: after t steps the walker is typically about the square root of t away from the start. In a quantum walk, amplitudes spread through interference. Paths that lead outward add up constructively, so the probability distribution has peaks that move away from the origin at a constant speed, a ballistic spread, rather than the bell curve of diffusion.

A discrete-time quantum walk needs an extra coin register that holds the direction of motion. Each step applies a coin operation, such as a Hadamard, that puts the walker in a superposition of directions, followed by a shift that moves it. A continuous-time walk skips the coin and evolves the state under a Hamiltonian built from the graph's adjacency matrix.

For search, a marked vertex is given a different energy or a different coin. The walk then evolves so that probability concentrates on the marked vertex after about the square root of N steps on a well-connected graph, matching Grover's algorithm. On a low-dimensional graph such as a two-dimensional grid, the walk reaches the quadratic speedup with extra logarithmic factors, while one-dimensional graphs show little speedup.

Step by step

1. Choose a graph that represents the search space and a quantum walk on it, either discrete time with a coin register or continuous time with the adjacency matrix as a Hamiltonian.
2. Prepare the walker in a uniform superposition over all vertices, or in a state concentrated on a starting vertex, depending on the problem.
3. Define the marked vertices by changing the coin operator on them or by adding an energy term to the Hamiltonian at those vertices.
4. Evolve the walk by applying the coin and shift operators repeatedly, or by applying the continuous-time evolution for a computed time.
5. Stop after the optimal number of steps, which is on the order of the square root of the hitting time, and measure the position register.
6. Check the output classically. If it is not a marked vertex, repeat the procedure.

A worked example

On the line, a classical random walker starting at the origin and taking 100 steps ends up typically within about 10 positions of the origin. A discrete quantum walk with a Hadamard coin and 100 steps has probability spread over a range of roughly 70 positions on each side, with peaks near the edges, which shows ballistic spreading.

For search on a complete graph with N vertices and one marked vertex, the quantum walk reaches the marked vertex after about the square root of N steps with high probability, the same as Grover's algorithm. A classical random walk would need about N steps.

Complexity and resources

What hardware it needs

• Qubits arranged to implement the graph structure, and enough coherence for hundreds of steps.
• Controlled coin and shift operations, or Hamiltonian simulation of the adjacency matrix.
• For search problems, an oracle for marked vertices, as in Grover's algorithm.

Applications

• Spatial search on networks and grids, and element distinctness in the query model.
• Triangle finding and other graph problems with polynomial speedups.
• A framework for converting classical Markov chain algorithms into quantum algorithms with quadratic speedups in mixing time.
• Modeling energy transport in photosynthesis and other physical systems, as an analogy.

Limitations and caveats

• The exponential speedup on glued trees applies to an artificial problem defined by an oracle.
• Search speedups are quadratic and match Grover's algorithm in the unstructured case.
• Performance depends heavily on graph geometry, and low-dimensional graphs show little advantage.
• Noise destroys the interference that powers the speed advantage, so the walk needs a coherent device.

Common misconceptions

• Quantum walks are not simply random walks on a quantum computer. The interference changes the spreading behavior fundamentally.
• They do not speed up every graph problem. Advantages are known for specific problems.

How it compares

• Grover's algorithm solves unstructured search with a quadratic speedup, and quantum walks reproduce it while also exploiting graph structure.
• Szegedy's framework turns any reversible Markov chain into a quantum walk with a quadratic speedup in the spectral gap.
• Amplitude amplification gives a general quadratic speedup for randomized algorithms, while quantum walks are tailored to graph problems.

Real-world impact

Used in specialized search applications and as a building block for some optimization and machine learning algorithms; less broadly known than Grover's but mathematically related.

Why it matters

Quantum walks provide a second way of designing quantum algorithms besides the Fourier transform and amplitude amplification. They are the source of several of the best known polynomial speedups, including element distinctness and triangle finding.

The universality result also means that any quantum computation can be recast as a walk on a graph, which gives physicists a different language for thinking about quantum computing and motivates analog quantum simulators.

Frequently asked questions

Keep learning

• Related algorithm: Grover's Algorithm
• Related algorithm: Quantum PageRank
• Related algorithm: Quantum Walk Approaches to Graph Isomorphism
• Related algorithm: Quantum Amplitude Amplification

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