Physics – Quantum Physics
Scientific paper
2000-09-08
Physics
Quantum Physics
This paper has been merged with another paper. See quant-ph/0102078. Except for this comment v2 is unchanged compared to v1. 1
Scientific paper
We prove that any exact quantum algorithm searching an ordered list of N elements requires more than \frac{1}{\pi}(\ln(N)-1) queries to the list. This improves upon the previously best known lower bound of {1/12}\log_2(N) - O(1). Our proof is based on a weighted all-pairs inner product argument, and it generalizes to bounded-error quantum algorithms. The currently best known upper bound for exact searching is roughly 0.526 \log_2(N). We give an exact quantum algorithm that uses \log_3(N) + O(1) queries, which is roughly 0.631 \log_2(N). The main principles in our algorithm are an quantum parallel use of the classical binary search algorithm and a method that allows basis states in superpositions to communicate.
Hoyer Peter
Neerbek Jan
No associations
LandOfFree
Bounds on quantum ordered searching does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Bounds on quantum ordered searching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds on quantum ordered searching will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-204196