pith. sign in

arxiv: 2606.01403 · v1 · pith:TCUVVFXGnew · submitted 2026-05-31 · 🪐 quant-ph

Spatial Search by Nonlinear Quantum Walk

David A. Meyer , Thomas G. Wong This is my paper

Pith reviewed 2026-06-28 16:37 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum searchnonlinear quantum walkspatial searchPaley graphscomplete bipartite graphscontinuous-time quantum walkquantum algorithms on graphs
0
0 comments X

The pith

Nonlinear quantum walks allow faster search for marked vertices on incomplete graphs such as Paley graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines continuous-time quantum walks with added nonlinear terms to solve the spatial search problem on graphs that are not fully connected. It identifies a class of sufficiently complete graphs that behave like the complete graph under linear walks and shows that suitable nonlinearities produce analytic speedups on Paley graphs and on complete bipartite graphs with both parts of size proportional to the total number of vertices. Numerical evidence extends the observation to hypercubes and to high-dimensional cubic lattices. The result indicates that nonlinear effects can preserve a quantum advantage even when the underlying network is sparse.

Core claim

For graphs that asymptotically search like the complete graph under a linear continuous-time quantum walk, the addition of cubic or cubic-quintic nonlinear terms yields provably faster search times on Paley graphs and on complete bipartite graphs whose partite sets are both of size Θ(N); the same nonlinearities also produce numerical speedups on hypercubes and on sufficiently high-dimensional lattices.

What carries the argument

The continuous-time nonlinear quantum walk governed by a Schrödinger equation containing cubic or cubic-quintic nonlinear terms that modify the evolution on the graph.

If this is right

  • Search time on Paley graphs improves beyond the linear √N scaling for appropriate cubic and cubic-quintic nonlinearities.
  • Search time on complete bipartite graphs with equal part sizes Θ(N) likewise improves for the same nonlinearities.
  • Numerical evidence indicates that stronger nonlinearities further reduce search time on hypercubes.
  • Certain nonlinearities reduce search time on cubic lattices once the dimension is high enough.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same nonlinear mechanism could be tested on other strongly regular graphs that share the asymptotic completeness property.
  • If many-body systems can realize the required nonlinearities, the approach may apply to physical networks whose connectivity is only locally dense.
  • The lattice results suggest checking whether the critical dimension for speedup depends on the precise form of the nonlinearity.

Load-bearing premise

The graphs under study must be sufficiently complete that their linear quantum-walk search time already matches the complete-graph scaling.

What would settle it

An explicit calculation or simulation showing that the search time on a Paley graph remains unchanged or worsens when the cubic nonlinearity is introduced would falsify the analytic speedup claim.

Figures

Figures reproduced from arXiv: 2606.01403 by David A. Meyer, Thomas G. Wong.

