Quantum Walk Algorithms

A quantum walk moves amplitudes coherently through a graph. Interference can concentrate probability at a useful vertex, and the spectrum can help a search algorithm rotate toward marked states. This page develops coined walks, Szegedy walks and continuous-time walks, then derives the $O(N^{2/3})$ value-query algorithm for element distinctness from a concrete subset graph.

The three walk models use different Hilbert spaces and updates. A graph alone does not specify an algorithm: one also needs an initial state, an update that can actually be implemented, and a measurement that returns the requested answer. The small examples below make these choices explicit before the asymptotic search results.

Helpful background. Quantum oracles explains coherent queries and inverse access; algorithmic primitives introduces reflections; eigenvalues and eigenvectors supplies the spectral decomposition used below.

Quantum Walks as Algorithmic State-Space Dynamics

A classical random walk updates a probability distribution by a stochastic matrix. A quantum walk instead updates amplitudes coherently, preserving relative phases until a declared measurement. Interfering histories can suppress some outcomes and reinforce others, so a graph’s spectrum can control a search or traversal procedure in a way that has no trajectory-by-trajectory classical interpretation. The graph-algorithm framework of Aharonov, Ambainis, Kempe, and Vazirani also emphasizes an important difference from classical mixing: a finite closed unitary walk does not ordinarily converge to a stationary probability distribution. Time averaging, an absorbing modification, a randomized stopping time, or a specified measurement schedule is therefore part of an algorithm rather than an optional presentation detail.

The three models here package coherence differently. A coined discrete-time walk lives on directed edges, or equivalently on a vertex register augmented by a local coin register. One step applies a vertex-local coin and a routing permutation. A Szegedy walk uses two coherent copies of a Markov-chain state space and alternates reflections about transition-state subspaces. A continuous-time walk lives on the vertex space and evolves as $e^{-itH_{\rm walk}}$ for a declared Hermitian generator. A spectral correspondence can connect particular instances, and Childs gives a precise relationship between continuous- and discrete-time walks, but this does not license replacing one access model, state space, or resource count by another.

Discrete-Time Coined Walks

Coin and shift on directed edges

Let $G=(V,E)$ be a finite undirected graph. Its directed-edge, or arc, Hilbert space is

$$\mathcal H_{\rm arc} = \operatorname{span} \{\lvert v,w\rangle:(v,w)\text{ is a directed edge}\}.$$

For each vertex $v$, the outgoing arcs span a local space of dimension $\deg(v)$. A local unitary $C_v$ mixes those outgoing directions, and the global coin is the orthogonal direct sum

$$C=\bigoplus_{v\in V}C_v.$$

The graph-general default here is the flip-flop shift

$$S\lvert v,w\rangle=\lvert w,v\rangle,$$

with the step convention

$$W_{\rm coin}=SC.$$

The direct sum is unitary exactly when every $C_v$ is unitary. The shift is a permutation with $S^2=I$, so it is unitary and self-inverse. Thus $W_{\rm coin}$ is unitary. This elementary proof is important operationally: an update that discards a direction label, samples a neighbor, or overwrites a cache is not this coherent walk until it has been embedded in a reversible operation with the necessary workspace.

A common regular-graph choice is the Grover diffusion coin $C_v=2\lvert s_v\rangle\langle s_v\rvert-I$, where $\lvert s_v\rangle$ is uniform over outgoing arcs. The local coin is a reflection; the complete Grover search algorithm also requires a markedness reflection and a suitable repetition count. At a marked vertex one may replace the local coin, apply a separate phase oracle, add a self-loop, or enlarge the coin space. These alternatives can have different spectra and success probabilities. On an irregular graph, padding all local spaces to a common register requires a declared action on unused labels; leaving that action unspecified leaves the purported unitary unspecified.

Order also matters. $SC$ means coin first and route second when operators act from the right, whereas $CS$ routes before mixing. A moving shift preserves a direction label while changing the vertex; a flip-flop shift reverses the directed edge. They may be related on a specially relabeled regular graph, but they are not textually interchangeable. Measuring the complete arc basis after every step gives the classical transition probabilities $\lvert\langle b|W_{\rm coin}|a\rangle\rvert^2$. Measuring only the vertex can retain coin coherence, so the vertex outcomes need not form a Markov chain on vertices alone. The initial state and sampling rule belong to the walk definition.

Exact interference on a four-cycle

For a compact finite example, use vertices $x\in\mathbb Z_4$ and coin labels $L,R$. This example explicitly changes from the preceding flip-flop default to the named moving shift

$$S\lvert L,x\rangle=\lvert L,x-1\bmod4\rangle, \qquad S\lvert R,x\rangle=\lvert R,x+1\bmod4\rangle.$$

Let the local coin be Hadamard,

$$H\lvert L\rangle =\frac{\lvert L\rangle+\lvert R\rangle}{\sqrt2}, \qquad H\lvert R\rangle =\frac{\lvert L\rangle-\lvert R\rangle}{\sqrt2},$$

define the local coin in the interleaved ordered basis by $C=\bigoplus_{x=0}^{3}H_x$, and set $U=SC$. Starting from $\lvert\psi_0\rangle=\lvert L,0\rangle$, repeated application gives

$$\begin{aligned} \lvert\psi_1\rangle &=\frac{\lvert L,3\rangle+\lvert R,1\rangle}{\sqrt2},\\ \lvert\psi_2\rangle &=\frac{\lvert L,0\rangle+\lvert R,0\rangle +\lvert L,2\rangle-\lvert R,2\rangle}{2},\\ \lvert\psi_3\rangle &=\frac{\lvert L,3\rangle+\lvert R,3\rangle}{\sqrt2},\\ \lvert\psi_4\rangle &=\lvert L,2\rangle. \end{aligned}$$

