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

Nonlinear Quantum Search / - eScholarship

Thomas G. Wong

Published Jan 1, 2014• 0 citations
OpenAlex

Abstract

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

Related papers

Quantum search with general nonlinearities

DAVID A. MEYER, Thomas G. Wong

Evolution by the Gross-Pitaevskii equation, which describes Bose-Einstein condensates under certain conditions, solves the unstructured search problem more efficiently than does the Schr\"odinger equation, because it includes a cubic nonlinearity, proportional to ${|\ensuremath{\psi}|}^{2}\ensuremath{\psi}$. This is not the only nonlinearity of the form $f(|\ensuremath{\psi}{|}^{2})\ensuremath{\psi}$ that arises in effective equations for the evolution of real quantum physical systems, however: The cubic-quintic nonlinear Schr\"odinger equation describes light propagation in nonlinear Kerr media with defocusing corrections, and the logarithmic nonlinear Schr\"odinger 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. In each of these cases the nonlinear equation is an effective approximation to a multiparticle Schr\"odinger equation, for search by which Grover's algorithm is optimal. Thus our results lead to quantum information-theoretic bounds on the physical resources required for these effective nonlinear theories to hold, asymptotically.

arXiv:1310.7301•Physical Review A•Jan 14, 2014•30 citations

Nonlinear quantum search using the Gross–Pitaevskii equation

David A Meyer, Thomas G Wong

We solve the unstructured search problem in constant time by computing with a physically motivated nonlinearity of the Gross–Pitaevskii type. This speedup comes, however, at the novel expense of increasing the time-measurement precision. Jointly optimizing these resource requirements results in an overall scaling of N 1/4 . This is a significant, but not unreasonable, improvement over the N 1/2 scaling of Grover's algorithm. Since the Gross–Pitaevskii equation approximates the multi-particle (linear) Schrödinger equation, for which Grover's algorithm is optimal, our result leads to a quantum information-theoretic lower bound on the number of particles needed for this approximation to hold, asymptotically.

arXiv:1303.0371•New Journal of Physics•Jun 12, 2013•32 citations

Spatial Search by Nonlinear Quantum Walk

David A. Meyer, Thomas G. Wong

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.

quant-pharXiv:2606.01403•Jun 2, 2026•0 citations

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

Optimal state discrimination and unstructured search in nonlinear quantum mechanics

Andrew M. Childs, Joshua Young

Nonlinear variants of quantum mechanics can solve tasks that are impossible in standard quantum theory, such as perfectly distinguishing nonorthogonal states. Here we derive the optimal protocol for distinguishing two states of a qubit using the Gross-Pitaevskii equation, a model of nonlinear quantum mechanics that arises as an effective description of Bose-Einstein condensates. Using this protocol, we present an algorithm for unstructured search in the Gross-Pitaevskii model, obtaining an exponential improvement over a previous algorithm of Meyer and Wong. This result establishes a limitation on the effectiveness of the Gross-Pitaevskii approximation. More generally, we demonstrate similar behavior under a family of related nonlinearities, giving evidence that the ability to quickly discriminate nonorthogonal states and thereby solve unstructured search is a generic feature of nonlinear quantum mechanics.

arXiv:1507.06334•Physical Review A•Feb 11, 2016•33 citations

Effective Dynamics of Interacting Bose Gases

LORENZO FEMIA

This thesis investigates the rigorous derivation of non-linear effective equations describing the time evolution of Bose-Einstein condensation from the N-particle linear Schrödinger equation, focusing on the one-particle reduced density matrix. The first chapter outlines the mathematical framework of many-body quantum mechanics, including the Fock space formalism. The second chapter studies the mean-field regime, proving that the condensed state converges to the non-linear Hartree equation by analyzing fluctuation dynamics to quantify the convergence rate. The third chapter addresses the physically realistic but mathematically challenging Gross-Pitaevskii regime, characterized by rare but strong interactions. Here, Bogoliubov transformations are used to capture crucial microscopic short-scale correlations, allowing for a quantitative derivation of the cubic non-linear Schrödinger equation. While the preceding chapters focus exclusively on repulsive interactions, the fourth chapter explores the focusing case with attractive potentials, which can lead to finite-time blow-up. Operating in an intermediate scaling regime, the effective focusing cubic non-linear Schrödinger equation is rigorously derived. Since the negative energy cannot bound many-body fluctuations, convergence is proven by approximating the dynamics via a quadratic Hamiltonian, in the spirit of Bogoliubov theory, and avoiding Grönwall estimates through the analysis of a coupled system of one-body linear equations for the one-particle density matrices.

