2003/11/27 by Sophie Laplante, Laplante, Sophie, Frederic Magniez +2
Computer Science · Mathematics · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computer science #Cryptography and Data Security #Discrete mathematics #FOS: Physical sciences #Kolmogorov complexity #Machine Learning and Algorithms #Mathematics #Physics #Quantum #Quantum Physics (quant-ph) #Quantum mechanics #Statistical physics #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0311189
arxiv created 2003/11/27 · openalex publication_date 2003/11/27 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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, adversary methods can only prove lower bounds for boolean functions f in O(min(√(n C0(f)),√(n C1(f)))), where C0, C1 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 Hoyer, Neerbek and Shi to give a quantum lower bound on ordered search and sorting.