Quantum Searching via Entanglement and Partial Diffusion
arXiv:quant-ph/0406207 · doi:10.1016/j.physd.2007.12.005
Abstract
In this paper, we will define a quantum operator that performs the inversion about the mean only on a subspace of the system (Partial Diffusion Operator). This operator is used in a quantum search algorithm that runs in O(sqrt{N/M}) for searching an unstructured list of size N with M matches such that 1<= M<=N. We will show that the performance of the algorithm is more reliable than known {fixed operators quantum search algorithms} especially for multiple matches where we can get a solution after a single iteration with probability over 90% if the number of matches is approximately more than one-third of the search space. We will show that the algorithm will be able to handle the case where the number of matches M is unknown in advance such that 1<=M<=N in O(sqrt{N/M}). A performance comparison with Grover's algorithm will be provided.
19 pages. Submitted to IJQI. Please forward comments/enquires for the first author to [email protected]
References in corpus (14)
- Elementary gates for quantum computation
- Quantum Amplitude Amplification and Estimation
- 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
- A different kind of quantum search
- 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
- Quantum Search Algorithm with more Reliable Behaviour using Partial Diffusion
- Grover's Algorithm for Multiobject Search in Quantum Computing
Cited by in corpus (5)
- A Bounded-error Quantum Polynomial Time Algorithm for Two Graph Bisection Problems
- A Quantum Algorithm for Testing Junta Variables and Learning Boolean Functions via Entanglement Measure
- Constant-Time Quantum Algorithm For The Unstructured Search Problem
- Hiding Quantum States in a Superposition
- A Quantum Algorithm for Finding Common Matches Between Databases with Reliable Behavior