2008/05/31 by V. Potocek, Václav Potoček, A. Gabris +4
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Combinatorics #Computer science #Constant (computer programming) #Discrete mathematics #Element (criminal law) #Geometry #Hypercube #Limit (mathematics) #Mathematics #Oracle #Physics #Point (geometry) #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum algorithm #Quantum mechanics #Quantum walk #Quantum-Dot Cellular Automata #Random walk #Statistics #quant-ph
paper · pdf · doi:10.1103/physreva.79.012325
published as Phys. Rev. A 79, 012325 (2009) · 7 pages, 2 figures. Major revision according to referee report
arxiv created 2008/12/12 · openalex publication_date 2009/01/28 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
Shenvi, Kempe, and Whaley's quantum random-walk search (SKW) algorithm [Phys. Rev. A 67, 052307 (2003)] is known to require O(√(N)) number of oracle queries to find the marked element, where N is the size of the search space. The overall time complexity of the SKW algorithm differs from the best achievable on a quantum computer only by a constant factor. We present improvements to the SKW algorithm which yield a significant increase in success probability, and an improvement on query complexity such that the theoretical limit of a search algorithm succeeding with probability close to one is reached. We point out which improvement can be applied if there is more than one marked element to find.