Quantum query complexity: the other shoe drops

Two weeks ago I blogged about a breakthrough in query complexity: namely, the refutation by Ambainis et al. of a whole slew of conjectures that had stood for decades (and that I mostly believed, and that had helped draw me into theoretical computer science as a teenager) about the largest possible gaps between various complexity measures for total Boolean functions. Specifically, Ambainis et al. built on a recent example of Göös, Pitassi, and Watson to construct bizarre Boolean functions f with, among other things, near-quadratic gaps between D(f) and R0(f) (where D is deterministic query complexity and R0 is zero-error randomized query complexity), near-1.5th-power gaps between R0(f) and R(f) (where R is bounded-error randomized query complexity), and near-4th-power gaps between D(f) and Q(f) (where Q is bounded-error quantum query complexity). See my previous post for more about the definitions of these concepts and the significance of the results (and note also that Mukhopadhyay and Sanyal independently obtained weaker results).

Because my mental world was in such upheaval, in that earlier post I took pains to point out one thing that Ambainis et al. hadn’t done: namely, they still hadn’t shown any super-quadratic separation between R(f) and Q(f), for any total Boolean function f. (Recall that a total Boolean function, f:{0,1}n→{0,1}, is one that’s defined for all 2n possible input strings x∈{0,1}n. Meanwhile, a partial Boolean function is one where there’s some promise on x: for example, that x encodes a periodic sequence. When you phrase them in the query complexity model, Shor’s algorithm and other quantum algorithms achieving exponential speedups work only for partial functions, not for total ones. Indeed, a famous result of Beals et al. from 1998 says that D(f)=O(Q(f)6) for all total functions f.)

So, clinging to a slender reed of sanity, I said it “remains at least a plausible conjecture” that, if you insist on a fair comparison—i.e., bounded-error quantum versus bounded-error randomized—then the biggest speedup quantum algorithms can ever give you over classical ones, for total Boolean functions, is the square-root speedup that Grover’s algorithm easily achieves for the n-bit OR function.

Today, I can proudly report that my PhD student, Shalev Ben-David, has refuted that conjecture as well.  Building on the Göös et al. and Ambainis et al. work, but adding a new twist to it, Shalev has constructed a total Boolean function f such that R(f) grows roughly like Q(f)2.5 (yes, that’s Q(f) to the 2.5th power). Furthermore, if a conjecture that Ambainis and I made in our recent “Forrelation” paper is correct—namely, that a problem called “k-fold Forrelation” has randomized query complexity roughly Ω(n1-1/k)—then one would get nearly a cubic gap between R(f) and Q(f).

The reason I found this question so interesting is that it seemed obvious to me that, to produce a super-quadratic separation between R and Q, one would need a fundamentally new kind of quantum algorithm: one that was unlike Simon’s and Shor’s algorithms in that it worked for total functions, but also unlike Grover’s algorithm in that it didn’t hit some impassable barrier at the square root of the classical running time.

Flummoxing my expectations once again, Shalev produced the super-quadratic separation, but not by designing any new quantum algorithm. Instead, he cleverly engineered a Boolean function for which you can use a combination of Grover’s algorithm and the Forrelation algorithm (or any other quantum algorithm that gives a huge speedup for some partial Boolean function—Forrelation is just the maximal example), to get an overall speedup that’s a little more than quadratic, while still keeping your Boolean function total. I’ll let you read Shalev’s short paper for the details, but briefly, it once again uses the Göös et al. / Ambainis et al. trick of defining a Boolean function that equals 1 if and only if the input string contains some hidden substructure, and the hidden substructure also contains a pointer to a “certificate” that lets you quickly verify that the hidden substructure was indeed there. You can use a super-fast algorithm—let’s say, a quantum algorithm designed for partial functions—to find the hidden substructure assuming it’s there. If you don’t find it, you can simply output 0. But if you do find it (or think you found it), then you can use the certificate, together with Grover’s algorithm, to confirm that you weren’t somehow misled, and that the substructure really was there. This checking step ensures that the function remains total.

Are there further separations to be found this way? Almost certainly! Indeed, Shalev, Robin Kothari, and I have already found some more things (as well as different/simpler proofs of known separations), though nothing quite as exciting as the above.

Update (July 1): Ronald de Wolf points out in the comments that this “trust-but-verify” trick, for designing total Boolean functions with unexpectedly low quantum query complexities, was also used in a recent paper by himself and Ambainis (while Ashley Montanaro points out that a similar trick was used even earlier, in a different context, by Le Gall).  What’s surprising, you might say, is that it took as long as it did for people to realize how many applications this trick has.

Update (July 2): In conversation with Robin Kothari and Cedric Lin, I realized that Shalev’s superquadratic separation between R and Q, combined with a recent result of Lin and Lin, resolves another open problem that had bothered me since 2001 or so. Given a Boolean function f, define the “projective quantum query complexity,” or P(f), to be the minimum number of queries made by a bounded-error quantum algorithm, in which the answer register gets immediately measured after each query. This is a model of quantum algorithms that’s powerful enough to capture (for example) Simon’s and Shor’s algorithms, but not Grover’s algorithm. Indeed, one might wonder whether there’s any total Boolean function for which P(f) is asymptotically smaller than R(f)—that’s the question I wondered about around 2001, and that I discussed with Elham Kashefi. Now, by using an argument based on the “Vaidman bomb,” Lin and Lin recently proved the fascinating result that P(f)=O(Q(f)2) for all functions f, partial or total. But, combining with Shalev’s result that there exists a total f for which R(f)=Ω(Q(f)2.5), we get that there’s a total f for which R(f)=Ω(P(f)1.25). In the other direction, the best I know is that P(f)=Ω(bs(f)) and therefore R(f)=O(P(f)3).

