{"id":2348,"date":"2015-06-30T23:06:31","date_gmt":"2015-07-01T03:06:31","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=2348"},"modified":"2019-01-28T15:08:44","modified_gmt":"2019-01-28T21:08:44","slug":"quantum-query-complexity-the-other-shoe-drops","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=2348","title":{"rendered":"Quantum query complexity: the other shoe drops"},"content":{"rendered":"

Two weeks ago I blogged about a breakthrough<\/a> in query complexity: namely, the refutation by Ambainis et al.<\/a> 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\u00f6\u00f6s, Pitassi, and Watson to construct bizarre Boolean functions f with, among other things, near-quadratic gaps between D(f) and R0<\/sub>(f) (where D is deterministic query complexity and R0<\/sub> is zero-error randomized query complexity), near-1.5th<\/sup>-power gaps between R0<\/sub>(f) and R(f) (where R is bounded-error randomized query complexity), and near-4th<\/sup>-power gaps between D(f) and Q(f) (where Q is bounded-error quantum query complexity). See my previous post<\/a> for more about the definitions of these concepts and the significance of the results (and note also that Mukhopadhyay and Sanyal<\/a> independently obtained weaker results).<\/p>\n

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<\/i> 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<\/i> Boolean function, f:{0,1}n<\/sup>\u2192{0,1}, is one that’s defined for all 2n<\/sup> possible input strings x\u2208{0,1}n<\/sup>. Meanwhile, a partial<\/i> 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.<\/a> from 1998 says that D(f)=O(Q(f)6<\/sup>) for all total functions f.)<\/p>\n

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.<\/p>\n

Today, I can proudly report that my PhD student, Shalev Ben-David, has refuted that<\/i> conjecture as well<\/a>.  Building on the G\u00f6\u00f6s 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<\/sup> (yes, that’s Q(f) to the 2.5th<\/sup> power). Furthermore, if a conjecture that Ambainis and I made in our recent “Forrelation” paper<\/a> is correct—namely, that a problem called “k-fold Forrelation” has randomized query complexity roughly \u03a9(n1-1\/k<\/sup>)—then one would get nearly a cubic gap between R(f) and Q(f).<\/p>\n

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<\/i>: 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.<\/p>\n

Flummoxing my expectations once again, Shalev produced the super-quadratic separation, but not<\/i> 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<\/i> 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<\/a> for the details, but briefly, it once again uses the G\u00f6\u00f6s 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.<\/i> 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<\/i> find it (or think<\/em> 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<\/i> there. This checking step ensures that the function remains total.<\/p>\n

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.<\/p>\n

Update (July 1):<\/strong> 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<\/a> by himself and Ambainis (while Ashley Montanaro points out that a similar trick was used even earlier<\/a>, 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.<\/p>\n

Update (July 2):<\/strong> 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<\/a>, resolves another<\/i> 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<\/i> Grover’s algorithm. Indeed, one might wonder whether there’s any<\/i> 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,”<\/a> Lin and Lin recently proved the fascinating result that P(f)=O(Q(f)2<\/sup>) for all functions f, partial or total. But, combining with Shalev’s result that there exists a total f for which R(f)=\u03a9(Q(f)2.5<\/sup>), we get that there’s a total f for which R(f)=\u03a9(P(f)1.25<\/sup>). In the other direction, the best I know is that P(f)=\u03a9(bs(f)) and therefore R(f)=O(P(f)3<\/sup>).<\/p>\n","protected":false},"excerpt":{"rendered":"

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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"jetpack_seo_schema_type":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"{title}\n\n{excerpt}\n\n{url}","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false,"jetpack_post_was_ever_published":false},"categories":[31,5,4],"tags":[],"class_list":["post-2348","post","type-post","status-publish","format-standard","hentry","category-announcements","category-complexity","category-quantum"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2348","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2348"}],"version-history":[{"count":5,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2348\/revisions"}],"predecessor-version":[{"id":4111,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2348\/revisions\/4111"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2348"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2348"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2348"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}