Quantum Walks

How far does a random walker get in \(T\) steps? Start a walker at position \(0\) on the integers. At each step flip a fair coin and move one step left or right. After \(T\) steps the position is a sum of \(T\) independent \(\pm1\) steps, with mean \(0\) and variance \(T\). The typical distance from the start is \(\sqrt T\). This \(\sqrt T\) growth is diffusive spreading, the signature of a classical random walk: to travel distance \(d\) takes about \(d^2\) steps.

On a graph, a random walk moves from a vertex to a uniformly random neighbour. It is described by a transition matrix \(P\), with \(P_{xy}\) the probability of moving from \(x\) to \(y\). If the walker’s distribution is a row vector \(q\), one step gives \(qP\), so \(t\) steps give \(qP^t\).

Why not simply make this walk coherent, replacing the coin flip by a superposition of left and right? On the line, the naive map \(\ket x\mapsto\frac{1}{\sqrt2}(\ket{x-1}+\ket{x+1})\) is not unitary. Apply it to \(\ket0\) and \(\ket2\): both images contain \(\ket1\) with amplitude \(\frac{1}{\sqrt2}\), so the images overlap, \(\frac12\neq0\), although \(\ket0\) and \(\ket2\) are orthogonal. A unitary must preserve orthogonality. The walker needs to remember something more than its position.

Give the walker a direction. Its state is \(\ket{c,x}\), with a coin register \(c\in\{0,1\}\) for left or right and a position register \(x\). One step of the coined quantum walk does two things:

1. Coin: apply a unitary \(C\) to the coin, for example the Hadamard gate, creating a superposition of directions.
2. Shift: move according to the coin, \(S\ket{0,x}=\ket{0,x-1}\) and \(S\ket{1,x}=\ket{1,x+1}\).

The shift operator \(S\) is a permutation of the basis states \(\ket{c,x}\), so it is unitary: the coin label tells us which way the walker came, so the move can be undone. The step is \(W=S(C\otimes I)\). The coin is what fixes the obstruction we found for the naive coherent walk: the two contributions to position \(x\) now arrive with different coin labels, \(\ket{1,x}\) from the left and \(\ket{0,x}\) from the right, so the images of different basis states stay orthogonal.

On a cycle of \(N\) vertices, positions are taken modulo \(N\) and the shift is a controlled increment or decrement, built from the reversible incrementer. Here is a four-cycle starting at \(\ket{0,0}\), with Hadamard coin. One step gives \(\frac{1}{\sqrt2}(\ket{0,3}+\ket{1,1})\). Two steps give

\[\tfrac12\big(\ket{0,2}+\ket{1,0}+\ket{0,0}-\ket{1,2}\big).\]

What to observe

Apply the Hadamard gate to the coin and shift. The contributions to \(\ket{0,1}\) and \(\ket{1,1}\) cancel exactly, while those to \(\ket{0,3}\) and \(\ket{1,3}\) add: the state is \(\frac{1}{\sqrt2}(\ket{0,3}+\ket{1,3})\). After three steps the walker is at vertex 3 with certainty. A classical walker after three steps is at vertex 1 or 3 with probability \(\frac12\) each.

That deterministic arrival is interference among routes, which classical walks cannot have. It also shows a hazard. Measuring the position after every step would collapse each superposition and turn the quantum walk back into a classical random walk. The walk must run coherently, and only the final position is measured.

Run the Hadamard walk on the line for many steps from a symmetric initial coin \(\frac{1}{\sqrt2}(\ket0+i\ket1)\) at position \(0\). The distribution looks nothing like the classical bell curve.

After \(T=60\) steps the quantum distribution has two sharp peaks near \(\pm T/\sqrt2\approx\pm42\) and is spread almost flat between them; its standard deviation is about \(32.5\approx0.54\,T\). The classical walk has standard deviation \(\sqrt{60}\approx7.7\). The quantum spread grows linearly in \(T\), ballistic spreading, like a particle moving at constant speed, while the classical spread grows like \(\sqrt T\).

