6.896 Quantum Complexity Theory October 14, 2008 Lecture 12 Lecturer: Scott Aaronson 1 A second non-symmetric example 1.1 Limitations of speed-ups without structure In the preceeding lectures, we examined the relationship between deterministic query complexity and quantum query complexity. In particular, we showed Theorem 1 ∀Boolean f D(f ) = O(Q(f)6) so we won’t ever obtain a s uperpolynomial improvement in the query complexity of total fun ctions, and to obtain a superpolynomial speed-up, we can’t treat the problem as a black-box like Grover’s algorithm does. We need to exploit some kind of structure, possibly in the form of a promise on the function, as Shor’s algorithm d oes. Moreover, for symmetric Boolean functions – OR, MAJORITY, PARITY, and the like – the largest separation possible is only quadratic, which is achieved by the OR function, as demonstrated by Grover’s algorithm and our various lower bounds. For functions such as MAJORITY, wh ich switches from 0 to 1 around the middle Hamming weight, the advantage only diminishes, and any quantum algorithm can be shown to require Ω(n) queries, ju st as classical algorithms do. We don’t have such a clear picture of the state of affairs for non-symmetric Boolean functions, but a few concrete examples have been worked out. A natural next question is to consider what happens when our simple functions are composed. For example, we saw last time th at for the two level OR-AND tree (with √n branches at each level), the quantum query complexity is Θ(√n), with the upper bound provided by a recursive application of Grover’s algorithm, and the lower bound obtained via Ambainis’ adversary method (stated without proof)—the quantum extension of the BBBV hybrid argument and variants, where we argue about what a quantum algorithm can do step-by-step. By contrast, we still don’t know how to obtain the lower bound using the polynomial method, where we reduce questions about quantu m algorithms to questions about low-degree polynomials, (the “pure math” approach) which is elegant when it works. Thus, these two methods seem to have complementary s tren gths and weaknesses. 1.2 The AND-OR tree, or: the power of randomization in black-box query complexity The second example which we u nderstand is also an AND-OR tree, but it is deeper, consisting of log n levels with two branches at each node (see Figure 1). We think of this as modeling a log n-round game of pure strategy between two players in which the players have two options at each round (we could thin k of it more generally as a constant number of moves), and the winner is determined by a black-box evaluation function—the natural computational question in such a game is, “is there a move I can make such that for every move you can make, I can force a win?” This is precisely the problem of game tree evaluation. This black-box assumption allows us to begin 12-1levels AND AND OR OR OR OR OR log n Figure 1: log n-depth AND-OR tree to address the question of what kind of a speed-up we can hope to obtain by us ing a quantum algorithm for playin g games. The kind of question we know how to address is again about the number of queries we require—how many of the leaves of the tree (labeled with bits) we need to examine to determine its value. The best classical algorithm turns out to be very simple: Algorithm EV AL − T REE: For the tree rooted at vertex v, 1. Let u be the left or right child, chosen uniformly at random; run EV AL − T REE(u). 2. If v is an AND and EV AL − T REE(u) = 0 or v is an OR and EV AL − T REE(u) = 1, return 0 or 1, respectively. 3. Otherwise, if w is the other child, return EV AL − T REE(w). The randomization is very important, since otherwise we might “get unlucky” at each level and need to evaluate every branch of the tree. It is actually an easy exercise to analyze the runnin g time of this algorithm—what is more difficult to see is that this algorithm is actually optimal: √ Theorem 2 (Saks-Wigderson ’86) R(AND − OR) = Θ(nlog 1+ 4 33 ). (where log 1+√33 .754)4 ≈This function is conjectured to exhibit the largest separation possible between classical query complexity and randomized query complexity (without promises). It is certainly, at least, the largest known separation. Of course, the caveat about promises is essential here too—if we are promised that the input has Hamming weight either at least 2/3n or at most 1/3n and we need to decide which, then deterministic algorithms need more than n/3 queries, but randomized algorithms only need one query. In any case, the situation with randomized algorithms is similar to the one we faced with quantum algorithms. In the following, let Rǫ denote the query complexity of a randomized algorithm that is allowed to err with probability ǫ. It is easy to see that for “Las Vegas” algorithms (i.e., ǫ = 0, like our pruning algorithm), R0(f) ≥ C(f), s ince the algorithm must see a certificate before it halts—otherwise, there’s both a 0-input and a 1-input that are consistent with the bits queried so far, so we would err on some in put. Since we also saw D(f) ≤ C(f)2, we find that D(f ) ≤ R0(f)2 for all Boolean total functions f, but we don’t know whether or not this is tight—the log n-level AND-OR tree obtains the largest known speed-up. L ikewise, for “Monte-Carlo” algorithms (ǫ > 0), observe that if f has block sensitivity k, then we have to examine each of our disjoint blocks with 12-2OR AND xOR xAND AND xANDy y x y y Figure 2: Two-level AND-OR trees computing x ⊕ y (left) and (x ⊕ y) (right). ¬probability at least 1 −2ǫ, since again otherwise there would be a 1-input and a 0-input that only differ in some unexamined blo ck, and then