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).
Follow
Comment #1 July 1st, 2015 at 1:55 am
Congratulations to Shalev! (And to the proud supervisor.) Great result, and an impressive line of breakthroughs.
Comment #2 July 1st, 2015 at 7:04 am
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:
http://homepages.cwi.nl/~rdewolf/publ/qc/approxdeg-allf-journal.pdf
Comment #3 July 1st, 2015 at 10:04 am
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.
Comment #4 July 1st, 2015 at 10:13 am
Actually… could one think of this as a “trust, but verify” approach to quantum query algorithm design? 🙂
Comment #5 July 1st, 2015 at 10:46 am
Ronald and Ashley: Thanks!! Added an update to the post.
Comment #6 July 1st, 2015 at 3:45 pm
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!
Comment #7 July 1st, 2015 at 3:46 pm
Sniffnoy #6: OK, done!
Comment #8 July 2nd, 2015 at 9:10 pm
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.
Comment #9 July 3rd, 2015 at 6:19 am
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
Comment #10 July 4th, 2015 at 4:20 am
Scot#9 thanks a lot. Will get working now to acquire those books and get myself busy.
Comment #11 July 4th, 2015 at 6:33 pm
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?
Comment #12 July 4th, 2015 at 6:39 pm
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.
Comment #13 July 4th, 2015 at 10:46 pm
Fred #11: Yup.
Comment #14 July 5th, 2015 at 1:34 am
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.
Comment #15 July 5th, 2015 at 10:16 am
Shmi Nux #14:
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.
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.
And it makes one think what other “obvious in retrospect” discoveries are just waiting to be revealed.
If you find any, let us know! 😀
Comment #16 July 5th, 2015 at 10:29 pm
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”:
http://www.theguardian.com/science/2015/jul/06/philae-comet-could-be-home-to-alien-life-say-top-scientists
Comment #17 July 5th, 2015 at 11:01 pm
Fred #12, thanks a lot.
Comment #18 July 9th, 2015 at 7:27 pm
Do any of these results have implication to P=NP?
Comment #19 July 9th, 2015 at 7:27 pm
Or communication complexity?
Comment #20 July 9th, 2015 at 10:29 pm
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.
Comment #21 July 11th, 2015 at 12:34 pm
What was the previous best separation between randomized and quantum communication complexities?
Comment #22 July 12th, 2015 at 9:37 am
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).
Comment #23 July 12th, 2015 at 9:05 pm
Opps
Sorry I am just curious.. does this have implication to separation between randomized and quantum QUERY complexities as well?
Comment #24 July 12th, 2015 at 10:07 pm
a #23: Well, yes, obviously—that’s exactly what this result is.