Physics – Quantum Physics
Scientific paper
2001-02-15
Physics
Quantum Physics
This new version contains new results. To appear at ICALP '01. Some of the results have previously been presented at QIP '01.
Scientific paper
We consider the quantum complexities of the following three problems: searching an ordered list, sorting an un-ordered list, and deciding whether the numbers in a list are all distinct. Letting N be the number of elements in the input list, we prove a lower bound of \frac{1}{\pi}(\ln(N)-1) accesses to the list elements for ordered searching, a lower bound of \Omega(N\log{N}) binary comparisons for sorting, and a lower bound of \Omega(\sqrt{N}\log{N}) binary comparisons for element distinctness. The previously best known lower bounds are {1/12}\log_2(N) - O(1) due to Ambainis, \Omega(N), and \Omega(\sqrt{N}), respectively. Our proofs are based on a weighted all-pairs inner product argument. In addition to our lower bound results, we give a quantum algorithm for ordered searching using roughly 0.631 \log_2(N) oracle accesses. Our algorithm uses a quantum routine for traversing through a binary search tree faster than classically, and it is of a nature very different from a faster algorithm due to Farhi, Goldstone, Gutmann, and Sipser.
Hoyer Peter
Neerbek Jan
Shi Yaoyun
No associations
LandOfFree
Quantum complexities of ordered searching, sorting, and element distinctness 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 Quantum complexities of ordered searching, sorting, and element distinctness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum complexities of ordered searching, sorting, and element distinctness will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-203074