Strength and Weakness in Grover's Quantum Search Algorithm

Abstract

Grover's quantum search algorithm is considered as one of the milestone in the field of quantum computing. The algorithm can search for a single match in a database with $N$ records in $O(\sqrt{N})$ assuming that the item must exist in the database with quadratic speedup over the best known classical algorithm. This review paper discusses the performance of Grover's algorithm in case of multiple matches where the problem is expected to be easier. Unfortunately, we will find that the algorithm will fail for $M>3N/4$, where $M$ is the number of matches in the list.

Review paper, 15 pages

References in corpus (12)

• Grover's quantum searching algorithm is optimal
• Quantum computers can search rapidly by using almost any transformation
• Grover Algorithm with zero theoretical failure rate
• A Quantum Algorithm for Finding the Minimum
• Quantum Counting
• On Arbitrary Phases in Quantum Amplitude Amplification
• A Family of Grover's Quantum Searching Algorithms
• Grover's Quantum Search Algorithm for an Arbitrary Initial Mixed State
• Searching in Grover's Algorithm
• A General Phase Matching Condition for Quantum Searching Algorithm
• Grover's Algorithm for Multiobject Search in Quantum Computing
• An Improved Quantum Scheduling Algorithm

Cited by in corpus (3)

• A Quantum Algorithm for Testing Juntas in Boolean Functions
• Quantum Oracles in Terms of Universal Gate Set
• A Quantum Algorithm for Finding Common Matches Between Databases with Reliable Behavior