In short

A continuous-time quantum walk (CTQW) on a graph G is what you get when you take the graph's adjacency matrix A — a matrix with A_{ij} = 1 if vertices i and j are connected, 0 otherwise — and use it as the Hamiltonian of a quantum system. The state |\psi(t)\rangle is a superposition over vertices, the evolution is |\psi(t)\rangle = e^{-i A t} |\psi(0)\rangle, and the walker's "wavefunction" spreads across the graph under the usual Schrödinger dynamics. This sounds unremarkable until you compare it to a classical random walk, where the walker is at one vertex at a time and hops to a neighbour at random. Classical walks diffuse — the spread after time t is \sqrt{t}. Quantum walks propagate ballistically — the spread is t. On a line graph this is a quadratic speedup. On a specially constructed graph called the glued trees graph, the quantum walk reaches the far side of the graph in polynomial time, while any classical algorithm — random walk or otherwise — needs exponential time. This exponential separation, proved by Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman in 2003, is one of the cleanest quantum speedup results in the literature. Quantum walks then became a platform for algorithms: Ambainis's element-distinctness algorithm (2003), Magniez-Santha-Szegedy triangle finding, and the MNRS (Magniez-Nayak-Roland-Santha 2007) framework that unifies walk-based search. Alongside the quantum Fourier transform (engine of Shor and phase estimation) and amplitude amplification (engine of Grover), quantum walks are the third pillar on which most quantum algorithmic speedups rest.

Here is a question. You are standing at vertex 0 of an infinite line of vertices \ldots, -2, -1, 0, 1, 2, \ldots, connected in a chain. At each time step you flip a coin and move left or right. After t steps, how far are you from where you started?

The answer, famously, is about \sqrt{t}. You could be at any vertex within distance t, but the distribution of your position is a bell curve whose width grows like \sqrt{t}. This is diffusion — the mathematics that describes pollen in water, heat in a bar, and impurities spreading through an alloy. Every classical random walk on every sensible graph has this square-root-of-time scaling as a rule.

Now consider the quantum version. Instead of a walker at one vertex at a time, you have a wavefunction — a complex amplitude assigned to each vertex, with the squared magnitudes summing to 1. Instead of coin-flipping, you let the wavefunction evolve under a Hamiltonian derived from the graph. After time t, the probability distribution over vertices is whatever the wavefunction gives you. And that distribution — for the line graph — is spread over a width of t, not \sqrt{t}.

