Discrete Quantum Walks

Here is a question a 15-year-old with a carrom board can ask. A striker is sitting in the middle of the board. You flick it in a random direction. It bounces around, losing a little energy with each bounce, and eventually settles. How long until it forgets where it started?

This is the mixing time of a random walk — the time until the position distribution is close to the stationary one. On a d-regular graph of N vertices, the classical mixing time is of order 1/\text{gap}(P), where \text{gap}(P) = 1 - \lambda_2 is the spectral gap of the transition matrix. Good expander graphs have constant gap, so they mix in time O(\log N). Bad graphs (the cycle C_N, the 2D grid) have tiny gaps and mix slowly.

Quantum walks do better. The quadratic speedup on mixing time — the square root of the classical number — is one of the oldest and most reliably useful quantum speedups in the book. But to get it, you cannot use the continuous-time walk directly; you need a discrete version that can be written as a sequence of unitary gates on a quantum circuit. This chapter is about that discrete version.

You saw continuous-time quantum walks in the previous chapter: take the graph's adjacency matrix A, use it as a Hamiltonian, evolve the wavefunction. Elegant, but hard to compile into a circuit — "evolve for time t" is not a gate. Discrete quantum walks do the same thing with a pair of unitaries you can actually implement. They also give you Grover's algorithm for free as a special case on the complete graph — a fact that reshapes how you think about both Grover and walks.

The coin-and-shift model — the two-register state space

A classical random walker on a graph has only one piece of state: which vertex it is at. A discrete quantum walker needs two. Here is why.

If you try to define a "quantum walk" by simply making the walker a superposition over vertices and at each step replacing it with a uniform superposition over its neighbours, you quickly hit a wall. The operation is not unitary. Two different starting vertices that happen to share a neighbour end up sending amplitude to the same place, and there is no way to invert the operation — information has been lost. A unitary operator must be reversible, and a step that merges distinct starting vertices is not.

The fix is to remember where the walker came from. Introduce a coin register alongside the vertex register. The coin state encodes the direction the walker is heading. A d-regular graph (every vertex has exactly d neighbours) needs a coin with d states: one for each direction. On the infinite line, d = 2 and the coin is a single qubit — "left" or "right."

The total Hilbert space is

where \mathcal{H}_V has basis \{|v\rangle : v \in V\} and \mathcal{H}_C has basis \{|c\rangle : c = 1, \ldots, d\}. A basis state |v\rangle|c\rangle says: "the walker is at vertex v, heading in direction c." A general state is a superposition of these.

Why the coin register rescues unitarity: with both vertex and coin in the state, the composite operator acts bijectively on the basis. A vertex-plus-direction pair (v, c) maps to a unique neighbour vertex v', and a unique updated direction c' that records "I just arrived along this edge." No two starting (v, c) pairs land on the same (v', c'). That reversibility is what makes the operator unitary.

The coin operator

The coin operator C is any unitary on the coin register. It decides — quantum-mechanically — which direction the walker should take next. The most common choices:

• Hadamard coin (d = 2): C = H, turning |0\rangle \to \tfrac{1}{\sqrt 2}(|0\rangle + |1\rangle), |1\rangle \to \tfrac{1}{\sqrt 2}(|0\rangle - |1\rangle). This is the walk people mean when they say "Hadamard walk on the line."
• Grover coin (d \ge 2): C = 2|s_d\rangle\langle s_d| - I where |s_d\rangle = \tfrac{1}{\sqrt d}\sum_c |c\rangle is the uniform superposition. This is a reflection about the uniform coin state and is the most common choice for general d-regular graphs.
• Discrete Fourier coin (d \ge 2): C = F, the d-dimensional discrete Fourier transform. Useful when the graph has cyclic symmetry.

Applied to the whole space, the coin operator is I_V \otimes C — it acts on the coin register and leaves the vertex register alone. It is what injects "quantum coinness" into the walk: instead of classical probabilities for "left" or "right," the coin register now holds complex amplitudes, and those amplitudes can interfere in subsequent steps.

The shift operator

The shift operator S moves the walker one edge, in the direction the coin currently points. For a d-regular graph with a labelling of the edges at each vertex (each edge gets a direction-number c \in \{1, \ldots, d\}), the shift acts as