The cancellations at the third step are visible in the second-step signs. The two amplitudes that could reach vertex $1$ cancel, while the amplitudes at vertex $3$ reinforce. Consequently the coherent position distribution at $t=3$ is concentrated at vertex $3$. A classical simple random walk on the same cycle, begun at vertex $0$, has distribution $(0,1/2,0,1/2)$ after three steps. The concentration at vertex $3$ comes from interference. It does not by itself solve a search problem: the graph has no marked vertex, and the desired computational output has not been specified.

This example also shows why the coin cannot be omitted from a state description. At $t=2$, the position distribution is split evenly between vertices $0$ and $2$, but the conditional coin states carry opposite relative phases. A measurement resolving both position and coin destroys the cross terms needed for the later cancellation. A position-only measurement retains coin coherence within each measured vertex. Here it gives the same third-step position distribution as the unmeasured walk, but a different joint state: an equal mixture of $|L,3\rangle$ and $|R,3\rangle$, instead of their coherent superposition. The difference becomes visible one step later. Thus equality of position probabilities at one time does not establish equality of walk states.

The same four-cycle walk is measured in three different ways immediately after step two. Position-only measurement preserves the third-step concentration at vertex $3$, yet removes the coin coherence that would concentrate the fourth-step probability at vertex $2$. Every row is a normalized position distribution.

Continuous-Time Quantum Walks

Adjacency and Laplacian generators

A continuous-time walk acts directly on the vertex space. With $\hbar=1$, the adjacency convention used here is

$$U(t)=e^{-itH_{\rm walk}}, \qquad H_{\rm walk}=-\gamma A,$$

where $A$ is the adjacency matrix and $\gamma>0$ fixes the energy and time scale. The continuous-time computational model introduced by Farhi and Gutmann uses Hamiltonian evolution rather than alternating coin and shift registers. For marked-vertex search, a standard rank-one perturbation is

$$H_{\rm search} =-\gamma A-\lvert w\rangle\langle w\rvert.$$

The initial state, marked vertex $w$, choice of $\gamma$, measurement time, and acceptable time window are all part of the search instance. Rescaling $H$ by $a$ and time by $1/a$ preserves the ideal unitary, so a claim quoting time without a normalization or implementation model is not invariant information.

Some authors use the graph Laplacian $L=D-A$, where $D$ is the degree matrix. On a $k$-regular graph,

$$\gamma L =\gamma kI-\gamma A =\gamma kI+H_{\rm walk},$$

and therefore

$$e^{-it\gamma L} =e^{-i\gamma kt}e^{-itH_{\rm walk}}.$$

The two evolutions have identical measurement probabilities after the sign convention is matched because the extra factor is a global phase. On an irregular graph, $D$ is not proportional to the identity. For the three-vertex path, $D=\operatorname{diag}(1,2,1)$, so the Laplacian adds a vertex-dependent diagonal potential. It changes relative phases and is operationally different from adjacency evolution. “A walk on the same graph” therefore does not determine a continuous-time generator.

Evolution time, measurement, and implementation

Spectral decomposition gives

$$e^{-itH_{\rm walk}} =\sum_j e^{-itE_j}\lvert E_j\rangle\langle E_j\rvert.$$

The moduli of the energy-basis amplitudes are constant, while their phases rotate. In a finite closed system this quasiperiodic behavior generally prevents convergence of the instantaneous vertex distribution. An algorithm may instead choose a specific time, sample a time from an interval, average probabilities over a window, or introduce a measurement or absorbing rule. Each choice defines a different output distribution. Hitting time, detection time, and time to produce a marked vertex should not be used as synonyms unless a theorem proves their equivalence in the stated model.

The two-vertex graph makes the time scale explicit. Its adjacency is the Pauli matrix $X$, so $H=-\gamma X$ and

$$e^{-itH} =e^{i\gamma tX} =\cos(\gamma t)I+i\sin(\gamma t)X.$$

From $\lvert0\rangle$, the state is $\cos(\gamma t)\lvert0\rangle+i\sin(\gamma t)\lvert1\rangle$, and the transition probability is $\sin^2(\gamma t)$. Perfect transfer first occurs at $t=\pi/(2\gamma)$. That value is an ideal evolution time, not a gate count.

An executable claim must state how the Hamiltonian is supplied, bound $\lVert H\rVert$, allocate simulation error, prepare the initial state, implement the marked potential, and measure the result. If the Hamiltonian is a physical interaction, calibration, control, and readout remain costs. If it is simulated by a circuit, oracle normalization, queries, gates, ancillas, and precision must be expanded through Hamiltonian Simulation Algorithms. The exact conversion between continuous and discrete walks developed by Childs is a mathematical construction with explicit overhead, not permission to call physical time a circuit depth.

Reversible Markov Chains and Szegedy Quantization

Time reversal, transition subspaces, and discriminant

Let $P=(p_{xy})$ be a finite irreducible row-stochastic Markov chain, so $p_{xy}$ is the probability of moving from $x$ to $y$. Let $\pi$ be stationary, $\pi^{\mathsf T}P=\pi^{\mathsf T}$, and define the time-reversed transition matrix by

$$\pi_xp_{xy}=\pi_yp^*_{yx}.$$

The coherent outgoing and reversed states are