This is the first fact every student of quantum walks should internalise: classical walks spread diffusively; quantum walks spread ballistically. The factor of \sqrt{t} versus t is a quadratic speedup in "how far a walker explores in time t." For a line, the speedup is only quadratic and small problems can be handled classically. But for more elaborate graphs, the quantum walker's ballistic behaviour combined with interference produces algorithmic speedups that range from small polynomial to exponential. Continuous quantum walks are one of the three load-bearing primitives in quantum algorithms — alongside the quantum Fourier transform (which powers Shor's factoring) and amplitude amplification (which powers Grover's search).

This chapter explains the Hamiltonian, the evolution, the line-graph comparison, the celebrated glued-trees exponential speedup, and the algorithmic applications that use walks as a black box. It assumes familiarity with unitary evolution, local Hamiltonians, and Grover-type search circuits.

Classical random walks on graphs — the baseline

A graph G = (V, E) has a set of vertices V and a set of edges E where each edge is a pair of vertices. The adjacency matrix A is a |V| \times |V| matrix with A_{ij} = 1 if there is an edge between vertex i and vertex j, and A_{ij} = 0 otherwise. It is a symmetric real matrix.

A classical random walk starts at some vertex v_0 and at each time step moves to a uniformly-random neighbour. The state of the walker at time t is a probability distribution p_t over vertices: p_t(v) is the probability that the walker is at vertex v at time t. The update rule is

p_{t+1}(v) = \sum_{u \text{ adjacent to } v} \frac{1}{\deg(u)} \, p_t(u).

Why: you are at vertex u with probability p_t(u), and you move to each of u's \deg(u) neighbours with equal probability 1/\deg(u). Summing over all u adjacent to v gives the probability of being at v next step. This is the discrete-time version; a continuous-time version replaces the discrete step with an exponentially-distributed waiting time per edge and uses the graph Laplacian L = D - A where D is the diagonal degree matrix.

On an infinite line graph, starting from v_0 = 0, a straightforward calculation gives the distribution at time t as approximately a Gaussian with mean 0 and variance t. The typical distance from the origin is \sqrt{t}. This is the central-limit-theorem result for a sum of t independent \pm 1 steps.

On any graph satisfying mild connectivity, the classical walk has a unique stationary distribution \pi (for a random walk on a d-regular graph, \pi is uniform over vertices), and the walk converges to \pi at a rate controlled by the spectral gap of the graph — the difference between the largest and second-largest eigenvalues of the transition matrix. Good expander graphs have constant gap and rapid mixing.

Quantum walk: the Hamiltonian and the evolution

To build the quantum version, assign each vertex v \in V a basis state |v\rangle. The total Hilbert space has dimension |V|, with orthonormal basis \{|v\rangle : v \in V\}. A general quantum state on the graph is a superposition

|\psi\rangle = \sum_{v \in V} \alpha_v |v\rangle, \qquad \sum_v |\alpha_v|^2 = 1.

The amplitude \alpha_v is a complex number; |\alpha_v|^2 is the probability of finding the walker at vertex v upon measurement.

Now for the key definition. Take the adjacency matrix A and use it directly as the Hamiltonian of the quantum system:

H = -\gamma A

for some positive constant \gamma (often absorbed into the time scale). The state evolves under the Schrödinger equation

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

Setting \hbar = 1 and \gamma = 1 for cleanliness:

|\psi(t)\rangle = e^{i A t} |\psi(0)\rangle.

That is it. That is the continuous-time quantum walk. Use the adjacency matrix as the Hamiltonian; evolve the wavefunction; you have a quantum walk.

Why this is "walk-like": each matrix element A_{ij} of the Hamiltonian connects basis states |i\rangle and |j\rangle. The Schrödinger evolution, expanded to first order, gives |\psi(dt)\rangle \approx (1 + i A \, dt)|\psi(0)\rangle. Applying this to |v\rangle produces |v\rangle + i \, dt \sum_{u \text{ adjacent to } v} |u\rangle — amplitude leaks onto each neighbour. Over time these amplitudes interfere. Because the interference is coherent, peaks can reinforce and troughs can cancel. This is absent in classical walks, which add probabilities rather than amplitudes.

Classical vs quantum walk on a lineTwo panels showing probability versus position on a line graph. Left panel is classical diffusion with a bell curve of width root t. Right panel is the quantum walk with two sharp peaks at position plus and minus t and an oscillating pattern in between. The visual contrast emphasises that classical walks spread to root t while quantum walks spread to t. Probability distribution after time t Classical walk: Gaussian, width √t position 0 −√t +√t P(x) Quantum walk: ballistic, edges at ±t position 0 −t +t |ψ|²
The signature contrast. A classical random walk on an infinite line, starting at $0$, produces after $t$ steps a Gaussian probability distribution of width $\sqrt{t}$. A continuous-time quantum walk on the same line, starting at $|0\rangle$ and evolved for time $t$, produces a probability distribution peaked at $\pm t$ with interference fringes in between — a width of order $t$. The quadratic speedup in spread is the simplest instance of a quantum advantage from interference.

The line graph in detail — solving it exactly

The line graph \mathbb{Z} with integer vertices \ldots, -2, -1, 0, 1, 2, \ldots and an edge between every consecutive pair has an adjacency matrix that is tridiagonal:

A_{ij} = \begin{cases} 1 & \text{if } |i - j| = 1 \\ 0 & \text{otherwise}. \end{cases}

This matrix's eigenstates are easy — they are plane waves |k\rangle = \sum_n e^{i k n} |n\rangle for k \in (-\pi, \pi]. Acting with A:

A |k\rangle = \sum_n e^{ikn} (|n+1\rangle + |n-1\rangle) = \sum_n (e^{ik(n-1)} + e^{ik(n+1)}) |n\rangle = 2\cos(k) |k\rangle.

Why this works: plane waves diagonalise translation-invariant operators. The line graph is translation-invariant (every vertex looks identical), and the adjacency matrix commutes with translation, so it must be diagonal in the Fourier basis. The eigenvalue is 2\cos(k) — twice the cosine of the wavenumber. This is the familiar one-dimensional tight-binding dispersion.

Evolution of a wavefunction starting at |0\rangle is straightforward in this basis. Decompose |0\rangle = \frac{1}{2\pi} \int_{-\pi}^{\pi} dk \, |k\rangle. Then

|\psi(t)\rangle = e^{iAt} |0\rangle = \frac{1}{2\pi} \int_{-\pi}^{\pi} dk \, e^{i \, 2\cos(k) \, t} |k\rangle.

The amplitude at position n is

\langle n | \psi(t) \rangle = \frac{1}{2\pi} \int_{-\pi}^{\pi} dk \, e^{-i k n + i \, 2\cos(k) \, t} = J_n(2t) \cdot i^n,

where J_n is the Bessel function of the first kind of integer order n. The probability of finding the walker at position n at time t is |J_n(2t)|^2.

The Bessel function J_n(x) is negligible for n > x and oscillates for n < x. So the probability distribution |J_n(2t)|^2 is essentially zero for |n| > 2t, concentrated at the edges n \approx \pm 2t, and oscillatory in between. The walker's wavefunction is, in effect, a front that propagates at speed 2 (from each edge), and the bulk fills in with interference fringes. Mean distance from origin: \sim 2t. Standard deviation of position: \sim t. This is the ballistic spread — linear in time.

The classical walk on the same graph, recall, has position distribution approximately Gaussian with standard deviation \sqrt{t}. So the quantum walk spreads quadratically faster. Whether this quadratic gain gives you an algorithmic speedup depends on the problem — for simple "spread from origin" it is interesting but not particularly useful; for search problems set up cleverly, it translates to the quadratic speedup of Grover-type search.

The glued trees — where the exponential speedup lives

In 2003, Andrew Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel Spielman proved something more startling. They constructed a graph — "glued trees" — on which a quantum walk reaches a specified target vertex in polynomial time, while any classical algorithm (random walk or otherwise) requires exponential time. The result is the cleanest proven exponential quantum speedup that does not rely on number-theoretic structure like Shor's algorithm.

Building the graph

Take two binary trees of depth n. The first tree has root s (the "start"); the second has root t (the "target"). Each tree has 2^n leaves at the bottom level. Now glue the leaves of the first tree to the leaves of the second tree via a random perfect matching — i.e., pair up the leaves one-to-one in a random way and put an edge across each pair.

The resulting graph has 2 \cdot (2^{n+1} - 1) = O(2^n) vertices, two distinguished vertices s and t, and is bipartite-ish in structure. The task is: start at s, reach t.

The glued-trees graphTwo binary trees, drawn mirrored. The left tree has root labelled s at top and fans down to leaves in the middle. The right tree has root labelled t on the far right and fans inward to leaves in the middle. A random matching of edges connects left-tree leaves to right-tree leaves. The graph has polynomial depth from s to t, but exponentially many vertices. Glued trees: polynomial depth, exponential classical bottleneck s t random matching between leaves — the only path across is polynomial depth, but exponentially wide
The glued-trees graph. Two binary trees of depth $n$, mirrored and joined by a random matching between their leaves. The total number of vertices is $O(2^n)$; the graph-distance from $s$ to $t$ is $2n + 1$ — polynomial. A quantum walk starting at $s$ reaches $t$ with constant probability in time $\text{poly}(n)$. A classical random walk gets lost in the combinatorial middle layer and requires time $\Omega(2^n)$ — exponential.

Why the quantum walk wins

Here is the intuition. A classical random walker moving through the left tree flows inward toward the leaves and then hits the random matching. From any leaf in the middle, the next step is equally likely to stay in the middle layer (by going to another matched leaf) or to move back into one of the two trees. The walker has no way to tell which side of the matching it is on; it gets stuck wandering the exponentially many leaves, with probability 1/2^n of reaching the root t of the target tree in any given attempt. Time to hit t: \Omega(2^n).

The quantum walk, by contrast, respects the graph's symmetries. Because the graph is constructed to look the same from s and t (both are tree roots), the walk's evolution preserves a symmetric subspace in which vertices at the same "column" (same graph-distance from s) are summed. The Hilbert space of the walk reduces to a walk on a line of length 2n + 1 — one basis state per column. And on a line of length L, the quantum walk reaches the far end in time \Theta(L) — polynomial. So the quantum walk on glued trees effectively becomes a quantum walk on a line of length 2n+1, and it traverses it in O(n) time.

Why the symmetric subspace is preserved: the walk's Hamiltonian is the adjacency matrix of the graph. The adjacency matrix commutes with permutations of vertices that preserve the graph structure. The starting state |s\rangle is fixed by every permutation that fixes s as a labelled vertex. The orbit of |s\rangle under the symmetric-group action is the column states (uniform superpositions over vertices in each column), so the evolution stays in the span of these — a (2n+1)-dimensional subspace. The reduced Hamiltonian on this subspace is itself the adjacency matrix of a line-like graph. The exponential speedup is essentially that classical random walks do not inherit this symmetry because they lack quantum coherence across permuted vertices.

The formal theorem: any classical algorithm that queries the graph (asks which vertices are neighbours of which) needs \Omega(2^{n/6}) queries to find t given only s. The quantum walk finds t in \text{poly}(n) time with constant probability.

This is an oracle-model separation — it assumes the graph is given only through a local neighbourhood query — but it is a provable exponential separation, which is rare. Childs et al. 2003 remains a foundational result.

Discrete-time quantum walks — a brief preview

Everything above is about continuous-time quantum walks: a wavefunction evolving under the Hamiltonian H = -\gamma A for real-valued time t. There is also a discrete-time quantum walk, which is slightly more common in algorithmic applications because it is cleaner to implement as a gate-model circuit.

In a discrete-time walk, the state lives in a larger Hilbert space |\text{vertex}\rangle \otimes |\text{coin}\rangle, where the coin is an extra quantum register specifying "which direction the walker just came from." At each step you apply a coin operator (a unitary on the coin register, e.g. a Hadamard) and then a shift operator that moves the vertex pointer by one edge in the direction indicated by the coin. The composite operator is one discrete-time step; iterating it T times gives a walk of depth T.

Mario Szegedy in 2004 showed that for any classical Markov chain, you can define a Szegedy walk whose quadratic speedup on the mixing time translates to quadratic speedup on hitting-time-based search. The Szegedy walk works on the "bipartite double cover" of the graph; this construction is the basis of the MNRS framework (Magniez-Nayak-Roland-Santha 2007) for walk-based search.

You can read more in the Szegedy walk chapter (forthcoming). The connection to continuous-time walks is: for many graph classes, the continuous and discrete walks produce similar speedups, and the choice between them is one of convenience.

Algorithmic applications — walks as a primitive

Quantum walks became important not just as a curiosity but as a primitive — a black-box tool you plug into bigger algorithms.

Element distinctness (Ambainis 2003). Given a list of N elements, are any two of them equal? Classical complexity: \Theta(N) queries. Quantum: \Theta(N^{2/3}) queries — a polynomial speedup. Ambainis's algorithm is a discrete-time quantum walk on the Johnson graph J(N, r) (vertices are r-subsets of a size-N universe), searching for a subset containing a collision. This was the first result that established quantum walks as a general algorithmic tool.

Triangle finding (Magniez-Santha-Szegedy 2005, Magniez-Nayak-Roland-Santha 2007). Given an n-vertex graph, does it contain a triangle? Classical: \Omega(n^2) queries. Quantum walk-based: O(n^{13/10}) queries (MSS); later improvements to O(n^{5/4}) and below. The improvements continue to be active research.

MNRS framework (2007). Magniez, Nayak, Roland, and Santha gave a general recipe: for a problem reducible to "walk on graph G searching for marked vertices," the quantum walk-based algorithm runs in O(S + \frac{1}{\sqrt{\epsilon}}(\frac{1}{\sqrt{\delta}} U + C)) queries, where S is the setup cost, U is the update cost per walk step, C is the check cost, \delta is the spectral gap of the walk, and \epsilon is the fraction of marked vertices. This framework subsumes Ambainis's element-distinctness and Grover's search as special cases; it is the standard tool for designing walk-based quantum algorithms.

Boson sampling (Aaronson-Arkhipov 2011) and quantum walks of photons — related ideas, though formally distinct. Continuous-time quantum walks of photons on a network of beam-splitters and phase shifters have been experimentally demonstrated at small scale.

Graph problems more broadly. Spatial search on various graph families (Childs-Goldstone 2004, Ambainis-Kempe-Rivosh 2005): for a random vertex marked as "target" in a graph, quantum walks achieve O(\sqrt{N}) search time on graphs with sufficient structure (complete graphs, hypercubes, the 2D grid for n \ge 5 dimensions), matching Grover. On some graphs quantum walks beat naive Grover search by exploiting structure.

This algorithmic usage is why walks are treated as a fundamental primitive. You rarely see "quantum walk" in a headline; you see them inside other algorithms as the engine.

The Indian context

There is a direct Indian connection to the quantum-walks literature that is worth naming. Ashwin Nayak (Indian-origin, IIT Kanpur and subsequent academic career) is the "N" in MNRS — a co-author of the 2007 MNRS framework that unified walk-based quantum search. The MNRS paper is genuinely one of the most important unifying results in quantum-algorithms theory, and it is a paper with real Indian-diaspora contribution. It is not a decoration to mention this; Nayak's work on quantum walks, quantum communication complexity, and quantum information more broadly is cited throughout the quantum-algorithms literature.

The Institute of Mathematical Sciences (IMSc) in Chennai, TIFR Mumbai, and IISc Bangalore all host researchers working on quantum walks and graph-based quantum algorithms. Walk-based spatial-search analyses and connections to quantum complexity theory appear regularly in Indian PhD theses and workshop proceedings.

The National Quantum Mission does not explicitly single out walks as a separate thrust — walks sit inside the "quantum algorithms" research agenda — but the algorithmic-primitives side of NQM's software portfolio includes walk-based methods as one of the standard tools.

Example 1: Quantum walk on a 3-vertex line

Run a continuous-time quantum walk on a line graph of 3 vertices \{0, 1, 2\} with edges \{(0,1), (1,2)\}, starting at vertex 0.

Step 1. Write the adjacency matrix.

A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}.

