Title :
A better lower bound for quantum algorithms searching an ordered list
Author :
Ambainis, Andris
Author_Institution :
Dept. of Comput. Sci., California Univ., Berkeley, CA, USA
Abstract :
We show that any quantum algorithm searching an ordered list of n elements needs to examine at least (log,n)/12-O(1) of them. Classically, log2 n queries are both necessary and sufficient. This shows that quantum algorithms can achieve only a constant speedup for this problem
Keywords :
computational complexity; quantum computing; search problems; constant speedup; lower bound; ordered list searching; quantum algorithms; queries; searching; Algorithms; Computer science; National electric code; Postal services; Quantum computing; Search problems;
Conference_Titel :
Foundations of Computer Science, 1999. 40th Annual Symposium on
Conference_Location :
New York City, NY
Print_ISBN :
0-7695-0409-4
DOI :
10.1109/SFFCS.1999.814606