$$\lvert p_x\rangle =\sum_y\sqrt{p_{xy}}\lvert y\rangle, \qquad \lvert p_y^*\rangle =\sum_x\sqrt{p^*_{yx}}\lvert x\rangle.$$

They define two subspaces of the doubled state space,

$$\mathcal A =\operatorname{span}\{\lvert x\rangle\lvert p_x\rangle\}, \qquad \mathcal B =\operatorname{span}\{\lvert p_y^*\rangle\lvert y\rangle\}.$$

With $R_{\mathcal A}=2\Pi_{\mathcal A}-I$ and $R_{\mathcal B}=2\Pi_{\mathcal B}-I$, the convention throughout this page is

$$W(P)=R_{\mathcal B}R_{\mathcal A}.$$

Operationally, reflecting about $\mathcal A$ requires coherently preparing and unpreparing each transition state $\lvert p_x\rangle$; reflecting about $\mathcal B$ requires the corresponding time-reversed access. Reversibility can simplify these circuits, but the abstract identity $P=P^*$ does not itself synthesize them. Preparing a classical random neighbor is insufficient: the transition amplitudes, their phases and the inverse preparation must be coherent.

The overlap between the two subspaces is encoded by the discriminant

$$D(P)_{xy}=\sqrt{p_{xy}p^*_{yx}}.$$

Substituting the time-reversal definition gives, even before assuming reversibility,

$$D(P) =\operatorname{diag}(\pi)^{1/2} P\operatorname{diag}(\pi)^{-1/2}$$

Thus $D(P)$ is similar to $P$. When detailed balance holds, $P=P^*$ and $D(P)$ is also symmetric; only then can its singular values be identified with the absolute values of its real eigenvalues. The coherent stationary state

$$\lvert\Pi\rangle =\sum_x\sqrt{\pi_x}\lvert x\rangle\lvert p_x\rangle$$

lies in the common stationary sector. Szegedy’s quantization turns these overlaps into eigenphases of a product of reflections.

From singular values to walk phases

Suppose a nontrivial singular value is $\sigma_j(D)=\cos\theta_j$ with $0<\sigma_j<1$. The associated principal two-dimensional subspace is invariant under both reflections. Their product is a rotation through twice the principal angle, so under the order $R_{\mathcal B}R_{\mathcal A}$ the walk eigenvalues are

$$e^{\pm2i\theta_j}.$$

Changing the reflection order conjugates these phases. The singular sectors at $1$ and $0$ require separate treatment. At singular value $1$, the subspaces intersect and include a zero-phase stationary direction. At singular value $0$, the principal angle is $\pi/2$ and the product acts in a degenerate phase-$\pi$ sector; forcing the generic paired notation onto either endpoint obscures multiplicities and invariant complements.

For a reversible ergodic chain, define the absolute spectral gap

$$\delta =1-\max_{\lambda\ne1}\lvert\lambda(P)\rvert.$$

The absolute value includes slowly decaying negative eigenvalues. Replacing $P$ by $(I+P)/2$ makes its spectrum nonnegative; this is the half-lazy convention used for the subset graph below. The smallest relevant nonzero walk phase satisfies

$$\Delta =2\arccos(1-\delta) \ge2\sqrt\delta, \qquad \Delta=\Theta(\sqrt\delta)$$

as $\delta\to0$. The square root is the spectral source of the walk-search improvement. It is not a statement that every classical hitting time is square-rooted: the marked overlap, setup, update, check, and output procedure still enter.

For a nonreversible chain, $D(P)$ remains similar to $P$ but generally is not symmetric, and its singular values need not equal the magnitudes of its eigenvalues. The MNRS extension requires a nonzero singular-value gap of $D(P)$; ordinary ergodicity alone does not guarantee that gap. Substituting an ordinary eigenvalue gap into the reversible theorem without proving the necessary spectral relationship is not justified. Even in the reversible case, a stated “gap” must say whether it is $1-\lambda_2$, an absolute gap, a singular-value gap, or the induced phase gap.

A two-state chain and an extra zero-phase vector

Consider

$$P= \begin{pmatrix} 3/4&1/4\\ 1/2&1/2 \end{pmatrix}.$$

The stationary distribution is $\pi=(2/3,1/3)$, and detailed balance makes the chain reversible. Its discriminant is

$$D= \begin{pmatrix} 3/4&1/(2\sqrt2)\\ 1/(2\sqrt2)&1/2 \end{pmatrix}.$$

It is positive symmetric with singular values $1$ and $1/4$. The nonstationary eigenvalue of $P$ is $1/4$, so the absolute gap is $3/4$, and the reflection order predicts phases $\pm2\arccos(1/4)$.

Constructing both transition isometries and multiplying their reflections gives the full walk, including the sector invisible to the discriminant’s nontrivial pair. In the ordered doubled basis $(\lvert00\rangle,\lvert01\rangle,\lvert10\rangle,\lvert11\rangle)$, its characteristic polynomial is

$$\chi_W(z) = \frac{(z-1)^2(4z^2+7z+4)}4.$$

Thus $W$ has the predicted conjugate pair and two $+1$ eigenvalues: the coherent stationary vector in $\mathcal A\cap\mathcal B$ and one vector in $\mathcal A^\perp\cap\mathcal B^\perp$. This finite example makes the invariant-subspace restriction in the search construction concrete.

The stationary vector and a normalized vector in the orthogonal complement are respectively

$$|\Pi\rangle=\frac{(\sqrt3,1,1,1)^{\mathsf T}}{\sqrt6}, \qquad |\chi\rangle=\frac{(1,-\sqrt3,-\sqrt3,\sqrt3)^{\mathsf T}}{\sqrt{10}}.$$

