A Quantum Walk Remembers Which Paths Interfered

Status: an interactive reconstruction of a PHY104 course project. The report surveys established quantum-walk results and includes numerical illustrations; it does not claim a new walk algorithm or complexity bound.

A random walker forgets. At every step it throws away the coin result and keeps only a new position distribution. A quantum walker cannot update probabilities that way because quantum evolution must remain unitary. It carries a coin state, keeps complex amplitudes for every path, and postpones measurement. Paths that arrive at the same position can then reinforce or cancel one another.

That one change replaces diffusive spreading, $\sigma\propto\sqrt t$, with ballistic spreading, $\sigma\propto t$. After a hundred steps the coherent width is about fifty-four sites against the classical ten, and the gap keeps opening.

“A quantum walk is faster” is where most short accounts stop, and it is the part worth being careful about. The speed comes from a specific spectral and interference structure. It buys no guarantee that a given quantum-walk algorithm beats its classical counterpart, and measuring a far-away position is by itself no solution to a computational problem.

Begin with the classical recurrence

For an unbiased walk on the integers, let $X_1,X_2,\ldots$ be independent steps with values $\pm1$. After $t$ steps,

$$S_t=\sum_{k=1}^tX_k, \qquad \mathbb E[S_t]=0, \qquad \operatorname{Var}(S_t)=t.$$

The exact probability of reaching $x$ is binomial:

$$P_t(x)=2^{-t}\binom{t}{(t+x)/2},$$

when $t+x$ is even, and zero otherwise. Parity matters: after an even number of steps, only even positions are reachable.

At large $t$, the central limit theorem gives a Gaussian envelope with width $\sqrt t$. The reason is already in the variance calculation. Independent increments add variances, not standard deviations.

The same scaling appears from a continuum limit. If the lattice spacing is $\ell$, the time step is $\tau$, and $\ell^2/(2\tau)\to D$, then the master equation approaches

$$\frac{\partial P}{\partial t}=D\frac{\partial^2P}{\partial x^2}.$$

A point source evolves into the heat kernel

$$P(x,t)=\frac{1}{\sqrt{4\pi Dt}} \exp\!\left(-\frac{x^2}{4Dt}\right).$$

Diffusion smooths and irreversibly loses information. Running the heat equation backward magnifies short-wavelength noise. A closed quantum system cannot behave this way, because its time evolution has to be reversible, and that constraint is what the next section has to build around.

Quantizing the walk requires an extra space

The obvious rule is to send half the amplitude left and half right. Try writing it as a matrix and it fails to be unitary: it cannot remember where the amplitude came from. A discrete-time quantum walk adds a two-dimensional coin space

$$\mathcal H=\mathcal H_{\mathrm{position}}\otimes \mathcal H_{\mathrm{coin}}.$$

Using coin basis states $|0\rangle$ and $|1\rangle$, one step consists of a coin rotation followed by a conditional translation. For the Hadamard coin,

$$H=\frac1{\sqrt2} \begin{pmatrix}1&1\\1&-1\end{pmatrix},$$

and

$$S|x,0\rangle=|x-1,0\rangle, \qquad S|x,1\rangle=|x+1,1\rangle.$$

The complete step operator is

$$U=S(I\otimes H).$$

Both $H$ and $S$ are unitary, so $U$ is unitary. No path information is discarded until measurement.

The first step resembles a classical split. The distinction appears once different histories meet. At a later site, one amplitude may arrive through the coin state $|0\rangle$ and another through $|1\rangle$; the next Hadamard operation mixes them. Their complex signs and phases determine whether the outgoing amplitude grows or vanishes.

The initial phase is physical

Consider the balanced initial coin

$$|c_\phi\rangle=\frac{|0\rangle+e^{i\phi}|1\rangle}{\sqrt2}.$$

Every value of $\phi$ gives equal initial probabilities for the two coin states. Yet the later position distribution can be strongly asymmetric because the relative phase changes interference. For the Hadamard walk, $\phi=\pi/2$ produces a symmetric distribution.

If you have met the rule that an overall phase is unobservable, this is the place to keep the two cases apart. The phase here is relative, between coin components, and relative phase is exactly what a later Hadamard reads.

Use the lower slider while the animation is paused. It changes only the initial relative phase; the coin, shift, and number of steps stay fixed.

steps60pauserestartinitial phase φ/π0.50

The two distributions occupy different scales. The classical mass remains near the origin. The quantum profile develops two outward-moving fronts and an oscillatory interior. Varying $\phi$ moves probability between the fronts but does not restore a Gaussian.

Ballistic spreading comes from phases that remain coherent

For a translation-invariant walk, Fourier transform position into quasi-momentum $k$. Translation becomes multiplication by $e^{\pm ik}$, so the infinite walk decomposes into independent $2\times2$ unitary matrices $U(k)$. Their eigenvalues have the form $e^{\pm i\omega(k)}$.

A localized state contains many $k$ values. After $t$ steps each mode acquires phase $e^{\pm it\omega(k)}$. Stationary-phase analysis says the largest long-time contributions occur along rays

