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 logN ) 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, Ω(N) , and
, respectively. Our proofs are based on a weighted all-pairs inner product argument.
In addition to our lower bound results, we give an exact 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 exact algorithm due to Farhi, Goldstone, Gutmann, and Sipser.
This is a preview of subscription content, log in via an institution to check access.
Access this article Subscribe and saveSpringer+ Basic
€34.99 /Month
Price includes VAT (Germany)
Instant access to the full article PDF.
Similar content being viewed by others Explore related subjectsDiscover the latest articles and news from researchers in related subjects, suggested using machine learning. Author information Authors and AffiliationsDepartment of Computer Science, University of Calgary, Calgary, Alberta, Canada T2N 1N4. hoyer@cpsc.ucalgary.ca., , , , , , CA
Hoyer
Department of Computer Science, University of Aarhus, DK-8000 Arhus C, Denmark. neerbek@daimi.au.dk., , , , , , DK
Neerbek
Department of Computer Science, Princeton University, Princeton, NJ 08544, USA. shiyy@cs.princeton.edu., , , , , , US
Shi
Hoyer, ., Neerbek, . & Shi, . Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness . Algorithmica 34, 429–448 (2002). https://doi.org/10.1007/s00453-002-0976-3
Issue Date: November 2002
DOI: https://doi.org/10.1007/s00453-002-0976-3
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4