where v' is the vertex reached from v along direction c, and c' is the direction back toward v from v' (i.e. the label of the same edge, seen from the other endpoint). This "flip" of the coin direction during shift is what preserves unitarity and is sometimes called the flip-flop convention.

On the infinite line, with coin |0\rangle = "right" and |1\rangle = "left":

The coin flips on each step because after the walker has moved from n to n+1, the "direction back to n" from n+1 is "left," not "right."

One step of the walk

One step of the discrete-time quantum walk is the composition

Apply the coin first, then the shift. Iterating T times produces U^T — a T-step walk.

You iterate this to watch the walk spread. On the infinite line with a Hadamard coin and an initial coin state of \tfrac{1}{\sqrt 2}(|0\rangle + i|1\rangle) (a symmetric starting condition), the walker's probability distribution after T steps is not a Gaussian of width \sqrt T — it is a roughly uniform distribution between \pm T/\sqrt 2, with two sharp peaks at the edges. Ballistic spread, just like the continuous-time walk, but with slightly different constants.

A two-step example on the line

Walk through two steps explicitly on the line, starting at n = 0 with coin |0\rangle.

Initial state. |\psi_0\rangle = |0\rangle |0\rangle.

After coin (step 1). (I \otimes H)|0\rangle|0\rangle = |0\rangle \cdot \tfrac{1}{\sqrt 2}(|0\rangle + |1\rangle) = \tfrac{1}{\sqrt 2}(|0\rangle|0\rangle + |0\rangle|1\rangle).

After shift (step 1). S sends |0\rangle|0\rangle \to |1\rangle|1\rangle (move right, flip coin) and |0\rangle|1\rangle \to |{-1}\rangle|0\rangle (move left, flip coin). So

After coin (step 2). Apply I \otimes H to each term. H|1\rangle = \tfrac{1}{\sqrt 2}(|0\rangle - |1\rangle); H|0\rangle = \tfrac{1}{\sqrt 2}(|0\rangle + |1\rangle). So

After shift (step 2). Apply S to each of the four terms:

Why this is already interesting: the amplitude at |0\rangle|0\rangle is -\tfrac{1}{2} and at |0\rangle|1\rangle is +\tfrac{1}{2}. If you trace out the coin (sum probabilities over coin states), the probability of being at vertex 0 is \tfrac{1}{4} + \tfrac{1}{4} = \tfrac{1}{2}. The probability of being at \pm 2 is \tfrac{1}{4} each. Compare to the classical walk: after 2 steps, the probability of being at 0 is \tfrac{1}{2} (either left-right or right-left), at \pm 2 is \tfrac{1}{4} each. At T = 2 the distributions happen to coincide — but they will diverge sharply by T = 4, with the quantum walker developing side peaks the classical walker cannot.

The point is not that the numbers differ at step 2. The point is that the next application of (I \otimes H) will cause the amplitudes at |0\rangle|0\rangle and |0\rangle|1\rangle to interfere. The minus sign on the |0\rangle|0\rangle amplitude matters: when H mixes the coin states, the -\tfrac{1}{2} cancels against parts of the +\tfrac{1}{2}, shifting amplitude away from vertex 0 and toward the edges. By step T = 10 or so, the quantum walk has two sharp peaks near \pm T/\sqrt 2 with a flat interior — the signature ballistic spread, driven entirely by the accumulation of signed amplitudes.

Szegedy walks — lifting a Markov chain to a quantum walk

The coin-and-shift model works beautifully for regular graphs, but many natural problems come with Markov chains (random walks with possibly non-uniform transition probabilities) that are not regular. In 2004, Mario Szegedy gave a construction that takes any reversible Markov chain and produces a discrete quantum walk with a provable quadratic mixing-time speedup.

Here is the construction. Start with a reversible Markov chain on vertex set V with transition matrix P — so P_{uv} is the probability of moving from u to v in one step, and \pi is the unique stationary distribution satisfying \pi_u P_{uv} = \pi_v P_{vu} (the reversibility condition).

Step 1: the bipartite double cover. Make two copies of V, call them V_L (left) and V_R (right). The Hilbert space is \mathcal{H} = \mathbb{C}^{V_L} \otimes \mathbb{C}^{V_R}, with basis \{|u\rangle_L |v\rangle_R\}. This is the "which edge am I on, and which direction am I heading" register, but expressed more symmetrically than in the coin-and-shift model.

