Quantum Walks: How Quantum Computers Explore Graphs

Classical Random Walk: A Baseline

A classical random walk on a line starts at position 0. At each step a coin is flipped: heads moves right (+1), tails moves left (-1). After N steps the probability distribution over positions is a binomial distribution approximately equal to a Gaussian centered at 0 with standard deviation sqrt(N).

This spreading rate, proportional to sqrt(N), limits how fast classical algorithms based on random walks can explore a graph. Randomized search on a graph of n nodes by classical random walk takes O(n^2) steps to visit all nodes in the worst case.

Quantum Walk: Quadratic Speedup

A quantum walk is the quantum analog of this process. Instead of a classical coin (heads or tails), it uses a quantum coin: a qubit that can be in superposition. Instead of a definite position, the walker occupies a superposition of all positions.

After N steps the position distribution of a quantum walk on a line has standard deviation proportional to N rather than sqrt(N). This quadratic speedup in spreading directly translates to speedups in graph algorithms: quantum walks hit the far end of a path of length n in O(n) steps versus O(n^2) classically.

Discrete-Time Quantum Walk on a Line

The discrete-time quantum walk uses two registers:

• A coin register (1 qubit): |0⟩ represents “left”, |1⟩ represents “right”.
• A position register (n_pos qubits): encodes the walker’s location in binary.

Each step consists of two operations:

1. Coin operator: Apply a Hadamard gate to the coin qubit. This puts the coin in superposition of left and right.
2. Shift operator: Conditioned on the coin qubit, increment (shift right) or decrement (shift left) the position register.

The shift operators are:

• Shift-right: Increment the position register if the coin qubit is |1⟩ (controlled increment).
• Shift-left: Decrement the position register if the coin qubit is |0⟩ (controlled decrement).

Qiskit Implementation

import numpy as np
import matplotlib.pyplot as plt
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator

# Parameters
n_steps = 8        # Number of walk steps
n_pos_qubits = 5   # Number of position qubits (supports 2^n_pos = 32 positions)
center = 2 ** (n_pos_qubits - 1)  # Start in the middle of the position space


def controlled_increment(qc: QuantumCircuit, control: int, target_qubits: list[int]):
    """
    Controlled increment: add 1 to target register when control qubit is |1>.
    Implemented via cascaded Toffoli gates.
    """
    n = len(target_qubits)
    # Ripple-carry increment: flip t[0], then flip t[1] if t[0] was 1, etc.
    for i in range(n - 1, -1, -1):
        if i == 0:
            qc.cx(control, target_qubits[0])
        else:
            qc.mcx([control] + target_qubits[:i], target_qubits[i])


def controlled_decrement(qc: QuantumCircuit, control: int, target_qubits: list[int]):
    """
    Controlled decrement: subtract 1 from target register when control qubit is |0>.
    Uses 2's complement: flip targets, increment, flip targets back.
    Active when control=|0>: X on control, do conditional flips and increment, X back.
    """
    # X on control so the gate fires when original control was |0>
    qc.x(control)
    # Flip all target bits conditionally (prepares for 2's complement increment)
    for t in target_qubits:
        qc.cx(control, t)
    # Controlled increment on the flipped register
    controlled_increment(qc, control, target_qubits)
    # Flip target bits back
    for t in target_qubits:
        qc.cx(control, t)
    # Restore control
    qc.x(control)


def quantum_walk_circuit(n_steps: int, n_pos_qubits: int, start: int) -> QuantumCircuit:
    """
    Build a discrete quantum walk circuit on a line.
    """
    coin = QuantumRegister(1, name="coin")
    position = QuantumRegister(n_pos_qubits, name="pos")
    c_coin = ClassicalRegister(1, name="cc")
    c_pos = ClassicalRegister(n_pos_qubits, name="cp")

    qc = QuantumCircuit(coin, position, c_coin, c_pos)

    # Initialize position to 'start' (encode start in binary)
    for bit_idx in range(n_pos_qubits):
        if (start >> bit_idx) & 1:
            qc.x(position[bit_idx])

    # Coin starts in |0>; each step begins with a Hadamard coin flip

    # Walk steps
    for step in range(n_steps):
        qc.barrier()
        # Coin flip: H on |0> creates |+> = (|0>+|1>)/sqrt(2)
        qc.h(coin[0])
        # Shift right (conditioned on coin = |1>)
        controlled_increment(qc, coin[0], list(position))
        # Shift left (conditioned on coin = |0>)
        controlled_decrement(qc, coin[0], list(position))

    qc.measure(coin, c_coin)
    qc.measure(position, c_pos)
    return qc


def run_and_extract_distribution(qc: QuantumCircuit, shots: int = 8192) -> dict:
    """Run the circuit and return position probability distribution."""
    sim = AerSimulator()
    job = sim.run(qc, shots=shots)
    counts = job.result().get_counts()

    # Parse counts: format is "pos_bits coin_bit" (space-separated)
    pos_counts = {}
    for bitstring, count in counts.items():
        parts = bitstring.split()
        # Qiskit output order: c_pos is printed first, c_coin second
        if len(parts) == 2:
            pos_bits = parts[0]  # position bits (MSB first in Qiskit output)
            pos = int(pos_bits, 2)  # direct conversion; Qiskit already outputs MSB first
        else:
            pos = int(parts[0], 2)
        pos_counts[pos] = pos_counts.get(pos, 0) + count

    # Normalize
    total = sum(pos_counts.values())
    return {k: v / total for k, v in pos_counts.items()}


