Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness
| |
|
Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness
Peter Høyer7  , Jan Neerbek8 and Yaoyun Shi9
| (7) |
Dept. of Comp. Sci., University of Calgary, Alberta, Canada, T2N 1N4 |
| (8) |
Dept. of Comp. Sci., University of Aarhus, DK-8000 Århus C, Denmark |
| (9) |
Dept. of Comp. Sci., Princeton University, Princeton, NJ 08544, USA |
Abstract
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 1/π(ln( N) - 1) accesses to the list elements for ordered searching, a lower bound of Ω( N log N) binary comparisons for sorting, and a lower bound of Ω(√ 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, Ω( N), and Ω(√ 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 log2(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.
Research supported by the EU fifth framework program QAIP, IST-1999-11234, and the National Science Foundation under grant
CCR-9820855.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|