algorithms advanced · 17 min read · May 1, 2026

Quantum Walks: Discrete and Continuous Time

Quantum walks are the quantum analog of classical random walks — and they spread quadratically faster on simple graphs, a polynomial speedup that underlies Grover, Shor's discrete-log, and several recent quantum algorithms. This tutorial covers discrete-time quantum walks (Szegedy and coined walks), continuous-time quantum walks, the speedup origin in interference, and where quantum walks turn into algorithmic primitives in 2026.

Prerequisites: Tutorial 10: Grover and Amplitude Amplification, Tutorial 30: Quantum Singular Value Transformation

A classical random walk on a graph spreads diffusively: after $t$ steps, the walker is typically at distance $O(\sqrt{t})$ from the start. A quantum walk on the same graph spreads ballistically: after $t$ steps, the walker is typically at distance $O(t)$ from the start. Quantum walks spread quadratically faster than their classical counterparts. This is a polynomial speedup that underlies a remarkable range of quantum algorithms: Grover’s search (when reformulated as a walk on a complete graph), spatial search on lattices, element distinctness, triangle finding, and the modern qubitization framework.

Two flavors of quantum walk: discrete-time (steps happen at fixed times, Szegedy and coined-walk variants) and continuous-time (the walk is generated by a Hamiltonian acting on the graph). They are dual in a precise sense — every problem solvable by one has a counterpart solvable by the other — but the algorithmic structures differ.

This tutorial covers both walk types, the speedup origin (quantum interference replacing classical diffusion), the canonical application to spatial search, and how quantum walks reappear in 2026 in qubitization-based algorithms (tutorial 30) where the walk operator is a structural primitive.

Classical random walk: the comparison point

A simple random walk on a 1D lattice: at each step, flip a coin, move left if heads and right if tails. After $t$ steps, the walker’s position is approximately Gaussian with standard deviation $\sigma \approx \sqrt{t}$ . The walker has explored a region of size $O(\sqrt{t})$ .

To search for a marked vertex on an $N$ -vertex graph by random walk: expected hitting time is $\Omega(N)$ for general graphs (longer for sparse-but-large graphs). To find a marked element among $N$ via random sampling: expected $N/2$ steps.

Both bounds reflect the diffusive scaling: classical exploration is bottlenecked by the square root.

Discrete-time quantum walk: coined walks

The basic discrete-time quantum walk on a graph has two registers:

Position register: holds the current vertex.
Coin register: a small auxiliary register that determines the direction of the next step.

The walk is a unitary $U = S \cdot (C \otimes I)$ where:

$C$ is the coin operator, applied to the coin register. Common choices: Hadamard for 1D, Grover diffusion for higher-degree graphs.
$S$ is the shift operator, which moves the position based on the coin register’s state.

Iterating $U$ for $t$ steps gives a quantum-walked state. Measuring the position register at any point gives a position distribution that does not look like a Gaussian — it is two peaks moving outward at constant velocity, producing a much wider spread than the classical walk.

Concretely, on a 1D lattice with $N$ vertices: classical walk after $t$ steps has variance $\sim t$ ; quantum walk after $t$ steps has variance $\sim t^2$ . Squeezing the quantum walker’s position spread to a fixed range $D$ takes $t \sim \sqrt{D}$ for the quantum walker, vs $t \sim D$ for the classical walker. Quadratic speedup in spread.

Discrete-time quantum walk: Szegedy walks

The Szegedy walk (2004) is a different formulation that emphasizes the connection to classical Markov chains. Given a classical reversible Markov chain $P$ on a graph, Szegedy constructs a quantum walk $W(P)$ acting on a Hilbert space twice the size of the graph. The walk has the property that:

$W(P)$ has eigenvalues $\pm e^{\pm i \theta_k}$ where $\cos\theta_k$ are square roots of the eigenvalues of $P$ .
The square root in the eigenvalues is the structural source of the quadratic speedup.

