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

Chinese Physics Letters

Quantum Search Algorithm Based on Multi-Phase

Tan Li, Wan‐Su Bao, Wen-Qian Lin, Hou Zhang, Xiang-Qun Fu

Published May 1, 2014• 9 citations
Publisher

Abstract

The success probability of the Grover quantum search algorithm decreases quickly when the fraction of target items exceeds 1/4, where the phase plays a significant role. Therefore, we use multiple phases to complement each other. We obtain three useful properties and an important theorem of the success probability and design a systematic solution of the optimal phases for an arbitrary number of phases. Based on these results, we finally propose a multi-phase quantum search algorithm whose success probability rises with the increase of the number of phases with just a single iteration, and it tends to be 100% when the fraction of target items is over a lower limit.

DOI
10.1088/0256-307x/31/5/050301

Related papers

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

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

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

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

Q-Learning-Based Adjustable Fixed-Phase Quantum Grover Search Algorithm

Ying Guo, Wensha Shi, Yijun Wang +1 more

We demonstrate that the rotation phase can be suitably chosen to increase the efficiency of the phase-based quantum search algorithm, leading to a dynamic balance between iterations and success probabilities of the fixed-phase quantum Grover search algorithm with Q-learning for a given number of solutions. In this search algorithm, the proposed Q-learning algorithm, which is a model-free reinforcement learning strategy in essence, is used for performing a matching algorithm based on the fraction of marked items λ and the rotation phase α. After establishing the policy function α = π(λ), we complete the fixed-phase Grover algorithm, where the phase parameter is selected via the learned policy. Simulation results show that the Q-learning-based Grover search algorithm (QLGA) enables fewer iterations and gives birth to higher success probabilities. Compared with the conventional Grover algorithms, it avoids the optimal local situations, thereby enabling success probabilities to approach one.

Journal of the Physical Society of Japan•Jan 27, 2017•6 citations
The success probability of the Grover quantum search algorithm decreases quickly when the fraction of target items exceeds 1/4, where the phase plays a significant role. Therefore, we use multiple phases to complement each other. We obtain three useful properties and an important theorem of the success probability and design a systematic solution of the optimal phases for an arbitrary number of phases. Based on these results, we finally propose a multi-phase quantum search algorithm whose success probability rises with the increase of the number of phases with just a single iteration, and it tends to be 100% when the fraction of target items is over a lower limit.
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%.
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%.
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.
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.
We demonstrate that the rotation phase can be suitably chosen to increase the efficiency of the phase-based quantum search algorithm, leading to a dynamic balance between iterations and success probabilities of the fixed-phase quantum Grover search algorithm with Q-learning for a given number of solutions. In this search algorithm, the proposed Q-learning algorithm, which is a model-free reinforcement learning strategy in essence, is used for performing a matching algorithm based on the fraction of marked items λ and the rotation phase α. After establishing the policy function α = π(λ), we complete the fixed-phase Grover algorithm, where the phase parameter is selected via the learned policy. Simulation results show that the Q-learning-based Grover search algorithm (QLGA) enables fewer iterations and gives birth to higher success probabilities. Compared with the conventional Grover algorithms, it avoids the optimal local situations, thereby enabling success probabilities to approach one.