|
Published Articles >> Table of Contents >> Abstract
19th Annual IEEE Conference on Computational Complexity (CCC'04)
pp. 294-304
Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
Sophie Laplante, LRI, Université Paris-Sud
Frederic Magniez, LRI, CNRS
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313852
Send link to a friend
| Abstract |
|
We prove a very general lower bound technique for quantum and randomized query complexity, that is easy to prove as well as to apply. To achieve this, we introduce the use of Kolmogorov complexity to query complexity. Our technique generalizes the weighted, unweighted methods of Ambainis, and the spectral method of Barnum, Saks and Szegedy. As an immediate consequence of our main theorem, it can be shown that adversary methods can only prove lower bounds for boolean functions f in 0(\min (\sqrt {nC_0 (f)} ,\sqrt {nC_1 (f)})), where C_0, C_1 is the certificate complexity, and n is the size of the input. We also derive a general form of the ad hoc weighted method used by Høyer, Neerbek and Shi to give a quantum lower bound on ordered search and sorting.
|
 Additional Information
|
Citation:
Sophie Laplante, Frederic Magniez,
"Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments,"
ccc,
pp. 294-304,
19th Annual IEEE Conference on Computational Complexity (CCC'04),
2004
|
|
