Quantum Walks

A classical random walk is the most economical model of blind diffusion: at each tick a token hops to a uniformly random neighbour, and after $t$ steps its position has spread by $\sigma\sim\sqrt t$ . Replace the probability vector by a quantum amplitude vector and the stochastic transition matrix by a unitary, and something qualitatively different happens. Amplitudes carry a phase, so the many paths reaching a vertex interfere — constructively here, destructively there — and the walker no longer diffuses but propagates. On the line it spreads ballistically, $\sigma\sim t$ , a full quadratic factor faster than its classical cousin. That single change of accounting, probabilities to amplitudes, is the seed of a whole family of quantum algorithms. Two formalisms make the idea precise. The discrete-time coined walk equips the walker with an internal qubit — a "coin" — and alternates a coin unitary $C$ with a coin-conditioned shift $S$ , so one step is $U=S(C\otimes I)$ . The continuous-time walk drops the coin and evolves the position register directly under a graph Hamiltonian, usually the adjacency matrix or Laplacian, giving $U(t)=e^{-iHt}$ . Both are unitary, hence reversible and norm-preserving — the opposite of the contractive, mixing dynamics of a Markov chain, and the reason a closed quantum walk never settles into a stationary distribution. The algorithmic payoff comes from shaping interference so that amplitude concentrates on marked vertices or rare structured configurations. Grover's search is exactly a walk on the complete graph; spatial search extends the question to geometrically constrained graphs; Ambainis's element-distinctness algorithm walks the Johnson graph to $O(N^{2/3})$ queries; and Szegedy's quantization turns any reversible chain into a walk whose spectral gap is quadratically amplified. This article develops both formalisms, their spectral analysis, and the derivations that make the speedups exact.

Key takeaways

A quantum walk propagates amplitudes, not probabilities, so interfering paths make it spread ballistically ( $\sigma\sim t$ ) rather than diffusively ( $\sigma\sim\sqrt t$ ) — a built-in quadratic speedup.
Two equivalent paradigms: the discrete-time coined walk $U=S(C\otimes I)$ alternating a coin flip with a conditional shift, and the continuous-time walk $e^{-iHt}$ generated by the graph adjacency matrix or Laplacian.
The walk operator's spectrum governs mixing, hitting, and search; Szegedy's quantization maps a classical gap $\delta$ to a quantum phase gap of order $\sqrt\delta$ .
Walks power speedups — Grover-like $\sqrt N$ spatial search, element distinctness in $O(N^{2/3})$ , exponential separations on structured graphs — and both formalisms are universal for quantum computation.
Closed walks are reversible and never relax; only time-averaged distributions converge, and only added decoherence recovers the classical diffusive law.
Key idea: replace the probability vector and stochastic matrix by an amplitude vector and a unitary; interference then turns diffusive $\sqrt t$ spreading into ballistic $t$ spreading and a mixing gap $\delta$ into an amplified gap $\sqrt\delta$ .

The core insight

Replace the classical probability vector and stochastic transition matrix by a quantum amplitude vector and a unitary evolution; interference then turns diffusive $\sqrt t$ spreading into ballistic $t$ spreading and turns mixing gaps $\delta$ into amplified gaps $\sqrt\delta$ .

Where this lives today

Quantum walks have moved from theory into laboratories and into the core of modern algorithms. On the hardware side, integrated photonic waveguide arrays implement walks directly: light in a lattice of coupled waveguides evolves under $e^{-iAz}$ with propagation distance $z$ as time, and experiments cleanly image the double-peaked ballistic distribution and watch it collapse to a Gaussian as disorder or dephasing is dialled in. Trapped-ion and superconducting platforms realize coined walks with tens of steps, and multi-walker photonic walks are the substrate of boson-sampling demonstrations — all doubling as simulators of coherent transport, Anderson localization, and the quantum-to-classical transition. On the algorithmic side, Szegedy's construction seeded the most important speedups of the last decade: element distinctness, triangle finding, and a general "quantum walk search" framework. Most consequentially, the Szegedy walk's spectral structure was refined by Low and Chuang into qubitization and the quantum singular value transformation — the near-optimal engine for Hamiltonian simulation and linear systems — so the block-encoding walks inside today's fault-tolerant algorithms are direct descendants of the reflection product $W=(2\Pi_B-I)(2\Pi_A-I)$ . The open frontier is finding problems with exponential, not merely quadratic, walk speedups on graphs that arise naturally rather than by construction.

The physical picture

