AMS subject classifications. 81P68, 68Q30, 68Q30 LOWER BOUNDS FOR RANDOMIZED AND QUANTUM QUERY COMPLEXITY USING KOLMOGOROV ARGUMENTS ∗

, 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 ( p nC0(f), p nC1(f))), where C0, C1 is the certificate complexity, and n is the size of the input. 1. Introduction. 1.1. Overview. In this paper, we study lower bounds for randomized and quantum query complexity. In the query model, the input is accessed using oracle queries, and the query complexity of an algorithm is the number of calls to the oracle. Since it is difficult to obtain lower bounds on time directly, the query model is often use