Generalized quantum search with parallelism

Robert M. Gingrich, Colin P. Williams, and Nicolas J. Cerf
Phys. Rev. A 61, 052313 – Published 19 April 2000
PDFExport Citation

Abstract

We generalize Grover’s unstructured quantum search algorithm to enable it to work with arbitrary starting superpositions and arbitrary unitary operators. We show that the generalized quantum search algorithm, when cast in a special orthonormal basis, can be understood as performing an exact rotation of a starting superposition into a target superposition. We derive a formula for the success probability of the generalized quantum search algorithm after n rounds of amplitude amplification. We then use this formula to determine the optimal strategy for a punctuated quantum search algorithm, i.e., one in which the amplitude amplified state is observed before the point of maximum success probability. On average, the optimal strategy is about 12% better than the naive use of Grover’s algorithm. The speedup obtained is not dramatic but it illustrates that a hybrid use of quantum computing and classical computing techniques can yield a performance that is better than either alone. In addition, we show that a punctuated quantum algorithm that takes the same average computation time as Grover’s standard algorithm only requires half the coherence time. We then extend the analysis to the case of a society of k quantum searches acting in parallel. We derive an analytic formula that connects the degree of parallelism with the expected computation time for k-parallel quantum search. The resulting parallel speedup scales as O(k), while the minimum number of agents needed to ensure success, k, decreases as the inverse of the square of the achievable coherence time. This result has practical significance for the design of rudimentary quantum computers that are likely to have a limited coherence time.

  • Received 3 November 1999

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

©2000 American Physical Society

Authors & Affiliations

Robert M. Gingrich1, Colin P. Williams2, and Nicolas J. Cerf1,2,3

  • 1W. K. Kellogg Radiation Laboratory, California Institute of Technology, Pasadena, California 91125
  • 2Information and Computing Technologies Research Section, Jet Propulsion Laboratory, California Institute of Technology, Pasadena, California 91109
  • 3Ecole Polytechnique, Université Libre de Bruxelles, B-1050 Brussels, Belgium

References (Subscription Required)

Click to Expand
Issue

Vol. 61, Iss. 5 — May 2000

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
×