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/9904077 · Communications in Theoretical Physics

Arbitrary Phase Rotation of the Marked State Cannot Be Used for Grover's Quantum Search Algorithm

Long GuiLu, Zhang WeiLin, Li YanSong, Niu Li

Published Oct 30, 1999• 64 citations
arXivHTMLPDF

Abstract

A misunderstanding that an arbitrary phase rotation of the marked state together with the inversion about average operation can be used to construct a (less efficient) quantum search algorithm is cleared. The rotation of the phase of the marked state is not only the choice for efficiency, but also vital in Grover's quantum search algorithm. The results also show that Grover's quantum search algorithm is robust.

DOI
10.1088/0253-6102/32/3/335

Related papers

Phase Matching in Quantum Searching and the Improved Grover Algorithm

Yang Sun

We briefly introduced some of our recent work related to the phase matching condition in quantum searching algorithms and the improved Grover algorithm. When one replaces the two phase inversions in the Grover algorithm with arbitrary phase rotations, the modified algorithm usually fails in searching the marked state unless a phase matching condition is satisfied between the two phases. The Grover algorithm is not 100% in success rate, an improved Grover algorithm with zero-failure rate is given by replacing the phase inversions with angles that depends on the size of the database. Other aspects of the Grover algorithm such as the SO(3) picture of quantum searching, the dominant gate imperfections in the Grover algorithm are also mentioned.

Yuanzihe wuli pinglun•Jan 1, 2004•7 citations

A novel SO(3) picture for quantum searching

Long, Gui Lu, Chang Cun Tu, Yan Li +2 more

An SO(3) picture of the generalized Grover's quantum searching algorithm,with arbitrary unitary transformation and with arbitrary phase rotations, is constructed. In this picture, any quantum search operation is a rotation in a 3 dimensional space. Exact formulas for the rotation angle and rotational axis are given. The probability of finding the marked state is just $(z+1)/2$, where z is the z-component of the state vector. Exact formulas for this probability is easily obtained. The phase matching requirement and the failure of algorithm when phase mismatches are clearly explained.

arXiv:quant-ph/9911004•Nov 3, 1999•2 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

Grover algorithm with zero theoretical failure rate

Gui‐Lu Long

In a standard Grover's algorithm for quantum searching, the probability of finding the marked item is not exactly 1. In this paper we present a modified version of Grover's algorithm that searches a marked state with full successful rate. The modification is done by replacing the phase inversion by phase rotation through angle $\ensuremath{\varphi}.$ The rotation angle is given analytically to be $\ensuremath{\varphi}=2\mathrm{arcsin}(\mathrm{sin}[\ensuremath{\pi}/(4J+6)]/\mathrm{sin}\ensuremath{\beta}),$ where $\mathrm{sin}\ensuremath{\beta}=1/\sqrt{N},$ N is the number of items in the database, and J is any integer equal to or greater than the integer part of $[(\ensuremath{\pi}/2)\ensuremath{-}\ensuremath{\beta}]/(2\ensuremath{\beta}).$ Upon measurement at the $(J+1)\mathrm{th}$ iteration, the marked state is obtained with certainty.

arXiv:quant-ph/0106071•Physical Review A•Jul 11, 2001•456 citations

An intrinsic limitation on the size of quantum database

Long, Gui Lu, Yan Li, Wei Lin Zhang +1 more

It is found that Grover's quantum search algorithm is not robust against phase inversion and Hadmard transformation inaccuracies. Imperfect phase inversions and Hadmard-Walsh transformations in Grover's quantum search algorithm lead to reductions in the maximum probability of the marked state and affect the efficiency of the algorithm. even in the absence of decoherence. Given the degrees of inaccuracies, we find that to guarantee half rate of success, the size of the database should be in the order of $O({1 \over δ^2})$, where $δ$ is the uncertainty.

arXiv:quant-ph/9910076•Oct 16, 1999•1 citation

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
A misunderstanding that an arbitrary phase rotation of the marked state together with the inversion about average operation can be used to construct a (less efficient) quantum search algorithm is cleared. The rotation of the phase of the marked state is not only the choice for efficiency, but also vital in Grover's quantum search algorithm. The results also show that Grover's quantum search algorithm is robust.
We briefly introduced some of our recent work related to the phase matching condition in quantum searching algorithms and the improved Grover algorithm. When one replaces the two phase inversions in the Grover algorithm with arbitrary phase rotations, the modified algorithm usually fails in searching the marked state unless a phase matching condition is satisfied between the two phases. The Grover algorithm is not 100% in success rate, an improved Grover algorithm with zero-failure rate is given by replacing the phase inversions with angles that depends on the size of the database. Other aspects of the Grover algorithm such as the SO(3) picture of quantum searching, the dominant gate imperfections in the Grover algorithm are also mentioned.
An SO(3) picture of the generalized Grover's quantum searching algorithm,with arbitrary unitary transformation and with arbitrary phase rotations, is constructed. In this picture, any quantum search operation is a rotation in a 3 dimensional space. Exact formulas for the rotation angle and rotational axis are given. The probability of finding the marked state is just (z+1)/2(z+1)/2(z+1)/2, where z is the z-component of the state vector. Exact formulas for this probability is easily obtained. The phase matching requirement and the failure of algorithm when phase mismatches are clearly explained.
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.
In a standard Grover's algorithm for quantum searching, the probability of finding the marked item is not exactly 1. In this paper we present a modified version of Grover's algorithm that searches a marked state with full successful rate. The modification is done by replacing the phase inversion by phase rotation through angle $\ensuremath{\varphi}.$ The rotation angle is given analytically to be $\ensuremath{\varphi}=2\mathrm{arcsin}(\mathrm{sin}[\ensuremath{\pi}/(4J+6)]/\mathrm{sin}\ensuremath{\beta}),$ where $\mathrm{sin}\ensuremath{\beta}=1/\sqrt{N},$ N is the number of items in the database, and J is any integer equal to or greater than the integer part of $[(\ensuremath{\pi}/2)\ensuremath{-}\ensuremath{\beta}]/(2\ensuremath{\beta}).$ Upon measurement at the (J+1)th(J+1)\mathrm{th}(J+1)th iteration, the marked state is obtained with certainty.
It is found that Grover's quantum search algorithm is not robust against phase inversion and Hadmard transformation inaccuracies. Imperfect phase inversions and Hadmard-Walsh transformations in Grover's quantum search algorithm lead to reductions in the maximum probability of the marked state and affect the efficiency of the algorithm. even in the absence of decoherence. Given the degrees of inaccuracies, we find that to guarantee half rate of success, the size of the database should be in the order of O(1δ2)O({1 \over δ^2})O(δ21​), where δδδ is the uncertainty.
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.