A better lower bound for quantum algorithms searching an ordered list
Author:
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 356 (02725428) , 352-357
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, log/sub 2/ n queries are both necessary and sufficient. This shows that quantum algorithms can achieve only a constant speedup for this problem.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Inductive inference of recursive functions: Complexity bounds2005
- Quantum lower bounds by polynomials2002
- On the power of quantum computationPhilosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 1998
- Strengths and Weaknesses of Quantum ComputingSIAM Journal on Computing, 1997
- Quantum Complexity TheorySIAM Journal on Computing, 1997
- A fast quantum mechanical algorithm for database search1996
- The Weighted Majority AlgorithmInformation and Computation, 1994