Both have eigenvalue $+1$. The second is orthogonal to every transition state in $\mathcal A$ and $\mathcal B$; a phase-zero test on an arbitrary ambient input therefore cannot distinguish it from the stationary state.

Search by Quantum Walk

Detection, finding, and the stationary reflection

Let $M$ be a marked subset of the Markov-chain state space. A coherent check may act as a phase oracle, multiplying $\lvert x\rangle$ by $-1$ exactly when $x\in M$, while preserving maintained data. Detection asks whether $M$ is empty. Finding asks for a classical marked state, and coherent production asks for a state supported substantially on $M$. Finding can imply detection after verification, but a detection routine that only produces a bit need not reveal a witness. A hitting-time statement must identify which task it solves.

For a reversible ergodic chain, the stationary state is the distinguished zero-phase direction in the relevant invariant subspace contained in $\mathcal A+\mathcal B$. That restriction matters: $\mathcal A^\perp\cap\mathcal B^\perp$ can contribute an additional $+1$ sector to the full product of reflections, so phase zero on the entire doubled Hilbert space does not by itself identify the stationary vector. The algorithm prepares and remains in the transition-generated invariant subspace. There an ideal stationary reflection preserves the stationary component and reverses the orthogonal components. Phase estimation can approximate this restricted operation by resolving phase zero from phases whose magnitudes are at least $\Delta$. The required phase resolution is therefore proportional to

$$\frac1\Delta=O\!\left(\frac1{\sqrt\delta}\right).$$

This argument explains the gap dependence. Implementing the reflection requires controlled walk steps, inverse uncomputation, phase workspace and sufficient precision, as developed in phase estimation. Alternating it with a markedness reflection then rotates amplitude toward the marked space. The log-free MNRS theorem uses a robust variable-precision construction; simply repeating one fixed-precision approximation introduces an extra logarithm in the straightforward error bound.

Under ideal exact markedness verification, one can use a one-sided decision convention: a returned witness is checked, so a negative instance never produces a false verified collision, while a positive instance may be missed with bounded probability. Approximate transitions and checks can spoil that property unless their errors are incorporated into the decision rule. “Bounded error” must therefore name which side can err and whether the claim concerns an ideal oracle algorithm or its approximate implementation.

The MNRS setup–update–check theorem

Let $P$ be a finite reversible ergodic chain. When $M\ne\varnothing$, suppose its stationary measure obeys $\pi(M)\ge\epsilon>0$, and let $\delta$ be the absolute spectral gap. The Magniez–Nayak–Roland–Santha framework assigns three costs:

• $S$ prepares the coherent stationary state together with all maintained data;
• $U$ implements coherent $P$ and $P^*$ transitions, including the inverses actually required by the walk; and
• $C$ implements a markedness phase check using the maintained data.

The bounded-error cost is

$$O\!\left[ S+ \frac1{\sqrt\epsilon} \left( \frac{U}{\sqrt\delta}+C \right) \right].$$

Theorem 3 of Search via Quantum Walk already finds a marked element, or reports that none exists, with a universal constant success probability under its hypotheses. It is stronger than a detection-only theorem. Repeating an independently verifiable procedure reduces failure to $\eta$ with a normally sufficient $O(\log(1/\eta))$ multiplicative factor. A more specialized amplification schedule may improve constants, but it must retain its own access and error conditions.

The formula is a typed cost expression, not a count of anonymous elementary operations. If $S,U,C$ are measured in value-oracle queries, the conclusion is in value-oracle queries. If each is a vector containing queries, gates, depth, and memory traffic, the expression can be evaluated componentwise only where the same coherent construction supports those currencies. Controlled transitions, inverse operations, phase resolution, clean work registers, and coherent data access remain implementation obligations. They cannot be inferred from a classical routine that samples one step of $P$.

Finding a marked state is therefore included in this bound. Extracting a different object encoded in that state can still require additional work. For element distinctness, the returned subset already contains queried values: recovering the colliding indices needs comparisons and readout, but no further value queries.

Element Distinctness on the Johnson Graph

Marked fraction and the lazy Johnson gap

Let the input be $x\in[q]^N$ with $q\ge N$, supplied by the coherent value oracle

$$O_x\lvert i,a,z\rangle = \lvert i,(a+x_i)\bmod q,z\rangle.$$

The extra register $z$ is workspace left unchanged by the query. We want to decide whether two distinct indices have the same value, and may also ask to produce such a pair. The assumption $q\ge N$ permits both outcomes: if $q<N$, the pigeonhole principle already settles the decision without any query, although finding a pair remains a separate task. Ambainis’s algorithm stores an $r$-subset $R\subset[N]$ and the associated values $\{x_i:i\in R\}$. A subset is marked if its cache contains two equal values.

Use the Johnson graph $J(N,r)$, whose vertices are $r$-subsets and whose edges exchange one selected index with one unselected index. The swap chain has degree $r(N-r)$ and the uniform stationary distribution. To use a nonnegative spectrum, take the half-lazy transition

$$P=\frac12(I+P_{\rm swap}), \qquad 2\le r\le\frac N2.$$

If the input contains a fixed colliding pair, the fraction of subsets containing both indices is

$$\epsilon =\frac{\binom{N-2}{r-2}}{\binom Nr} =\frac{r(r-1)}{N(N-1)}.$$

Additional collision pairs can only increase the marked fraction, so this is a valid lower bound without a unique-collision promise. The adjacency eigenvalues of the swap graph are