Picture a coin-flipping walker on a line, except the coin is a qubit and the flips are unitary. A classical walker's left/right choices are independent tosses, so by the central limit theorem its displacement piles into a Gaussian of width $\sqrt t$ at the origin. The quantum walker instead keeps a coherent superposition of every path; amplitudes of paths ending at the same vertex add before they are squared into a probability, and their relative phases decide whether the sum reinforces or cancels. The result is not a central hump but two peaks racing outward at a fixed speed — the amplitude has developed a group velocity, and the distribution grows linearly in time.

Figure

Position distribution after t = 100 steps: the classical walk in red piles into one Gaussian hump of width σ = √t = 10, while the Hadamard quantum walk in blue splits into two ballistic peaks near x ≈ ±t/√2 ≈ ±71 with overall width σ ≈ 0.54 t ≈ 54 — diffusive √t versus ballistic t spreading

Where does the fixed speed come from? Translation symmetry on the line lets us pass to momentum $k$ , in which the walk operator is block-diagonal — one $2\times2$ unitary per $k$ , with eigenphases $\pm\omega(k)$ and group velocity $v(k)=\omega'(k)$ . For the Hadamard coin the dispersion is $\cos\omega=\tfrac{1}{\sqrt2}\cos k$ , bounding the group velocity by $v_{\max}=1/\sqrt2$ . Stationary phase then says the walker's weight collects at $x\approx v(k)\,t$ , concentrating inside $|x|\lesssim t/\sqrt2$ with two bright caustics at the maximum-velocity edges — precisely the twin peaks of the first figure. The second figure is that dispersion curve, the mechanism behind the picture above.

Figure

Group velocity v(k) = sin k / √(2 − cos²k) of the Hadamard walk, peaking at v_max = 1/√2 ≈ 0.707 at k = ±π/2 — the finite maximum speed that places the two ballistic peaks at x ≈ ±v_max t = ±t/√2 ≈ ±0.71 t

The continuous-time walk tells the same story in solid-state language. Read the adjacency matrix $A$ as a tight-binding Hamiltonian: $e^{-iAt}$ propagates a particle tunnelling between connected sites, its eigenvectors are stationary modes, and spreading is their dephasing. Search then adds a rank-one potential $-|w\rangle\langle w|$ that pushes two eigenmodes into a near-degeneracy, driving a slow Rabi rotation onto the marked vertex.

The core equations

The discrete-time coined walk is the cleanest place to start, because it makes the interference explicit. One step is a coin unitary acting on an internal qubit, followed by a shift that moves the walker in a direction dictated by that qubit.

|\psi_{t+1}\rangle = U|\psi_t\rangle,\qquad U = S\,(C\otimes I_{\mathcal H_P}) \qquad (1)

where: $\mathcal H=\mathcal H_C\otimes\mathcal H_P$ — coin space tensored with position space; $C$ — coin unitary on $\mathcal H_C$ (the Hadamard $H$ on a line); $S$ — coin-conditioned shift; $|\psi_t\rangle$ — joint coin–position state after $t$ steps. Reading: the coin must be conditioned because a plain unconditional translation carries no interference — the coin is what tags a direction and lets paths recombine. The shift is a permutation of basis states, hence manifestly unitary, and the coin is the small $2\times2$ unitary that manufactures superpositions of directions.

S=\sum_x\big(|0\rangle\langle0|\otimes|x{+}1\rangle\langle x|+|1\rangle\langle1|\otimes|x{-}1\rangle\langle x|\big),\qquad C=H=\tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix} \qquad (2)

where: coin state $|0\rangle$ moves the walker right, $|1\rangle$ moves it left; $H$ splits each coin state into an equal superposition. Reading: without $C$ the walker drifts deterministically; with $C$ the two directions overlap and interfere step after step. The continuous-time walk dispenses with the coin. Time evolution is generated directly by a Hermitian operator built from the graph, so the walker tunnels between adjacent vertices with no auxiliary register.

H=A\quad\text{or}\quad H=L=D-A,\qquad U(t)=e^{-iHt} \qquad (3)

where: $A$ — adjacency matrix, $A_{xy}=1$ iff $x\sim y$ ; $D$ — degree matrix, $D_{xx}=\deg(x)$ ; $L$ — graph Laplacian, equal to $A$ up to a diagonal shift on a regular graph; $U(t)$ — the propagator. Reading: on regular graphs $A$ and $L$ generate the same dynamics up to a global phase, so the choice is a convention. The empirical signature that separates the quantum walk from its classical parent is the growth law of the position spread.

P_t^{\text{quantum}}(x)=|\langle x|\psi_t\rangle|^2,\qquad \sigma_{\text{quantum}}(t)\sim t\;\gg\;\sigma_{\text{classical}}(t)\sim\sqrt t \qquad (4)

