|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
18 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A better lower bound for quantum algorithms searching an ordered list | | Andris Ambainis
; | | Date: |
14 Feb 1999 | | Subject: | Quantum Physics; Data Structures and Algorithms; Computational Complexity | quant-ph cs.CC cs.DS | | Abstract: | We show that any quantum algorithm searching an ordered list of n elements needs to examine at least 1/12 log n-O(1) of them. Classically, log n queries are both necessary and sufficient. This shows that quantum algorithms can achieve only a constant speedup for this problem. Our result improves lower bounds of Buhrman and de Wolf(quant-ph/9811046) and Farhi, Goldstone, Gutmann and Sipser (quant-ph/9812057). | | Source: | arXiv, quant-ph/9902053 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER