2020/09/16 by Herzog, Basile, Di Molfetta, Giuseppe
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2009.07800
We provide numerical evidence that the nonlinear searching algorithm introduced by Wong and Meyer \citemeyer2013nonlinear, rephrased in terms of quantum walks with effective nonlinear phase, can be extended to the finite 2-dimensional grid, keeping the same computational advantage \BHgwith respect to the classical algorithms. For this purpose, we have considered the free lattice Hamiltonian, with linear dispersion relation introduced by Childs and Ge \citeChilds2014. The numerical simulations showed that the walker finds the marked vertex in O(N1/4 log3/4 N) steps, with probability O(1/log N), for an overall complexity of O(N1/4log7/4N). 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.