def classical_walk_distribution(n_steps: int, start: int) -> dict:
    """Simulate a classical random walk by sampling."""
    n_samples = 8192
    positions = np.full(n_samples, start)
    for _ in range(n_steps):
        moves = np.random.choice([-1, 1], size=n_samples)
        positions += moves
    unique, counts = np.unique(positions, return_counts=True)
    return dict(zip(unique.tolist(), (counts / n_samples).tolist()))


def compare_walks(n_steps: int = 8):
    n_pos_qubits = 5
    start = 2 ** (n_pos_qubits - 1)  # position 16

    print(f"Running quantum walk for {n_steps} steps...")
    qc = quantum_walk_circuit(n_steps, n_pos_qubits, start)
    print(f"Circuit depth: {qc.depth()}, gates: {sum(qc.count_ops().values())}")
    quantum_dist = run_and_extract_distribution(qc, shots=8192)

    print("Computing classical walk distribution...")
    classical_dist = classical_walk_distribution(n_steps, start)

    # Compute standard deviations
    q_positions = list(quantum_dist.keys())
    q_probs = list(quantum_dist.values())
    q_mean = sum(p * x for x, p in zip(q_positions, q_probs))
    q_std = np.sqrt(sum(p * (x - q_mean) ** 2 for x, p in zip(q_positions, q_probs)))

    c_positions = list(classical_dist.keys())
    c_probs = list(classical_dist.values())
    c_mean = sum(p * x for x, p in zip(c_positions, c_probs))
    c_std = np.sqrt(sum(p * (x - c_mean) ** 2 for x, p in zip(c_positions, c_probs)))

    print(f"\nAfter {n_steps} steps starting at position {start}:")
    print(f"  Quantum walk std dev:  {q_std:.2f}")
    print(f"  Classical walk std dev: {c_std:.2f} (expected ~{np.sqrt(n_steps):.2f})")
    print(f"  Speedup ratio: {q_std / c_std:.2f}x")
    # Example output (8 steps):
    #   Quantum walk std dev:  ~3.9  (wider than classical -- quantum speedup)
    #   Classical walk std dev: ~2.8  (expected ~2.83)
    #   Speedup ratio: ~1.4x

    # Plot
    all_pos = sorted(set(q_positions + c_positions))
    fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 5))

    ax1.bar([p - start for p in q_positions], q_probs, color="royalblue", alpha=0.8)
    ax1.set_title(f"Quantum Walk ({n_steps} steps)")
    ax1.set_xlabel("Displacement from start")
    ax1.set_ylabel("Probability")
    ax1.axvline(0, color="red", linestyle="--", alpha=0.5)

    ax2.bar([p - start for p in c_positions], c_probs, color="tomato", alpha=0.8)
    ax2.set_title(f"Classical Random Walk ({n_steps} steps)")
    ax2.set_xlabel("Displacement from start")
    ax2.set_ylabel("Probability")
    ax2.axvline(0, color="red", linestyle="--", alpha=0.5)

    plt.tight_layout()
    plt.savefig("quantum_vs_classical_walk.png", dpi=120)
    plt.show()


if __name__ == "__main__":
    compare_walks(n_steps=8)

Understanding the Distribution Shape

The classical walk produces a Gaussian-shaped distribution centered at the start, spreading as sqrt(N). The quantum walk produces a markedly different distribution with two peaks, one on each side of the starting position, and very little probability near the center. This is a direct consequence of interference.

At the center, the left-moving and right-moving amplitudes cancel each other out via destructive interference. At the edges, constructive interference concentrates the probability. The result is a spread of order N after N steps, not sqrt(N).

Cycle Graph Walk

On a cycle graph (circular line with periodic boundary conditions) the walk wraps around. The circuit is the same except the position arithmetic is done modulo the cycle length. For a cycle of length 2^n_pos, the Qiskit position register naturally wraps due to integer overflow, so the same increment/decrement circuit works without modification.

The cycle walk eventually distributes uniformly over all positions after enough steps, but the mixing time is O(n) steps for a quantum walk on a cycle of length n, versus O(n^2) for a classical random walk.

Connection to Grover’s Algorithm

The connection between quantum walks and Grover’s algorithm is deeper than it first appears. Grover’s algorithm can be understood as a quantum walk on the complete graph, where the marked state is a “trap” that has modified phase.

More formally, quantum walk search on a graph works as follows:

1. Run the unmodified walk for some number of steps to reach a near-uniform distribution.
2. Apply a phase flip to the marked vertex (equivalent to the Grover oracle).
3. Run a reflected walk that concentrates amplitude on the marked vertex.

For graphs with good spectral expansion (expander graphs), this quantum walk search finds a marked vertex in O(sqrt(n)) steps, exactly matching Grover’s quadratic speedup. For general graphs the speedup depends on the spectral gap.

This formulation, developed by Szegedy and further analyzed by Childs and others, shows that amplitude amplification (the engine of Grover’s algorithm) is equivalent to a quantum walk on a bipartite double cover of the original graph. The two perspectives are mathematically equivalent but physically intuitive in different ways: Grover as reflection-based search, and quantum walk search as diffusion-based search.

Practical Applications

Quantum walk algorithms have concrete applications:

• Element distinctness (Ambainis): Given N elements, find any two that are equal. Quantum walk achieves O(N^(2/3)) queries versus classical O(N).
• Triangle finding: Detect if a graph has a triangle. Quantum walk improves over classical algorithms.
• Spatial search: Find a marked vertex on a 2D grid in O(sqrt(N) log N) steps versus classical O(N).
• Continuous-time quantum walks: Used in quantum chemistry for simulating exciton transport in photosynthesis, where quantum coherence may contribute to energy transfer efficiency.

Quantum walks are one of the most general frameworks for designing quantum algorithms, alongside amplitude amplification and quantum Fourier sampling.