Analysis of Grover’s quantum search algorithm as a dynamical system
Authors:
- Ofer BihamOBOfer Biham
- Daniel ShapiraDSDaniel Shapira
- Yishai ShimoniYSYishai Shimoni
- 29 August 2003
- journal article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 68 (2)
Abstract
Grover's quantum search algorithm is analyzed for the case in which the initial state is an arbitrary pure quantum state $|\phi>$ of $n$ qubits. It is shown that the optimal time to perform the measurement is independent of $| \phi>$, namely, it is identical to the optimal time in the original algorithm in which $| \phi > = | 0>$, with the same number of marked states, $r$. The probability of success $P_{\rm s}$ is obtained, in terms of the amplitudes of the state $| \phi>$, and is shown to be independent of $r$. A class of states, which includes fixed points and cycles of the Grover iteration operator is identified. The relevance of these results in the context of using the success probability as an entanglement measure is discussed. In particular, the Groverian entanglement measure, previously limited to a single marked state, is generalized to the case of several marked states
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Grover’s quantum search algorithm for an arbitrary initial mixed statePhysical Review A, 2002
- Entanglement monotone derived from Grover’s algorithmPhysical Review A, 2002
- Analysis of generalized Grover quantum search algorithms using recursion equationsPhysical Review A, 2000
- Synthesis of Quantum Superpositions by Quantum ComputationPhysical Review Letters, 2000
- Generalized quantum search with parallelismPhysical Review A, 2000
- Grover's search algorithm: An optical approachJournal of Modern Optics, 2000
- Grover’s quantum search algorithm for an arbitrary initial amplitude distributionPhysical Review A, 1999
- Single quantum querying of a databasePhysical Review A, 1998
- Tight Bounds on Quantum SearchingFortschritte der Physik, 1998
- Quantum Computers Can Search Arbitrarily Large Databases by a Single QueryPhysical Review Letters, 1997