$$\frac{x}{t}=\pm\frac{d\omega}{dk},$$

the group velocities of the two bands. Because these velocities are finite and nonzero, the dominant fronts move a distance proportional to $t$.

For the symmetric Hadamard walk, the rescaled position $X_t/t$ approaches a non-Gaussian limit supported inside $[-1/\sqrt2,1/\sqrt2]$. In particular,

$$\frac{\sigma_q(t)}{t}\longrightarrow \sqrt{1-\frac1{\sqrt2}}\approx0.541,$$

whereas $\sigma_c(t)/\sqrt t\to1$ for the classical unbiased walk. If you want one number to carry away, take the $0.541$: the coherent width settles at a fixed fraction of the elapsed time, while the classical width settles at a fixed fraction of its square root. The two limits scale different random variables: $X_t/t$ in the coherent case and $X_t/\sqrt t$ in the diffusive case. This distinction is made precise by Konno’s one-dimensional limit theorem.

It is tempting to read the quantum speed as a larger diffusion constant, and the reading fails on the exponent alone: any $D$ whatsoever still gives width proportional to $\sqrt t$. Raising $D$ changes the prefactor and leaves the exponent sitting at one half.

What happens if we measure every step?

Suppose the coin is measured after each application of $U$ and the result is forgotten. The off-diagonal coherences in the coin-position density matrix are removed. Alternative paths no longer meet as amplitudes; they meet as ordinary probabilities. For the Hadamard coin this repeated dephasing recovers a classical-like diffusive walk.

That is what coherence buys, operationally: the ability to preserve and later compare the phases of paths that would otherwise be distinguishable. The outward fronts sit where those surviving amplitudes agree in phase.

Continuous time removes the coin, not interference

On a graph $G$, a continuous-time classical walk evolves through a Markov generator, often the graph Laplacian $L$:

$$\frac{d\mathbf p}{dt}=-\gamma L\mathbf p.$$

The exponential $e^{-\gamma Lt}$ damps modes with positive eigenvalues and drives probability toward equilibrium when the graph permits it.

A continuous-time quantum walk instead uses a Hermitian graph operator as a Hamiltonian:

$$i\frac{d}{dt}|\psi(t)\rangle=H|\psi(t)\rangle, \qquad |\psi(t)\rangle=e^{-iHt}|\psi(0)\rangle.$$

$H$ may be an adjacency matrix or a Laplacian, depending on convention and the physical model. It is easy to say that the $i$ “makes the classical matrix unitary,” but the work is done by Hermiticity: $H=H^\dagger$ is what makes $e^{-iHt}$ unitary. Each graph eigenmode acquires a phase instead of being exponentially damped.

On the infinite line, choosing a nearest-neighbour Hamiltonian yields amplitudes proportional to Bessel functions:

$$\langle x|\psi(t)\rangle=i^xJ_x(2\gamma t), \qquad P_t(x)=J_x^2(2\gamma t),$$

up to an overall phase and convention for $H$. The Bessel profile again has a ballistic front. Konno’s continuous-time analysis places this contrast with the classical central-limit scaling on a precise limit-theorem footing.

A wide distribution is not yet an algorithm

Quantum walks become algorithmic when graph structure makes a desired answer interfere constructively while unwanted answers cancel. The performance claim must then include the cost of preparing the state, implementing the walk, querying an oracle, and extracting the result.

Two examples show the range of the idea:

• The Shenvi–Kempe–Whaley walk searches a hypercube with $O(\sqrt N)$ oracle calls, a Grover-like query advantage in that oracle model.
• Childs showed that scattering in a continuous-time walk on a sparse graph can encode universal quantum computation in the graph itself.

Neither result follows merely from $\sigma_q\propto t$. Ballistic transport is a useful primitive; computation requires a problem-dependent interference design and a complexity analysis.

The same caution applies to mixing. A classical ergodic walk can converge to a stationary distribution because its nonconstant spectral modes decay. A closed unitary walk keeps rotating phases and generally does not converge pointwise. Researchers therefore study time-averaged distributions, hitting probabilities, state transfer, or decohered variants, each with a definition chosen for the task.

What the course report establishes

The report develops the classical lattice walk and its heat-equation limit, introduces the Hilbert-space machinery needed for coherent evolution, constructs both coined and continuous-time walks, and surveys search, mixing, and state transfer. Its strongest reusable lesson is the comparison of generators:

$$\text{classical: }e^{-tL} \qquad\text{versus}\qquad \text{quantum: }e^{-itH}.$$

One semigroup damps; the other rotates. Diffusion versus interference follows from that, and so does stationary behaviour versus persistent oscillation, and so does the awkwardness of defining quantum hitting and mixing times at all when there is nothing for the walk to settle into.

The report is a course survey, not a new theorem. Some application sections summarize proposals whose practical advantage depends on their computational model and hardware assumptions. The interactive above reproduces the cleanest claim directly: unitary Hadamard dynamics on the line, with a controlled initial phase, spreads ballistically while the matched classical walk spreads diffusively.

• Read the complete PHY104 report (PDF)
• Inspect the project repository