6533b862fe1ef96bd12c7555
RESEARCH PRODUCT
Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification
Andris AmbainisNikolajs NahimovsArturs BackursAlexander RivoshRaitis Ozolssubject
CombinatoricsDiscrete mathematicsAmplitude amplification010201 computation theory & mathematics0103 physical sciencesQuantum walk0102 computer and information sciencesNuclear Experiment010306 general physicsGrid01 natural sciencesMathematicsdescription
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})\).
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2013-01-01 |