The Hamiltonian is H = -A (using \gamma = 1).

Step 2. Diagonalise. The eigenvalues of A are \{-\sqrt 2, 0, +\sqrt 2\} with corresponding eigenvectors

|v_{+}\rangle = \tfrac{1}{2}|0\rangle + \tfrac{1}{\sqrt 2}|1\rangle + \tfrac{1}{2}|2\rangle, \quad |v_{0}\rangle = \tfrac{1}{\sqrt 2}(|0\rangle - |2\rangle), \quad |v_{-}\rangle = \tfrac{1}{2}|0\rangle - \tfrac{1}{\sqrt 2}|1\rangle + \tfrac{1}{2}|2\rangle.

Why these work: a 3 \times 3 tridiagonal matrix with 1's off-diagonal has a clean closed-form spectrum. The eigenvectors are discrete sine functions v_j(n) = \sin(\pi (n+1)(j+1)/4) for n, j \in \{0, 1, 2\}, normalised. The outer entries of each vector have the same magnitude by left-right symmetry.

Step 3. Decompose the initial state into eigenvectors.

|0\rangle = \tfrac{1}{2}|v_+\rangle + \tfrac{1}{\sqrt 2}|v_0\rangle + \tfrac{1}{2}|v_-\rangle.

(Check: \langle v_+|0\rangle = \tfrac{1}{2}, \langle v_0|0\rangle = \tfrac{1}{\sqrt 2}, \langle v_-|0\rangle = \tfrac{1}{2}, and \tfrac14 + \tfrac12 + \tfrac14 = 1.)