where: $P_t(x)$ — probability of finding the walker at $x$ at time $t$ ; $\sigma(t)$ — standard deviation of that distribution. Reading: the linear-versus-square-root law is the whole speedup in one line — quantum reaches distance $t$ in time $t$ , classical needs time $t^2$ . Translation symmetry diagonalizes the line walk in momentum, reducing the whole evolution to independent $2\times2$ blocks.

\widetilde U(k)=R(k)\,(C\otimes I),\quad R(k)=\mathrm{diag}(e^{-ik},e^{ik}),\quad |\psi_t\rangle=\int_{-\pi}^{\pi}\frac{\mathrm dk}{2\pi}\,\widetilde U(k)^t\,\widetilde\psi_0(k) \qquad (5)

where: $k$ — quasimomentum conjugate to position; $\widetilde U(k)$ — the $2\times2$ block at momentum $k$ ; $\widetilde\psi_0(k)$ — Fourier transform of the initial state. Reading: since $S$ commutes with translations, $k$ is conserved and each block evolves on its own, which makes stationary phase tractable. Szegedy's quantization is the bridge from a classical Markov chain to a quantum walk: each vertex is assigned a normalized superposition over its neighbours, weighted by square-roots of the transition probabilities.

|\psi_x\rangle=\sum_y\sqrt{P_{xy}}\;|x\rangle|y\rangle,\qquad \Pi=\sum_x|\psi_x\rangle\langle\psi_x| \qquad (6)

where: $P_{xy}$ — transition probability $x\to y$ of a reversible chain; $|\psi_x\rangle$ — neighbour-superposition state; $\Pi$ — projector onto their span. Reading: the square-root weighting ties the walk's spectrum to the chain's discriminant. The walk operator is a product of two reflections whose spectrum encodes the chain's mixing with a square-root amplification.

W=(2\Pi_B-I)(2\Pi_A-I),\qquad \text{eigenphases }\pm2\arccos\lambda_j,\qquad D(P)_{xy}=\sqrt{P_{xy}P_{yx}} \qquad (7)

where: $\Pi_A,\Pi_B$ — projectors onto the two interleaved copies of the Szegedy span; $\lambda_j$ — singular values of the discriminant $D(P)$ ; a reversible chain with spectral gap $\delta=1-\lambda_2$ acquires phase gap $\Delta(W)=2\arccos(1-\delta)\approx2\sqrt{2\delta}$ . Reading: the classical gap $\delta$ appears as a quantum phase gap of order $\sqrt\delta$ , the algebraic origin of the quadratic hitting-time speedup. Continuous-time spatial search adds a marking potential to the graph Hamiltonian and reads off the search time from the avoided-crossing gap it opens.

H_{\text{search}}=-\gamma A-|w\rangle\langle w|,\qquad T\sim\frac{1}{|\langle w|\psi(T)\rangle|}\cdot\frac{1}{\Delta E} \qquad (8)

where: $\gamma$ — hopping rate, tuned to a critical $\gamma_c$ ; $|w\rangle$ — marked vertex, a rank-one potential well; $\Delta E$ — gap between the two relevant eigenstates at $\gamma_c$ . Reading: the run time is set by the reciprocal of the minimal avoided-crossing gap the geometry allows.

Derivation ABallistic spreading of the Hadamard walk on the line

The goal is to prove that the discrete-time coined walk with a Hadamard coin spreads linearly, $\sigma\sim t$ , rather than diffusively, and to pin the coefficient. The strategy: exploit translation symmetry to block-diagonalize the walk in momentum, extract the dispersion $\omega(k)$ and its group velocity, then evaluate the long-time position amplitude by stationary phase, the standard tool for oscillatory integrals.

Step 1. Fourier-transform along the line. Since $S$ commutes with unit translation, momentum $k$ is conserved and the walk is block-diagonal: at each $k$ it acts as $\widetilde U(k)=\mathrm{diag}(e^{-ik},e^{ik})\cdot\tfrac1{\sqrt2}\big(\begin{smallmatrix}1&1\\1&-1\end{smallmatrix}\big)$ . Why: a symmetry commuting with $U$ splits it into independent sectors — one $2\times2$ block per $k$ .

Step 2. Diagonalize the block. Its eigenvalues are $e^{\mp i\omega(k)}$ , and the trace condition $2\cos\omega=\sqrt2\cos k$ gives the dispersion $\cos\omega(k)=\tfrac{1}{\sqrt2}\cos k$ , so $\widetilde U(k)^t=\sum_\pm e^{\mp i\omega(k)t}\,|\chi_\pm\rangle\langle\chi_\pm|$ . Why: reducing $U^t$ to scalar phases turns matrix powers into an ordinary oscillatory integral.

