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

Complementary-multiphase quantum search for all numbers of target items

Tan Li, Wan‐Su Bao, He-Liang Huang, Feng‐Guang Li, Xiang-Qun Fu, Shuo Zhang, Chu Guo, Yu-Tao Du, Xiang Wang, Jie Lin

Published Dec 6, 2018• 4 citations
arXivHTMLPDF

Abstract

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%.

DOI
10.1103/physreva.98.062308

Related papers

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

Exact quantum search based on analytical multiphase matching for known number of target items and the experimental demonstration on IBM Q

Tan Li, Xiang-Qun Fu, Yan Wang +4 more

In [Phys. Rev. Lett. 113, 210501 (2014)], to achieve the optimal fixed-point quantum search in the case of unknown fraction (denoted by $λ$) of target items, the analytical multiphase matching (AMPM) condition has been proposed. In this paper, we find out that the AMPM condition can also be used to design the exact quantum search algorithm in the case of known $λ$, and the minimum number of iterations reaches the optimal level of existing exact algorithms. Experiments are performed to demonstrate the proposed algorithm on IBM's quantum computer. In addition, we theoretically find two coincidental phases with equal absolute value in our algorithm based on the AMPM condition and that algorithm based on single-phase matching. Our work confirms the practicability of the AMPM condition in the case of known $λ$, and is helpful to understand the mechanism of this condition.

arXiv:1908.00269•Aug 1, 2019•0 citations

Quantum Search Algorithm Based on Multi-Phase

Tan Li, Wan‐Su Bao, Wen-Qian Lin +2 more

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.

Chinese Physics Letters•May 1, 2014•9 citations

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

Quantum search for unknown number of target items by hybridizing fixed-point method with trail-and-error method*

Tan Li, Shuo Zhang, Xiang-Qun Fu +4 more

For the unsorted database quantum search with the unknown fraction λ of target items, there are mainly two kinds of methods, i.e., fixed-point and trail-and-error. (i) In terms of the fixed-point method, Yoder et al. [Phys. Rev. Lett. 113 210501 (2014)] claimed that the quadratic speedup over classical algorithms has been achieved. However, in this paper, we point out that this is not the case, because the query complexity of Yoder’s algorithm is actually in O ( 1 / λ 0 ) rather than O ( 1 / λ ) , where λ 0 is a known lower bound of λ. (ii) In terms of the trail-and-error method, currently the algorithm without randomness has to take more than 1 times queries or iterations than the algorithm with randomly selected parameters. For the above problems, we provide the first hybrid quantum search algorithm based on the fixed-point and trail-and-error methods, where the matched multiphase Grover operations are trialed multiple times and the number of iterations increases exponentially along with the number of trials. The upper bound of expected queries as well as the optimal parameters are derived. Compared with Yoder’s algorithm, the query complexity of our algorithm indeed achieves the optimal scaling in λ for quantum search, which reconfirms the practicality of the fixed-point method. In addition, our algorithm also does not contain randomness, and compared with the existing deterministic algorithm, the query complexity can be reduced by about 1/3. Our work provides a new idea for the research on fixed-point and trial-and-error quantum search.

arXiv:1912.01773•Chinese Physics B•Nov 1, 2019•8 citations

PHASE MATCHING IN FIXED-POINT QUANTUM SEARCH ALGORITHM

Hong‐Fu Wang, Shou Zhang, Yongfang Zhao

We investigate the phase matching problem in the fixed-point quantum search algorithm proposed by Grover [Phys. Rev. Lett.95 (2005) 150501]. We show that the optimal phase shift is π/3.61, which replaces the π/3 phase shift in fixed-point quantum search algorithm. The π/3.61-phase algorithm can be achieved in [Formula: see text] with the success probability of at least 94.11%, which offsets disadvantage that the success probability of getting correct results usually decreases with the increase of marked items when original Grover quantum search algorithm is applied to search an unordered database. In the meantime, this work also indicates that Grover quantum search algorithm is considerably robust to certain kinds of perturbations and is robust against modest noise in the initialization procedure.

International Journal of Quantum Information•Sep 1, 2009•2 citations
Grover's algorithm achieves a quadratic speedup over classical algorithms, but it is considered necessary to know the value of \ensuremathλ\ensuremath{\lambda}\ensuremathλ exactly [Phys. Rev. Lett. 95, 150501 (2005); Phys. Rev. Lett. 113, 210501 (2014)], where \ensuremathλ\ensuremath{\lambda}\ensuremathλ 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λ\ensuremath{\lambda}\ensuremathλ 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λ\ensuremath{\lambda}\ensuremathλ, 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%.
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.
In [Phys. Rev. Lett. 113, 210501 (2014)], to achieve the optimal fixed-point quantum search in the case of unknown fraction (denoted by λλλ) of target items, the analytical multiphase matching (AMPM) condition has been proposed. In this paper, we find out that the AMPM condition can also be used to design the exact quantum search algorithm in the case of known λλλ, and the minimum number of iterations reaches the optimal level of existing exact algorithms. Experiments are performed to demonstrate the proposed algorithm on IBM's quantum computer. In addition, we theoretically find two coincidental phases with equal absolute value in our algorithm based on the AMPM condition and that algorithm based on single-phase matching. Our work confirms the practicability of the AMPM condition in the case of known λλλ, and is helpful to understand the mechanism of this condition.
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.
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.
For the unsorted database quantum search with the unknown fraction λ of target items, there are mainly two kinds of methods, i.e., fixed-point and trail-and-error. (i) In terms of the fixed-point method, Yoder et al. [Phys. Rev. Lett. 113 210501 (2014)] claimed that the quadratic speedup over classical algorithms has been achieved. However, in this paper, we point out that this is not the case, because the query complexity of Yoder’s algorithm is actually in O ( 1 / λ 0 ) rather than O ( 1 / λ ) , where λ 0 is a known lower bound of λ. (ii) In terms of the trail-and-error method, currently the algorithm without randomness has to take more than 1 times queries or iterations than the algorithm with randomly selected parameters. For the above problems, we provide the first hybrid quantum search algorithm based on the fixed-point and trail-and-error methods, where the matched multiphase Grover operations are trialed multiple times and the number of iterations increases exponentially along with the number of trials. The upper bound of expected queries as well as the optimal parameters are derived. Compared with Yoder’s algorithm, the query complexity of our algorithm indeed achieves the optimal scaling in λ for quantum search, which reconfirms the practicality of the fixed-point method. In addition, our algorithm also does not contain randomness, and compared with the existing deterministic algorithm, the query complexity can be reduced by about 1/3. Our work provides a new idea for the research on fixed-point and trial-and-error quantum search.
We investigate the phase matching problem in the fixed-point quantum search algorithm proposed by Grover [Phys. Rev. Lett.95 (2005) 150501]. We show that the optimal phase shift is π/3.61, which replaces the π/3 phase shift in fixed-point quantum search algorithm. The π/3.61-phase algorithm can be achieved in [Formula: see text] with the success probability of at least 94.11%, which offsets disadvantage that the success probability of getting correct results usually decreases with the increase of marked items when original Grover quantum search algorithm is applied to search an unordered database. In the meantime, this work also indicates that Grover quantum search algorithm is considerably robust to certain kinds of perturbations and is robust against modest noise in the initialization procedure.