Step 2: the Szegedy states. For each vertex u \in V_L, define

This is a superposition, on the right register, weighted by the square-root of the transition probability from u. For each vertex v \in V_R, define symmetrically

where P^*_{vu} = \pi_u P_{uv} / \pi_v is the reverse-chain transition probability (equal to P_{vu} when P is reversible).

Step 3: the two reflections. Define the projectors onto the spans of these states:

The Szegedy walk operator is

Two reflections, composed. Exactly the pattern you have seen in Grover's algorithm and in amplitude amplification.

Step 4: the phase gap. Szegedy's theorem: the eigenvalues of W on the relevant subspace are e^{\pm i \theta_k}, where \cos\theta_k = \sigma_k and \sigma_k are the singular values of a certain matrix D with entries D_{uv} = \sqrt{P_{uv} P^*_{vu}}. The largest singular value is \sigma_1 = 1 (corresponding to the stationary distribution), and the second-largest is \sigma_2 = 1 - \Delta where \Delta = \text{gap}(P) is the classical spectral gap. So the phase gap of W — the angle separating the +1 eigenspace from the rest — is

The phase gap is the square root of the classical gap. Mixing time scales inversely with gap; so the quantum mixing time is O(1/\sqrt{\Delta}) compared to classical O(1/\Delta). That is the quadratic speedup.

Why the square-root appears: W is a product of two reflections R_A = 2\Pi_A - I and R_B = 2\Pi_B - I. The composition of two reflections is a rotation. On the 2D invariant subspace spanned by |\phi_u\rangle and a corresponding |\psi_v\rangle, W acts as a rotation by 2\theta_k where \cos\theta_k is the overlap \langle\phi_u|\psi_v\rangle. Those overlaps turn out to equal the singular values of a certain normalised transition matrix, which in turn equal 1 - \Delta and smaller. Taking \arccos of something near 1 gives \sqrt 2 \sqrt{1 - (1-\Delta)} = \sqrt{2\Delta} — the square root of the gap. This is the same phenomenon that turns Grover's 1/N probability into \pi/4 \sqrt N iterations.

Continuous versus discrete — a side-by-side

You have now seen two flavours of quantum walk.

For most graph-theoretic purposes they give comparable asymptotic speedups, and there are explicit mappings between them (Childs 2010). Practical quantum algorithm designers usually reach for the discrete-time version because it compiles straight into a circuit — no "simulate a Hamiltonian" step needed. The continuous-time version is the cleaner theoretical object for spectral analysis and for the glued-trees exponential speedup you saw in the previous chapter.

Grover's algorithm is a discrete quantum walk

Here is a surprise that reshapes how you should think about Grover. The complete graph K_N has N vertices and an edge between every pair, so every vertex has N - 1 neighbours. Consider a discrete quantum walk on K_N with Grover coin C = 2|s\rangle\langle s| - I (where |s\rangle is the uniform superposition over directions), and a single vertex w "marked" by perturbing the coin at w to -I instead of 2|s\rangle\langle s| - I.

Work out the walk operator. On every unmarked vertex, applying C and then S turns out — after some algebra — to be equivalent to the Grover diffusion operator D = 2|s\rangle\langle s| - I on the vertex register. The perturbed coin at w implements the phase oracle O = I - 2|w\rangle\langle w|. So one step of the walk is exactly one Grover iteration: U_\text{walk} \propto D \cdot O.

Grover's algorithm is a discrete quantum walk on the complete graph with one marked vertex. The walk's phase gap is \Theta(1/\sqrt N), and after O(\sqrt N) steps the walker is concentrated at the marked vertex. This is the exact O(\sqrt N) Grover runtime, rederived from the walk framework. Grover is not a separate algorithm — it is the simplest walk-based search, on the simplest graph (everything connected to everything), with the simplest marking rule (one target vertex).

Why this reframing matters: if Grover is a walk on K_N with one marked vertex, then walks on other graphs correspond to other search problems. The MNRS framework (chapter preview below) takes this seriously: given a Markov chain on any graph and any marked-vertex set, the walk-based algorithm runs in O(S + \tfrac{1}{\sqrt{\varepsilon}}(\tfrac{1}{\sqrt{\Delta}} U + C)) queries, where \varepsilon is the fraction of marked vertices, \Delta is the spectral gap, and S, U, C are setup, update, and check costs. Grover is \varepsilon = 1/N, \Delta = 1 (the complete graph is maximally well-connected) — giving O(\sqrt N). Element distinctness (next chapter) is \varepsilon comparable to 1/N^{r} and \Delta \sim 1/r — giving O(N^{2/3}) after optimising r.