24 Responses to “Quantum query complexity: the other shoe drops”

  1. Gil Kalai Says:

    Congratulations to Shalev! (And to the proud supervisor.) Great result, and an impressive line of breakthroughs.

  2. Ronald de Wolf Says:

    Exciting progress!

    The idea of making a promise function (with large quantum-classical gap) total using a Grover-based verification of the promise, was also used in a CCC’13 paper by Andris and me. We used a sequence of instances of Bernstein-Vazirani as our promise function, see Section 3.1 of the journal version here:

  3. Ashley Says:

    Indeed, very exciting! Always good to see long-believed conjectures shot down.

    It may also be worth mentioning that an idea with a slightly similar flavour was used by Francois Le Gall in 2006 to give a total function displaying an exponential separation between quantum and classical online space complexity. There the idea was to define a promise problem with an exponential quantum-classical separation, and also give efficient algorithms to determine whether the input indeed satisfies the promise.

    The notion of “making a partial function total by verification” seems like it could have many more applications.

  4. Ashley Says:

    Actually… could one think of this as a “trust, but verify” approach to quantum query algorithm design? 🙂

  5. Scott Says:

    Ronald and Ashley: Thanks!! Added an update to the post.

  6. Sniffnoy Says:

    No substantial comment, but would you mind fixing the last link to point to the abstract rather than directly to the PDF? (For the usual reasons — the PDF doesn’t have a link back, the abstract has useful links, etc.) Thank you!

  7. Scott Says:

    Sniffnoy #6: OK, done!

  8. aviti Says:

    Well done to the Ambainis and the cool achievement.

    @Scott I sort of try to learn complexity theory on my own on my spare time. So I followed your advice, and bought your book, QCSD. I read all of it cover to cover. Frankly speaking, I did not understand 95% of the materials, especially how easily you posed and solved the problems. I have not given up, and I will re-read the book again after I finish writing my PhD thesis (my major is engineering), somewhere in March 2016. I think I need more background materials. I searched my university library and found a book by Chuang et al. “Quantum computation and quantum information.“ Do you reccomend this book? Also what othe authors should I seek to cover enough starting materials to enrich my understanding of complexity theory?

    Sorry I put this here where everyone is cheering the recent good work.

  9. Scott Says:

    aviti #8: Yes, Nielsen and Chuang is the standard textbook for quantum computing; it’s excellent (even though 16 years old by now). If you wanted to start with something shorter and more introductory, you could try David Mermin’s “Introduction to Quantum Computer Science.”

    And if you wanted classical complexity theory rather than quantum, here are four books I recommend (the first is the most introductory, the third and fourth are the most modern in what they cover):

    Sipser, Intro to the Theory of Computation
    Papadimitriou, Computational Complexity
    Arora and Barak, Computational Complexity: A Modern Approach
    Mertens and Moore, The Nature of Computation

  10. Aviti Says:

    Scot#9 thanks a lot. Will get working now to acquire those books and get myself busy.

  11. fred Says:

    It’s seems the problem was more with a failure of imagination regarding the expressiveness of Boolean functions than about coming up with new Quantum algorithms?

  12. fred Says:

    Aviti #10
    as an engineer, I found the book “Quantum Computing for Computer Scientists” to be quite good, with very lots of clear practical exercises.

  13. Scott Says:

    Fred #11: Yup.

  14. Shmi Nux Says:

    This seems like one of those rare cases where all the mathematical machinery has been there for some time, and the scientists’ imagination had to catch up. I wonder if John Bell’s discovery of his famous theorem felt the same way… After all, the EPR paradox had been out there for 30 years by then.

    And it makes one think what other “obvious in retrospect” discoveries are just waiting to be revealed.

  15. Scott Says:

    Shmi Nux #14:


    Such cases are not particularly rare!

    Bell’s Theorem is a slightly different case, where it took 30 years for anyone even to pose the question with any mathematical precision—but once they did, the answer was just simple arithmetic. Here, the questions were posed in the 1990s, but it took until now for anyone to have the right idea about what the answers would look like.


    If you find any, let us know! 😀

  16. Raoul Ohio Says:

    Scott #15,

    Speaking of “waiting for scientists imagination to catch up”, check out the following and be prepared to say: “Why didn’t I think of this”:


  17. aviti Says:

    Fred #12, thanks a lot.

  18. a Says:

    Do any of these results have implication to P=NP?

  19. a Says:

    Or communication complexity?

  20. Scott Says:

    a #18, #19: For P=NP, no.

    For communication complexity (e.g., getting better separations between randomized and quantum communication complexities for total Boolean functions than are currently known), very possibly yes. I know people who are working on it right now.

  21. a Says:

    What was the previous best separation between randomized and quantum communication complexities?

  22. Scott Says:

    a #21: For partial functions, exponential (originally by Raz 1999).

    For total functions, quadratic, from the disjointness problem, a sort of “distributed” version of Grover search (Buhrman-Cleve-Wigderson 1998, Razborov 2002, a log factor removed by de Wolf and then by me and Ambainis).

  23. a Says:


    Sorry I am just curious.. does this have implication to separation between randomized and quantum QUERY complexities as well?

  24. Scott Says:

    a #23: Well, yes, obviously—that’s exactly what this result is.