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:1310.7301 · Physical Review A

Quantum search with general nonlinearities

DAVID A. MEYER, Thomas G. Wong

Published Jan 14, 2014• 30 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.89.012312

Related papers

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

Nonlinear Quantum Search

Thomas G. Wong

Although quant mech is linear, there are nevertheless quant sys with multiple interacting particles in which the effective evo of a single particle is governed by a nonlinear eq. This includes Bose-Einstein condensates, which are gov by the Gross-Pitaevskii eq (GPE), which is a cubic nonlin Schrodinger eq (NLSE) with a term propto $|ψ|^2ψ$. Evo by this eq solves the unstruct search prob in const time, but at the novel expense of increasing the time-measurement precision. Jointly optimizing these resources results in an overall scaling of $N^{1/4}$, which is a significant, but not unreasonable, improvement over the $N^{1/2}$ scaling of Grover's algo. Since the GPE effectively approx the multi-particle Schrodinger eq, for which Grover's algo is optimal, our result leads to a quant info-theoretic bound on the num of particles needed for this approx to hold, asymp. The GPE is not the only nonlin of the form $f(|ψ|^2)ψ$ that arises in effective eqs for the evo of real quant phys sys, however: The cubic-quintic NLSE describes light propagation in nonlin Kerr media with defocusing corrections, and the log NLSE describes Bose liquids under certain cond. Analysis of comput with such sys yields some surprising results; e.g., when time-measurement precision is included in the resource accounting, searching a "database" when there is a single correct ans may be easier than searching when there are multiple correct ans. These results lead to quant info-theoretic bounds on the phys resources required for these effective nonlin theories to hold, asymp. Further, strongly reg graphs, which have no global sym, are sufficiently complete for quant search on them to asymp behave like unstruct search. Certain suff complete graphs retain the improved runtime and resource scalings for some nonlin, so our scheme for nonlin, analog quant comput retains its benefits even when some struct is introduced.

arXiv:1506.04388•Jun 14, 2015•3 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

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

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
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ψ∣2\ensuremathψ{|\ensuremath{\psi}|}^{2}\ensuremath{\psi}∣\ensuremathψ∣2\ensuremathψ. This is not the only nonlinearity of the form f(∣\ensuremathψ∣2)\ensuremathψf(|\ensuremath{\psi}{|}^{2})\ensuremath{\psi}f(∣\ensuremathψ∣2)\ensuremathψ 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.
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
Although quant mech is linear, there are nevertheless quant sys with multiple interacting particles in which the effective evo of a single particle is governed by a nonlinear eq. This includes Bose-Einstein condensates, which are gov by the Gross-Pitaevskii eq (GPE), which is a cubic nonlin Schrodinger eq (NLSE) with a term propto ∣ψ∣2ψ|ψ|^2ψ∣ψ∣2ψ. Evo by this eq solves the unstruct search prob in const time, but at the novel expense of increasing the time-measurement precision. Jointly optimizing these resources results in an overall scaling of N1/4N^{1/4}N1/4, which is a significant, but not unreasonable, improvement over the N1/2N^{1/2}N1/2 scaling of Grover's algo. Since the GPE effectively approx the multi-particle Schrodinger eq, for which Grover's algo is optimal, our result leads to a quant info-theoretic bound on the num of particles needed for this approx to hold, asymp. The GPE is not the only nonlin of the form f(∣ψ∣2)ψf(|ψ|^2)ψf(∣ψ∣2)ψ that arises in effective eqs for the evo of real quant phys sys, however: The cubic-quintic NLSE describes light propagation in nonlin Kerr media with defocusing corrections, and the log NLSE describes Bose liquids under certain cond. Analysis of comput with such sys yields some surprising results; e.g., when time-measurement precision is included in the resource accounting, searching a "database" when there is a single correct ans may be easier than searching when there are multiple correct ans. These results lead to quant info-theoretic bounds on the phys resources required for these effective nonlin theories to hold, asymp. Further, strongly reg graphs, which have no global sym, are sufficiently complete for quant search on them to asymp behave like unstruct search. Certain suff complete graphs retain the improved runtime and resource scalings for some nonlin, so our scheme for nonlin, analog quant comput retains its benefits even when some struct is introduced.
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.
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.
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.