Step 4. Evolve. Multiply each eigenvector component by e^{iEt} where E is its eigenvalue (using H = -A, eigenvalues of H are the negatives of those of A):

|\psi(t)\rangle = \tfrac{1}{2} e^{-i\sqrt 2 t}|v_+\rangle + \tfrac{1}{\sqrt 2}|v_0\rangle + \tfrac{1}{2} e^{+i\sqrt 2 t}|v_-\rangle.

Step 5. Compute the probability at vertex 2 as a function of time.

\langle 2 | \psi(t) \rangle = \tfrac{1}{2}\cdot\tfrac{1}{2} e^{-i\sqrt 2 t} + \tfrac{1}{\sqrt 2} \cdot (-\tfrac{1}{\sqrt 2}) + \tfrac{1}{2}\cdot\tfrac{1}{2} e^{+i\sqrt 2 t} = \tfrac{1}{2}\cos(\sqrt 2 t) - \tfrac{1}{2}.

So the probability is

P(2, t) = \left|\tfrac{1}{2}\cos(\sqrt 2 t) - \tfrac{1}{2}\right|^2 = \tfrac{1}{4}(1 - \cos(\sqrt 2 t))^2.

This oscillates between 0 (when \cos(\sqrt 2 t) = 1, i.e. t = 0, \pi\sqrt 2, 2\pi\sqrt 2, \ldots) and 1 (when \cos(\sqrt 2 t) = -1, i.e. t = \pi/\sqrt 2, 3\pi/\sqrt 2, \ldots).

