Grover’s quantum searching algorithm is optimal

Christof Zalka
Phys. Rev. A 60, 2746 – Published 1 October 1999
PDFExport Citation

Abstract

I show that for any number of oracle lookups up to about π/4N, 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.

  • Received 20 February 1998

DOI:https://doi.org/10.1103/PhysRevA.60.2746

©1999 American Physical Society

Authors & Affiliations

Christof Zalka*

  • T-6, Theoretical Astrophysics, MS B288, Los Alamos National Laboratory, Los Alamos, New Mexico 87545

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

References (Subscription Required)

Click to Expand
Issue

Vol. 60, Iss. 4 — October 1999

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×