2011/12/14 by Andris Ambainis, Arturs Backurs, Ambainis, Andris +8
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning and Algorithms #Optimization and Search Problems #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata #cs.CC #cs.DS #quant-ph
paper · pdf · doi:10.48550/arxiv.1112.3337
22 pages, 3 figures
arxiv created 2011/12/14 · openalex publication_date 2011/12/14 · arxiv updated 2011/12/15 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
We study search by quantum walk on a finite two dimensional grid. The algorithm of Ambainis, Kempe, Rivosh (quant-ph/0402107) takes O(√(N log N)) steps and finds a marked location with probability O(1/log N) for grid of size √(N) * √(N). This probability is small, thus amplitude amplification is needed to achieve Θ(1) success probability. The amplitude amplification adds an additional O(√(log N)) factor to the number of steps, making it O(√(N) log N). In this paper, we show that despite a small probability to find a marked location, the probability to be within an O(√(N)) neighbourhood (at an O(√[4]N) distance) of the marked location is Θ(1). This allows to skip amplitude amplification step and leads to an O(√(log N)) speed-up. We describe the results of numerical experiments supporting this idea, and we prove this fact analytically.