$$\theta_j =(r-j)(N-r-j)-j =r(N-r)-j(N-j+1).$$

After normalization by the degree and half-lazification, the eigenvalues become

$$\mu_j =1- \frac{j(N-j+1)}{2r(N-r)}.$$

The first nonstationary value is $\mu_1=1-N/[2r(N-r)]$. In the stated range, the lazy spectrum is nonnegative and no lower eigenvalue has larger absolute value, so

$$\delta =\frac{N}{2r(N-r)}.$$

These exact combinatorial and spectral identities are the bridge from the chosen data structure to the MNRS theorem. Replacing the Johnson walk by a different subset update changes the gap and requires a new spectral calculation.

Optimizing subset size and query cost

Preparing the stationary cache queries $r$ values, so $S=\Theta(r)$. A coherent exchange updates only constantly many cached values, giving $U=\Theta(1)$ value-query cost under the standard cached-update convention. Once values are stored, detecting a duplicate uses $C=0$ additional value queries, although comparison networks, routing, flags, and their inverses still use gates and workspace. Substitution gives

$$\begin{aligned} S+\frac{U}{\sqrt{\epsilon\delta}} &=\Theta\!\left( r+ \sqrt{\frac{2(N-1)(N-r)}{r-1}} \right)\\ &=\Theta\!\left(r+\frac N{\sqrt r}\right). \end{aligned}$$

Balancing $r$ with $N/\sqrt r$ gives $r=\Theta(N^{2/3})$ and total bounded-error value-query complexity $\Theta(N^{2/3})$. The construction is due to Ambainis. The lower bound of Aaronson and Shi, extended to all ranges $q\ge N$ by Ambainis, shows that this scaling is optimal in the quantum value-query model. Optimal query scaling does not imply that the cached data structure, coherent comparisons, or fault-tolerant implementation is optimal.

For the finite substitution $N=64$, $r=16$,

$$\epsilon=\frac5{84}, \qquad \delta=\frac1{24}, \qquad \Delta=2\arccos\frac{23}{24},$$

and

$$\frac1{\sqrt{\epsilon\delta}} =12\sqrt{\frac{14}{5}}, \qquad 16+12\sqrt{\frac{14}{5}} \approx36.0798406368.$$

The last number is a finite parameter substitution inside an asymptotic cost theorem under a unit-cost update convention. It is not an exact integer query count. If a reversible cache replacement is priced at two oracle calls, the same substitution becomes

$$16+24\sqrt{\frac{14}{5}} \approx56.1596812736.$$

The exponent is unchanged, but the two numbers price the update differently. Storing $r$ indices and $r$ values already needs at least

$$r\bigl(\lceil\log_2N\rceil+\lceil\log_2q\rceil\bigr)$$

logical data qubits in a straightforward representation, before subset-ordering data, the walk coin, collision flags, routing workspace, and error correction. Reporting the query theorem without this memory boundary would misdescribe what must be executed.

Spatial Search and Oracle Traversal Are Model-Dependent

Spatial-search results depend sharply on graph dimension, degree, boundary conditions, locality, marked multiplicity, marking geometry, coin choice, self-loops, initial state, access, and whether the task is detection or finding. The search Hamiltonian $-\gamma A-\lvert w\rangle\langle w\rvert$ does not have the same avoided crossing or marked-state overlap on every graph. Childs and Goldstone found $O(\sqrt N)$ continuous-time search with constant-order success for their periodic-lattice construction when $d>4$. At the critical dimension $d=4$, the fixed-Hamiltonian evolution lasts $\Theta(\sqrt{N\log N})$ but reaches the mark with only $\Theta(1/\log N)$ probability. Independent verified repetition therefore costs $O(\sqrt N\log^{3/2}N)$, while amplitude amplification can give $O(\sqrt N\log N)$ only when the required reflection and inverse access are licensed. For $d<4$, that construction gives no substantial speedup. These are not generic bounds for graphs of order $N$.

Discrete coined search has equally specific hypotheses. Shenvi, Kempe, and Whaley analyzed a unique marked item on the hypercube with a particular coin and symmetry reduction. For a two-dimensional grid with one marked vertex, Ambainis, Kempe, and Rivosh obtained $O(\sqrt N\log N)$ steps under their coined-walk conventions. Tulsi’s ancilla-controlled modification improves the two-dimensional scaling to $O(\sqrt{N\log N})$. The logarithm, ancilla, start state, marked multiplicity, boundary conditions, and readout procedure cannot be dropped when transplanting either result to another lattice.

Traversal gives a different lesson. Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman constructed a continuous-time walk that traverses an implicitly supplied glued-tree graph with an exponential oracle separation from classical algorithms in that problem. The instance is not an arbitrary explicit graph: its layered structure is promised while vertex labels are hidden behind an adjacency oracle. The output is the exit label reached from the entrance. The result is therefore evidence that coherent propagation can exploit a specially promised oracle graph, not a theorem of generic exponential advantage for graph search, shortest paths, or explicit adjacency lists.

From Walk Queries to Executable Resources

Approximation errors accumulate through the actual sequence. For unitary ideal and implemented discrete steps obeying $\lVert\widetilde W-W\rVert\le\varepsilon_{\rm step}$, telescoping gives

$$\begin{aligned} \widetilde W^T-W^T &=\sum_{j=0}^{T-1} \widetilde W^{T-1-j}(\widetilde W-W)W^j,\\ \lVert\widetilde W^T-W^T\rVert &\le T\lVert\widetilde W-W\rVert \le T\varepsilon_{\rm step}. \end{aligned}$$