Why the difference? No walker moves more than one site per step, so the spread can never exceed \(T\). In the classical walk the steps are independent and partly cancel, like a sum of coin flips, which leaves only \(\sqrt T\). The quantum walker’s amplitudes do not average this way. To see what they do instead, we need the eigenvectors of a walk, which we find for walks on a cycle once we can exponentiate a matrix.

Faster spreading is suggestive but is not an algorithm. An algorithm needs a problem, an input model, and a measurement with a high chance of answering it. The quadratic difference between \(T\) and \(\sqrt T\) does foreshadow a recurring pattern, though: quantum walks often reach their targets in about the square root of the classical time. Turning that pattern into theorems requires stated assumptions about the problem and the access.

What should a walk that flows continuously look like? Let \(U(t)\) be the operation that runs it for time \(t\). Running for \(s\) and then for \(t\) should equal running for \(s+t\), so \(U(s+t)=U(t)U(s)\) and \(U(0)=I\). Over a very short time \(\delta\), the walker should barely move: \(U(\delta)\approx I+\delta M\), where \(M\) has nonzero entries only along the graph’s edges.

Which \(M\) keep \(U\) unitary? To first order in \(\delta\), \(U(\delta)^\dagger U(\delta)\approx I+\delta(M+M^\dagger)\), so we need \(M^\dagger=-M\). Write \(M=-iH\). Then the condition becomes \(H^\dagger=H\): \(H\) must be Hermitian, equal to its own conjugate transpose. The adjacency matrix of a graph, scaled by a coupling strength \(\gamma\), is real and symmetric, so it qualifies. The factor \(-i\) is what turns a symmetric matrix into a small rotation rather than a stretch.

Now build time \(t\) from \(n\) short steps: \(U(t)=U(t/n)^n\approx(I-iHt/n)^n\). As \(n\) grows this becomes the matrix exponential. A continuous-time quantum walk on a graph with Hermitian \(H\) built from its edges evolves the state by

\[U(t)=e^{-iHt},\]

where the exponential of a matrix is defined by the same power series as for numbers: \(e^{M}=I+M+M^2/2!+M^3/3!+\cdots\). Take two vertices joined by an edge. Their adjacency matrix with coupling \(\gamma\) is \(H=\gamma X\), and for it the series is easy, because \(X^2=I\): even powers of \(X\) are \(I\) and odd powers are \(X\). Grouping terms,

\[e^{-i\gamma tX}=\Big(1-\tfrac{(\gamma t)^2}{2!}+\cdots\Big)I-i\Big(\gamma t-\tfrac{(\gamma t)^3}{3!}+\cdots\Big)X=\cos(\gamma t)\,I-i\sin(\gamma t)\,X.\]

So \(U(t)\ket0=\cos(\gamma t)\ket0-i\sin(\gamma t)\ket1\). The walker moves to the other vertex with probability \(\sin^2(\gamma t)\), completely at \(t=\pi/(2\gamma)\), and then back.

Is the result unitary, as the derivation intended? Here we can check directly: \((\cos\gamma t\,I+i\sin\gamma t\,X)(\cos\gamma t\,I-i\sin\gamma t\,X)=(\cos^2\gamma t+\sin^2\gamma t)I=I\), using \(X^2=I\). Notice also that only the product \(\gamma t\) matters. Doubling every coupling halves the time, so “time” alone is not a cost. The cost of simulating a walk on a quantum computer grows with \(\|H\|t\), where \(\|H\|\) is the operator norm.

For larger graphs the power series is not summed so easily. Can eigenvalues do the work? If \(H\ket{v_j}=\lambda_j\ket{v_j}\), then every power acts on \(\ket{v_j}\) by \(\lambda_j^k\), so the series acts by the ordinary exponential:

\[e^{-iHt}\ket{v_j}=e^{-i\lambda_jt}\ket{v_j}.\]

