Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification
Andris Ambainisa, Artūrs Bačkursa, Nikolajs Nahimovsa, Raitis Ozolsa, Alexander Rivosha
- aFaculty of Computing, University of Latvia, Raina bulv. 19, Riga, LV-1586, Latvia
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
We study search by quantum walk on a finite two dimensional grid. The algorithm of Ambainis, Kempe, Rivosh [AKR05] uses \(O(\sqrt{N \log{N}})\) steps and finds a marked location with probability O(1 / logN) for grid of size \(\sqrt{N} \times \sqrt{N}\). This probability is small, thus [AKR05] needs amplitude amplification to get Θ(1) probability. The amplitude amplification adds an additional \(O(\sqrt{\log{N}})\) factor to the number of steps, making it \(O(\sqrt{N} \log{N})\).
TL;DRThis work studies search by quantum walk on a finite two dimensional grid using amplitude amplification to find a marked location with probability O(1 / logN) for grid of size \(\sqrt{N} \times \sqRT{N}\). (Semantic Scholar)