Step 3. Write the position amplitude as $\langle x|\psi_t\rangle=\int_{-\pi}^{\pi}\tfrac{\mathrm dk}{2\pi}\,e^{i(kx-\omega(k)t)}\,a(k)$ , with slowly varying envelope $a(k)$ . Why: for large $t$ the rapid phase $\phi(k)=kx-\omega(k)t$ cancels almost everywhere, so only special momenta survive.

Step 4. Apply stationary phase. The integral is dominated by momenta where $\phi'(k)=0$ , i.e. $x=v(k)\,t$ with $v(k)=\dfrac{\sin k}{\sqrt{2-\cos^2 k}}$ . Since $|v(k)|\le v_{\max}=1/\sqrt2$ (at $k=\pm\pi/2$ ), the amplitude concentrates on $|x|\lesssim t/\sqrt2$ , with sharp caustic peaks at the maximum-velocity edges. Why: a finite maximum group velocity is a light-cone — the walker cannot outrun $v_{\max}\,t$ , and piles up at the cone's edge.

Step 5. Read off the width. Because $x\approx v(k)\,t$ across a finite band of velocities, $\langle x^2\rangle=\int\mathrm dk\,|a(k)|^2 v(k)^2\,t^2+O(t)\propto t^2$ , so $\sigma\propto t$ ; the symmetric-coin coefficient is

\sigma_{\text{quantum}}(t)=\Big(1-\tfrac{1}{\sqrt2}\Big)^{1/2}t+o(t)\approx0.54\,t\quad\Longleftrightarrow\quad\sigma\sim t

against the classical $\langle x^2\rangle=t$ . Why: the classical walk averages over incoherent velocities that cancel to zero mean speed and $\sqrt t$ diffusion; the quantum walk keeps a coherent band of nonzero velocities and travels. *Verified: $v_{\max}=1/\sqrt2\approx0.7071$ at $k=\pm\pi/2$ and $\sigma_q\approx0.5412\,t$ (so $\sigma_q(100)\approx54.1$ , peaks at $\pm70.7$ ), reproducing the standard Nayak–Vishwanath and Kempe (2003) results.*

Go deeper · Derivation B · 1 minGrover search as a continuous-time walk on the complete graph

Derivation BGrover search as a continuous-time walk on the complete graph

The goal is to show that continuous-time search on the complete graph is nothing but Grover's algorithm, reaching the marked vertex in time $\tfrac{\pi}{2}\sqrt N$ . The strategy: the search Hamiltonian preserves the two-dimensional subspace spanned by the uniform and marked states, so reduce it to a $2\times2$ matrix there and recognise the dynamics as a Rabi oscillation whose frequency is the avoided-crossing gap. Take $H=-|s\rangle\langle s|-|w\rangle\langle w|$ with $|s\rangle=\tfrac1{\sqrt N}\sum_x|x\rangle$ and $|w\rangle$ the marked vertex.

Step 1. Confine to a 2D subspace. Both terms of $H$ are rank-one projectors onto states inside $\mathcal S=\mathrm{span}\{|s\rangle,|w\rangle\}$ , so $H$ annihilates everything orthogonal to $\mathcal S$ and the dynamics stay there. The states are nearly orthogonal, $\langle s|w\rangle=1/\sqrt N$ . Why: a two-level problem is exactly solvable, and the tiny overlap $1/\sqrt N$ is the small parameter that sets the speed.

Step 2. Build the effective matrix. In the orthonormal basis $\{|w\rangle,|r\rangle\}$ with $|r\rangle\propto|s\rangle-\tfrac1{\sqrt N}|w\rangle$ , one finds $H|_{\mathcal S}=-\big(\begin{smallmatrix}1+1/N & \sqrt{1-1/N}/\sqrt N\\ \sqrt{1-1/N}/\sqrt N & 1-1/N\end{smallmatrix}\big)$ , off-diagonal coupling $\Theta(1/\sqrt N)$ . Why: the off-diagonal element is the amplitude between "spread out" and "found it", so its size is the rotation rate.

Step 3. Compute the gap. The splitting of a $2\times2$ symmetric matrix is $\Delta E=\sqrt{(\text{diag diff})^2+4(\text{off-diag})^2}$ ; the entries cancel exactly to $\Delta E=2/\sqrt N$ . Why: this avoided-crossing gap fixes everything downstream.

