Applications of Quantum Walks

Quantum walks are not merely a theoretical curiosity. They serve as the algorithmic engine behind several concrete quantum speedups, and they provide a unified design framework for building new quantum algorithms. This lesson surveys the most important applications.

Element distinctness

The element distinctness problem asks: given $n$ numbers $x_1, x_2, \ldots, x_n$ , are any two equal? Classically, the best deterministic algorithm requires $\Theta(n)$ queries to the list; randomized algorithms offer no asymptotic improvement.

Ambainis showed in 2003 that a quantum walk on a Johnson graph solves element distinctness with only $O(n^{2/3})$ queries — an exponential improvement in the query exponent. The key idea is to walk over subsets of indices of size $r$ , storing the corresponding values. The walk has a marked vertex whenever the stored subset contains a collision ( $x_i = x_j$ for $i \neq j$ ). By tuning the subset size to $r = n^{2/3}$ , the walk finds the collision in $O(n^{2/3})$ steps.

This result is tight: no quantum algorithm can solve element distinctness in $o(n^{2/3})$ queries.

Triangle finding

The triangle finding problem asks whether an $n$ -vertex graph contains a triangle (three mutually adjacent vertices). Classical algorithms based on fast matrix multiplication run in $O(n^{2.37})$ time; query-complexity lower bounds show any quantum algorithm needs at least $\Omega(n)$ queries.

Quantum walk algorithms achieve $O(n^{1.3})$ quantum queries. The construction nests a Grover-style amplitude amplification around a quantum walk on the Johnson graph, letting the algorithm detect triangles faster than repeatedly scanning adjacency lists.

Spatial search on graphs

Classical random walks are used for searching graphs: run the walk and test each visited vertex. The hitting time from a start vertex to the marked target governs the cost. On an $n$ -vertex graph, classical hitting times can be $\Theta(n)$ or worse.

Childs, Farhi, and Gutmann showed that the continuous-time quantum walk on certain graphs achieves optimal $O(\sqrt{n})$ hitting time, matching the Grover lower bound for unstructured search. For the $\sqrt{n} \times \sqrt{n}$ grid graph specifically, the quantum walk locates a marked vertex in $O(\sqrt{n} \log n)$ steps (within a logarithmic factor of optimal), whereas the classical cover time is $\Theta(n \log n)$ .

The spatial search result is conceptually satisfying: Grover's algorithm is a quantum walk on a complete graph. Other graph topologies generalize Grover to structured spaces.

NAND tree evaluation

A NAND tree of depth $d$ is a binary tree whose leaves are Boolean variables; each internal node computes the NAND of its two children. Evaluating the root requires reading some leaves, and the question is: how many leaf queries are needed?

Farhi, Goldstone, and Gutmann showed that a continuous-time quantum walk on the NAND tree evaluates it with $O(n^{0.5})$ quantum queries, beating the classical deterministic bound of $\Theta(n)$ and the classical randomized bound of $\Theta(n^{0.793})$ (Saks and Wigderson). The quantum walk achieves this by exploiting the tree's recursive structure and the interference of amplitudes propagating from the root to the leaves.

Matrix product verification

Given three matrices $A$ , $B$ , and $C$ of size $n \times n$ , the matrix product verification problem asks whether $AB = C$ . A quantum walk algorithm verifies this in $O(n^{5/3})$ quantum queries to the matrix entries, improving on both the classical $O(n^2)$ bound and earlier quantum approaches.

A unifying framework: MNRS and the quantum walk framework

Many of these results follow a common template formalized by Magniez, Nayak, Roland, and Santha (MNRS). Given a Markov chain on a graph, the MNRS framework lifts it to a quantum walk operator whose spectral gap controls the cost of finding marked vertices. The total complexity is

$T_{\text{walk}} = S + \frac{1}{\sqrt{\epsilon}}\left(\frac{1}{\sqrt{\delta}} \cdot U + C\right),$

where $S$ is the setup cost, $\epsilon$ is the fraction of marked vertices, $\delta$ is the spectral gap of the walk, $U$ is the per-step update cost, and $C$ is the checking cost per vertex. Plugging in the parameters of the Johnson graph reproduces the element distinctness bound; plugging in the grid reproduces spatial search.

Summary table

| Problem | Classical queries | Quantum walk queries | |---|---|---| | Element distinctness ( $n$ elements) | $\Theta(n)$ | $O(n^{2/3})$ | | Triangle finding ( $n$ vertices) | $O(n^{2.37})$ (time) | $O(n^{1.3})$ | | Spatial search ( $n$ nodes) | $\Theta(n)$ | $O(\sqrt{n}\log n)$ | | NAND tree (depth $d$ , $n = 2^d$ leaves) | $\Theta(n^{0.793})$ rand. | $O(\sqrt{n})$ | | Matrix product verification ( $n \times n$ ) | $O(n^2)$ | $O(n^{5/3})$ |

The consistent theme is a square-root or fractional-power improvement in query complexity, tracing directly to the ballistic spreading of quantum walks that was explored in earlier lessons.

Quantum walks also appear as subroutines in quantum chemistry (preparing ground states) and topological data analysis (persistent homology estimation), underscoring their role as a broadly applicable primitive in the quantum algorithm designer's toolbox.