The Indian connection

The walk-based framework has real Indian-diaspora authorship. Ashwin Nayak (IIT Kanpur undergraduate, later at University of Waterloo) is the "N" in the MNRS framework — the 2007 paper that unified walk-based quantum search with Markov chains. The MNRS paper is one of the most cited results in quantum algorithms and sits at the centre of this chapter's intellectual tradition. Nayak's work on quantum communication complexity and query lower bounds is also frequently cited in Indian quantum-algorithms curricula.

The Institute of Mathematical Sciences (IMSc) Chennai, TIFR Mumbai, IISc Bangalore, and IIT Madras all host researchers working on quantum walks, graph algorithms, and the connection between walks and quantum query complexity. Research groups in India also contribute to the ongoing refinement of triangle-finding and graph-property-testing algorithms, which are downstream of the framework you have just seen.

The National Quantum Mission (2023, ₹6000 crore) puts quantum algorithms — including walk-based techniques — inside its research portfolio. The theoretical side of the Mission's algorithms thrust uses walk-based methods as a standard tool, alongside amplitude amplification and the quantum Fourier transform.

Common confusions

• "The coin is a literal coin flip." It is an arbitrary unitary on the coin register. The name "coin" is misleading historical terminology — a Hadamard coin does not produce a random direction; it produces a superposition of directions with complex amplitudes. The quantum-mechanical interference between those amplitudes is the entire source of the walk's speedup over classical.
• "You need two registers because quantum is weird." The two-register structure is forced by unitarity, not by weirdness. Any unitary random walk has to be reversible; tracking "where you came from" (the coin) is the minimum extra information required for reversibility. Without it, distinct starting configurations merge and the operator is not unitary.
• "Continuous and discrete walks are different algorithms." They are formally related — Childs 2010 gave explicit mappings between them — and on most graphs they produce the same order of speedup. Choose based on the problem: discrete for circuit implementation, continuous for Hamiltonian analysis.
• "Szegedy walks only work on reversible Markov chains." Reversibility is the standard assumption, and it covers almost every natural random walk on an undirected graph. The walk on a directed, non-reversible chain can be handled, but the theory is less clean and the speedups less straightforward. In practice, "Markov chain \to Szegedy walk" is the reversible case unless otherwise stated.
• "Grover and quantum walks are separate topics." They are not. Grover is a discrete quantum walk on the complete graph. Amplitude amplification is the reflection structure that appears inside every Szegedy walk. The MNRS framework makes them different special cases of one recipe.
• "The walk's quadratic speedup means it is always faster than classical." No. The quadratic speedup is on spread distance or mixing time or hitting time. Whether this translates to a speedup on the problem you care about depends on how your problem maps to a walk. For search on a complete graph (no structure), the walk gives Grover's \sqrt N. For search on a graph with more structure, walks can give better than \sqrt N — element distinctness is N^{2/3}. For problems that do not map to walks, walks give you nothing.

Going deeper

Szegedy's spectral theorem

Let P be a reversible Markov chain with stationary distribution \pi. Define the discriminant matrix D with entries D_{uv} = \sqrt{P_{uv} P^*_{vu}}. For reversible chains, D_{uv} = \sqrt{P_{uv} P_{vu} \pi_v / \pi_u}, which after some algebra equals \sqrt{\pi_u / \pi_v} \cdot P_{uv}. Let \sigma_1 \ge \sigma_2 \ge \cdots \ge 0 be the singular values of D.

Theorem (Szegedy 2004). The eigenvalues of the walk operator W, on the subspace spanned by the Szegedy states, are \pm 1 and e^{\pm 2i\theta_k} where \cos\theta_k = \sigma_k. The +1 eigenvector corresponds to the stationary distribution. The smallest non-zero phase \theta_2 satisfies \theta_2 \approx \sqrt{2(1 - \sigma_2)} = \sqrt{2 \cdot \text{gap}(P)} when the classical gap \text{gap}(P) = 1 - \sigma_2 is small.