This formulation gives a clean speedup statement: for any classical random-walk-based algorithm with hitting time $T$ , the Szegedy quantum walk gives an algorithm with effective time $O(\sqrt{T})$ .

The Szegedy framework underlies most modern quantum-walk algorithms because it directly connects to classical analysis: take a classical walk that does what you want, lift to a Szegedy walk, get a quadratic speedup. This is how Grover’s search is recovered as a special case (Szegedy walk on the complete graph) and how element distinctness, triangle finding, etc. inherit their speedups.

Continuous-time quantum walk

The continuous-time quantum walk on a graph $G$ is generated by the graph Laplacian $L_G$ :

|\psi(t)\rangle \;=\; e^{-i L_G t} |\psi(0)\rangle.

The walk is just Hamiltonian evolution under the Laplacian. No coin register is needed — the walk happens directly on the position register.

The continuous-time formulation has the simplest theoretical analysis. For a graph with $N$ vertices, the walk evolves under $L_G$ which is an $N \times N$ Hermitian matrix; the dynamics are linear and amenable to standard quantum-algorithm analysis (Trotter expansion, qubitization).

For 1D lattices, the continuous-time walk has the same quadratic-speedup property as discrete-time. For higher-dimensional structures (lattices, Cayley graphs, expanders), the continuous-time walk often has cleaner analysis but similar performance.

Spatial search: the canonical application

The spatial-search problem: given a graph with one or more marked vertices, find a marked vertex by querying the graph’s structure plus an oracle that identifies marked vertices.

For a 2D lattice with $N$ vertices and one marked vertex:

Classical random walk: expected $\Theta(N \log N)$ steps.
Grover’s search (no graph structure): $\Theta(\sqrt{N})$ steps but ignores the geometric structure.
Quantum walk on the lattice: $\Theta(\sqrt{N \log N})$ steps for 2D, $\Theta(\sqrt{N})$ for 3D and higher.

The quantum walk uses the graph structure (only nearest-neighbor moves) and still achieves near-optimal speedup. This is impossible with Grover’s search, which requires a flat oracle independent of structure.

Aaronson-Ambainis 2003 proved that spatial search on planar graphs cannot achieve full $\Theta(\sqrt{N})$ — the logarithmic factor in 2D is fundamental. Quantum walks are tight against the structural lower bound for planar geometry.

Quantum walks in qubitization

A modern reincarnation of quantum walks: tutorial 30’s qubitization framework. A block-encoded matrix $A$ defines a quantum-walk-like operator $W$ whose eigenvalues are related to the singular values of $A$ . Iterating $W$ — analogous to iterating a quantum walk — implements polynomial transformations of $A$ .

Specifically: for any block-encoding of $A$ , the qubitization walk $W$ has the property that $W^k$ for various $k$ implements Chebyshev polynomials of $A$ . This is a quantum walk where the “graph” is replaced by a block-encoded matrix. All the walk-theoretic intuition about quadratic speedups carries over: implementing a polynomial of degree $d$ in $A$ takes $O(d)$ uses of $W$ , which translates to $O(d)$ block-encoding queries.

This connection is structural, not just analogical. The same algebraic technology — Szegedy-walk eigenstructure, Chebyshev polynomial expansions — underlies both quantum walks and qubitization. Modern quantum algorithms are quantum walks at heart, even when not framed as such.

A small quantum-walk demonstration

Concrete code simulating a discrete-time quantum walk on a line:

import numpy as np
import pennylane as qml

n_position_qubits = 5
n_coin_qubits = 1
total_qubits = n_position_qubits + n_coin_qubits
N = 2 ** n_position_qubits  # number of positions

dev = qml.device("default.qubit", wires=total_qubits)


def shift_left(circuit_wires_pos):
    """Decrement the position register (subtract 1)."""
    n = len(circuit_wires_pos)
    qml.PauliX(wires=circuit_wires_pos[-1])  # Flip lowest bit and propagate.
    # Simplified: full implementation requires more careful arithmetic
    # circuitry. PennyLane has no built-in increment circuit, so this is a sketch.


