Electrostatic Limits on Quantum Spatial Search
Abstract
We prove that a quantum walker cannot search a two-dimensional lattice in Grover's O(√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× L lattice, N=L2, needs Ω(√(Nlog 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.
Related
- Quantum-classical algorithm interpolation for spatial search
- Application and Performance Assessment of Annealing Methods for Electrostatic-Energy-Based Configuration Search in Mixed Crystals
- Quantum transport and unified scaling law in graphene with polyadic Cantor electrostatic barriers
- Electrostatic Stabilization of Near-Surface Quantum Sensors via Dielectric Interface Engineering
- Electrostatic Control Enables Robust Helical Edge Channel Transport in III-V Quantum Spin Hall Insulators
BibTeX
@misc{li2026electrostatic,
title = {{Electrostatic Limits on Quantum Spatial Search}},
author = {Weikang Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.23560},
eprint = {2610.23560},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.23560},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Electrostatic Limits on Quantum Spatial Search
AU - Weikang Li
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.23560
UR - https://arxiv.org/abs/2610.23560
AB - We prove that a quantum walker cannot search a two-dimensional lattice in Grover's O(√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× L lattice, N=L^2, needs Ω(√(Nlog 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.
ER -