For normalized initial states, the final state-vector difference is at most $T\varepsilon_{\rm step}$. If $\Pi_M$ is the declared success projector, expanding the difference of quadratic forms gives the conservative probability bound

$$\left| \langle\widetilde\psi\rvert\Pi_M\lvert\widetilde\psi\rangle -\langle\psi\rvert\Pi_M\lvert\psi\rangle \right| \le2T\varepsilon_{\rm step}.$$

This worst-case linear estimate may be loose, but replacing it by an assumed incoherent square-root law would be unjustified. Stationary-state preparation error, transition-state preparation error, inverse mismatch, marked-check error, phase-resolution error, and final sampling error should be bounded separately before combining them.

Continuous-time implementations have their own budgets. For Hermitian $H$ and $\widetilde H$ under a common time convention, a Duhamel estimate gives

$$\lVert e^{-it\widetilde H}-e^{-itH}\rVert \le |t|\lVert\widetilde H-H\rVert.$$

A simulation algorithm then adds approximation and synthesis error beyond any modeling error in the generator. The norm, time, target precision, oracle normalization, and failure probability all influence circuit resources. Physical evolution for time $t$ and a digital approximation of $e^{-itH}$ are different resource statements even when their ideal unitaries coincide.

An update that uses only two input queries can still need many reversible comparisons, routing operations and memory qubits. Report those costs separately when turning a query theorem into a circuit estimate. Likewise, cached data can make a markedness check cost zero input queries without making its circuit free.

If one independent verified trial succeeds with probability at least a constant $p_0>0$, then $k$ failures have probability at most $(1-p_0)^k$, so $k=O(\log(1/\eta))$ suffices for failure at most $\eta$. Coherent amplification can have a different dependence, but requires accurate reflections and inverse operations. Sampling an unverified bit and taking a majority may instead produce two-sided errors.

Finally, a matched comparator receives the same input representation, promise, output information, and error criterion. Comparing a quantum neighbor oracle with a classical explicit adjacency matrix, or a quantum decision bit with a classical list of all collisions, does not isolate the walk’s contribution. Query Complexity supplies the general discipline for these comparisons; the present page specializes it to walk access and outputs.

The reflection-based search uses amplitude amplification and phase estimation. Block encodings and QSVT provides related operator transformations; quantum algorithms for optimization applies walk and tree-search methods to optimization tasks. These connections do not identify the generic graph walk with the specialized Hamiltonian signal walk of qubitization.

Computing the four-cycle distributions

This short NumPy example constructs the complete eight-dimensional unitary in the order $(|L,0\rangle,|R,0\rangle,\ldots,|L,3\rangle,|R,3\rangle)$. Propagating amplitudes before squaring them reproduces the interference above.

import numpy as np

H = np.array([[1., 1.], [1., -1.]])/np.sqrt(2)
C = np.kron(np.eye(4), H)
S = np.zeros((8, 8))
for x in range(4):
    S[2*((x-1) % 4), 2*x] = 1
    S[2*((x+1) % 4)+1, 2*x+1] = 1
U = S @ C
psi = np.eye(8)[0]
for t in range(5):
    print(t, np.sum(abs(psi.reshape(4, 2))**2, axis=1))
    psi = U @ psi

The position distributions are $(1,0,0,0)$, $(0,1/2,0,1/2)$, $(1/2,0,1/2,0)$, $(0,0,0,1)$ and $(0,0,1,0)$. Replacing amplitudes by probabilities after every update would instead remove the relative signs responsible for the last two rows.

Common pitfalls

A faster-spreading wave packet is not yet a faster algorithm. A variance describes a distribution, not a computational answer. A speedup also requires a specified input representation, requested output, success probability and cost comparison.

The same graph can support different walks. Coin choice, moving versus flip-flop shift, adjacency versus Laplacian, marking and measurement can each change the spectrum or output. Keep these choices with any quoted result.

Physical time, queries and gates measure different resources. A continuous evolution time requires an energy scale; a query bound assumes specified coherent input operations. Neither alone gives the cost of a complete device implementation.

Exercises

1. Unitarity of a coined step. Let $C=\bigoplus_v C_v$ with every $C_v$ unitary, and let $S\lvert v,w\rangle=\lvert w,v\rangle$. Prove that $C$, $S$, and $SC$ are unitary. Identify what fails if a proposed “shift” erases the incoming vertex label.

Solution

The arc space is an orthogonal direct sum of the outgoing subspaces at each vertex. Therefore

$$C^\dagger C =\bigoplus_v C_v^\dagger C_v =\bigoplus_v I_v =I_{\rm arc}.$$

The shift permutes the directed-edge basis and satisfies $S^2=I$, hence $S^{-1}=S=S^\dagger$. It follows that

$$(SC)^\dagger(SC) =C^\dagger S^\dagger SC =C^\dagger C =I_{\rm arc}.$$

If a map sends $\lvert v,w\rangle$ only to $\lvert w\rangle$, then distinct incoming arcs can acquire the same output. The map is not injective, does not preserve inner products, and cannot be a unitary shift. A reversible implementation must retain enough direction or workspace information to reconstruct the input.

2. Measurement inside the four-cycle walk. Verify the coherent fourth-step state in the worked example. Then measure the complete coin-position basis immediately after step two, discard the outcome, and take one more step. Find the resulting position distribution and compare it with the unmeasured third step.

Solution

