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.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.3537Physical Review ASep 11, 201310 citations

Conserved Quantities in Linear and Nonlinear Quantum Search

DAVID A. MEYER, Thomas G. Wong

Abstract In this tutorial, which contains some original results, we bridge the fields of quantum computing algorithms, conservation laws, and many-body quantum systems by examining three algorithms for searching an unordered database of size N using a continuous-time quantum walk, which is the quantum analogue of a continuous-time random walk. The first algorithm uses a linear quantum walk, and we apply elementary calculus to show that the success probability of the algorithm reaches 1 when the jumping rate of the walk takes some critical value. We show that the expected value of its Hamiltonian H 0 is conserved. The second algorithm uses a nonlinear quantum walk with effective Hamiltonian H ( t ) = H 0 + λ | ψ | 2 , which arises in the Gross-Pitaevskii equation describing Bose-Einstein condensates. When the interactions between the bosons are repulsive, λ > 0, and there exists a range of fixed jumping rates such that the success probability reaches 1 with the same asymptotic runtime of the linear algorithm, but with a larger multiplicative constant. Rather than the effective Hamiltonian, we show that the expected value of H 0 + 1 2 λ | ψ | 2 {H_0} + {1 \over 2}\lambda |\psi {|^2} is conserved. The third algorithm utilizes attractive interactions, corresponding to λ < 0. In this case, there is a time-varying critical function for the jumping rate γ c ( t ) that causes the success probability to reach 1 more quickly than in the other two algorithms, and we show that the expected value of H ( t )/[ γ c ( t ) N ] is conserved.Abstract In this tutorial, which contains some original results, we bridge the fields of quantum computing algorithms, conservation laws, and many-body quantum systems by examining three algorithms for searching an unordered database of size N using a continuous-time quantum walk, which is the quantum analogue of a continuous-time random walk. The first algorithm uses a linear quantum walk, and we apply elementary calculus to show that the success probability of the algorithm reaches 1 when the jumping rate of the walk takes some critical value. We show that the expected value of its Hamiltonian H 0 is conserved. The second algorithm uses a nonlinear quantum walk with effective Hamiltonian H ( t ) = H 0 + λ | ψ | 2 , which arises in the Gross-Pitaevskii equation describing Bose-Einstein condensates. When the interactions between the bosons are repulsive, λ > 0, and there exists a range of fixed jumping rates such that the success probability reaches 1 with the same asymptotic runtime of the linear algorithm, but with a larger multiplicative constant. Rather than the effective Hamiltonian, we show that the expected value of H 0 + 1 2 λ | ψ | 2 {H_0} + {1 \over 2}\lambda |\psi {|^2} is conserved. The third algorithm utilizes attractive interactions, corresponding to λ < 0. In this case, there is a time-varying critical function for the jumping rate γ c ( t ) that causes the success probability to reach 1 more quickly than in the other two algorithms, and we show that the expected value of H ( t )/[ γ c ( t ) N ] is conserved.

arXiv:2503.06423Quantum Information and ComputationAug 1, 20251 citation

Quantum search with a continuous-time quantum walk in momentum space

Michele Delvecchio, Caspar Groiseau, Francesco Petiziol +2 more

Abstract The atom-optics kicked rotor can be used to prepare specific momentum distributions on a discrete basis set. We implement a continuous-time quantum walk (QW) and a quantum search protocol in this momentum basis. In particular we propose ways to identify a specific marked state from the final momentum distribution after the walker’s evolution. Our protocol is guided by current experimental possibilities making it accessible to experimentally implemented QWs with Bose–Einstein condensates.Abstract The atom-optics kicked rotor can be used to prepare specific momentum distributions on a discrete basis set. We implement a continuous-time quantum walk (QW) and a quantum search protocol in this momentum basis. In particular we propose ways to identify a specific marked state from the final momentum distribution after the walker’s evolution. Our protocol is guided by current experimental possibilities making it accessible to experimentally implemented QWs with Bose–Einstein condensates.

arXiv:2002.09139Journal of Physics B Atomic Molecular and Optical PhysicsDec 18, 201915 citations

Interactions in trapped Bose-Einstein condensates

David A. W. Hutchinson, R. J. Dodd, Nick P. Proukakis +4 more

International Conference on Atomic Physics (ICAP)Jan 1, 19990 citations

N

\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.