The eigenvalues of a Hermitian matrix are real. Indeed, if \(H\ket v=\lambda\ket v\) with \(\braket vv=1\), then \(\lambda=\bra vH\ket v\), and conjugating gives \(\lambda^*=\bra vH^\dagger\ket v=\lambda\). As for unitaries, the spectral theorem, which we assume, provides an orthonormal basis of eigenvectors. Together these give the spectral decomposition \(H=\sum_j\lambda_j\ket{v_j}\bra{v_j}\). To evolve any state, expand it in eigenvectors, multiply each coefficient by its own phase \(e^{-i\lambda_jt}\), and recombine. Each phase has magnitude one because \(\lambda_j\) is real, so \(e^{-iHt}\) sends an orthonormal basis to an orthonormal basis: it is unitary for every Hermitian \(H\).

In physics a Hermitian generator of evolution is called a Hamiltonian, and its eigenvalues are energies. The eigenvector with the smallest eigenvalue is the ground state, and the difference between the two smallest eigenvalues is the energy gap. We will use these names whenever a Hermitian matrix plays this role.

Check on the two-vertex graph. \(X\) has eigenvectors \(\ket+\) (eigenvalue \(1\)) and \(\ket-\) (eigenvalue \(-1\)). So \[e^{-i\gamma tX}\ket0=\frac{1}{\sqrt2}(e^{-i\gamma t}\ket++e^{i\gamma t}\ket-)=\cos(\gamma t)\ket0-i\sin(\gamma t)\ket1\], as before.

This picture explains what a continuous walk does: each eigenvector rotates its phase at a rate given by its eigenvalue, and interference among them produces the motion. Differences between eigenvalues set the timescales. The largest eigenvalue magnitude, \(\|H\|\), sets the fastest timescale, which is why it controls simulation cost. And it is the same picture as phase estimation: running phase estimation on \(e^{-iHt}\) samples the eigenvalues \(\lambda_j\), weighted by the squared overlaps of the initial state.

Which graphs have eigenvectors we can write down? On a cycle of \(N\) vertices, the adjacency matrix \(A\) sends \(\ket x\) to \(\ket{x-1}+\ket{x+1}\). The cycle looks the same from every vertex, and the Fourier transform turns a shift into a phase, so we try Fourier states. Let \(\ket{\tilde k}=\frac{1}{\sqrt N}\sum_x\omega^{kx}\ket x\), with \(\omega=e^{2\pi i/N}\). Then

\[A\ket{\tilde k}=\frac{1}{\sqrt N}\sum_x\omega^{kx}(\ket{x-1}+\ket{x+1})=(\omega^{k}+\omega^{-k})\ket{\tilde k}=2\cos\!\left(\frac{2\pi k}{N}\right)\ket{\tilde k}.\]

Each Fourier mode is an eigenvector, with eigenvalue \(2\cos(2\pi k/N)\). The continuous walk on the cycle is therefore: Fourier transform, apply phases \(e^{-2i\gamma t\cos(2\pi k/N)}\), inverse Fourier transform. The quantum Fourier transform implements the change of basis efficiently, so for the cycle, and for other graphs with this kind of symmetry, the walk can be simulated exactly with \(O(n^2)\) gates.

Now we can answer why quantum walks spread linearly in time. Take the walk \(e^{-i\gamma At}\), so mode \(k\) has eigenvalue \(\lambda(k)=2\gamma\cos(2\pi k/N)\), and suppose the initial state is built from modes with \(k\) close to some \(k_0\). Write \(\kappa=2\pi k/N\), so that mode \(k\) has amplitude proportional to \(e^{i\kappa x}\) at vertex \(x\). After time \(t\) it carries the extra phase \(e^{-i\lambda t}\). For \(\kappa\) near \(\kappa_0\), \(\lambda\approx\lambda_0+v(\kappa-\kappa_0)\), where \(v\) is the slope of \(\lambda\) as a function of \(\kappa\). Then

