PaperlayerView exact revision on arXiv

Source-linked AI summary

Electrostatic Limits on Quantum Spatial Search

Weikang Li

arXiv:2610.23560v1quant-phcs.CC

TL;DR

Whether a local quantum walker can search a two-dimensional lattice in Grover time was an open question. The paper uses an electrostatic weighted-overlap argument to prove a local-step lower bound with an extra logarithmic factor, and concludes that Tulsi’s algorithm is asymptotically optimal.

  • Problem

    Whether a quantum walker restricted to neighbouring lattice hops can search a two-dimensional lattice in Grover time remained open, despite the known Ω(√N log N) local-step bound stated in the paper.

    Source: p. 1

  • Method

    The proof weights the overlap of marked and unmarked runs by the electrostatic potential drop, whose field energy limits its change under local steps while queries leave it unchanged.

    Source: pp. 1–2

  • Results

    On the square lattice, the lower bound is Ω(√(N log N)) local steps, and Tulsi’s algorithm is asymptotically optimal.

    Source: p. 1

  • Takeaways & Limitations

    On a broad class of vertex-transitive graphs, locality permits at most a quadratic speedup over the simple random walk, and for several marked vertices the bound depends on their arrangement through capacitance.

    Source: pp. 1, 4

    The model covers one walker with local hops and oracle queries on marked vertices; multiple oracle-coupled walkers, nonlinear dynamics, and queries away from marks are outside its stated scope.

    Source: pp. 2, 4

Abstract

