Analysis of generalized Grover quantum search algorithms using recursion equations

Eli Biham, Ofer Biham, David Biron, Markus Grassl, Daniel A. Lidar, and Daniel Shapira
Phys. Rev. A 63, 012310 – Published 13 December 2000
PDFExport Citation

Abstract

The recursion equation analysis of Grover’s quantum search algorithm presented by Biham et al. [Phys. Rev. A 60, 2742 (1999)] is generalized. It is applied to the large class of Grover-type algorithms in which the Hadamard transform is replaced by any other unitary transformation and the phase inversion is replaced by a rotation by an arbitrary angle. The time evolution of the amplitudes of the marked and unmarked states, for any initial complex amplitude distribution, is expressed using first-order linear difference equations. These equations are solved exactly. The solution provides the number of iterations T after which the probability of finding a marked state upon measurement is the highest, as well as the value of this probability, Pmax. Both T and Pmax are found to depend on the averages and variances of the initial amplitude distributions of the marked and unmarked states, but not on higher moments.

  • Received 18 August 2000

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

©2000 American Physical Society

Authors & Affiliations

Eli Biham1, Ofer Biham2, David Biron2,*, Markus Grassl3, Daniel A. Lidar4,†, and Daniel Shapira2

  • 1Computer Science Department, Technion, Haifa 32000, Israel
  • 2Racah Institute of Physics, The Hebrew University, Jerusalem 91904, Israel
  • 3Institut für Algorithmen und Kognitive Systeme, Universität Karlsruhe, Am Fasanengarten 5, D-76128 Karlsruhe, Germany
  • 4Department of Chemistry, University of California, Berkeley, California 94720

  • *Present address: Department of Physics of Complex Systems, Weizmann Institute of Science, Rehovot 76100, Israel.
  • Permanent address: Chemistry Department, University of Toronto, 80 St. George Street, Toronto, ON, Canada M5S 3H6.

References (Subscription Required)

Click to Expand
Issue

Vol. 63, Iss. 1 — January 2001

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
×