Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.01403

Spatial Search by Nonlinear Quantum Walk

David A. Meyer, Thomas G. Wong

quant-phSubmitted May 31, 2026• Announced Jun 2, 2026• 0 citations
arXivHTMLPDF

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 $Θ(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.

Comments
22 pages, 3 figures; supersedes arXiv:1502.06281

Related papers

Completeness is Unnecessary for Fast Nonlinear Quantum Search

DAVID A. MEYER, Thomas G. Wong

Although strongly regular graphs and the hypercube are not complete, they are "sufficiently complete" such that a randomly walking quantum particle asymptotically searches on them in the same $Θ(\sqrt{N})$ time as on the complete graph, the latter of which is precisely Grover's algorithm. We show that physically realistic nonlinearities of the form $f(|ψ|^2)ψ$ can speed up search on sufficiently complete graphs, depending on the nonlinearity and graph. Thus nonlinear (quantum) computation can retain its power even when a degree of noncompleteness is introduced.

arXiv:1502.06281•Feb 22, 2015•2 citations

Constant-time quantum search with a many-body quantum system

Benjamin DalFavero, Alexander Meill, DAVID A. MEYER +2 more

The optimal runtime of a quantum computer searching a database is typically cited as the square root of the number of items in the database, which is famously achieved by Grover's algorithm. With parallel oracles, however, it is possible to search faster than this. We consider a many-body quantum system that naturally effects parallel queries, and we show that its parameters can be tuned to search a database in constant time, assuming a sufficient number of interacting particles. In particular, we consider Bose-Einstein condensates with pairwise and three-body interactions in the mean-field limit, which effectively evolve by a nonlinear Schr\"odinger equation with cubic and quintic nonlinearities. We solve the unstructured search problem formulated as a continuous-time quantum walk searching the complete graph in constant time. Depending on the number of marked vertices, however, the success probability can peak sharply, necessitating high precision time measurement to observe the system at this peak. Overcoming this, we prove that the relative coefficients of the cubic and quintic terms can be tuned to eliminate the need for high time-measurement precision by widening the peak in success probability or having it plateau. Finally, we derive a lower bound on the number of atoms needed for the many-body system to evolve by the effective nonlinearity.

arXiv:2408.05376•Physical Review A•Nov 7, 2024•2 citations

Spatial search via non-linear quantum walk

Mahdi Ebrahimi Kahou

One approach to the development of quantum search algorithms is the quantum walk. A spatial search can be effected by the continuous-time evolution of a single quantum particle on a lattice or graph containing a marked site. In most conceivable physical applications, however, one would rather expect to have multiple interacting particles. In bosonic systems at zero temperature, the dynamics would be well-described by a discrete non-linear Schrodinger equation. In this thesis we investigate the role of non-linearity in determining the efficiency of the spatial search algorithm within the quantum walk model, for the complete graph. Our analytical results indicate that the search time for this non-linear quantum search scales with size of the database N like square root of N, equivalent to linear spatial search time. The analytical results will be compared with numerical calculations of multiple interacting quantum walkers.

•Jan 1, 2013•1 citation

Nonlinear Quantum Search / - eScholarship

Thomas G. Wong

Although quantum mechanics is linear, there are nevertheless quantum systems with multiple interacting particles in which the effective evolution of a single particle is governed by a nonlinear equation. This includes Bose-Einstein condensates, which are governed by the Gross-Pitaevskii equation, which is a cubic nonlinear Schrodinger equation with a term proportional to /[psi]/ ²[psi] scaling of Grover's algorithm. Since the Gross- Pitaevskii equation effectively approximates the multi- particle Schrodinger equation, for which Grover's algorithm is optimal, our result leads to a quantum information-theoretic bound on the number of particles needed for this approximation to hold, asymptotically. The Gross-Pitaevskii equation is not the only nonlinearity of the form f(/[psi]/²)[psi] that arises in effective equations for the evolution of real quantum physical systems, however : The cubic-quintic nonlinear Schrodinger equation describes light propagation in nonlinear Kerr media with defocusing corrections, and the logarithmic nonlinear Schrodinger equation describes Bose liquids under certain conditions. Analysis of computation with such systems yields some surprising results; for example, when time-measurement precision is included in the resource accounting, searching a database'' when there is a single correct answer may be easier than searching when there are multiple correct answers. These results lead to quantum information-theoretic bounds on the physical resources required for these effective nonlinear theories to hold, asymptotically. Furthermore, strongly regular graphs, which have no global symmetry, are sufficiently complete for quantum search on them to asymptotically behave like unstructured search. Certain sufficiently complete graphs retain the improved runtime and resource scalings for some nonlinearities, so our scheme for nonlinear, analog quantum computation retains its benefits even when some structure is introduced

•Jan 1, 2014•0 citations

Quantum search with the signless Laplacian

Molly E. McLaughlin, Thomas G. Wong

Continuous-time quantum walks are typically effected by either the discrete Laplacian or the adjacency matrix. In this paper, we explore a third option: the signless Laplacian, which has applications in algebraic graph theory and may arise in layered antiferromagnetic materials. We explore spatial search on the complete bipartite graph, which is generally irregular and breaks the equivalence of the three quantum walks for regular graphs, and where the search oracle breaks the equivalence of the Laplacian and signless Laplacian quantum walks on bipartite graphs without the oracle. We prove that a uniform superposition over all the vertices of the graph partially evolves to the marked vertices in one partite set, with the choice of set depending on the jumping rate of the quantum walk. We boost this success probability to 1 by proving that a particular nonuniform initial state completely evolves to the marked vertices in one partite set, again depending on the jumping rate. For some parameter regimes, the signless Laplacian yields the fastest search algorithm of the three, suggesting that it could be a new tool for developing faster quantum algorithms.

arXiv:2501.17128•Physical Review A•Mar 25, 2025•1 citation

Quantum search with interacting Bose-Einstein condensates

Mahdi Ebrahimi Kahou, David L. Feder

One approach to the development of quantum search algorithms is the quantum walk. A spatial search can be effected by the continuous-time evolution of a single quantum particle on a graph containing a marked site. In many physical implementations, however, one might expect to have multiple particles. In interacting bosonic systems at zero temperature, the dynamics is well described by a discrete nonlinear Schr\"odinger equation. We investigate the role of nonlinearity in determining the efficiency of the spatial search algorithm within the quantum walk model, for the complete graph. The analytical calculations reveal that the nonlinear search time scales with the size of the search space $N$ like $\sqrt{N}$, equivalent to the linear case, though with a different overall constant. The results indicate that interacting Bose-Einstein condensates at zero temperature could be natural systems for implementation of the quantum search algorithm.

arXiv:1303.3537•Physical Review A•Sep 11, 2013•10 citations
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 Θ(N)Θ(N)Θ(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.
Although strongly regular graphs and the hypercube are not complete, they are "sufficiently complete" such that a randomly walking quantum particle asymptotically searches on them in the same Θ(N)Θ(\sqrt{N})Θ(N​) time as on the complete graph, the latter of which is precisely Grover's algorithm. We show that physically realistic nonlinearities of the form f(∣ψ∣2)ψf(|ψ|^2)ψf(∣ψ∣2)ψ can speed up search on sufficiently complete graphs, depending on the nonlinearity and graph. Thus nonlinear (quantum) computation can retain its power even when a degree of noncompleteness is introduced.
The optimal runtime of a quantum computer searching a database is typically cited as the square root of the number of items in the database, which is famously achieved by Grover's algorithm. With parallel oracles, however, it is possible to search faster than this. We consider a many-body quantum system that naturally effects parallel queries, and we show that its parameters can be tuned to search a database in constant time, assuming a sufficient number of interacting particles. In particular, we consider Bose-Einstein condensates with pairwise and three-body interactions in the mean-field limit, which effectively evolve by a nonlinear Schr\"odinger equation with cubic and quintic nonlinearities. We solve the unstructured search problem formulated as a continuous-time quantum walk searching the complete graph in constant time. Depending on the number of marked vertices, however, the success probability can peak sharply, necessitating high precision time measurement to observe the system at this peak. Overcoming this, we prove that the relative coefficients of the cubic and quintic terms can be tuned to eliminate the need for high time-measurement precision by widening the peak in success probability or having it plateau. Finally, we derive a lower bound on the number of atoms needed for the many-body system to evolve by the effective nonlinearity.
One approach to the development of quantum search algorithms is the quantum walk. A spatial search can be effected by the continuous-time evolution of a single quantum particle on a lattice or graph containing a marked site. In most conceivable physical applications, however, one would rather expect to have multiple interacting particles. In bosonic systems at zero temperature, the dynamics would be well-described by a discrete non-linear Schrodinger equation. In this thesis we investigate the role of non-linearity in determining the efficiency of the spatial search algorithm within the quantum walk model, for the complete graph. Our analytical results indicate that the search time for this non-linear quantum search scales with size of the database N like square root of N, equivalent to linear spatial search time. The analytical results will be compared with numerical calculations of multiple interacting quantum walkers.
Although quantum mechanics is linear, there are nevertheless quantum systems with multiple interacting particles in which the effective evolution of a single particle is governed by a nonlinear equation. This includes Bose-Einstein condensates, which are governed by the Gross-Pitaevskii equation, which is a cubic nonlinear Schrodinger equation with a term proportional to /[psi]/ ²[psi] scaling of Grover's algorithm. Since the Gross- Pitaevskii equation effectively approximates the multi- particle Schrodinger equation, for which Grover's algorithm is optimal, our result leads to a quantum information-theoretic bound on the number of particles needed for this approximation to hold, asymptotically. The Gross-Pitaevskii equation is not the only nonlinearity of the form f(/[psi]/²)[psi] that arises in effective equations for the evolution of real quantum physical systems, however : The cubic-quintic nonlinear Schrodinger equation describes light propagation in nonlinear Kerr media with defocusing corrections, and the logarithmic nonlinear Schrodinger equation describes Bose liquids under certain conditions. Analysis of computation with such systems yields some surprising results; for example, when time-measurement precision is included in the resource accounting, searching a database'' when there is a single correct answer may be easier than searching when there are multiple correct answers. These results lead to quantum information-theoretic bounds on the physical resources required for these effective nonlinear theories to hold, asymptotically. Furthermore, strongly regular graphs, which have no global symmetry, are sufficiently complete for quantum search on them to asymptotically behave like unstructured search. Certain sufficiently complete graphs retain the improved runtime and resource scalings for some nonlinearities, so our scheme for nonlinear, analog quantum computation retains its benefits even when some structure is introduced
Continuous-time quantum walks are typically effected by either the discrete Laplacian or the adjacency matrix. In this paper, we explore a third option: the signless Laplacian, which has applications in algebraic graph theory and may arise in layered antiferromagnetic materials. We explore spatial search on the complete bipartite graph, which is generally irregular and breaks the equivalence of the three quantum walks for regular graphs, and where the search oracle breaks the equivalence of the Laplacian and signless Laplacian quantum walks on bipartite graphs without the oracle. We prove that a uniform superposition over all the vertices of the graph partially evolves to the marked vertices in one partite set, with the choice of set depending on the jumping rate of the quantum walk. We boost this success probability to 1 by proving that a particular nonuniform initial state completely evolves to the marked vertices in one partite set, again depending on the jumping rate. For some parameter regimes, the signless Laplacian yields the fastest search algorithm of the three, suggesting that it could be a new tool for developing faster quantum algorithms.
One approach to the development of quantum search algorithms is the quantum walk. A spatial search can be effected by the continuous-time evolution of a single quantum particle on a graph containing a marked site. In many physical implementations, however, one might expect to have multiple particles. In interacting bosonic systems at zero temperature, the dynamics is well described by a discrete nonlinear Schr\"odinger equation. We investigate the role of nonlinearity in determining the efficiency of the spatial search algorithm within the quantum walk model, for the complete graph. The analytical calculations reveal that the nonlinear search time scales with the size of the search space NNN like N\sqrt{N}N​, equivalent to the linear case, though with a different overall constant. The results indicate that interacting Bose-Einstein condensates at zero temperature could be natural systems for implementation of the quantum search algorithm.