APS » PROLA » Phys. Rev. A » Volume 60 » Issue 4
< Previous article | Next article >

Phys. Rev. A 60, 2746 - 2751 (1999)

Grover’s quantum searching algorithm is optimal

Download: PDF (77 kB) or Buy this Article (Use Article Pack) Export: BibTeX or EndNote (RIS)

Christof Zalka *
T-6, Theoretical Astrophysics, MS B288, Los Alamos National Laboratory, Los Alamos, New Mexico 87545

Received 20 February 1998; revised 28 December 1998

I show that for any number of oracle lookups up to about π/4 sqrt[N], Grover’s quantum searching algorithm gives the maximal possible probability of finding the desired element. I explain why this is also true for quantum algorithms which use measurements during the computation. I also show that unfortunately quantum searching cannot be parallelized better than by assigning different parts of the search space to independent quantum computers.


©1999 The American Physical Society

URL: http://link.aps.org/doi/10.1103/PhysRevA.60.2746
DOI: 10.1103/PhysRevA.60.2746
PACS: 03.67.Lx, 03.65.Bz

* Electronic address: zalka@t6-serv.lanl.gov

[ Abstract  |  Previous article  |  Next article  |  Issue 4 ]