PaperfootJoin free
arXiv

Quantum search on a two-dimensional grid faces a speed limit

A proof shows that a quantum walker hopping across a two-dimensional grid needs extra steps to find a target, resolving an open question from 2003.

Paper by Weikang Li
Figure 1. Electrostatic bound. (a) Potential drop B_m​(x)=A−K⁡(x,m), the Dirichlet-optimal weight of the overlap, on a 41×41 torus in units of A, with contours at B_m/A=0.5, 0.75 and 1 and white lines along…
Open the figure at full size
Figure 1. Electrostatic bound. (a) Potential drop B_m​(x)=A−K⁡(x,m), the Dirichlet-optimal weight of the overlap, on a 41×41 torus in units of A, with contours at…Electrostatic bound. (a) Potential drop B_m​(x)=A−K⁡(x,m), the Dirichlet-optimal weight of the overlap, on a 41×41 torus in units of A, with contours at B_m/A=0.5, 0.75 and 1 and white lines along every fourth row and column.Li, CC BY
Preprint: theory

Edited by Boris Djordjevic · Paperfoot

Paper

In a preprint reporting a theory result, the authors proved that a quantum walker hopping between neighboring sites of a two-dimensional lattice cannot search the grid in Grover's search time. This proof resolves an open question posed by Aaronson and Ambainis in 2003. For an L by L lattice with N sites, the walker needs at least a number of local steps proportional to the square root of N log N to find a marked vertex, even with unlimited memory and free queries. The result shows that an existing method, Tulsi's algorithm, is asymptotically optimal.

The proof connects quantum spatial search to classical electrostatics, the physics of electric charges. Treating the marked vertex as a point charge reveals a lower bound—a limit no algorithm can beat—set by the charge's self-potential. When multiple vertices are marked, the limit depends on their arrangement through capacitance.

Why it matters

The mathematical proof settles a question open since 2003 by establishing the absolute speed limit for quantum search on two-dimensional grids. By proving that Tulsi's algorithm is optimal, it shows that no quantum walker can overcome the extra logarithmic time penalty when moving across a flat lattice.

Caveats

The result is a mathematical proof that applies specifically to quantum walkers hopping between neighboring sites on a two-dimensional lattice. The paper is also a preprint that has not yet been peer-reviewed.

In this paper

Methods
Tulsi's algorithm (evaluated)

What it shows

A quantum walker needs at least Ω(√N log N) local steps to find a marked vertex on a two-dimensional lattice, resolving an open question posed by Aaronson and Ambainis.

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.

Abstract

Quoted word for word from the abstract on arXiv.

The paper

Electrostatic Limits on Quantum Spatial Search

Weikang Li

arXiv, Oct 16, 2026, Open access, CC BY, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.23560

arXiv:2610.23560v1 in quant-ph, also cs.CC

AbstractPDFHTML

Cite as BibTeX
@misc{li2026electrostatic,
  title = {Electrostatic Limits on Quantum Spatial Search},
  author = {Li, Weikang},
  year = {2026},
  eprint = {2610.23560},
  archivePrefix = {arXiv},
  primaryClass = {quant-ph},
  doi = {10.48550/arxiv.2610.23560},
  url = {https://arxiv.org/abs/2610.23560}
}

More in Quantum