Complementary-multiphase quantum search for all numbers of target items

Abstract

Grover's algorithm achieves a quadratic speedup over classical algorithms, but it is considered necessary to know the value of $\lambda$ exactly [Phys. Rev. Lett. 95, 150501 (2005); Phys. Rev. Lett. 113, 210501 (2014)], where $\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 $\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, %with general iterations, 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, for the first time 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 $\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 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 commentEditorially approved for publication in Physical Review A. 12 pages, 5 figures, 2 tables. Comments are warmly welcome!

References in corpus (16)

• Quantum Mechanics helps in searching for a needle in a haystack
• Strengths and Weaknesses of Quantum Computing
• Tight bounds on quantum searching
• Grover's quantum searching algorithm is optimal
• Quantum computers can search rapidly by using almost any transformation
• Grover Algorithm with zero theoretical failure rate
• Quantum Counting
• Fixed-point quantum search with an optimal number of queries
• A different kind of quantum search
• On Arbitrary Phases in Quantum Amplitude Amplification
• Phase matching in quantum searching
• A Review on Quantum Search Algorithms
• Quantum Search Algorithm with more Reliable Behaviour using Partial Diffusion
• Multi-phase matching in the Grover algorithm
• Generalized Grover's algorithm for multiple phase inversion states
• A General Phase Matching Condition for Quantum Searching Algorithm

Cited by in corpus (2)

• Quantum-Inspired Support Vector Machine
• Exact quantum search based on analytical multiphase matching for known number of target items and the experimental demonstration on IBM Q