Result. At t = \pi/\sqrt 2 \approx 2.22, the walker is with certainty at vertex 2 — it has completely transferred from vertex 0 to vertex 2 in finite time. This is perfect state transfer, a purely quantum phenomenon with no classical analogue: a classical random walk on this graph has stationary distribution (\tfrac14, \tfrac12, \tfrac14) and never puts more than 1/2 probability on any single vertex. The quantum walk, by contrast, routes amplitude from vertex 0 to vertex 2 constructively, at a specific time, with probability 1.

What this shows. Interference between eigenstates is the source of quantum-walk magic. The three eigenstates evolve with different phases; at specific times these phases combine to concentrate amplitude on the target vertex and cancel amplitude on others. The classical walker has no amplitudes to cancel — it can only average, and averaging cannot concentrate probability at will.

Example 2: The glued-trees speedup, intuition via column-reduction

This is less a numerical calculation than an argument — the full Childs-Cleve-Deotto-Farhi-Gutmann-Spielman proof fills a paper. But the key structural step is tractable.

Step 1. The graph. Glued-trees graph of depth n = 5: two binary trees of depth 5, each with 2^5 = 32 leaves, glued at the leaves by a random matching. Total vertices: 2 \times (2^6 - 1) = 126. Graph distance from root s to root t: 11 edges.