\[e^{i\kappa x}e^{-i\lambda t}\approx e^{i(\kappa_0x-\lambda_0t)}\;e^{i(\kappa-\kappa_0)(x-vt)}.\]

The first factor is common to all the modes. The second depends on \(x\) only through \(x-vt\), so the whole superposition is its initial shape moved a distance \(vt\). It travels at constant speed

\[v=\frac{d}{d\kappa}\,2\gamma\cos\kappa=-2\gamma\sin\kappa_0,\]

which ranges between \(-2\gamma\) and \(2\gamma\). A state built from many modes contains parts moving at all these speeds, so its width grows in proportion to \(t\). A classical walker has no phases to keep its moves aligned, and its width grows only like \(\sqrt t\). The coined Hadamard walk has eigenphases that depend on \(\kappa\) in a similar way; the same calculation, which we do not repeat, gives a largest speed of \(1/\sqrt2\) sites per step, matching the peaks near \(\pm T/\sqrt2\).

The cycle is special because its symmetry makes the eigenvectors known. For a general graph the eigenvectors are unknown, and a walk is implemented step by step from local access to the graph: given a vertex, list its neighbours. How can a walk be built from that local access alone?

How do we turn a classical chain into a pair of reflections? Let \(P\) be the transition matrix of a Markov chain, a walk whose next step depends only on its current vertex, on vertices \(x\in\{1,\ldots,N\}\). Work on pairs \(\ket x\ket y\), thought of as directed edges. For each \(x\), define the state that spreads from \(x\) according to \(P\):

\[\ket{\psi_x}=\ket x\otimes\sum_y\sqrt{P_{xy}}\,\ket y.\]

The states \(\ket{\psi_x}\) are orthonormal, since they have different first registers. Let \(R_A=2\sum_x\ket{\psi_x}\bra{\psi_x}-I\) be the reflection about their span, and define \(R_B\) the same way with the roles of the two registers exchanged (spreading from \(y\) back to \(x\)). The Szegedy walk is the product

\[W=R_BR_A.\]

Each reflection is built like the reflection about a prepared state: a circuit \(V\) with \(V\ket x\ket0=\ket{\psi_x}\), a reflection about \(\ket0\) on the second register, and \(V^\dagger\). So one walk step needs a coherent procedure that, given \(x\), prepares the superposition of its neighbours weighted by \(\sqrt{P_{xy}}\). For a graph given by neighbour lists, that is a coherent neighbour query plus a uniform superposition over the degree.

Why two reflections? Start with the smallest case: one state \(\ket a\) from the first family and one state \(\ket b\) from the second, with real overlap \(\braket ab=\cos\theta\). In the plane they span, \(2\ket a\bra a-I\) reflects across the line through \(\ket a\), and \(2\ket b\bra b-I\) across the line through \(\ket b\). The two lines meet at angle \(\theta\), and we saw with the Grover iterate that two such reflections compose to a rotation by \(2\theta\). Outside the plane both act as \(-I\), so their product is the identity there.

With many states in each family the planes might seem to tangle. A linear-algebra result we quote, Jordan’s lemma, says they do not: the space splits into planes that both reflections preserve, plus pieces on which the product is simply \(\pm I\). The angles of the planes are set by the overlaps between the two families,

\[\braket{\psi_x}{\phi_y}=\sqrt{P_{xy}P_{yx}}=D_{xy},\]

where \(\ket{\phi_y}=\sum_x\sqrt{P_{yx}}\ket x\otimes\ket y\) are the states of the second family. For a symmetric chain \(D=P\). Szegedy’s construction (Szegedy, 2004) thus turns a classical chain into a quantum walk whose rotation angles are determined by the chain’s spectrum.

