Speedup in quantum spatial search finally resolved

Imagine you are heading toward the city centre, knowing there are several good pizzerias there. Without a map or navigation system, you don’t know the best route, so you simply pick a street at random and keep walking until you find one. How long might that take? This is the essence of the spatial search problem: given a network (graph) of locations and connections, how long does it take to find a “marked” location (like a pizzeria) when you can only move locally along the links?

In a recent work, Simon Apers (IRIF, Paris), Shantanav Chakraborty (IIIT Hyderabad), Leonardo Novo (ULB Brussels), and Jérémie Roland (ULB Brussels) have shown that quantum computers can solve this task faster than any classical computer. On a quantum computer, the search is performed via a continuous-time quantum walk on the graph: a quantum wave that propagates along all links simultaneously, in superposition. For nearly two decades, it was unknown whether such quantum walks offer a general advantage for spatial search. Earlier results showed speedups only in special cases—for example, with a single marked node or for very specific graph topologies.

This new result closes the question by proving that a purely continuous-time quantum walk achieves a quadratic speedup for spatial search on any graph, with any number of marked nodes. Beyond resolving a long-standing open problem, the work also points to a broader design principle for near-term quantum algorithms: it shows that coupling discrete quantum systems with simple continuous-variable systems can lead to new, physically natural algorithms for optimization and machine learning that are simpler than many existing approaches. In this way, the result not only settles a fundamental question in quantum computing theory, but also opens up promising avenues for practical, analog quantum algorithms.

Publication: S. Apers, S. Chakraborty, L. Novo, and J. Roland, Quadratic speedup for spatial search by continuous-time quantum walk, Physical Review Letters 129, 160502 (2022). arXiv. Presented as a talk at the 17th Conference on Theory of Quantum Computing, Communication and Cryptography (TQC 2022).