Algorithm Zoo · Primitives
Quantum Walks
First described: Aharonov, Ambainis, Kempe, Vazirani (continuous); Ambainis (discrete), 2003
The problem
Walk on a graph quantumly — used as a primitive for search, element-distinctness, and matrix algorithms.
Discrete-time: coin-flip plus shift operator on an edge-set Hilbert space. Continuous-time: e^{-iAt} with A the graph adjacency or Laplacian. Both achieve quadratic speedup over classical random walks on hitting time.
Best classical
Random walks, label-propagation, eigenvector-centrality computation.
Quantum complexity
O(√N) hitting time on regular graphs vs O(N) classical for many graph families.
Our verdict
A clean primitive that underlies a lot of quantum algorithms (element distinctness, spatial search, k-distinctness). The asymptotic speedup is real and the framework is elegant. Like much of QC, the engineering pain is in the oracle/block-encoding construction, not in the walk itself.
When to use it
- Element distinctness — Ambainis O(N^{2/3}) algorithm.
- Spatial search on graphs — quadratic speedup over Grover for low-connectivity graphs.
- Inside QSVT-based algorithms — quantum walks naturally embed graphs as block encodings.
When not to use it
- When the graph has structure classical algorithms exploit (planar graphs, bounded-degree, etc.).
- When data loading dominates — same QML caveat as elsewhere.
Classical baseline
Modern graph algorithms (BFS, PageRank, betweenness centrality) are extremely fast in practice. The asymptotic advantage of quantum walks is real but rarely the bottleneck of a real-world graph workload.
Hardware cost
Depends on graph encoding. Discrete-time walks need O(log E) qubits for E edges. Continuous-time walks need Hamiltonian simulation of the adjacency matrix.
Key papers
- Quantum Walks on Graphs ↗
Aharonov, Ambainis, Kempe, Vazirani · 2001 · STOC
- Quantum walk algorithm for element distinctness ↗
Ambainis · 2007 · SIAM J. Computing
Deep-dive tutorials
Last verified: 2026-05-24