•Sep 20, 2026•0 citations
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
Evolution by the Gross-Pitaevskii equation, which describes Bose-Einstein condensates under certain conditions, solves the unstructured search problem more efficiently than does the Schr\"odinger equation, because it includes a cubic nonlinearity, proportional to ${|\ensuremath{\psi}|}^{2}\ensuremath{\psi}$. This is not the only nonlinearity of the form $f(|\ensuremath{\psi}{|}^{2})\ensuremath{\psi}$ that arises in effective equations for the evolution of real quantum physical systems, however: The cubic-quintic nonlinear Schr\"odinger equation describes light propagation in nonlinear Kerr media with defocusing corrections, and the logarithmic nonlinear Schr\"odinger 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. In each of these cases the nonlinear equation is an effective approximation to a multiparticle Schr\"odinger equation, for search by which Grover's algorithm is optimal. Thus our results lead to quantum information-theoretic bounds on the physical resources required for these effective nonlinear theories to hold, asymptotically.
We solve the unstructured search problem in constant time by computing with a physically motivated nonlinearity of the Gross–Pitaevskii type. This speedup comes, however, at the novel expense of increasing the time-measurement precision. Jointly optimizing these resource requirements results in an overall scaling of N 1/4 . This is a significant, but not unreasonable, improvement over the N 1/2 scaling of Grover's algorithm. Since the Gross–Pitaevskii equation approximates the multi-particle (linear) Schrödinger equation, for which Grover's algorithm is optimal, our result leads to a quantum information-theoretic lower bound on the number of particles needed for this approximation to hold, asymptotically.
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.
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.
Nonlinear variants of quantum mechanics can solve tasks that are impossible in standard quantum theory, such as perfectly distinguishing nonorthogonal states. Here we derive the optimal protocol for distinguishing two states of a qubit using the Gross-Pitaevskii equation, a model of nonlinear quantum mechanics that arises as an effective description of Bose-Einstein condensates. Using this protocol, we present an algorithm for unstructured search in the Gross-Pitaevskii model, obtaining an exponential improvement over a previous algorithm of Meyer and Wong. This result establishes a limitation on the effectiveness of the Gross-Pitaevskii approximation. More generally, we demonstrate similar behavior under a family of related nonlinearities, giving evidence that the ability to quickly discriminate nonorthogonal states and thereby solve unstructured search is a generic feature of nonlinear quantum mechanics.
This thesis investigates the rigorous derivation of non-linear effective equations describing the time evolution of Bose-Einstein condensation from the N-particle linear Schrödinger equation, focusing on the one-particle reduced density matrix. The first chapter outlines the mathematical framework of many-body quantum mechanics, including the Fock space formalism. The second chapter studies the mean-field regime, proving that the condensed state converges to the non-linear Hartree equation by analyzing fluctuation dynamics to quantify the convergence rate. The third chapter addresses the physically realistic but mathematically challenging Gross-Pitaevskii regime, characterized by rare but strong interactions. Here, Bogoliubov transformations are used to capture crucial microscopic short-scale correlations, allowing for a quantitative derivation of the cubic non-linear Schrödinger equation. While the preceding chapters focus exclusively on repulsive interactions, the fourth chapter explores the focusing case with attractive potentials, which can lead to finite-time blow-up. Operating in an intermediate scaling regime, the effective focusing cubic non-linear Schrödinger equation is rigorously derived. Since the negative energy cannot bound many-body fluctuations, convergence is proven by approximating the dynamics via a quadratic Hamiltonian, in the spirit of Bogoliubov theory, and avoiding Grönwall estimates through the analysis of a coupled system of one-body linear equations for the one-particle density matrices.