Walk Algorithms

Quantum Walk

Quantum analog of random walks for search and simulation

Quantum walks are the quantum mechanical analogues of classical random walks, where a walker evolves according to unitary dynamics rather than stochastic transitions. They exhibit fundamentally different behavior from their classical counterparts, including ballistic propagation rather than diffusive spreading, and they can provide polynomial and even exponential speedups for certain search and sampling problems. Quantum walks underpin some of the most powerful quantum algorithms for element distinctness, spatial search, and simulation of quantum physical systems.

Classical vs Quantum Walks

In a classical random walk on a graph, a walker occupies a vertex and at each time step moves to a neighboring vertex according to a probability distribution. Over many steps, the probability distribution of the walker's position spreads diffusively, with the standard deviation growing as the square root of the number of steps. This behavior underlies classical algorithms for Monte Carlo integration, Markov chain Monte Carlo sampling, and randomized search.

A quantum walk replaces the classical probability distribution over vertices with a quantum superposition of position states, and the stochastic transition matrix is replaced by a unitary evolution operator. Because quantum evolution is reversible and coherent, the amplitudes of different paths can interfere constructively or destructively. This interference leads to striking departures from classical behavior: on a line, the quantum walk propagates ballistically with standard deviation growing linearly in time, and on certain graphs, the hitting time — the expected time to reach a target — can be exponentially shorter.

p(t+1) = T \cdot p(t)

Classical transition

|\psi(t+1)\rangle = \hat{U} |\psi(t)\rangle

Quantum evolution

P(x, t) = |\langle x | \psi(t) \rangle|^2

Position probability

•Diffusive vs Ballistic: Classical walks spread as sqrt(t); quantum walks spread linearly in t due to coherent interference.
•Unitary Evolution: Quantum walks evolve via a unitary operator U, preserving total probability and enabling interference.
•Coin and Position: Discrete quantum walks use a coin register to control the direction of movement on the graph.
•Exponential Speedups: Certain graph traversal problems admit exponential quantum speedups over any classical random walk.

Discrete Quantum Walks

The discrete-time quantum walk model, introduced by Aharonov, Davidovich, and Zagury, operates on a composite Hilbert space consisting of a coin space and a position space. The coin is a small auxiliary register (typically one qubit for a walk on a line) that determines the direction of the next step. The evolution operator is decomposed into a coin operator C, which rotates the coin state, and a shift operator S, which moves the walker conditionally based on the coin state. The full step is U = S · (C ⊗ I).

Common choices for the coin operator include the Hadamard coin, which creates an equal superposition of moving left and right, and the Grover coin, which is used for higher-dimensional walks. The shift operator translates the position register: for a walk on a line, S|0⟩|x⟩ = |0⟩|x+1⟩ and S|1⟩|x⟩ = |1⟩|x-1⟩. After many steps, the position distribution develops characteristic interference peaks that are entirely absent in classical walks. On cyclic graphs or higher-dimensional lattices, the coin can be generalized to a d-dimensional register controlling movement along d axes.

\hat{U} = \hat{S} \cdot (\hat{C} \otimes \hat{I})

Step operator

\hat{S} = \sum_x |0\rangle\langle 0| \otimes |x+1\rangle\langle x| + |1\rangle\langle 1| \otimes |x-1\rangle\langle x|

Shift on line

\hat{C} = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}

Hadamard coin

•Hadamard Coin: The one-qubit Hadamard gate creates symmetric superpositions, producing characteristic bimodal distributions.
•Grover Coin: For d-dimensional lattices, the Grover diffusion operator serves as a highly symmetric coin.
•Shift Operator: S conditionally increments or decrements the position register based on the coin state.
•Interference Patterns: Repeated applications of U generate non-classical probability distributions with oscillatory structure.

Applications in Search and Simulation

Quantum walks provide a powerful framework for developing search algorithms on graphs. In the spatial search problem, a marked vertex is to be found on a graph where the walker can only move along edges. Classical random walks solve this in O(N) steps on average for many graphs, but quantum walks can achieve O(sqrt(N)) steps on certain highly symmetric graphs like the hypercube, matching the performance of Grover's algorithm. This connection is not coincidental: Grover's algorithm can be viewed as a quantum walk on the complete graph.