from arXiv · show

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 $\Omega(\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.

Supplemental Material: Electrostatic Limits on Quantum Spatial Search

The supplement proves electrostatic bounds for one marked vertex on vertex-transitive graphs and translated marked sets on the square torus, evaluates the bounds on lattices, and describes matching algorithms and numerical illustrations.

Supplemental Material: Electrostatic Limits on Quantum Spatial Search

  • The supplement proves the bounds for one marked vertex on vertex-transitive graphs and translated marked sets on the square torus, and evaluates them on lattices.It also constructs matching algorithms and describes numerical illustrations.Source: Supplemental Material: Electrostatic… · p. 7

S1.1. Definitions

  • The model uses one walker with a position-dependent internal workspace and counts local steps while granting queries for free.A local step may move amplitude only between a vertex and itself or an adjacent vertex; the input-independent start and common final measurement complete the model.Source: S1.1. Definitions · p. 7

S1.2. Scope of the model

  • Coined, Szegedy, and ancilla-controlled walks fit the local-step model, while staggered walks with distance-two cells require a constant number of local steps per cell unitary.Certain continuous-time nearest-neighbour transformations are covered when each is counted as 2π local steps.Source: S1.2. Scope of the model · p. 8
  • Additional position registers coupled to the oracle, nonlinear evolution, and queries away from marked vertices lie outside the model; long-range hops instead change the graph whose self-potential sets the bound.The result applies to the enlarged graph when it is vertex-transitive.Source: S1.2. Scope of the model · p. 8

S1.3. Range of the results

  • Asymptotic lower bounds require success probability bounded away from zero, and matching complexities for marked sets additionally assume N/k→∞.The stated matching worst-case upper bound assumes k is known; the lower-bound forms apply when η or η_M tends to zero.Source: S1.3. Range of the results · p. 8

S2. ELECTROSTATIC POTENTIALS

This section defines the graph potential of a unit charge against a uniform neutralizing background and relates its self-potential to electrical energy, effective resistance, and random-walk hitting times.

S2.1. One charge on a vertex-transitive graph

  • K(·, m) is the electrostatic potential of a unit charge at m in a uniform neutralizing background.It has zero mean and is invariant under graph automorphisms; vertex transitivity makes its self-potential A and squared norm S² independent of m.Source: S2.1. One charge on a… · p. 8
  • The self-potential A equals the Dirichlet energy of the current entering at m and leaving uniformly across the graph.This is the effective resistance between m and the uniform distribution; the mean effective resistance from m to a vertex is 2A.Source: S2.1. One charge on a… · p. 9
  • For the non-lazy simple random walk started uniformly, the mean hitting time of m is t_h = NdA.From a starting vertex x, the mean hitting time is Nd[A − K(x, m)].Source: S2.1. One charge on a… · p. 9

S2.2. The equilibrium potential of a marked set

The section constructs the equilibrium potential for a marked set and characterizes its self-potential through a charge minimization; the associated Dirichlet problem also yields hitting times to the set.

S2.2. The equilibrium potential of a marked set

  • K_M is the unique zero-mean potential that is constant on the marked set M, with value A_M.The equilibrium charge is supported on M, and A_M is its self-potential.Source: S2.2. The equilibrium potential of a… · pp. 9–10
  • A_M is the minimum of ρᵀGρ over charges supported on M with total charge 1, even when signed charges are allowed.The construction solves a Dirichlet problem with potential zero on M and unit Laplacian off M.Source: S2.2. The equilibrium potential of a… · pp. 9–10
  • For the non-lazy simple random walk on the square torus, the expected time to hit M is h_M = 4u, where u solves the stated Dirichlet problem.The section also identifies S_M as the coefficient of variation of mean hitting time over starting vertices.Source: S2.2. The equilibrium potential of a… · p. 10

S3. THE ELECTROSTATIC BOUND

The electrostatic argument weights the overlap between marked and unmarked runs by a potential-derived function that queries leave unchanged, while local steps change it at a rate limited by field energy. A query-only hybrid bound complements this approach, and an interpolated walk provides a matching upper bound in terms of classical hitting time.

Electrostatic bound

  • The weighted overlap is unchanged by queries, while each local step changes it by at most a quantity controlled by the potential’s edge differences.The weight B_m vanishes at the marked vertex; the local-step bound follows by controlling the commutator through neighboring potential differences.Source: S3. THE ELECTROSTATIC BOUND · p. 10

Query lower bound

  • Even with free queries, the hybrid argument gives T + 1 ≥ (√(Np) − 1)/2, complementing the electrostatic bound on dense graphs.The text notes that the self-potential is small on dense graphs.Source: S3. THE ELECTROSTATIC BOUND · p. 11

Electrostatic bound

  • The potential-derived weight is Dirichlet-optimal among invariant weights vanishing at the mark, maximizing mean weight relative to the square root of its energy.Equality holds for a nonnegative multiple of A − K(·, m).Source: S3. THE ELECTROSTATIC BOUND · p. 11

Matching upper bound

  • The interpolated walk of Ref. finds a single marked vertex with constant probability in O(√t_h) local steps.The implementation counts each controlled walk as O(1) local steps; preparing the uniform state and fixed-probability repetitions fit within the same asymptotic budget.Source: S3. THE ELECTROSTATIC BOUND · p. 12

S4. LATTICES

The self-potential determines how the electrostatic bound scales across lattice dimensions. In two dimensions it grows logarithmically with side length, while the one-dimensional fixed-success lower bound is linear in N.

Two-dimensional lattices

  • For the square torus, A = (2π)^−1 ln L + O(1), so the two-dimensional self-potential diverges logarithmically with system size.The more precise expansion is A = (2π)^−1 ln L + c□ + O(L^−2), with c□ ≈ 0.0488.Source: S4. LATTICES · pp. 12–13

Other dimensions

  • For n = 1, every fixed p > 0 gives T = Ω(N).The passage derives this from a lower bound on T/N for fixed p.Source: S4. LATTICES · p. 13
  • For every fixed n ≥ 3, A converges to a positive constant; in two dimensions it diverges only logarithmically.The cited passage also states that A diverges in one dimension.Source: S4. LATTICES · p. 13
  • For n = 3, A∞ = G3/6, where G3 ≈ 1.5164 is Watson’s integral.The passage identifies G3 as the expected number of visits of the simple random walk on Z3 to its starting point.Source: S4. LATTICES · p. 13

S5. ROUTING AND OPEN BOUNDARIES

Routing implements input-independent permutations along fixed nearest-neighbor paths using local steps and added workspace. Folding the torus onto an open lattice simulates Tulsi’s walk with at most twice the local steps and four added internal states per vertex.

Routing

  • A fixed-path permutation of distinguished basis states with paths of length at most D can be implemented in D local steps, with no amplitude left in added workspace.An on-site unitary applied before the permutation can be absorbed into the first local step.Source: S5. ROUTING AND OPEN BOUNDARIES · p. 13

Open boundaries

  • Tulsi’s walk on the L × L torus runs on the open L × L lattice with at most twice as many local steps and at most four added internal states per vertex.The simulation uses the same queries.Source: S5. ROUTING AND OPEN BOUNDARIES · p. 14

Preparation

  • Preparing Tulsi’s uniform starting state from one vertex takes 2(L − 1) further local steps, which does not change the scaling.Verification and a fixed number of independent trials preserve the stated asymptotic cost on both the torus and open lattice.Source: S5. ROUTING AND OPEN BOUNDARIES · p. 14

S6. SEVERAL MARKED VERTICES

The several-marked-vertex setting considers translates of a fixed nonempty proper marked set on the torus, with the translation chosen uniformly. The algorithm may know the fixed pattern but not its location, and success means outputting any marked vertex.

Several marked vertices

S6.1. The bound for translated marked sets

For translated marked sets, the lower bound is governed by the set’s potential and applies when the marked fraction and endpoint ratio vanish. The proof uses translated Dirichlet-optimal weights, which queries leave invariant and whose field energy limits overlap change.

S6.1. The bound for translated marked sets

  • When p ≥ p0, k/N → 0, and η_M → 0, every algorithm searching translates of M requires Ω(√(N A_M)) local steps.The bound applies when success is averaged over the translates of M.Source: S6.1. The bound for translated marked… · p. 14
  • Translated weights A_M − K_g vanish on each marked set, remain invariant under its query, and are Dirichlet-optimal.Their translation average gives the initial overlap A_M; their edge energy is 2A_M.Source: S6.1. The bound for translated marked… · p. 15
  • Deciding whether an input is unmarked or a translate of M also requires the detection bound stated in Corollary S6.2.The corollary allows false-positive and false-negative probabilities at most ε < 1/2.Source: S6.1. The bound for translated marked… · p. 15
  • For a known random pattern, the theorem covers one realization and its translates, not a newly sampled pattern for every input.An asymptotic statement for random patterns would require probabilistic control of both A_M and η_M.Source: S6.1. The bound for translated marked… · p. 15

S6.2. Periodic subgrids

For periodic subgrids, the marked-set potential and norm reduce to those of a single mark on a quotient torus. This gives a lower bound matching the single-mark bound there, while translation symmetry also supports an upper-bound algorithm.

S6.2. Periodic subgrids

  • For a periodic subgrid, ρ_M = k^-1 1_M, K_M(x) = k^-1 K(ℓ)(x mod ℓ), A_M = A(ℓ)/k, and S_M^2 = S(ℓ)^2/k.Thus Eq. (S24) coincides with the single-mark bound on the quotient torus.Source: S6.2. Periodic subgrids · p. 15
  • With A(ℓ) = (ln ℓ)/(2π) + O(1), the periodic subgrid’s self-potential follows the quotient-torus scaling, where ℓ² = N/k.The proposition gives the potential and norm by reduction to the quotient torus.Source: S6.2. Periodic subgrids · p. 15
  • A uniform start and identical on-site operations reduce the walk to the quotient torus, where Tulsi’s walk searches as a single-mark walk.A localized start can be prepared in O(ℓ) local steps in an open ℓ × ℓ window containing one marked vertex.Source: S6.2. Periodic subgrids · p. 15
  • For patterns invariant under exchanging the axes up to translation, the commutator bound doubles the right side of Eq. (S24).The passage also identifies periodic subgrids as having this symmetry.Source: S6.2. Periodic subgrids · p. 16

S6.3. Compact clusters and the worst case

Compact clusters have a logarithmically growing self-potential, yielding a lower bound for searching their translates. The section also gives worst-case search bounds for known k and describes algorithms for arbitrary placements and for ensemble-average success.

S6.3. Compact clusters and the worst case

  • For translates of a compact cluster, every local algorithm with fixed average success probability obeys the lower bound stated for that family.The argument uses η_Ck = O(1/A_Ck) and the translated-marked-set theorem.Source: S6.3. Compact clusters and the worst… · p. 16
  • For compact clusters, A_Ck = (2π)^-1 ln(L/κ) + O(1), where κ is the cluster’s linear scale.The lower- and upper-bound estimates use the cluster’s diameter and a contained κ × κ square.Source: S6.3. Compact clusters and the worst… · p. 16
  • With known k and N/k → ∞, Theorem S6.5 gives worst-case local-step bounds for finding exactly k marked vertices or deciding OR(k).The upper bound includes O(L) preparation from a known starting vertex; the lower bound allows arbitrary workspace and free queries.Source: S6.3. Compact clusters and the worst… · p. 16
  • Thinning selects one representative per cell and searches a coarse torus; repeated trials yield a verified marked vertex uniformly over placements.The representatives’ paths simulate adjacent coarse moves, and the search is conditioned on exactly one marked representative.Source: S6.3. Compact clusters and the worst… · pp. 16–17
  • Parallel windows run a folded single-mark walk simultaneously, with average success at least c1 times the average fraction of windows containing exactly one mark.For a uniformly random k-subset, the expected fraction of such windows tends to e^-1 when k and N/k both tend to infinity.Source: S6.3. Compact clusters and the worst… · p. 17
  • The worst-case upper bound in Theorem S6.5 assumes k is known.The passage distinguishes this guarantee from ensemble-average statements and reviews existing frameworks with logarithmic overheads or setup costs.Source: S6.3. Compact clusters and the worst… · p. 17

S7. SHARPENED SPEED LIMITS

A commutator identity bounds how much a local step changes the potential-weighted overlap. On triangle-free graphs the bound sharpens, and on square tori the passage gives a corresponding coefficient while stating symmetry-related limits.

S7. SHARPENED SPEED LIMITS

  • For vertex- and edge-transitive graphs, the commutator identity bounds the local-step change using the self-potential A and the on-site part of the unitary.The general left-side bound is 4A/(dN); when the graph has no triangles, the upper bound improves.Source: S7. SHARPENED SPEED LIMITS · p. 17
  • On graphs without triangles, fixed p > 0 and η → 0 imply T = Ω(√t_h) without a degree factor.Vertex and edge transitivity alone do not ensure η → 0; the cycle is given as an example.Source: S7. SHARPENED SPEED LIMITS · p. 18
  • For a square torus with L ≥ 4, the commutator bound has coefficient A/(2N).For L = 3, the general bound is A/N and A/(2N) can be exceeded.Source: S7. SHARPENED SPEED LIMITS · p. 18
  • The A/(2N) commutator bound is attained when U_d a = 0, so tightening the commutator alone cannot improve the sharpened speed limit.The constant in Eq. (S34) may still be improvable by other means.Source: S7. SHARPENED SPEED LIMITS · p. 18
  • The equal-edge-correlation argument need not apply to graphs that are only vertex-transitive or to marked patterns lacking axis-exchange symmetry up to translation.The passage gives the L = 3 torus as an instance where the coefficient A/(2N) can be exceeded.Source: S7. SHARPENED SPEED LIMITS · p. 18

S8. CONTINUOUS-TIME EVOLUTION

The section extends the local-search speed-limit argument to continuous-time evolution and compares motion accounting with controlled intermittent quantum walks.

S8. CONTINUOUS-TIME EVOLUTION

  • The continuous-time model assumes a common self-adjoint nearest-neighbour Hamiltonian, with marked-run oracle terms supported on the marked vertex.For well-defined normalized evolutions, the passage gives bounded, piecewise-continuous Hamiltonians as an example.Source: S8. CONTINUOUS-TIME EVOLUTION · p. 18
  • The speed-limit proof uses that the marked potential vanishes under the weighted-overlap operator and bounds the commutator with the hopping Hamiltonian.The local-step argument yields a rate bound proportional to J(t), as stated in the passage.Source: S8. CONTINUOUS-TIME EVOLUTION · p. 18
  • For constant hopping budget J, the evolution time is at least the right side of Eq. (S12) divided by J.The same argument applies to Theorem S6.1 when oracle terms are supported on the marked set.Source: S8. CONTINUOUS-TIME EVOLUTION · p. 18
  • Ref. uses O(ε^-1/2) queries and evolution time O(λ^-1 ε^-1/2), with λ^2 = Θ(N^-1) on the square torus.The passage sets ε = k/N for this comparison.Source: S8. CONTINUOUS-TIME EVOLUTION · p. 18
  • The section counts approximate-reflection evolution as motion and places the controlled search construction within the continuous-time model.The cited construction uses a control qubit per controlled evolution and has hopping norm at most four on the square torus.Source: S8. CONTINUOUS-TIME EVOLUTION · p. 18

S9. NUMERICAL ILLUSTRATIONS

The numerical illustrations simulate Tulsi’s walk and check the proof’s identities and speed limit. They also compare equilibrium quantities for different arrangements of marked vertices.

S9. NUMERICAL ILLUSTRATIONS

  • cos δ = Θ((ln N)^-1/2) gives constant success probability for Tulsi’s walk under the stated choice of A.The passage gives A = (ln N)/(4π) + O(1).Source: S9. NUMERICAL ILLUSTRATIONS · p. 19
  • The simulations found queries changed F by less than 10^-12 and the state norm stayed within 10^-9 of one at every step.Across these runs, F decreased monotonically up to the peak step T.Source: S9. NUMERICAL ILLUSTRATIONS · p. 19
  • For uniformly random marked sets with k = 64, the median 4πkA_M/ln(N/k) fell from 1.695 at L = 64 to 1.327 at L = 1024.The passage says these values are compatible with convergence to the periodic-subgrid value, for which the ratio tends to one.Source: S9. NUMERICAL ILLUSTRATIONS · p. 19
  • The numerical checks covered identities and inequalities on 28 small vertex-transitive graphs, with agreement to rounding error below 10^-12.The speed limit was also checked at every local step in runs on tori with L = 5, 8, 12, and 16.Source: S9. NUMERICAL ILLUSTRATIONS · p. 19
  • Table S4 reports equilibrium quantities and a local-step lower bound for marked sets on a 1024 × 1024 torus with k = 64.The periodic subgrid also admits the sharpened bound 55.61.Source: Table S4 · p. 20

Related papers

Loading 2610.23560v1…