At step three the state is $(\lvert L,3\rangle+\lvert R,3\rangle)/\sqrt2$. The Hadamard coin maps $(\lvert L\rangle+\lvert R\rangle)/\sqrt2$ to $\lvert L\rangle$, and the moving shift sends $\lvert L,3\rangle$ to $\lvert L,2\rangle$. Thus $\lvert\psi_4\rangle=\lvert L,2\rangle$.

At step two, the four basis states $\lvert L,0\rangle$, $\lvert R,0\rangle$, $\lvert L,2\rangle$, and $\lvert R,2\rangle$ each have probability $1/4$. A complete measurement removes all relative phases. From either coin basis state at vertex $0$, the next Hadamard and shift distribute probability equally between vertices $3$ and $1$. The same is true from vertex $2$, with the directions interchanged. Averaging the four incoherent branches yields

$$(p_0,p_1,p_2,p_3)=(0,1/2,0,1/2).$$

Without measurement, interference instead gives $(0,0,0,1)$. With position-only measurement, the two remaining coin states at step two are $|+\rangle$ at vertex $0$ and $|-\rangle$ at vertex $2$, each with probability $1/2$. The next coin and shift send both branches to vertex $3$, one with coin $L$ and the other with coin $R$. The position distribution is therefore still $(0,0,0,1)$, but the coin is mixed. At step four it gives $(1/2,0,1/2,0)$ rather than the coherent $(0,0,1,0)$.

3. Two-vertex continuous-time transfer. Starting from $H=-\gamma X$ and $\lvert0\rangle$, derive the exact state, both vertex probabilities, and the first perfect-transfer time. Verify normalization without diagonalizing $X$.

Solution

Because $X^2=I$, even and odd powers separate in the exponential series:

$$e^{i\gamma tX} =\sum_{m=0}^\infty\frac{(i\gamma t)^{2m}}{(2m)!}I +\sum_{m=0}^\infty\frac{(i\gamma t)^{2m+1}}{(2m+1)!}X =\cos(\gamma t)I+i\sin(\gamma t)X.$$

Applying this to $\lvert0\rangle$ gives

$$\lvert\psi(t)\rangle =\cos(\gamma t)\lvert0\rangle +i\sin(\gamma t)\lvert1\rangle.$$

Hence $p_0(t)=\cos^2(\gamma t)$ and $p_1(t)=\sin^2(\gamma t)$. Their sum is one by the trigonometric identity, which verifies normalization. The first positive time with $p_1=1$ is $\gamma t=\pi/2$, or $t=\pi/(2\gamma)$ for $\gamma>0$.

4. Adjacency versus Laplacian evolution. Prove that adjacency and Laplacian conventions can be matched up to a global phase on a $k$-regular graph. Use the three-vertex path to show why the same argument fails on an irregular graph.

Solution

For a $k$-regular graph, $D=kI$ and $L=kI-A$. Comparing $H_A=-\gamma A$ with $H_L=\gamma L$ gives $H_L=\gamma kI+H_A$. Since the identity commutes with $H_A$,

$$e^{-itH_L} =e^{-i\gamma kt}e^{-itH_A}.$$

The prefactor multiplies every amplitude by the same phase and cannot change any measurement probability. For the path $0$–$1$–$2$,

$$D=\operatorname{diag}(1,2,1),$$

which is not a scalar multiple of the identity. The difference $H_L-H_A=\gamma D$ therefore assigns a different diagonal energy to the middle vertex. It changes relative phases and cannot be factored out globally. An initial superposition involving the middle vertex and an endpoint distinguishes the two evolutions at arbitrarily short nonzero time.

5. Explicit Szegedy phase-gap bounds. Let $0\le\delta\le1$ and $\Delta=2\arccos(1-\delta)$. Derive explicit upper and lower square-root bounds and recover the weaker lower bound used in the search discussion.

Solution

Write $x=\arccos(1-\delta)$. The half-angle identity gives

$$\delta=1-\cos x=2\sin^2(x/2),$$

so

$$\Delta=2x =4\arcsin\sqrt{\frac\delta2}.$$

For $0\le y\le1$, $y\le\arcsin y\le(\pi/2)y$. Substituting $y=\sqrt{\delta/2}$ yields

$$2\sqrt{2\delta} \le\Delta \le\pi\sqrt{2\delta}.$$

In particular $\Delta\ge2\sqrt\delta$, as quoted on the page, and the two bounds prove $\Delta=\Theta(\sqrt\delta)$ near zero. Constants depend on the convention $W=R_{\mathcal B}R_{\mathcal A}$; defining the phase as the principal angle rather than the product-reflection angle changes them by a factor of two.

6. Complete mixing and Grover scaling. Apply the MNRS theorem to the chain $p_{xy}=1/N$ with $m$ marked states. Assume ideal uniform-state preparation and unit-cost update and check. Show that its marked-fraction and gap dependence reduces to Grover scaling.

Solution

Every row of $P$ is uniform, so $\pi_x=1/N$. The stationary eigenvalue is one and every vector orthogonal to the uniform vector has eigenvalue zero. Thus the absolute gap is $\delta=1$. If there are $m$ marked states, then $\epsilon=\pi(M)=m/N$.

With $S,U,C=O(1)$ under the exercise’s ideal access assumptions, MNRS gives

$$O\!\left[ 1+\sqrt{\frac Nm}(1+1) \right] =O\!\left(\sqrt{\frac Nm}\right).$$

This matches Grover’s query scaling. It does not replace Grover’s exact rotation theorem: the constant factors, state preparation, and implementation of a complete-mixing transition are model dependent. The reduction only shows that the walk-search cost expression contains unstructured search as the unit-gap special case.

