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:0801.2956 · Physical Review A

Multiphase matching in the Grover algorithm

F. Masafumi Toyama, W. van Dijk, Yukihisa Nogami, M. Tabuchi, Yuki Kimura

Published Apr 30, 2008• 26 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.77.042324

Related papers

Matched-multiphase Grover algorithm for a small number of marked states

F. Masafumi Toyama, S. Kasai, W. van Dijk +1 more

Recently, we proposed a multiphase-matching method for the Grover algorithm with a matching rule for multiple phases ${\ensuremath{\alpha}}_{j}$ and ${\ensuremath{\beta}}_{j}$, $j=1,\dots{},k$, where $k$ is the number of Grover operations. The phases are matched such that ${\ensuremath{\alpha}}_{j}=\ensuremath{-}{\ensuremath{\beta}}_{k\ensuremath{-}j+1}$ globally over a sequence of $k$ Grover operations. The success probability ${P}_{6}(\ensuremath{\lambda})$ for $k=6$ was found to be almost constant and unity over a wide range of $\ensuremath{\lambda}$, i.e., $0.107\phantom{\rule{0.2em}{0ex}}77\ensuremath{\leqslant}\ensuremath{\lambda}\ensuremath{\leqslant}1$, where $\ensuremath{\lambda}$ is the fraction of marked items in a database state. For $\ensuremath{\lambda}<0.107\phantom{\rule{0.2em}{0ex}}77$, however, ${P}_{6}(\ensuremath{\lambda})$ decreases rapidly to zero as $\ensuremath{\lambda}$ decreases and the efficiency of the method deteriorates. In this Brief Report we show that the difficulty with small values of $\ensuremath{\lambda}$ mentioned above can be alleviated by increasing the number of operations $k$. With $k=20$, for example, we find a value of ${P}_{20}(\ensuremath{\lambda})$ that is almost constant and unity in the region of small $\ensuremath{\lambda}$ where the matching with six Grover operations is not effective. The matching with $k=6$ and the one with $k=20$ complement each other so that the entire range of $0\ensuremath{\lesssim}\ensuremath{\lambda}<1$ can be well covered.

Physical Review A•Jan 12, 2009•10 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 grover's algorithm

Xin Li, Kaoping Song, Ning Sun +1 more

When the Grover's algorithm is applied to search an unordered database, the probability of getting correct results usually decreases with the increase of marked items. The reason for this phenomenon is analyzed in this Letter, the Grover iteration is studied, and a new phase matching is proposed. With application of the new phase matching, when the fraction of marked items is greater than 1/3, the probability of getting correct results is greater than 25/27 with only one Grover iteration. The validity of the new phase matching is verified by a search example.

Chinese Control Conference (CCC)•Jul 26, 2013•1 citation

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

Complementary-multiphase quantum search for all numbers of target items

Tan Li, Wan‐Su Bao, He-Liang Huang +7 more

Grover's algorithm achieves a quadratic speedup over classical algorithms, but it is considered necessary to know the value of $\ensuremath{\lambda}$ exactly [Phys. Rev. Lett. 95, 150501 (2005); Phys. Rev. Lett. 113, 210501 (2014)], where $\ensuremath{\lambda}$ is the fraction of target items in the database. In this paper, we find out that the Grover algorithm can actually apply to the case where one can identify the range that $\ensuremath{\lambda}$ belongs to from a given series of disjoint ranges. However, Grover's algorithm still cannot maintain high success probability when there exist multiple target items. For this problem, we proposed a complementary-multiphase quantum search algorithm in which multiple phases complement each other so that the overall high success probability can be maintained. Compared to the existing algorithms, in the case defined above, our algorithm achieves the following three goals simultaneously: (1) the success probability can be no less than any given value between 0 and 1, (2) the algorithm is applicable to the entire range of $\ensuremath{\lambda}$, and (3) the number of iterations is almost the same as that of Grover's algorithm. Especially compared to the optimal fixed-point algorithm [Phys. Rev. Lett. 113, 210501 (2014)], our algorithm uses fewer iterations to achieve a success probability greater than 82.71%, e.g., when the minimum success probability is required to be 99.25%, the number of iterations can be reduced by 50%.

arXiv:1806.03259•Physical Review A•Dec 6, 2018•4 citations

Phase Matching in Quantum Searching Algorithm with Weighted Targets

Panchi Li, Shiyong Li

As searching targets in an unordered database with Grover's algorithm,difference in marked items is not taken into consideration.If fraction of marked items is greater than 1/4,success probability of search decreases rapidly with increase of marked items.When the fraction of marked items is greater than 1/2,the algorithm is disabled.Aiming at above problems,an improved Grover's algorithm with weighted targets is proposed in which every target is assigned a weight coefficient according to its significance.With these weight coefficients,targets are represented as quantum superpositions which make probability getting target equal to its weight coefficient.An adaptive phase matching method is proposed based on weighted targets.The directions of phase rotations are contrary,and amplitudes of the two phase rotations are determined by inner-product of target quantum superposition and initial state of the system.As the inner-product is greater than(((3-5)/8)~(1/2),) success probability is equal to 1 with two steps of Grover iteration at most.The improved quantum searching algorithm and the new phase matching are verified by an example.