This phase gap controls the walk's mixing time: after T = O(1/\theta_2) steps of W, the walk's state concentrated near the stationary eigenvector can be distinguished (via phase estimation) from the other eigenvectors. This is the formal source of the quadratic speedup: mixing in O(1/\sqrt{\text{gap}(P)}) steps against the classical O(1/\text{gap}(P)).

The MNRS framework — full statement

Let P be a reversible Markov chain on a vertex set V with spectral gap \Delta. Let M \subseteq V be a set of marked vertices, with |M|/|V| \ge \varepsilon (the fraction of marked vertices is at least \varepsilon). Suppose you have three quantum subroutines:

• Setup costing S queries — prepares a state corresponding to the stationary distribution of the walk on V.
• Update costing U queries — implements one step of the walk.
• Check costing C queries — detects whether the current vertex is marked.

Theorem (MNRS 2007). There is a quantum algorithm that finds a marked vertex with high probability using

queries.

This is the general recipe. Grover is \varepsilon = 1/N, \Delta = \Theta(1) (complete graph), S = O(1), U = O(1), C = O(1) — giving O(\sqrt N). Element distinctness is Johnson graph J(N, r) with \varepsilon \approx 1/\binom{N}{r} and \Delta \approx 1/r — giving O(N^{2/3}) after optimising r = N^{2/3}. Triangle finding via walks (MSS 2005) is a nested application: walk to a subset of vertices, then walk again within.

Connection to quantum singular value transformation (QSVT)

The modern unifying perspective (Gilyén-Su-Low-Wiebe 2019) treats quantum walks, amplitude amplification, and phase estimation as instances of singular value transformation of a block-encoded matrix. A block-encoded matrix is a unitary U whose top-left block equals a desired matrix A/\|A\|. Given a polynomial p(x), QSVT produces a unitary that block-encodes p(A)/\|A\| using \deg(p) applications of U.

Szegedy walks are the special case where the block-encoding comes from the Markov chain's transition matrix and the polynomial is \cos(k \theta) — a Chebyshev polynomial. Mixing via phase estimation is the polynomial that projects onto the +1 eigenspace. Amplitude amplification is the polynomial that amplifies small singular values. All three algorithmic primitives collapse into one framework, parameterised by the choice of polynomial.

This is the cleanest modern formulation of the quantum algorithmic toolkit. Understanding it requires some representation-theory machinery (the algebra of SU(2) rotations under composition), but the payoff is enormous: most quantum algorithms you will meet are QSVT for the right polynomial on the right block-encoding.

When the coin matters

The choice of coin operator affects fine details but rarely the asymptotic speedup. The Hadamard coin gives an asymmetric walk on the line; the Grover coin is the right choice for d-regular graphs; the Fourier coin exploits cyclic symmetry. For spatial search problems, the Grover coin is typically optimal. Changing coins on the same graph changes the walk's local spread pattern but preserves the \sqrt{\text{classical mixing}} asymptotic.

The deep reason: all reasonable coins are rotations within the same invariant subspace, and the subspace dimension (not the specific rotation) controls the asymptotic speedup. This is one of the facts that makes walks feel like a "clean" primitive — the framework is robust to coin choice.

Where this leads next

• Continuous Quantum Walks — the Hamiltonian-evolution flavour and the glued-trees exponential speedup.
• Element Distinctness and Walks — Ambainis 2003, the first walk-based speedup beyond Grover.
• Amplitude Amplification — the reflection structure at the heart of every Szegedy walk.
• Grover Algorithm Circuit — revisit Grover knowing it is a walk.

References

1. Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh Vazirani, Quantum walks on graphs (2001), STOC — arXiv:quant-ph/0012090. The coin-and-shift formulation.
2. Mario Szegedy, Quantum speed-up of Markov chain based algorithms (2004), FOCS — IEEE Xplore / open summary on ECCC. The Szegedy walk and the quadratic phase-gap theorem.
3. Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha, Search via quantum walk (2007) — arXiv:quant-ph/0608026. The MNRS framework.
4. Andrew M. Childs, On the relationship between continuous- and discrete-time quantum walk (2010), Commun. Math. Phys. — arXiv:0810.0312. The explicit mapping between the two flavours.
5. Salvador Elías Venegas-Andraca, Quantum walks: a comprehensive review (2012), Quantum Information Processing — arXiv:1201.4780.
6. Wikipedia, Quantum walk.