Step 2. The classical walk. Classical random walk starting at s. The walker descends the first tree in time O(n), arriving at a random leaf. From there, the walker is at a "left leaf" connected by matching to a "right leaf"; the next step is with probability \tfrac{1}{3} back into the left tree and with probability \tfrac{1}{3} to each of two matching options on the right (approximately, depending on the degree structure; the numbers shift slightly in the bulk). The walker is stuck in the combinatorial middle for time exponential in n: typical hitting time to t is \Omega(2^n) = \Omega(32). Why exponential: from any leaf in the middle, the walker has equal probability to return to its own tree or to cross to the other. It is doing a random walk on the bipartite "leaf graph," and hitting the root t requires first reaching one specific leaf of the right tree (out of 2^n) and then climbing — a needle-in-haystack problem with coverage time \Omega(2^n).

Step 3. The quantum walk — column states. Define column states

|\text{col}_j\rangle = \frac{1}{\sqrt{N_j}} \sum_{v \text{ at graph-distance } j \text{ from } s} |v\rangle

for j = 0, 1, \ldots, 2n+1, where N_j is the number of vertices at that distance. The column states form an orthonormal basis of an (2n+2)-dimensional subspace. The starting state |s\rangle = |\text{col}_0\rangle lies in this subspace.

Step 4. The walk preserves the subspace. The adjacency matrix A acts on a column state by sending each vertex to its neighbours. A vertex at column j has neighbours only in columns j-1 and j+1. Because the graph's symmetry makes the restriction of A to the column-state subspace act as a tridiagonal matrix on 2n+2 column states, the walk reduces to an effective walk on a line of length 2n+2.

Step 5. The effective line walk. Quantum walks on lines of length L propagate ballistically — in time \Theta(L) a wavepacket starting at one end reaches the other end with constant probability. So for L = 2n+2, the quantum walk reaches column 2n+1 (the target) in time O(n). Measuring at this time yields, with some probability, the target vertex t or one of its column-neighbours. Repeat O(1) times to boost the success probability to close to 1.

Result. Quantum walk hitting time from s to t: O(n). Classical walk hitting time: \Omega(2^n). For n = 5: quantum walk takes around 10 time units; classical walk takes around 32 time units (or more, depending on the precise model). For n = 40: quantum takes \sim 80; classical takes \sim 10^{12} — an astronomical gap. As n grows, the separation is exponential.

What this shows. The quantum walk's exponential speedup on glued trees comes from two ingredients: graph symmetry (which reduces the effective Hilbert space to a polynomial-dimensional subspace) and ballistic spread (which gets you across that reduced line quickly). Without the symmetry, you would not collapse the exponential vertex count to a polynomial column count. Without the ballistic spread, you would not traverse the reduced line quickly. Both ingredients are coherent-quantum-mechanical. Neither has a classical analogue.

