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/0106071 · Physical Review A

Grover algorithm with zero theoretical failure rate

Gui‐Lu Long

Published Jul 11, 2001• 456 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.64.022307

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

Multiphase matching in the Grover algorithm

F. Masafumi Toyama, W. van Dijk, Yukihisa Nogami +2 more

Phase matching has been studied for the Grover algorithm as a way of enhancing the efficiency of the quantum search. Recently Li and Li found that a particular form of phase matching yields, with a single Grover operation, a success probability greater than $25/27$ for finding the equal-amplitude superposition of marked states when the fraction of the marked states stored in a database state is greater than $1/3$. Although this single operation eliminates the oscillations of the success probability that occur with multiple Grover operations, the latter oscillations reappear with multiple iterations of Li and Li's phase matching. In this paper we introduce a multiphase matching subject to a certain matching rule by which we can obtain a multiple Grover operation that with only a few iterations yields a success probability that is almost constant and unity over a wide range of the fraction of marked items. As an example we show that a multiphase operation with six iterations yields a success probability between 99.8 and $100\text{ }%$ for a fraction of marked states of $1/10$ or larger.

arXiv:0801.2956•Physical Review A•Apr 30, 2008•26 citations

Grover’s Quantum Search Algorithm Based on Adaptive Phase Rotation

Shiyong Li

When the Grover's algorithm is applied to search an unordered database, the success probability usually decreases with the increase of marked items. The reason for this phenomenon was analyzed, the Grover iteration was studied, and a new adaptive phase rotation was proposed. With application of the new phase rotation, when the fraction of marked items is a rational number in range (3-5~(1/2)) / 8to 1/4, the success probability is equal to 1 after two Grover iterations; and when the fraction of marked items is greater than1/4, the success probability is equal to 1 after the only one Grover iteration. The effectiveness of the new phase rotation is verified by a search example.

Jisuanji fangzhen•Jan 1, 2009•0 citations

Exact results on Quantum search algorithm

Saptarshi Roy Chowdhury, Swarupananda Pradhan

We generalize Grover algorithm with two arbitrary phases in a density matrix set up. We give exact analytic expressions for the success probability after arbitrary number of iteration of the generalized Grover operator as a function of number of iterations, two phase angles (α, \{beta}) and parameter ξ introduced in the off diagonal terms of the density matrix in a sense to capture the coherence present in the initial quantum register. We extend Li and Li's idea and show for the phase matching condition α = -\{beta} = 0.35π with two iterations and ξ = 1, we can achieve success probability >= 0.8 only with a knowledge about the lower bound of λ = 0.166 where λ is the ratio of marked to total number states in the database. Finally we quantify success probability of the algorithm with decrease in coherence of the initial quantum state against modest noise in this simple model.

arXiv:2207.09762•Jul 20, 2022•0 citations

Adaptive Phase Matching in Grover’s Algorithm

Panchi Li, Kaoping Song

When the Grover’s algorithm is applied to search an unordered database, the successful probability usually decreases with the increase of marked items. In order to solve this problem, an adaptive phase matching is proposed. With application of the new phase matching, when the fraction of marked items is greater , the successful probability is equal to 1 with at most two Grover iterations. The validity of the new phase matching is verified by a search example.

Journal of Quantum Information Science•Jan 1, 2011•4 citations

Phase matching in quantum search algorithm

Saptarshi Roy Chowdhury, Sudarshan Baruah, Biswaranjan Dikshit

Abstract We systematically generalize the Grover algorithm in a density matrix formalism by exploiting the underlying two-dimensional subspace of the problem. Using this, we derive analytic expressions for the success probability after arbitrary iterations of the generalized Grover operator with two generic phase angles . We show for the phase matching condition with three iterations, success probability can be achieved only with knowledge about the lower bound , where λ is the ratio of marked to total number of states in the database. This result will improve the quantum search algorithm when applied to databases with unknown number of marked states in the specified regime of λ , at the cost of decreased efficiency in the smaller λ region.