7. Johnson parameters and repricing. Derive the marked fraction and lazy gap for the $r$-subset walk, optimize the standard query expression, and then state how update cost $u$ and checking cost $c$ change it. Evaluate the $N=64,r=16$ walk contribution for $u=2$ and $c=0$.

Solution

For a fixed colliding pair, choose the other $r-2$ indices from $N-2$ possibilities. Dividing by all $r$-subsets gives

$$\epsilon =\frac{\binom{N-2}{r-2}}{\binom Nr} =\frac{r(r-1)}{N(N-1)}.$$

The first nontrivial swap-chain adjacency eigenvalue is $r(N-r)-N$. After division by $r(N-r)$ and half-lazification,

$$\mu_1 =1-\frac{N}{2r(N-r)}, \qquad \delta=\frac{N}{2r(N-r)}.$$

For constant update cost and zero value-query check cost,

$$r+\frac1{\sqrt{\epsilon\delta}} =\Theta\!\left(r+\frac N{\sqrt r}\right).$$

Balancing the terms gives $r^{3/2}=\Theta(N)$ and hence $r=\Theta(N^{2/3})$. With general costs, the input-query expression is

$$\Theta\!\left( r+u\frac N{\sqrt r}+c\frac N r \right)$$

in the regime $r\ll N$. Thus an expensive check can change the optimum rather than merely its constant. For $N=64,r=16$, $1/\sqrt{\epsilon\delta}=12\sqrt{14/5}$. Setting $u=2$ and $c=0$ makes the walk contribution $24\sqrt{14/5}\approx40.1596812736$ and the setup-plus-walk proxy approximately $56.1596812736$.

8. A hidden collision and the classical comparison. Suppose $q\ge N$. A positive input has exactly one colliding pair, with its two positions uniformly hidden among the $\binom N2$ possibilities and its distinct values otherwise randomly relabeled. Compare it with a uniformly relabeled injective input. After $k$ distinct classical value queries, what is the probability of having exposed both positions? Explain why bounded-error decision needs $k=\Omega(N)$ in this family, and compare this with the quantum walk. What changes in the decision problem when $q<N$?

Solution

Until the second member of the collision is queried, the observed values are distinct, and their random labels reveal no preferred location for the hidden partner. Adaptivity therefore does not improve the probability of exposing the pair:

$$p_{\rm pair}=\frac{\binom k2}{\binom N2} =\frac{k(k-1)}{N(N-1)}.$$

Conditioned on not exposing the pair, the distribution of queried values agrees with that of the randomly relabeled injective input. With equal prior probabilities for the two families, the best success probability is $(1+p_{\rm pair})/2$. Success at least $2/3$ requires $p_{\rm pair}\ge1/3$, hence $k=\Omega(N)$. Querying every entry gives the matching linear upper bound.

The quantum $\Theta(N^{2/3})$ value-query result is therefore a polynomial improvement for this decision problem. Its cache, coherent updates and comparison gates remain additional resources. If $q<N$, every input contains a collision by the pigeonhole principle, and the decision has a zero-query answer; this does not automatically output colliding indices.

References

• S. Aaronson and Y. Shi, “Quantum Lower Bounds for the Collision and the Element Distinctness Problems,” Journal of the ACM 51(4), 595–605 (2004), doi:10.1145/1008731.1008735.
• D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani, “Quantum Walks on Graphs,” in Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 50–59 (2001), doi:10.1145/380752.380758.
• A. Ambainis, “Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range,” Theory of Computing 1, 37–46 (2005), doi:10.4086/toc.2005.v001a003.
• A. Ambainis, “Quantum Walk Algorithm for Element Distinctness,” SIAM Journal on Computing 37(1), 210–239 (2007), doi:10.1137/S0097539705447311.
• A. Ambainis, J. Kempe, and A. Rivosh, “Coins Make Quantum Walks Faster,” in Proceedings of the Sixteenth Annual ACM–SIAM Symposium on Discrete Algorithms, 1099–1108 (2005), doi:10.1145/1070432.1070590.
• A. M. Childs, “On the Relationship Between Continuous- and Discrete-Time Quantum Walk,” Communications in Mathematical Physics 294, 581–603 (2010), doi:10.1007/s00220-009-0930-1.
• A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, “Exponential Algorithmic Speedup by a Quantum Walk,” in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 59–68 (2003), doi:10.1145/780542.780552.
• A. M. Childs and J. Goldstone, “Spatial Search by Quantum Walk,” Physical Review A 70, 022314 (2004), doi:10.1103/PhysRevA.70.022314.
• E. Farhi and S. Gutmann, “Quantum Computation and Decision Trees,” Physical Review A 58, 915–928 (1998), doi:10.1103/PhysRevA.58.915.
• F. Magniez, A. Nayak, J. Roland, and M. Santha, “Search via Quantum Walk,” SIAM Journal on Computing 40(1), 142–164 (2011), doi:10.1137/090745854.
• N. Shenvi, J. Kempe, and K. B. Whaley, “Quantum Random-Walk Search Algorithm,” Physical Review A 67, 052307 (2003), doi:10.1103/PhysRevA.67.052307.
• M. Szegedy, “Quantum Speed-Up of Markov Chain Based Algorithms,” in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 32–41 (2004), doi:10.1109/FOCS.2004.53.
• A. Tulsi, “Faster Quantum-Walk Algorithm for the Two-Dimensional Spatial Search,” Physical Review A 78, 012310 (2008), doi:10.1103/PhysRevA.78.012310.