Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments
Authors:
- Sophie LaplanteSLSophie Laplante
- Frédéric MagniezFMFrédéric Magniez
- 1 January 2008
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 38 (1) , 46-62
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 and 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 $O(\min(\sqrt{n C_0(f)},\sqrt{n C_1(f)}))$, where $C_0, C_1$ is the certificate complexity and n is the size of the input.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Quantum Query Complexity of Some Graph ProblemsSIAM Journal on Computing, 2006
- Lower Bounds for Local Search by Quantum ArgumentsSIAM Journal on Computing, 2006
- On the power of Ambainis lower boundsTheoretical Computer Science, 2005
- A lower bound on the quantum query complexity of read-once functionsJournal of Computer and System Sciences, 2004
- Quantum Complexities of Ordered Searching, Sorting, and Element DistinctnessAlgorithmica, 2002
- Quantum lower bounds by polynomialsJournal of the ACM, 2001
- Quantum Complexity TheorySIAM Journal on Computing, 1997
- On the Power of Quantum ComputationSIAM Journal on Computing, 1997
- Rapid solution of problems by quantum computationProceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 1992
- Quantum theory, the Church–Turing principle and the universal quantum computerProceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 1985