How fast does the classical chain forget where it started? Take a symmetric chain. Its rows and its columns sum to one, so the uniform distribution \(\pi\) satisfies \(\pi P=\pi\). A distribution left unchanged by a step is a stationary distribution. A symmetric \(P\) has real eigenvalues and orthonormal eigenvectors \(w_j\), with \(w_1\) proportional to \(\pi\) and eigenvalue \(\lambda_1=1\). Order the rest by magnitude, \(1\ge|\lambda_2|\ge|\lambda_3|\ge\cdots\). Expanding a starting distribution \(q_0=\sum_jc_jw_j\) gives

\[q_0P^t=\pi+\sum_{j\ge2}c_j\lambda_j^tw_j,\]

since \(c_1w_1=\pi\) for any distribution. Every other term shrinks at least as fast as \(|\lambda_2|^t\). The spectral gap is \(\delta=1-|\lambda_2|\), so the distance from stationarity falls like \((1-\delta)^t\le e^{-\delta t}\). The mixing time, the number of steps until the distribution is close to \(\pi\), is therefore of order \(1/\delta\), up to a logarithm of the required accuracy.

What are the walk’s rotation angles? Szegedy’s theorem, which we quote, completes the two-state picture. Each eigenvalue \(\lambda=\cos\theta\) of \(D\) gives a two-dimensional invariant plane on which \(W\) acts as a rotation by \(2\theta\), with eigenvalues \(e^{\pm2i\theta}\). The eigenvalue \(\lambda_1=1\) gives \(\theta=0\): a stationary state of the walk, unchanged by \(W\). The next eigenvalue \(\lambda_2=1-\delta\) gives \(\cos\theta=1-\delta\), so

\[\theta\approx\sqrt{2\delta}\quad\text{for small }\delta,\]

using \(\cos\theta\approx1-\theta^2/2\). The phase gap, the smallest nonzero eigenphase of \(W\), is \(2\theta\ge2\sqrt\delta\). A gap of \(\delta\) in the classical chain becomes a gap of order \(\sqrt\delta\) in the walk.

This square root is the source of the speedup. Phase estimation distinguishes the stationary eigenphase \(0\) from all others with precision of order \(\sqrt\delta\), which costs order \(1/\sqrt\delta\) walk steps, against \(1/\delta\) classical steps. Amplitude amplification had the same structure. There the rotation angle satisfied \(\sin\theta=\sqrt p\), so a small probability \(p\) gave an angle of order \(\sqrt p\). Here \(\cos\theta=1-\delta\), so a small gap \(\delta\) gives an angle of order \(\sqrt\delta\). In both, the number of rotations needed is one over the angle.

Suppose a fraction \(\varepsilon\) of the vertices of a graph are marked, and the classical walk has spectral gap \(\delta\). Classically, a simple strategy is: walk for order \(1/\delta\) steps to reach a nearly random vertex, check whether it is marked, and repeat about \(1/\varepsilon\) times. Total cost about \(\frac1\varepsilon\cdot\frac1\delta\) walk steps. This bounds the hitting time, the expected number of steps until the walker first reaches a marked vertex.

The quantum version replaces both loops by their square roots. The framework of Magniez, Nayak, Roland, and Santha (2007) performs amplitude amplification in which the reflection about the stationary state of the walk is implemented by phase estimation on \(W\), distinguishing phase \(0\) from phases at least \(2\sqrt\delta\). With setup cost \(\mathsf S\) (prepare the stationary state), update cost \(\mathsf U\) (one walk step), and checking cost \(\mathsf C\) (test whether a vertex is marked), walk search finds a marked vertex at cost

\[\mathsf S+\frac{1}{\sqrt\varepsilon}\left(\frac{1}{\sqrt\delta}\,\mathsf U+\mathsf C\right).\]

Compare classical \(\mathsf S+\frac1\varepsilon\big(\frac1\delta\mathsf U+\mathsf C\big)\). Both factors are square-rooted.