Step 4. Read the Rabi oscillation. A two-level system driven from one eigenstate transfers population as $|\langle w|\psi(t)\rangle|^2=\sin^2(\tfrac{\Delta E}{2}t)$ , so from $|s\rangle$ the amplitude rotates onto $|w\rangle$ at frequency $\Delta E/2=1/\sqrt N$ . Why: the whole search is a single Rabi flop from uniform to marked.

Step 5. Optimize the time. The amplitude on $|w\rangle$ is maximal when $\tfrac{\Delta E}{2}T=\tfrac{\pi}{2}$ , giving

T=\frac{\pi}{\Delta E}=\frac{\pi}{2}\sqrt N\,(1+o(1))

the continuous-time counterpart of Grover's $\tfrac{\pi}{4}\sqrt N$ iterations. Why: overshooting rotates past $|w\rangle$ and the amplitude falls again, so the optimal stopping time is a quarter Rabi period. *Verified: overlap $1/\sqrt N$ , gap $2/\sqrt N$ , and $T=\tfrac{\pi}{2}\sqrt N$ ; for $N=10^6$ , $\Delta E=2\times10^{-3}$ and $T\approx1571$ versus a classical $N/2=5\times10^5$ , matching the Childs–Goldstone (2004) analysis.*

Go deeper · Derivation C · 2 minThe Szegedy spectral correspondence

Derivation CThe Szegedy spectral correspondence

The goal is to relate the eigenphases of the quantized walk $W$ to the singular values of the discriminant $D(P)$ , proving that a classical gap $\delta$ is amplified to a quantum phase gap of order $\sqrt\delta$ . The strategy is Jordan's lemma: any two projectors carve the space into invariant subspaces of dimension at most two, on each of which the product of the two reflections is a rotation by twice the principal angle between the subspaces. Build $W$ from reflections about the Szegedy span $\mathcal A=\mathrm{span}\{|\psi_x\rangle\}$ and its register-swapped copy $\mathcal B$ .

Step 1. Write $W$ as two reflections, $W=R_BR_A$ with $R_A=2\Pi_A-I$ , $R_B=2\Pi_B-I$ , the $\Pi$ 's projecting onto the two interleaved copies of the neighbour-superposition states. Why: a product of two reflections is a rotation, and the angle carries the spectral information.

Step 2. Invoke Jordan's lemma. The pair $(\Pi_A,\Pi_B)$ block-diagonalizes into subspaces of dimension $\le2$ ; on each, $W$ is a rotation by $2\theta_j$ with $\theta_j$ the principal angle between $\mathcal A$ and $\mathcal B$ . Why: this converts a high-dimensional unitary into a list of ordinary rotations.

Step 3. Identify the angles with the discriminant: $\cos\theta_j=\lambda_j$ , the singular values of $D(P)_{xy}=\sqrt{P_{xy}P_{yx}}$ . For a reversible chain the largest is $\lambda_1=1$ (the stationary mode), the rest strictly below. Why: the discriminant's spectrum governs classical mixing, so tying $\theta_j$ to $\lambda_j$ imports all of Markov-chain spectral theory.

Step 4. Assemble the eigenphases. Each 2D block contributes a conjugate pair $W|\pm_j\rangle=e^{\pm i\,2\theta_j}|\pm_j\rangle$ with $2\theta_j=2\arccos\lambda_j$ , plus the fixed subspaces at $0$ and $\pi$ :

\text{eigenphases of }W=\{\pm2\arccos\lambda_j\}\cup\{0,\pi\}

Why: the master formula — the whole spectrum of $W$ read off from the singular values of a classical matrix.

Step 5. Amplify the gap. If $\lambda_2=1-\delta$ , its phase is $2\arccos(1-\delta)\approx2\sqrt{2\delta}$ . Phase estimation on $W$ resolves it in $O(1/\sqrt\delta)$ applications versus the classical $O(1/\delta)$ mixing time — the quadratic hitting-time speedup. Why: $\arccos(1-\delta)\approx\sqrt{2\delta}$ is the square-root that separates quantum from classical. *Verified: $2\arccos(1-\delta)\approx2\sqrt{2\delta}$ (for $\delta=0.01$ , $0.2831$ versus $0.2828$ ), giving quantum cost $1/\sqrt\delta=10$ against classical $1/\delta=100$ ; consistent with Szegedy (2004) and the Jordan-angle treatment in Watrous.*

Limiting cases

Quantum walks specialize to several familiar regimes; each limit is a check on the formalism.

