Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0010077 · Physical Review A

Analysis of generalized Grover quantum search algorithms using recursion equations

Eli Biham, Ofer Biham, David Biron, Markus Grassl, Daniel A. Lidar, Daniel Shapira

Published Dec 13, 2000• 72 citations
arXivHTMLPDF

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, ${P}_{\mathrm{max}}.$ Both T and ${P}_{\mathrm{max}}$ 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.

DOI
10.1103/physreva.63.012310

Related papers

Grover’s quantum search algorithm for an arbitrary initial amplitude distribution

Eli Biham, Ofer Biham, David Biron +2 more

Grover's algorithm for quantum searching is generalized to deal with arbitrary initial complex amplitude distributions. First-order linear difference equations are found for the time evolution of the amplitudes of the marked and unmarked states. These equations are solved exactly. New expressions are derived for the optimal time of measurement and the maximal probability of success. They 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. Our results imply that Grover's algorithm is robust against modest noise in the amplitude initialization procedure.

arXiv:quant-ph/9807027•Physical Review A•Oct 1, 1999•119 citations

Generalized Grover Search Algorithm for Arbitrary Initial Amplitude Distribution

David Biron, Ofer Biham, Eli Biham +2 more

Grover's algorithm for quantum searching of a database is generalized to deal with arbitrary initial amplitude distributions. First order linear difference equations are found for the time evolution of the amplitudes of the r marked and N-r unmarked states. These equations are solved exactly. An expression for the optimal measurement time T \sim O(\sqrt{N/r}) is derived which is shown to depend only on the initial average amplitudes of the marked and unmarked states. A bound on the probability of measuring a marked state is derived, which depends only on the standard deviation of the initial amplitude distributions of the marked or unmarked states.

arXiv:quant-ph/9801066•Jan 28, 1998•3 citations

Phase matching in quantum searching

Gui‐Lu Long, Yan Li, Wei Lin Zhang +2 more

Each iteration in Grover’s original quantum search algorithm contains 4 steps: two Hadamard-Walsh transformations and two amplitudes inversions. When the inversion of the marked state is replaced by arbitrary phase rotation θ and the inversion for the prepared state |γ 〉 is replaced by rotation through φ, we found that these phase rotations must satisfy a matching condition θ = φ. Approximate formula for the amplitude of the marked state after an arbitrary number of iterations are also derived. When phase matching is obtained, we found that the generalized quantum search is still a rotation in 2-dimensional space, but with a small angle β ′ ≈ (2sin θ 2)β, where θ is the angle of phase rotation of the marked state and 2β is the angle of U(2) rotation when the phase rotations are the inversions in the original version. We give also a simple explanation of the phase matching requirement.

•Jan 1, 1999•109 citations

Analysis of Grover’s quantum search algorithm as a dynamical system

Ofer Biham, Daniel Shapira, Yishai Shimoni

Grover's quantum search algorithm is analyzed for the case in which the initial state is an arbitrary pure quantum state $|\ensuremath{\varphi}〉$ of n qubits. It is shown that the optimal time to perform the measurement is independent of $|\ensuremath{\varphi}〉,$ namely, it is identical to the optimal time in the original algorithm in which $|\ensuremath{\varphi}〉=|0〉,$ with the same number of marked states, r. The probability of success ${P}_{\mathrm{s}}$ is obtained in terms of the amplitudes of the state $|\ensuremath{\varphi}〉$ 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.

arXiv:quant-ph/0307141•Physical Review A•Aug 29, 2003•15 citations

General SU(2) formulation for quantum searching with certainty

Jin-Yuan Hsieh, Che‐Ming Li

A general quantum search algorithm with arbitrary unitary transformations and an arbitrary initial state is considered in this work. To search a marked state with certainty, we have derived, using an SU(2) representation: (1) the matching condition relating the phase rotations in the algorithm, (2) a concise formula for evaluating the required number of iterations for the search, and (3) the final state after the search, with a complex phase in its amplitude. Moreover, the optimal choices and modifications of the phase angles in the Grover kernel are also studied.

arXiv:quant-ph/0112035•Physical Review A•May 7, 2002•16 citations

Research on Quantum Searching Algorithms Based on Phase Shifts

Zhong Pu-Cha, Wan‐Su Bao