Common confusions

Going deeper

If you understand that a continuous-time quantum walk is Schrödinger evolution under the graph's adjacency matrix as Hamiltonian, that classical walks spread diffusively (\sqrt{t}) while quantum walks spread ballistically (t) on the line, that glued-trees gives a provable exponential quantum-over-classical speedup (Childs-Cleve-Deotto-Farhi-Gutmann-Spielman 2003), that Szegedy walks are the discrete-time analogue and MNRS (Magniez-Nayak-Roland-Santha 2007) is the general search framework, and that walks are a primitive used in element-distinctness and triangle-finding — you have chapter 182. What follows is the rigorous version: Szegedy's mapping, spectral-gap analysis, Childs's 2009 universality result, the amplitude-amplification connection, and the current state of walk-based algorithms.

Szegedy walks and the quantum-classical mapping

Mario Szegedy's 2004 construction gives, for every classical Markov chain with transition matrix P, a discrete-time quantum walk U_P on an enlarged Hilbert space whose eigenvalues are \pm e^{\pm i \theta} with \cos\theta = \sigma and \sigma an eigenvalue of a related matrix \sqrt{P P^T}. The walk's phase gap is quadratic in the classical chain's spectral gap: \text{gap}(U_P) \approx \sqrt{\text{gap}(P)}. This is the source of quadratic mixing-time speedups.

Szegedy's construction lives naturally on the bipartite double cover of the graph — you have two copies of the vertex set and edges only between copies. The walk alternates two reflection operators, one on each copy. The composed operator is the walk.

Childs 2009: universal computation from continuous-time quantum walks

Andrew Childs showed in 2009 that any quantum computation can be reduced to a continuous-time quantum walk on a graph of polynomial size. This establishes CTQW as a universal quantum computational model — much like the adiabatic model and the gate model. The construction encodes the circuit into the graph structure; the walk simulates the circuit. As a computational model it is equivalent to BQP.

The amplitude-amplification connection

Walk-based search algorithms frequently combine walks with amplitude amplification (the generalisation of Grover's search; see amplitude amplification). The walk prepares a superposition spread over the graph; amplitude amplification then boosts the weight on marked vertices. The MNRS framework is essentially a disciplined way of combining a quantum walk (for mixing) with amplitude amplification (for marking).

Hitting times, commute times, and conductance

Classical random-walk analysis provides a rich toolkit — hitting time, commute time, cover time, conductance — tied to the graph's spectral properties. Quantum walks inherit analogous quantities with quadratic-speedup relationships in many cases. The quantum hitting time from s to t is bounded by \sqrt{\text{classical hitting time}} times polylog factors for many graphs. The precise statements involve the phase gap of the walk and structural properties of the marked-vertex set.

Current algorithmic frontier

As of the mid-2020s, quantum-walk research continues on several fronts:

The unifying QSVT framework treats all three pillars — Fourier transform, amplitude amplification, quantum walks — as polynomial transformations of singular values of a block-encoded matrix. It is the most elegant modern formulation of the algorithmic toolkit.

The Ashwin Nayak connection, in more depth

Ashwin Nayak (currently at University of Waterloo; Indian-origin, undergraduate at IIT Kanpur) is a co-author of the MNRS paper and has contributed foundational results in quantum-walk theory, quantum communication complexity, and quantum information theory more broadly. His work on bit commitment protocols, on quantum query complexity, and on walk-based search is cited throughout the quantum-algorithms literature. Students in India interested in quantum-algorithms theory routinely read his papers and lecture notes — they are standard references.

Where this leads next

References

  1. Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman, Exponential algorithmic speedup by quantum walk (2003), STOC — arXiv:quant-ph/0209131. The glued-trees paper.
  2. Andris Ambainis, Quantum walk algorithm for element distinctness (2003) — arXiv:quant-ph/0311001. First walk-based algorithmic speedup beyond Grover.
  3. Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha, Search via quantum walk (2007), SIAM J. Comp. — arXiv:quant-ph/0608026. The MNRS framework.
  4. Andrew M. Childs, Universal computation by quantum walk (2009) — arXiv:0806.1972. Walks as a universal quantum model.
  5. Salvador Elías Venegas-Andraca, Quantum walks: a comprehensive review (2012), Quantum Information Processing — arXiv:1201.4780.
  6. Wikipedia, Quantum walk.