Case	Result	Meaning
Decoherence → classical	$\rho_{t+1}=(1-p)\,U\rho_tU^\dagger+p\,\mathcal D(\rho_t)$	per-step dephasing $p\to1$ destroys coherence, so ballistic $\sigma\sim t$ degrades to diffusive $\sigma\sim\sqrt t$ — the quantum-to-classical crossover
Complete graph → Grover	$H=-\|s\rangle\langle s\|-\|w\rangle\langle w\|,\ \|s\rangle=\tfrac1{\sqrt N}\sum_x\|x\rangle$	search on the complete graph is exactly Grover's $O(\sqrt N)$ rotation in the 2D span of uniform and marked states
Coined walk → continuous	$C\to I+i\epsilon H_c\ \Rightarrow\ U^{t}\to e^{-iHt}$	letting the coin approach identity and rescaling time recovers a continuous-time walk; the two formalisms agree in the limit
Lattice dimension	$T_{\text{search}}\sim\sqrt{N\log N}\ (d=2),\ \sqrt N\ (d\ge3)$	Grover-optimal $\sqrt N$ search is achievable for $d\ge3$ ; $d=2$ pays a $\log$ penalty and $d=1$ gives no speedup at all

Common trapA quantum walk converges to a stationary distribution like its classical cousin

It does not. A classical chain is contractive — its transition matrix has eigenvalues inside the unit disc, so all modes but the stationary one decay and the distribution relaxes. A closed quantum walk is unitary, every eigenvalue of modulus one, so nothing decays; the state oscillates quasi-periodically and the instantaneous distribution never settles. Two rescues exist: the time-averaged distribution $\bar P(x)=\lim_{T\to\infty}\tfrac1T\sum_{t<T}|\langle x|\psi_t\rangle|^2$ does converge, and it is this averaged object "mixing time" refers to; and adding decoherence or measurement opens the system and restores relaxation — at the cost of the ballistic speedup. A related trap: never dismiss the coin as bookkeeping. On a line a shift with no coin is the identity or a rigid translation, both interference-free; the coin is what makes the walk quantum.

Worked examples

1 · Ballistic versus diffusive spread after 100 steps (fully worked)

A symmetric Hadamard walk and a classical unbiased walk both run for $t=100$ steps on the line. Compare where the probability sits and how wide the distribution is.

Step 1. Classical spread. A sum of $t$ independent $\pm1$ steps gives $\langle x\rangle=0$ , $\langle x^2\rangle=t$ , so $\sigma_{\text{cl}}=\sqrt{100}=\mathbf{10}$ — a single Gaussian hump at the origin.

Step 2. Quantum peaks. The Hadamard dispersion caps the group velocity at $v_{\max}=1/\sqrt2\approx0.707$ , so the amplitude piles up at the light-cone edges $x\approx\pm v_{\max}t=\pm100/\sqrt2=\mathbf{\pm70.7}$ , with the centre comparatively depleted.

Step 3. Quantum width. $\sigma_{\text{q}}=(1-1/\sqrt2)^{1/2}t=0.5412\times100=\mathbf{54.1}$ — about $\mathbf{5.4\times}$ wider than classical after only 100 steps, and the ratio $\sigma_{\text{q}}/\sigma_{\text{cl}}\propto\sqrt t$ grows without bound.

Step 4. Interpretation. To reach distance $d=70$ the quantum walker needs $t\approx d/v_{\max}\approx99$ steps; the classical walker needs $t\approx d^2\approx4900$ . The quantum walk reaches distance $d$ in time $\Theta(d)$ against the classical $\Theta(d^2)$ — the quadratic speedup made concrete.

2 · Continuous-time Grover search on a million vertices

Search a complete graph of $N=10^6$ vertices with $H=-|s\rangle\langle s|-|w\rangle\langle w|$ . Find the avoided-crossing gap, the optimal run time, and compare to classical search.

Step 1. Overlap and gap. The states overlap by $\langle s|w\rangle=1/\sqrt N=10^{-3}$ , giving the avoided-crossing gap $\Delta E=2/\sqrt N=\mathbf{2\times10^{-3}}$ .

Step 2. Optimal time. A quarter Rabi period gives $T=\pi/\Delta E=\tfrac{\pi}{2}\sqrt N=\tfrac{\pi}{2}\times10^3\approx\mathbf{1571}$ (units where $H$ has unit coupling).

Step 3. Classical baseline. Unstructured classical search inspects on average $N/2=\mathbf{5\times10^5}$ vertices. The speedup is $\Theta(\sqrt N)=10^3$ — a thousandfold at a million vertices, growing as $\sqrt N$ . $T\approx1571$ versus $5\times10^5$ — a $\sqrt N$ speedup.

