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•30 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•1 citation

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

Grover's search algorithm for nnn qubits with optimal number of iterations

Simanraj Sadana

The success probability of a search of $M$ targets from a database of size $N$, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as $\mathcal{O}(\sqrt{N})$ for large $N$, the asymptote is not a good indicator of the optimal number of iterations when $\sqrt{M/N}$ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of $n$-qubit Grover's search algorithm with $1 \leq M \leq N$ target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given $N$ and $M$, there is an upper-bound on the success probability of the algorithm.

arXiv:2011.04051•Nov 8, 2020•4 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.
The success probability of a search of MMM targets from a database of size NNN, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as O(N)\mathcal{O}(\sqrt{N})O(N​) for large NNN, the asymptote is not a good indicator of the optimal number of iterations when M/N\sqrt{M/N}M/N​ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of nnn-qubit Grover's search algorithm with 1≤M≤N1 \leq M \leq N1≤M≤N target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given NNN and MMM, there is an upper-bound on the success probability of the algorithm.
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.