Quantum spatial search on grids needs more steps than grover says
Electrostatic Limits on Quantum Spatial Search
Computational Complexity
Summary
Finding a special spot in a grid using quantum methods is slower than previously hoped. The authors show it takes a bit more time, which means some quantum search strategies are the fastest possible. They figured this out by thinking about how electric charges and potentials behave in physics, which helped explain why the search can't be sped up more. This solves a puzzle experts have wondered about for over 20 years.
What this means in practice
- •For quantum algorithm designers: Avoid designing quantum grid search algorithms claiming runtimes faster than the established lower bound that includes a logarithmic slowdown factor.
- •For quantum hardware engineers: Value realistic performance expectations for quantum spatial search on two-dimensional hardware layouts, avoiding overly optimistic speedups.
A theory result. No direct application yet.
Authors
Weikang Li
Abstract
We prove that a quantum walker cannot search a two-dimensional lattice in Grover's $O(\sqrt N)$ time, resolving the long-standing open question posed by Aaronson and Ambainis in 2003. A walker that hops between neighbouring sites of an $L\times L$ lattice, $N=L^2$, needs $Ω(\sqrt{N\log N})$ local steps at least to find a marked vertex, even with unlimited memory and free queries. Hence, Tulsi's algorithm is asymptotically optimal. Our proof rests on a surprising correspondence with classical electrostatics. We treat the marked vertex as a point charge and weight the overlap between the walker's states with and without the mark by the potential drop, which vanishes where queries act. Only local steps change this weighted overlap, at a rate limited by the field energy, so the lower bound is set by the self-potential of the charge. In the plane this self-potential grows logarithmically with system size, like the Coulomb potential, leading to the extra root-logarithmic factor. Several marked vertices turn the charge into a conductor, and the lower bound depends on their arrangement through its capacitance.