3 · Szegedy gap amplification for a slowly mixing chain

A reversible Markov chain has classical spectral gap $\delta=0.01$ (second discriminant singular value $\lambda_2=0.99$ ). Quantify the quantum hitting-time advantage.

Step 1. Classical cost. Reversible-chain mixing and hitting times scale as $1/\delta$ , so here $1/\delta=\mathbf{100}$ steps.

Step 2. Quantum phase gap. Szegedy's walk turns $\lambda_2=0.99$ into eigenphases $\pm2\arccos(0.99)$ , a phase gap $\Delta(W)=0.283\approx2\sqrt{2\delta}=2\sqrt{0.02}=\mathbf{0.283}$ — the small- $\delta$ approximation already tight.

Step 3. Quantum cost. Phase estimation resolves $\Delta(W)$ in $O(1/\sqrt\delta)$ steps, so $1/\sqrt\delta=\mathbf{10}$ . The walk hits in $\approx10$ steps against the classical $\approx100$ — a clean $1/\delta\to1/\sqrt\delta$ improvement.

Physics of the portrait

The quantum walk is where quantum computation, condensed-matter transport, and Markov-chain theory converge on one object — and its history is a relay of ideas, each contributor handing the baton on.

Origins · 1 minquantum walk and how this was discovered

quantum walk

amplitude analogue of a random walk, unitary U = S(C⊗I) or e^{−iHt} · quantum algorithms and coherent transport

The quantum walk began as a curiosity and became a pillar of quantum algorithms. Yakir Aharonov, Luiz Davidovich, and Nicim Zagury introduced the quantum random walk in 1993, showing a coin-driven walker on a line spreads far faster than diffusion — the ballistic $\sigma\sim t$ derived here. For five years it stayed a physics oddity, until Edward Farhi and Sam Gutmann recast it in continuous time in 1998, evolving a walker under $e^{-iAt}$ to speed up decision-tree search. Then it turned algorithmic in a rush: Aharonov, Ambainis, Kempe, and Vazirani built the theory of walks on graphs and their mixing and hitting times (2001); Childs and collaborators produced the first exponential separation on a "glued-trees" graph (2003); and Mario Szegedy quantized an arbitrary reversible chain, proving the square-root gap amplification $\delta\to\sqrt\delta$ (2004). Ambainis then walked the Johnson graph to element distinctness in an optimal $O(N^{2/3})$ queries (2007), the first walk to beat both Grover and the best classical bound on a natural problem. Childs closed the loop in 2009 by proving a single-particle continuous-time walk on a sparse graph universal for quantum computation. What Aharonov began as a coin on a line is now the engine behind Hamiltonian simulation, quantum search, and qubitization.

History

1993

— Aharonov, Davidovich and Zagury introduce the quantum random walk on a line

1998

— Farhi and Gutmann formulate the continuous-time quantum walk for decision trees

2003

— Childs and collaborators show an exponential speedup by a walk on glued trees

2004

— Szegedy quantizes reversible Markov chains, amplifying the spectral gap δ to √δ

2007

— Ambainis solves element distinctness in an optimal O(N^{2/3}) queries by a walk

Going further

Texts and papers. Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniv. ed. · Kempe, "Quantum random walks: an introductory overview", Contemp. Phys. 44, 307 (2003) · Aharonov, Ambainis, Kempe, Vazirani, "Quantum walks on graphs", STOC 2001 · Childs et al., "Exponential algorithmic speedup by a quantum walk", STOC 2003 · Szegedy, "Quantum speed-up of Markov chain based algorithms", FOCS 2004 · Ambainis, "Quantum walk algorithm for element distinctness", SIAM J. Comput. 37, 210 (2007) · Childs, "Universal computation by quantum walk", Phys. Rev. Lett. 102, 180501 (2009) · Watrous, The Theory of Quantum Information.

Provenance. The Hadamard dispersion $\cos\omega=\tfrac1{\sqrt2}\cos k$ , group velocity $v(k)=\sin k/\sqrt{2-\cos^2k}$ with $v_{\max}=1/\sqrt2$ , and width $\sigma_q\approx0.54\,t$ check against Kempe (2003) and Nayak–Vishwanath. The continuous Grover result $\Delta E=2/\sqrt N$ , $T=\tfrac{\pi}{2}\sqrt N$ follows Childs–Goldstone (2004). The Szegedy eigenphases $\pm2\arccos\lambda_j$ with $D(P)_{xy}=\sqrt{P_{xy}P_{yx}}$ and gap $2\arccos(1-\delta)\approx2\sqrt{2\delta}$ match Szegedy (2004) and Watrous. Element distinctness $O(N^{2/3})$ is Ambainis (2007); dimension-dependent search times are Childs–Goldstone and Ambainis–Kempe–Rivosh. A verifier should recompute the momentum block and stationary-phase condition, the $2\times2$ search gap, and the Jordan angle decomposition.

