Searching via nonlinear quantum walk on the 2D-grid

Abstract

We provide numerical evidence that the nonlinear searching algorithm introduced by Wong and Meyer \cite{meyer2013nonlinear}, rephrased in terms of quantum walks with effective nonlinear phase, can be extended to the finite 2-dimensional grid, keeping the same computational advantage \BHg{with} respect to the classical algorithms. For this purpose, we have considered the free lattice Hamiltonian, with linear dispersion relation introduced by Childs and Ge \cite{Childs_2014}. The numerical simulations showed that the walker finds the marked vertex in $O(N^{1/4}{\log }^{3/4}N)$ steps, with probability $O(1/\log N)$, for an overall complexity of $O(N^{1/4}{\log }^{7/4}N)$. We also proved that there exists an optimal choice of the walker parameters to avoid that the time measurement precision affects the complexity searching time of the algorithm.

References in corpus (18)

• Universal computation by quantum walk
• Exponential algorithmic speedup by quantum walk
• Spatial search by quantum walk
• Universal computation by multi-particle quantum walk
• Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
• Spatial search and the Dirac equation
• Topological quantum walks in momentum space with a Bose-Einstein condensate
• Quantum Walks as simulators of neutrino oscillations in vacuum and matter
• Nonlinear optical Galton board
• Quantum walks as massless Dirac Fermions in curved Space-Time
• Spatial search by continuous-time quantum walks on crystal lattices
• The Dirac equation as a quantum walk over the honeycomb and triangular lattices
• Quantum search on graphene lattices
• Quantum Search with General Nonlinearities
• Finding a marked node on any graph by continuous-time quantum walk
• The Grover search as a naturally occurring phenomenon
• Quantum walk of a Bose-Einstein condensate in the Brillouin zone
• Quantum search with interacting Bose-Einstein condensates