arXiv:2610.23560
Electrostatic Limits on Quantum Spatial Search
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.
AI Summary
Can a quantum walker search a two-dimensional lattice in Grover time despite nearest-neighbour locality? The paper proves an $\Omega(\sqrt{N\log N})$ lower bound for finding one marked vertex on an $L\times L$ lattice, $N=L^2$, matching Tulsi’s algorithm. The bound counts local unitary steps, allows unlimited internal workspace and time- and position-dependent operations, and grants oracle queries for free. It holds for fixed nonzero success probability, on both periodic and open lattices. The proof tracks the overlap between marked and unmarked executions, weighted by an electrostatic potential drop that vanishes at the marked vertex. Queries therefore leave this quantity unchanged, while locality bounds its change per step through the weight’s Dirichlet energy. The graph Green function optimizes the mean-to-energy ratio. On the square torus its self-potential is $A=(\ln L)/(2\pi)+O(1)$, producing the logarithmic overhead. More generally, the method gives lower bounds governed by classical hitting time on vertex-transitive graphs, subject to an endpoint-error condition; for bounded degree and a stated spectral condition, the bound is $\Omega(\sqrt{t_{\rm hit}})$. For multiple marks, conductor capacitance controls the bound. In the sparse regime $k=o(N)$, matching bounds distinguish periodic subgrids, $\Theta(\sqrt{(N/k)\log(N/k)})$, from worst-case placements, $\Theta(\sqrt{N\log(N/k)})$, for known $k$. The model concerns a single local walker with oracle action confined to marked sites. Multiple walkers, long-range hopping, nonlinear dynamics, or spatially extended oracle fields fall outside these assumptions. Extensions to non-transitive graphs, unknown mark counts, and dense or typical random marked sets remain open.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.