Beyond search, continuous-time quantum walks — where the walker evolves under a Hamiltonian given by the graph adjacency matrix or Laplacian — have been applied to simulate quantum physical systems, analyze graph properties, and even solve satisfiability problems. The quantum walk formulation of algorithm design has proven to be a fertile source of new quantum speedups and continues to inspire research in quantum computing theory and applications.

\hat{H} = \gamma \hat{L} \quad \text{or} \quad \hat{H} = \gamma \hat{A}

Continuous-time Hamiltonian

|\psi(t)\rangle = e^{-i\hat{H}t} |\psi(0)\rangle

State evolution

•Spatial Search: Quantum walks achieve O(sqrt(N)) search on hypercubes and other symmetric graphs.
•Element Distinctness: Ambainis' quantum walk algorithm solves element distinctness in O(N^{2/3}) queries, beating classical O(N).
•Graph Properties: Quantum walks can detect graph isomorphism and evaluate Boolean formulas with quantum advantages.
•Physical Simulation: Continuous-time quantum walks naturally simulate transport phenomena in quantum systems.

Code in Action

Runnable implementations you can copy and experiment with.

Quantum Walk with Qiskit

A discrete quantum walk on a 4-node cycle using 2 position qubits and 1 coin qubit, implementing Hadamard coin and conditional shift.

quantum_walk_qiskit.py

from qiskit import QuantumCircuit

# 2 position qubits + 1 coin qubit
qc = QuantumCircuit(3, 2)
coin = 2
pos = [0, 1]

# Initialize coin and position
qc.h(coin)
qc.h(pos)

# Hadamard coin
qc.h(coin)

# Controlled shift: increment if coin=0, decrement if coin=1
# Controlled increment (coin=0):
qc.x(coin)
qc.ccx(coin, pos[0], pos[1])
qc.cx(coin, pos[0])
qc.x(coin)

# Controlled decrement (coin=1):
qc.cx(coin, pos[0])
qc.ccx(coin, pos[0], pos[1])

qc.measure(pos, [0, 1])

print(qc.draw(output='text'))

Quantum Walk with PennyLane

A PennyLane implementation of a discrete quantum walk on a 4-node cycle, returning position probabilities.

quantum_walk_pennylane.py

import pennylane as qml
import numpy as np

dev = qml.device('default.qubit', wires=3)

@qml.qnode(dev)
def quantum_walk():
    # Initialize
    qml.Hadamard(wires=2)
    qml.Hadamard(wires=0)
    qml.Hadamard(wires=1)
    # Coin
    qml.Hadamard(wires=2)
    # Controlled increment (coin=0)
    qml.PauliX(wires=2)
    qml.Toffoli(wires=[2, 0, 1])
    qml.CNOT(wires=[2, 0])
    qml.PauliX(wires=2)
    # Controlled decrement (coin=1)
    qml.CNOT(wires=[2, 0])
    qml.Toffoli(wires=[2, 0, 1])
    return qml.probs(wires=[0, 1])

print(quantum_walk())

Explore next

Grover's Algorithm

Explore next

Quantum Simulation

from qiskit import QuantumCircuit # 2 position qubits + 1 coin qubit qc = QuantumCircuit(3, 2) coin = 2 pos = [0, 1] # Initialize coin and position qc.h(coin) qc.h(pos) # Hadamard coin qc.h(coin) # Controlled shift: increment if coin=0, decrement if coin=1 # Controlled increment (coin=0): qc.x(coin) qc.ccx(coin, pos[0], pos[1]) qc.cx(coin, pos[0]) qc.x(coin) # Controlled decrement (coin=1): qc.cx(coin, pos[0]) qc.ccx(coin, pos[0], pos[1]) qc.measure(pos, [0, 1]) print(qc.draw(output='text'))

import pennylane as qml import numpy as np dev = qml.device('default.qubit', wires=3) @qml.qnode(dev) def quantum_walk(): # Initialize qml.Hadamard(wires=2) qml.Hadamard(wires=0) qml.Hadamard(wires=1) # Coin qml.Hadamard(wires=2) # Controlled increment (coin=0) qml.PauliX(wires=2) qml.Toffoli(wires=[2, 0, 1]) qml.CNOT(wires=[2, 0]) qml.PauliX(wires=2) # Controlled decrement (coin=1) qml.CNOT(wires=[2, 0]) qml.Toffoli(wires=[2, 0, 1]) return qml.probs(wires=[0, 1]) print(quantum_walk())