Nonlinear Quantum Search Using the Gross-Pitaevskii Equation

Abstract

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.

15 pages, 6 figures

References in corpus (2)

• Spatial search by quantum walk
• Efficient discrete-time simulations of continuous-time quantum query algorithms

Cited by in corpus (19)

• Connectivity is a Poor Indicator of Fast Quantum Search
• Fast quantum state discrimination with nonlinear PTP channels
• Optimal state discrimination and unstructured search in nonlinear quantum mechanics
• Quantum Search with General Nonlinearities
• Grover search and the no-signaling principle
• Continuous limits of linear and nonlinear quantum walks
• Irreconcilable Difference Between Quantum Walks and Adiabatic Quantum Computing
• Experimental orthogonalization of highly overlapping quantum states with single photons
• Quantum search with interacting Bose-Einstein condensates
• Nonlinear flip-flop quantum walks through potential barriers
• Nonlinear and non-CP gates for Bloch vector amplification
• Proposal for a Lorenz qubit
• Protocol for nonlinear state discrimination in rotating condensate
• Unitary Evolutions Sourced By Interacting Quantum Memories: Closed Quantum Systems Directing Themselves Using Their State Histories
• Concise Quantum Associative Memories with Nonlinear Search Algorithm
• Constant-Time Quantum Search with a Many-Body Quantum System
• Conserved Quantities in Linear and Nonlinear Quantum Search
• The universe as a nonlinear quantum simulation: Large $n$ limit of the central spin model
• Does Quantum Mechanics Breed Larger, More Intricate Quantum Theories? The Case for Experience-Centric Quantum Theory and the Interactome of Quantum Theories