Figure 1
Figure 1. Figure 1: FIG. 1. (a) A complete graph of [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. Success probability as a function of time for quantum search on various graphs with various nonlinearities (NLs) using [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Success probability as a function of time for quantum search on various graphs with various nonlinearities using [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
read the original abstract

Many-body quantum systems with effective nonlinearities have been shown to speed up quantum search on the complete graph, \textit{i.e.}, the combinatorial version of Grover's algorithm, at the expense of the number of particles needed for the effective nonlinearity to hold. Physically, however, data may not be arranged in an all-to-all network, and the task of searching incomplete graphs is the spatial search problem. We explore spatial search using a continuous-time nonlinear quantum walk on a variety of graphs. First, we consider incomplete graphs that are ``sufficiently complete'' so as to asymptotically search like the complete graph under a continuous-time (linear) quantum walk, which includes strongly regular graphs such as Paley graphs, regular graphs such as hypercubes, and irregular graphs such as complete bipartite graphs. For these sufficiently complete graphs, we analytically prove nonlinear speedups for Paley graphs and for complete bipartite graphs whose two partite sets both have size $\Theta(N)$, for suitable cubic and cubic-quintic nonlinearities, and we give numerical evidence for stronger nonlinearities and for hypercubes. Second, we explore arbitrary-dimensional cubic lattices, and we numerically show that certain nonlinearities speed up search on sufficiently high dimensional lattices. Thus, nonlinear quantum search can remain viable even when the underlying graph is incomplete.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript explores continuous-time nonlinear quantum walks for spatial search on incomplete graphs. It identifies a class of 'sufficiently complete' graphs (strongly regular graphs such as Paley, regular graphs such as hypercubes, and irregular graphs such as complete bipartite) that asymptotically match complete-graph search under linear continuous-time walks. For these graphs the authors analytically prove nonlinear speedups (cubic and cubic-quintic nonlinearities) on Paley graphs and on balanced complete bipartite graphs K_{m,m} with m=Θ(N), supply numerical evidence for stronger nonlinearities and hypercubes, and numerically demonstrate speedups on high-dimensional cubic lattices.

Significance. If the central analytical claims hold, the work extends nonlinear-search speedups beyond the complete graph to graphs that arise in spatial-search settings, showing that the advantage is not confined to all-to-all connectivity. The lattice numerics further indicate viability in physically motivated geometries. The absence of free parameters in the stated derivations and the provision of both analytic and numeric support are positive features.

major comments (2)
  1. [Analytical proofs (Paley and complete-bipartite cases)] The analytical proofs for Paley graphs and K_{m,m} (m=Θ(N)) rest on the claim that these graphs inherit the effective two-level nonlinear ODE derived for the complete graph. No explicit perturbation analysis or error bound is supplied showing that the local cubic (or cubic-quintic) term does not couple to the O(1) deviations from all-to-all connectivity that remain in strongly regular or balanced bipartite graphs, leaving the leading-order O(N^{1/4}) scaling unverified.
  2. [Introduction and methods (sufficiently-complete-graph assumption)] The premise that linear-case equivalence survives the nonlinearity is invoked without a quantitative control on the resulting perturbation to the marked-vertex amplitude dynamics; this control is load-bearing for the claimed speedups.
minor comments (1)
  1. [Abstract] The abstract states that numerical evidence is given 'for stronger nonlinearities and for hypercubes' but does not specify the range of nonlinearity strengths or the lattice sizes used; a brief clarification would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying points where the analytical justification requires additional rigor. We address the major comments below and will revise the manuscript to supply the requested perturbation analysis and error bounds.

read point-by-point responses

  1. Referee: [Analytical proofs (Paley and complete-bipartite cases)] The analytical proofs for Paley graphs and K_{m,m} (m=Θ(N)) rest on the claim that these graphs inherit the effective two-level nonlinear ODE derived for the complete graph. No explicit perturbation analysis or error bound is supplied showing that the local cubic (or cubic-quintic) term does not couple to the O(1) deviations from all-to-all connectivity that remain in strongly regular or balanced bipartite graphs, leaving the leading-order O(N^{1/4}) scaling unverified.

    Authors: We agree that an explicit perturbation analysis is needed to rigorously close the argument. The sufficiently-complete-graph definition controls the deviation of the adjacency matrix from the complete-graph case in the linear setting, but the manuscript does not quantify how this deviation interacts with the nonlinear term at leading order. In the revised version we will add a dedicated subsection deriving first-order error bounds on the marked-vertex amplitude, showing that the coupling remains O(N^{-3/4}) or smaller and therefore does not alter the O(N^{1/4}) scaling for both cubic and cubic-quintic nonlinearities. revision: yes

  2. Referee: [Introduction and methods (sufficiently-complete-graph assumption)] The premise that linear-case equivalence survives the nonlinearity is invoked without a quantitative control on the resulting perturbation to the marked-vertex amplitude dynamics; this control is load-bearing for the claimed speedups.

    Authors: We concur that the survival of the linear-case equivalence under nonlinearity must be placed on a quantitative footing. The revision will include explicit bounds (derived via Gronwall-type estimates on the amplitude equations) demonstrating that the perturbation to the two-level dynamics remains subdominant throughout the search interval, thereby preserving the claimed speedups. revision: yes

Circularity Check

0 steps flagged

Minor self-citation present but not load-bearing; derivations rest on independent graph-theoretic assumptions.

full rationale

The paper analytically proves nonlinear speedups by extending the complete-graph nonlinear dynamics to Paley graphs and balanced complete bipartite graphs under the premise that these graphs are 'sufficiently complete' (i.e., asymptotically equivalent to the complete graph under linear continuous-time quantum walk). This premise is a standard graph-theoretic property (strongly regular graphs, balanced bipartitions) established independently of the present nonlinear analysis and does not reduce to a self-referential fit or definition. No equations are shown to be equivalent by construction, no fitted parameters are relabeled as predictions, and any self-citation to prior complete-graph work is peripheral rather than the sole justification for the central claims. The derivation chain therefore remains self-contained against external graph benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only abstract available; ledger entries are minimal and drawn directly from stated premises.

axioms (1)
  • domain assumption Effective nonlinearities arise from many-body quantum systems
    Invoked in the first sentence of the abstract as the source of the nonlinearity.

pith-pipeline@v0.9.1-grok · 5751 in / 1021 out tokens · 23486 ms · 2026-06-28T16:37:28.384703+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references · 2 linked inside Pith

  1. [1]

    spatial search

    for the unstructured search problem, assuming that the oracle is queried sequentially. A quantum computer with parallel queries (or equivalently, multiple oracles), however, can search faster than this, as the product of the runtimeTand the square of the number of oraclesS is lower-bounded byN,i.e.,ST 2 = Ω(N) [5, 6]. Many- body quantum systems undergoing...

    Pith/arXiv arXiv 2026

  2. [2]

    Cubic Nonlinearity The cubic nonlinearity takes the formf(p) =p. In Fig. 2e, we plot the success probability when searching the same complete graphs from Fig. 2a, but now with the cubic nonlinearity withg=N−1 andℓ= 1, and we see that the success probability reaches 1 at a constant time ofπ/2 [6, 7]. Now, let us explore whether sufficiently complete graphs...

  3. [3]

    Cubic-Quintic Nonlinearity For the cubic-quintic nonlinearity, letf(p) =p−p 2. In Fig. 2i, we plot the success probability when searching the same complete graphs as before, but now using the cubic-quintic nonlinearity withg=N−1. The success probability reaches 1 at a constant time ofπ[7]. The success probability also forms a broad plateau near 1, in cont...

  4. [4]

    3D” and “4D

    Loglinear Nonlinearity For the loglinear nonlinearity,f(p) = lnp. In Fig. 2m, we plot the success probability when searching the same complete graphs as before, but now with the loglinear nonlinearity and withg= √ N /lnN, and we see that the success probability reaches 1 at a constant time around t= 2.3 [7]. Now, let us explore search on sufficiently comp...

  5. [5]

    L. K. Grover, A fast quantum mechanical algorithm for database search, inProceedings of the 28th annual ACM symposium on Theory of computing, STOC ’96 (ACM, New York, NY, USA, 1996) pp. 212–219

    1996

  6. [6]

    Farhi and S

    E. Farhi and S. Gutmann, Analog analogue of a digital quantum computation, Phys. Rev. A57, 2403 (1998)

    1998

  7. [7]

    A. M. Childs and J. Goldstone, Spatial search by quan- tum walk, Phys. Rev. A70, 022314 (2004)

    2004

  8. [8]

    Boyer, G

    M. Boyer, G. Brassard, P. Høyer, and A. Tapp, Tight bounds on quantum searching, Fortschritte der Physik 46, 493 (1998)

    1998

  9. [9]

    Zalka, Grover’s quantum searching algorithm is opti- mal, Phys

    C. Zalka, Grover’s quantum searching algorithm is opti- mal, Phys. Rev. A60, 2746 (1999)

    1999

  10. [10]

    D. A. Meyer and T. G. Wong, Nonlinear quantum search using the Gross-Pitaevskii equation, New J. Phys.15, 063014 (2013)

    2013

  11. [11]

    D. A. Meyer and T. G. Wong, Quantum search with gen- eral nonlinearities, Phys. Rev. A89, 012312 (2014)

    2014

  12. [12]

    DalFavero, A

    B. DalFavero, A. Meill, D. A. Meyer, T. G. Wong, and J. P. Wrubel, Constant-time quantum search with a many-body quantum system, Phys. Rev. A110, 052411 (2024)

    2024

  13. [13]

    Gross, Structure of a quantized vortex in boson sys- tems, Il Nuovo Cimento (1955-1965)20, 454 (1961)

    E. Gross, Structure of a quantized vortex in boson sys- tems, Il Nuovo Cimento (1955-1965)20, 454 (1961)

    1955

  14. [14]

    Pitaevskii, Vortex lines in an imperfect Bose gas, So- viet Physics JETP-USSR13, 451 (1961)

    L. Pitaevskii, Vortex lines in an imperfect Bose gas, So- viet Physics JETP-USSR13, 451 (1961)

    1961

  15. [15]

    S. N. Bose, Plancks gesetz und lichtquantenhypothese, Z. Phys.26(1924)

    1924

  16. [16]

    Einstein, Zur quantentheorie des einatomigen idealen gases, Sitzungsber

    A. Einstein, Zur quantentheorie des einatomigen idealen gases, Sitzungsber. K. Preuss. Akad. Wiss.261(1924)

    1924

  17. [17]

    Einstein, Quantentheorie des einatomigen idealen gases

    A. Einstein, Quantentheorie des einatomigen idealen gases. Zweite abhandlung., Sitzungsber. Preuss. Akad. Wiss.3(1925)

    1925

  18. [18]

    Gammal, T

    A. Gammal, T. Frederico, L. Tomio, and P. Chomaz, Atomic Bose-Einstein condensation with three-body in- teractions and collective excitations, J. Phys. B: At. Mol. Opt. Phys.33, 4053 (2000)

    2000

  19. [19]

    Trallero-Giner and T

    C. Trallero-Giner and T. Liew, One-dimensional cubic- quintic Gross-Pitaevskii equation for Bose-Einstein con- densates in a trap potential, Eur. Phys. J. D67, 143 (2013)

    2013

  20. [20]

    Kerr, On rotation of the plane of polarization by reflec- tion from the pole of a magnet, Philosophical Magazine 3, 321 (1877)

    J. Kerr, On rotation of the plane of polarization by reflec- tion from the pole of a magnet, Philosophical Magazine 3, 321 (1877)

  21. [21]

    Kerr, On reflection of polarized light from the equato- rial surface of a magnet, Philosophical Magazine Series 5 5, 161 (1878)

    J. Kerr, On reflection of polarized light from the equato- rial surface of a magnet, Philosophical Magazine Series 5 5, 161 (1878)

  22. [22]

    Weinberger, John Kerr and his effects found in 1877 and 1878, Philosophical Magazine Letters88, 897 (2008)

    P. Weinberger, John Kerr and his effects found in 1877 and 1878, Philosophical Magazine Letters88, 897 (2008)

    2008

  23. [23]

    A. V. Avdeenkov and K. G. Zloshchastiev, Quantum bose liquids with logarithmic nonlinearity: self-sustainability and emergence of spatial extent, Journal of Physics B: Atomic, Molecular and Optical Physics44, 195303 (2011)

    2011

  24. [24]

    Benioff, Space searches with a quantum robot, inQuantum computation and information, Contemp

    P. Benioff, Space searches with a quantum robot, inQuantum computation and information, Contemp. Math., Vol. 305 (AMS, Providence, RI, 2002) pp. 1–12

    2002

  25. [25]

    Aaronson and A

    S. Aaronson and A. Ambainis, Quantum search of spatial regions, Theor. Comput.1, 47 (2005)

    2005

  26. [26]

    Di Molfetta and B

    G. Di Molfetta and B. Herzog, Searching via nonlinear quantum walk on the 2d-grid, Algorithms13, 305 (2020)

    2020

  27. [27]

    T. G. Wong, Unstructured search by random and quan- tum walk, Quantum Inf. Comput.22, 53 (2022)

    2022

  28. [28]

    T. G. Wong, Grover search with lackadaisical quantum walks, J. Phys. A: Math. Theor.48, 435304 (2015)

    2015

  29. [29]

    T. G. Wong, Corrigendum: Grover search with lack- adaisical quantum walks (2015 J. Phys. A: Math. Theor. 48 435304), J. Phys. A: Math. Theor.51, 069501 (2018)

    2015

  30. [30]

    D. A. Meyer and T. G. Wong, Connectivity is a poor indicator of fast quantum search, Phys. Rev. Lett.114, 110503 (2015)

    2015

  31. [31]

    Janmark, D

    J. Janmark, D. A. Meyer, and T. G. Wong, Global sym- metry is unnecessary for fast quantum search, Phys. Rev. Lett.112, 210502 (2014)

    2014

  32. [32]

    T. G. Wong, Quantum walk search on Johnson graphs, J. Phys. A: Math. Theor.49, 195303 (2016)

    2016

  33. [33]

    Chakraborty, L

    S. Chakraborty, L. Novo, A. Ambainis, and Y. Omar, Spatial search by quantum walk is optimal for almost all graphs, Phys. Rev. Lett.116, 100501 (2016)

    2016

  34. [34]

    Cameron and J

    P. Cameron and J. van Lint,Designs, Graphs, Codes and Their Links, London Mathematical Society Student Texts (Cambridge University Press, 1991)

    1991

  35. [35]

    Farhi, J

    E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution, arXiv:quant-ph/0001106 (2000)

    Pith/arXiv arXiv 2000

  36. [36]

    A. M. Childs, E. Deotto, E. Farhi, J. Goldstone, S. Gut- mann, and A. J. Landahl, Quantum search by measure- ment, Phys. Rev. A66, 032314 (2002)

    2002

  37. [37]

    T. G. Wong, L. Tarrataca, and N. Nahimov, Laplacian versus adjacency matrix in quantum walk search, Quan- tum Inf. Process.15, 4029 (2016)

    2016

  38. [38]

    Pazy,Semigroups of Linear Operators and Applica- tions to Partial Differential Equations, Applied Mathe- matical Sciences, Vol

    A. Pazy,Semigroups of Linear Operators and Applica- tions to Partial Differential Equations, Applied Mathe- matical Sciences, Vol. 44 (Springer, New York, 1983)

    1983

  39. [39]

    Teschl,Ordinary Differential Equations and Dynami- cal Systems, Graduate Studies in Mathematics, Vol

    G. Teschl,Ordinary Differential Equations and Dynami- cal Systems, Graduate Studies in Mathematics, Vol. 140 (American Mathematical Society, Providence, RI, 2012)

    2012

  40. [40]

    Kato,Perturbation Theory for Linear Operators, 2nd ed., Classics in Mathematics (Springer, Berlin, Heidel- berg, 1995)

    T. Kato,Perturbation Theory for Linear Operators, 2nd ed., Classics in Mathematics (Springer, Berlin, Heidel- berg, 1995)

    1995