def shift_right(circuit_wires_pos):
    """Increment the position register (add 1)."""
    n = len(circuit_wires_pos)
    qml.PauliX(wires=circuit_wires_pos[-1])


@qml.qnode(dev)
def quantum_walk(steps):
    """Discrete-time quantum walk with Hadamard coin on a 1D lattice."""
    # Initial state: walker at position N/2, coin in |0>
    init_pos = N // 2
    bin_init = bin(init_pos)[2:].zfill(n_position_qubits)
    for i, bit in enumerate(bin_init):
        if bit == '1':
            qml.PauliX(wires=i)
    # Walk for `steps` iterations.
    for _ in range(steps):
        # Coin: Hadamard on coin qubit (last wire).
        qml.Hadamard(wires=total_qubits - 1)
        # Conditional shift.
        # Simplified: actual implementation requires controlled increment/decrement
        # which involves arithmetic circuits.
    return qml.probs(wires=range(n_position_qubits))


# Sample run.
probs = quantum_walk(steps=10)
print(f"After 10 steps, position distribution shape: {len(probs)} entries")
print(f"Maximum probability: {max(probs):.4f}")
print(f"Mean position: {sum(i * p for i, p in enumerate(probs)):.2f}")

The shift operations are simplified above — a full implementation requires reversible arithmetic circuits. For a concrete tutorial use case, libraries like PennyLane’s qml.qchem or specialized walk-implementation packages handle this.

The qualitative behavior to expect: at each step, the probability distribution on positions has two peaks moving outward at constant velocity, with interference creating a characteristic “horns” shape. After many steps, the distribution is concentrated on the boundaries, not in the center as a classical walk would produce.

Common misconceptions

“Quantum walks give exponential speedups.” They give quadratic speedups (in the spread / hitting-time sense), not exponential. Exponential speedups in quantum computing come from problems with periodic structure (Shor) or oracular structure (Grover-amplification of arbitrary subroutines), not from walks per se.

“Quantum walks are useful only for graph problems.” They are mathematically about graphs, but the qubitization connection generalizes them to arbitrary block-encoded matrices. Quantum walks are now an algorithmic primitive used in many contexts that don’t look like graph problems.

“Discrete-time and continuous-time walks are equivalent.” They are dual but have different algorithmic structures and constants. For specific problems, one is usually more natural than the other.

“Quantum walks compete with Grover’s algorithm.” They complement it. Grover’s algorithm assumes a flat oracle; quantum walks exploit graph structure when available, achieving better-than-Grover for spatial-search-style problems.

“Quantum walks are a NISQ-era topic.” Walks formulate cleanly at the NISQ level, but the most-cited modern uses (qubitization, QSVT) are fault-tolerant in nature. Walks are a structural primitive that spans both eras.

Decision rule

Use quantum-walk thinking when:

Your problem has graph structure that the classical algorithm exploits via random walks.
You need spatial search on lattices or specific graphs.
You’re doing algorithm design with block encodings. The qubitization formalism is essentially quantum walks.
You need a quadratic speedup and the structural prerequisite (a connection to a classical Markov chain) is met.

Don’t use quantum-walk frameworks when:

The classical algorithm is not based on random walks. Quantum walks excel at lifting random-walk classical algorithms; they don’t help directly with non-walk-based algorithms.
The required speedup is super-quadratic. Walks give quadratic; for exponential speedups you need different approaches (Shor’s structure, Hamiltonian simulation, qubitization for specific functions).

For most modern quantum algorithm research in 2026, walks are not the explicit framing — qubitization and QSVT are. But the underlying mathematics is walk-theoretic, and reading walks-pre-2017-style papers is still useful for intuition.

Exercises

1. Spread comparison

A classical random walk on a 1D lattice runs for 100 steps. A quantum walk on the same lattice runs for 10 steps. Compare their spreads.

Show answer