Builds on: Quantum Parallelism and the Oracle Model · Grover's Search Algorithm · Amplitude Amplification · Quantum Phase Estimation · Quantum Fourier Transform. Leads to: Element Distinctness via Quantum Walks · Hamiltonian Simulation · Quantum Spatial Search.

Ask the tutor: Ask me to walk you through the stationary-phase derivation of the ballistic peaks, or to quantize a specific Markov chain and read off its Szegedy speedup step by step.

Are the discrete-time and continuous-time quantum walks the same thing?

They are close relatives, not identical constructions. The discrete-time coined walk needs an extra coin register and applies a fixed unitary $U=S(C\otimes I)$ per step; the continuous-time walk has no coin and evolves the position register alone under $e^{-iHt}$ . On many graphs they map onto one another — letting the coin approach the identity and rescaling time recovers the continuous walk, and both reduce to Grover on the complete graph. The discrete (especially Szegedy) form is natural for Markov-chain problems, the continuous form for Hamiltonian-simulation and transport. Both share the essential feature: unitary, interference-driven, ballistic spreading.

Why can't a quantum walk on a line work without the coin?

On a line the only interference-free translations are the identity and a rigid one-site shift, both deterministic — there is no nontrivial unitary that "moves left or right at random" without an extra degree of freedom. The coin supplies it: it holds a direction, the shift acts conditioned on it, and the coin unitary $C$ mixes the two directions so paths can recombine and interfere. Remove the coin and you remove the branching, and with it the interference that makes the ballistic double peak. The continuous-time walk sidesteps this because its Hamiltonian couples neighbours directly, playing the coin's role implicitly.

Do quantum walks give exponential or only polynomial speedups?

Both, depending on the problem. For unstructured search the speedup is quadratic: $\sqrt N$ spatial search, $O(N^{2/3})$ element distinctness, the general Szegedy $1/\delta\to1/\sqrt\delta$ improvement. But on specially structured graphs the separation can be exponential — the Childs et al. glued-trees walk crosses root to root exponentially faster than any classical algorithm. The catch is that the exponential examples rely on graphs engineered to defeat classical algorithms, not ones that arise on their own; finding a natural problem with an exponential walk speedup remains open.

What is the discriminant matrix, and why does it appear?

The discriminant $D(P)_{xy}=\sqrt{P_{xy}P_{yx}}$ is the symmetric matrix built from a chain's forward and backward transition probabilities. For a reversible chain it is similar to the transition matrix (same eigenvalues), but being symmetric its singular values are clean and real. Szegedy's theorem makes the eigenphases of $W$ exactly $\pm2\arccos\lambda_j$ with $\lambda_j$ the singular values of $D(P)$ . That is why it appears everywhere: its spectrum controls both classical mixing (through $\delta=1-\lambda_2$ ) and quantum phase gaps (through $2\arccos(1-\delta)\approx2\sqrt{2\delta}$ ), the bridge that makes the square-root speedup exact.

How does decoherence turn a quantum walk classical?

Model each step as unitary evolution with probability $1-p$ and a dephasing channel with probability $p$ : $\rho_{t+1}=(1-p)U\rho_tU^\dagger+p\,\mathcal D(\rho_t)$ . Dephasing randomizes the relative phases between paths — exactly what interference depends on. For any fixed $p>0$ the long-time behaviour crosses from ballistic to diffusive: past a coherence time set by $p$ the walker forgets its phase and its variance grows like $t$ rather than $t^2$ , recovering $\sigma\sim\sqrt t$ . Photonic and ion-trap experiments tune $p$ to watch the double-peaked distribution melt into a single Gaussian — a controlled picture of the quantum-to-classical transition.

If Grover is a quantum walk, why bother with the walk framework?

Because the walk framework generalizes Grover to problems it cannot reach. Grover assumes an oracle over an unstructured set and gives a flat $\sqrt N$ ; the walk framework replaces that with the geometry of an arbitrary graph or Markov chain, so the speedup tracks the spectral gap and connectivity of the actual problem. That is what lets element distinctness beat Grover ( $N^{2/3}$ over the naive encoding), makes spatial search dimension-dependent, and powers the glued-trees separation. Grover is the special case on the complete graph — maximally connected and structureless; the walk is the general theory of which it is the simplest instance.