Optimized quantum random-walk search algorithms

Simple item page
dc.creatorPotocek, V.
dc.creatorGabris, A.
dc.creatorKiss, T.
dc.creatorJex, I.
dc.date2008-05-28
dc.date2008-12-12
dc.date.accessioned2026-07-07T12:54:02Z
dc.date.available2026-07-07T12:54:02Z
dc.descriptionShenvi, Kempe and Whaley's quantum random-walk search (SKW) algorithm [Phys. Rev. A 67, 052307 (2003)] is known to require $O(\sqrt 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 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.
dc.description7 pages, 2 figures. Major revision according to referee report
dc.identifierhttps://arxiv.org/abs/0805.4347
dc.identifierhttp://arxiv.org/abs/0805.4347
dc.identifierPhys. Rev. A 79, 012325 (2009)
dc.identifierdoi:10.1103/PhysRevA.79.012325
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/223793
dc.subjectQuantum Physics
dc.titleOptimized quantum random-walk search algorithms
dc.typetext

Files

Collections

arXiv