One iterative in Grover's original quantum search algorithm consists of two Hadamard–Walsh transformations, a selective amplitude inversion and a diffusion amplitude inversion. We concentrate on the relation among the probability of success of the algorithm, the phase shifts, the number of target items and the number of iterations via replacing the two amplitude inversions by phase shifts of an arbitrary ϕ = ϕ(0 ⩽ ϕ, ϕ ⩽ 2π). Then, according to the relation we find out the optimal phase shifts when the number of iterations is given. We present a new quantum search algorithm based on the optimal phase shifts of 1.018 after 0.5π/ iterations. The new algorithm can obtain either a single target item or multiple target items in the search space with the probability of success at least 93.43%.

Chinese Physics Letters•Jul 29, 2008•7 citations
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.{P}_{\mathrm{max}}.Pmax​. Both T and Pmax{P}_{\mathrm{max}}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.
Grover's algorithm for quantum searching is generalized to deal with arbitrary initial complex amplitude distributions. First-order linear difference equations are found for the time evolution of the amplitudes of the marked and unmarked states. These equations are solved exactly. New expressions are derived for the optimal time of measurement and the maximal probability of success. They 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. Our results imply that Grover's algorithm is robust against modest noise in the amplitude initialization procedure.
Grover's algorithm for quantum searching of a database is generalized to deal with arbitrary initial amplitude distributions. First order linear difference equations are found for the time evolution of the amplitudes of the r marked and N-r unmarked states. These equations are solved exactly. An expression for the optimal measurement time T \sim O(\sqrt{N/r}) is derived which is shown to depend only on the initial average amplitudes of the marked and unmarked states. A bound on the probability of measuring a marked state is derived, which depends only on the standard deviation of the initial amplitude distributions of the marked or unmarked states.
Each iteration in Grover’s original quantum search algorithm contains 4 steps: two Hadamard-Walsh transformations and two amplitudes inversions. When the inversion of the marked state is replaced by arbitrary phase rotation θ and the inversion for the prepared state |γ 〉 is replaced by rotation through φ, we found that these phase rotations must satisfy a matching condition θ = φ. Approximate formula for the amplitude of the marked state after an arbitrary number of iterations are also derived. When phase matching is obtained, we found that the generalized quantum search is still a rotation in 2-dimensional space, but with a small angle β ′ ≈ (2sin θ 2)β, where θ is the angle of phase rotation of the marked state and 2β is the angle of U(2) rotation when the phase rotations are the inversions in the original version. We give also a simple explanation of the phase matching requirement.
Grover's quantum search algorithm is analyzed for the case in which the initial state is an arbitrary pure quantum state $|\ensuremath{\varphi}〉$ of n qubits. It is shown that the optimal time to perform the measurement is independent of $|\ensuremath{\varphi}〉,$ namely, it is identical to the optimal time in the original algorithm in which $|\ensuremath{\varphi}〉=|0〉,$ with the same number of marked states, r. The probability of success Ps{P}_{\mathrm{s}}Ps​ is obtained in terms of the amplitudes of the state $|\ensuremath{\varphi}〉$ 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.
A general quantum search algorithm with arbitrary unitary transformations and an arbitrary initial state is considered in this work. To search a marked state with certainty, we have derived, using an SU(2) representation: (1) the matching condition relating the phase rotations in the algorithm, (2) a concise formula for evaluating the required number of iterations for the search, and (3) the final state after the search, with a complex phase in its amplitude. Moreover, the optimal choices and modifications of the phase angles in the Grover kernel are also studied.
One iterative in Grover's original quantum search algorithm consists of two Hadamard–Walsh transformations, a selective amplitude inversion and a diffusion amplitude inversion. We concentrate on the relation among the probability of success of the algorithm, the phase shifts, the number of target items and the number of iterations via replacing the two amplitude inversions by phase shifts of an arbitrary ϕ = ϕ(0 ⩽ ϕ, ϕ ⩽ 2π). Then, according to the relation we find out the optimal phase shifts when the number of iterations is given. We present a new quantum search algorithm based on the optimal phase shifts of 1.018 after 0.5π/ iterations. The new algorithm can obtain either a single target item or multiple target items in the search space with the probability of success at least 93.43%.