Jisuan wuli•Jan 1, 2008•1 citation
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.
Recently, we proposed a multiphase-matching method for the Grover algorithm with a matching rule for multiple phases ${\ensuremath{\alpha}}_{j}$ and ${\ensuremath{\beta}}_{j}$, j=1,…,kj=1,\dots{},kj=1,…,k, where kkk is the number of Grover operations. The phases are matched such that ${\ensuremath{\alpha}}_{j}=\ensuremath{-}{\ensuremath{\beta}}_{k\ensuremath{-}j+1}$ globally over a sequence of kkk Grover operations. The success probability ${P}_{6}(\ensuremath{\lambda})$ for k=6k=6k=6 was found to be almost constant and unity over a wide range of $\ensuremath{\lambda}$, i.e., $0.107\phantom{\rule{0.2em}{0ex}}77\ensuremath{\leqslant}\ensuremath{\lambda}\ensuremath{\leqslant}1$, where $\ensuremath{\lambda}$ is the fraction of marked items in a database state. For $\ensuremath{\lambda}<0.107\phantom{\rule{0.2em}{0ex}}77$, however, ${P}_{6}(\ensuremath{\lambda})$ decreases rapidly to zero as $\ensuremath{\lambda}$ decreases and the efficiency of the method deteriorates. In this Brief Report we show that the difficulty with small values of $\ensuremath{\lambda}$ mentioned above can be alleviated by increasing the number of operations kkk. With k=20k=20k=20, for example, we find a value of ${P}_{20}(\ensuremath{\lambda})$ that is almost constant and unity in the region of small $\ensuremath{\lambda}$ where the matching with six Grover operations is not effective. The matching with k=6k=6k=6 and the one with k=20k=20k=20 complement each other so that the entire range of $0\ensuremath{\lesssim}\ensuremath{\lambda}<1$ can be well covered.
When the Grover's algorithm is applied to search an unordered database, the probability of getting correct results usually decreases with the increase of marked items. The reason for this phenomenon is analyzed in this Letter, the Grover iteration is studied, and a new phase matching is proposed. With application of the new phase matching, when the fraction of marked items is greater than 1/3, the probability of getting correct results is greater than 25/27 with only one Grover iteration. The validity of the new phase matching is verified by a search example.
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.
Grover's algorithm achieves a quadratic speedup over classical algorithms, but it is considered necessary to know the value of $\ensuremath{\lambda}$ exactly [Phys. Rev. Lett. 95, 150501 (2005); Phys. Rev. Lett. 113, 210501 (2014)], where $\ensuremath{\lambda}$ is the fraction of target items in the database. In this paper, we find out that the Grover algorithm can actually apply to the case where one can identify the range that $\ensuremath{\lambda}$ belongs to from a given series of disjoint ranges. However, Grover's algorithm still cannot maintain high success probability when there exist multiple target items. For this problem, we proposed a complementary-multiphase quantum search algorithm in which multiple phases complement each other so that the overall high success probability can be maintained. Compared to the existing algorithms, in the case defined above, our algorithm achieves the following three goals simultaneously: (1) the success probability can be no less than any given value between 0 and 1, (2) the algorithm is applicable to the entire range of $\ensuremath{\lambda}$, and (3) the number of iterations is almost the same as that of Grover's algorithm. Especially compared to the optimal fixed-point algorithm [Phys. Rev. Lett. 113, 210501 (2014)], our algorithm uses fewer iterations to achieve a success probability greater than 82.71%, e.g., when the minimum success probability is required to be 99.25%, the number of iterations can be reduced by 50%.
As searching targets in an unordered database with Grover's algorithm,difference in marked items is not taken into consideration.If fraction of marked items is greater than 1/4,success probability of search decreases rapidly with increase of marked items.When the fraction of marked items is greater than 1/2,the algorithm is disabled.Aiming at above problems,an improved Grover's algorithm with weighted targets is proposed in which every target is assigned a weight coefficient according to its significance.With these weight coefficients,targets are represented as quantum superpositions which make probability getting target equal to its weight coefficient.An adaptive phase matching method is proposed based on weighted targets.The directions of phase rotations are contrary,and amplitudes of the two phase rotations are determined by inner-product of target quantum superposition and initial state of the system.As the inner-product is greater than(((3-5)/8)~(1/2),) success probability is equal to 1 with two steps of Grover iteration at most.The improved quantum searching algorithm and the new phase matching are verified by an example.