Classical spread after 100 steps: $\sqrt{100} = 10$ . Quantum spread after 10 steps: $10$ (linear). The 10-step quantum walk reaches the same spread as the 100-step classical walk. This is the quadratic speedup made concrete: $\sqrt{T}$ for classical = $T$ for quantum, so quantum needs $\sqrt{T_\text{classical}} = T_\text{quantum}$ steps to match. In practical terms: a problem whose classical hitting time is $10^6$ steps has a quantum-walk hitting time of $10^3$ steps.

2. Why interference causes the speedup

Classical random walks have a Gaussian-distributed position because successive coin flips average out via the central limit theorem. Quantum walks have a non-Gaussian (two-peaked) distribution. What is the quantum-mechanical mechanism?

Show answer

In a classical walk, the probability of arriving at a position is the sum of probabilities of paths reaching that position. In a quantum walk, the amplitude of arriving at a position is the sum of amplitudes of paths. Amplitudes can interfere constructively or destructively. Constructive interference creates the moving peaks; destructive interference makes the center underweighted. The result is ballistic spread (peaks moving outward at constant velocity) instead of diffusive spread (Gaussian widening). This is the same interference mechanism that gives Grover’s search its $\sqrt{N}$ speedup — and indeed, Grover is a quantum walk on the complete graph with appropriate coin choice.

3. The Szegedy connection to Markov chains

The Szegedy walk lifts a classical Markov chain $P$ to a quantum walk with eigenvalue spectrum involving $\sqrt{\text{spectrum}(P)}$ . Why is this square root the source of the quadratic speedup?

Show answer

Classical Markov chain hitting times scale as $1/(1 - \lambda_1)$ , where $\lambda_1$ is the second-largest eigenvalue of $P$ (close to 1 for slow-mixing chains). Szegedy walks have spectral gap $1 - \sqrt{\lambda_1}$ , which is roughly $\sqrt{1 - \lambda_1} \cdot \sqrt{2}$ when $\lambda_1$ is close to 1. The square root in the eigenvalue translates to a $\sqrt{}$ in the hitting time. Concretely: classical hitting time $T \sim 1/(1-\lambda_1)$ becomes quantum hitting time $T \sim 1/\sqrt{1-\lambda_1} = \sqrt{T_\text{classical}}$ . This square-root structure is the deepest reason for the quadratic speedup of walk-based quantum algorithms.

4. When walks don’t help

A computational problem reduces to evaluating a sum $\sum_{i=1}^N f(i)$ where $f$ is an arbitrary function with no structural redundancy. Why don’t quantum walks give a speedup here?

Show answer

Walk speedups come from the graph structure or random-walk reduction of the underlying problem. A flat sum over $N$ unstructured terms has no graph or walk structure — it is essentially the unstructured search problem (Grover’s). For Grover’s, the speedup is $\sqrt{N}$ (or amplitude estimation for the sum gives $1/\epsilon$ ). Quantum walks are not better than Grover’s on unstructured problems. Walks are a structured-speedup tool: they leverage the fact that the classical algorithm has a walk-like reduction. Without that reduction, walks have no advantage. The relevant question for any speedup question is “what classical structure does my algorithm exploit?” — walks help when the answer is “random walk on a graph.”

Where this goes next

Tutorial 58 covers HHL — the quantum algorithm for solving sparse linear systems, which is itself a structurally walk-related algorithm and was one of the original “exponential speedup” claims that Tang’s dequantization (tutorial 41) partially deflated. Tutorial 59 covers LCU (linear combination of unitaries), the framework that powers HHL, qubitization, and modern Hamiltonian simulation.

Classical random walk: the comparison point

Discrete-time quantum walk: coined walks

Discrete-time quantum walk: Szegedy walks

Continuous-time quantum walk

Spatial search: the canonical application

Quantum walks in qubitization

A small quantum-walk demonstration

Common misconceptions

Decision rule

Exercises

1. Spread comparison

2. Why interference causes the speedup

3. The Szegedy connection to Markov chains

4. When walks don’t help

Where this goes next

Quantum, for people who already code.