On the complete graph, a random step already lands on a random vertex: \(\delta\approx1\), and with one marked item, \(\varepsilon=1/N\). The formula gives \(O(\sqrt N)\), and the walk reduces to Grover search. The value of the framework is on graphs where \(\delta\) is small but steps are cheap and reuse previous work, which is exactly the situation in element distinctness. On a two-dimensional grid of \(N\) vertices, walk search finds a marked vertex in \(O(\sqrt N\log N)\) steps (Ambainis, Kempe, and Rivosh, 2005), whereas a classical walk on the grid needs order \(N\log N\).

Can a walk beat Grover search on a problem with structure? Given oracle access to a list \(T(1),\ldots,T(N)\), decide whether two entries are equal. This is element distinctness. Classically it needs order \(N\) queries. Grover search over all pairs needs \(\sqrt{N^2}=N\) queries, no better. Ambainis found an algorithm with \(O(N^{2/3})\) queries (Ambainis, 2004), and a matching lower bound of \(\Omega(N^{2/3})\) is known.

The walk is on the Johnson graph: vertices are subsets \(S\) of \(\{1,\ldots,N\}\) of size \(r\), and two subsets are adjacent if they differ in one element. Each vertex stores the queried values \(T(i)\) for \(i\in S\). A vertex is marked if its subset contains a colliding pair. What does each part of the walk-search cost formula become?

Setting up means querying \(r\) values, so \(\mathsf S=r\). An update swaps one element out of the subset and one in. That needs \(O(1)\) queries, because the other \(r-1\) stored values are reused, so \(\mathsf U=O(1)\). Checking costs nothing: the stored values already reveal any collision, so \(\mathsf C=0\).

How many vertices are marked? If one colliding pair exists, a random \(r\)-subset contains both of its elements with probability about \((r/N)^2\), so \(\varepsilon\approx r^2/N^2\). How fast does the walk mix? Each step replaces one of the \(r\) elements. After about \(r\) steps most of the original elements have been replaced, so the walk has forgotten its start, which suggests \(\delta\approx1/r\). The exact value, which we quote from the known spectrum of the Johnson graph, is \(\delta=N/\big(r(N-r)\big)\), close to \(1/r\) when \(r\ll N\).

Substituting into the walk-search cost, the total is

\[r+\frac{N}{r}\Big(\sqrt r\cdot O(1)+0\Big)=r+\frac{N}{\sqrt r}.\]

Balancing the two terms with \(r=N^{2/3}\) gives \(O(N^{2/3})\) queries.

The insight is reuse. Grover over pairs pays one query per check and finds nothing between checks. The walk keeps a large set of values in memory and changes it a little at a time, so each step is cheap and checking is free. The price is space: the algorithm stores \(r=N^{2/3}\) values coherently, and its gate count includes data-structure operations on that memory. The query count is optimal; the time and space costs depend on how that coherent memory is implemented.

Can a walk ever give more than a polynomial speedup? On one specially built problem, yes. In the glued trees problem, two binary trees of depth \(n\) are joined at their leaves by a random cycle, and we are given an oracle that returns the neighbours of a vertex, with vertices labelled by random strings. Starting at one root, find the other. A classical algorithm gets lost in the exponentially many middle vertices and provably needs exponentially many queries. A continuous-time quantum walk, viewed in a basis of “column” states that group vertices by distance from the root, behaves like a walk on a line of length \(2n\) and reaches the far root in polynomial time (Childs et al., 2003).

The glued-trees result is an oracle separation for a contrived problem; it has no known practical application. It shows that walks can exploit global structure, the symmetry of the graph, in a way classical exploration cannot.

The limits are as important as the results. Walk algorithms are stated in query models with coherent neighbour access. Their time complexity includes the cost of implementing that access, the coherent data structures, and the precision of phase estimation inside the framework. A spectral gap must be known or bounded to set parameters. And on graphs that are classically easy to search, a walk cannot do better than a quadratic improvement in general.

The walk operator \(W\) has an eigenvalue structure tied to a matrix \(D\) through \(\lambda=\cos\theta\). The same relation will hold for any matrix placed inside a unitary, provided we can place a matrix that is not unitary inside a unitary at all.