Europhysics Letters (EPL)•Feb 8, 2023•2 citations
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φ.\ensuremath{\varphi}.\ensuremathφ. The rotation angle is given analytically to be \ensuremathφ=2arcsin(sin[\ensuremathπ/(4J+6)]/sin\ensuremathβ),\ensuremath{\varphi}=2\mathrm{arcsin}(\mathrm{sin}[\ensuremath{\pi}/(4J+6)]/\mathrm{sin}\ensuremath{\beta}),\ensuremathφ=2arcsin(sin[\ensuremathπ/(4J+6)]/sin\ensuremathβ), where sin\ensuremathβ=1/N,\mathrm{sin}\ensuremath{\beta}=1/\sqrt{N},sin\ensuremathβ=1/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π/2)\ensuremath−\ensuremathβ]/(2\ensuremathβ).[(\ensuremath{\pi}/2)\ensuremath{-}\ensuremath{\beta}]/(2\ensuremath{\beta}).[(\ensuremathπ/2)\ensuremath−\ensuremathβ]/(2\ensuremathβ). Upon measurement at the (J+1)th(J+1)\mathrm{th}(J+1)th iteration, the marked state is obtained with certainty.
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.
Phase matching has been studied for the Grover algorithm as a way of enhancing the efficiency of the quantum search. Recently Li and Li found that a particular form of phase matching yields, with a single Grover operation, a success probability greater than 25/2725/2725/27 for finding the equal-amplitude superposition of marked states when the fraction of the marked states stored in a database state is greater than 1/31/31/3. Although this single operation eliminates the oscillations of the success probability that occur with multiple Grover operations, the latter oscillations reappear with multiple iterations of Li and Li's phase matching. In this paper we introduce a multiphase matching subject to a certain matching rule by which we can obtain a multiple Grover operation that with only a few iterations yields a success probability that is almost constant and unity over a wide range of the fraction of marked items. As an example we show that a multiphase operation with six iterations yields a success probability between 99.8 and 100 100\text{ }%100  for a fraction of marked states of 1/101/101/10 or larger.
When the Grover's algorithm is applied to search an unordered database, the success probability usually decreases with the increase of marked items. The reason for this phenomenon was analyzed, the Grover iteration was studied, and a new adaptive phase rotation was proposed. With application of the new phase rotation, when the fraction of marked items is a rational number in range (3-5~(1/2)) / 8to 1/4, the success probability is equal to 1 after two Grover iterations; and when the fraction of marked items is greater than1/4, the success probability is equal to 1 after the only one Grover iteration. The effectiveness of the new phase rotation is verified by a search example.
We generalize Grover algorithm with two arbitrary phases in a density matrix set up. We give exact analytic expressions for the success probability after arbitrary number of iteration of the generalized Grover operator as a function of number of iterations, two phase angles (α, \{beta}) and parameter ξ introduced in the off diagonal terms of the density matrix in a sense to capture the coherence present in the initial quantum register. We extend Li and Li's idea and show for the phase matching condition α = -\{beta} = 0.35π with two iterations and ξ = 1, we can achieve success probability >= 0.8 only with a knowledge about the lower bound of λ = 0.166 where λ is the ratio of marked to total number states in the database. Finally we quantify success probability of the algorithm with decrease in coherence of the initial quantum state against modest noise in this simple model.
Abstract We systematically generalize the Grover algorithm in a density matrix formalism by exploiting the underlying two-dimensional subspace of the problem. Using this, we derive analytic expressions for the success probability after arbitrary iterations of the generalized Grover operator with two generic phase angles . We show for the phase matching condition with three iterations, success probability can be achieved only with knowledge about the lower bound , where λ is the ratio of marked to total number of states in the database. This result will improve the quantum search algorithm when applied to databases with unknown number of marked states in the specified regime of λ , at the cost of decreased efficiency in the smaller λ region.