I promised myself I’d stop blogging about controversial issues whose mere mention could instigate a flamewar and permanently get me in trouble.\u00a0 Well, today I’m going to violate that rule, by blogging about the difference relativized and unrelativized complexity classes.<\/p>\n
Recently a colleague of mine, who works in the foundations of quantum mechanics, sent me a long list of questions about the seminal 1993 paper of Bernstein and Vazirani<\/a> that introduced the complexity class BQP<\/a> (Bounded-Error Quantum Polynomial-Time).\u00a0 It was clear to me that all of his questions boiled down to a single point: the distinction between the relativized and unrelativized worlds. \u00a0This is an absolutely crucial distinction that trips up just about everyone<\/em> when they’re first learning quantum computing.<\/p>\n So I fired off a response, which my colleague said he found extremely helpful.\u00a0 It then occurred to me that what one person found helpful, another might as well—and that which makes 30% of my readers’ eyes glaze over with its thoroughgoing duh-obviousness, might be very thing that another 30% of my readers most want to see.\u00a0 So without further ado, the two worlds of quantum complexity theory…<\/p>\n In the relativized world<\/font><\/strong>, we let our algorithms access potentially-powerful oracles, whose internal structure we don’t examine (think of Simon’s algorithm for concreteness). \u00a0In that world, we can indeed prove unconditionally that BPP\u2260BQP—that is, quantum computers can solve certain problems exponentially faster than classical computers, when both computers are given access to the same oracle.<\/p>\n In general, almost every “natural” complexity class has a relativized version associated with it, and the relativized versions tend to be much<\/em> easier to separate than the unrelativized versions (it’s basically the difference between a masters or PhD thesis and a Fields Medal!) \u00a0So for example, within the relativized world, we can separate not only BPP from BQP, but also P from NP, NP from PSPACE, NP from BQP, etc.<\/p>\n By contrast, in the unrelativized world<\/font><\/strong> (where there are no oracles), we can’t separate any<\/em> complexity classes between P and PSPACE. \u00a0Doing so is universally recognized as one of the biggest open problems in mathematics (in my opinion, it’s far-and-away the biggest problem).<\/p>\n Now, Bernstein and Vazirani proved that BQP is “sandwiched” between P and PSPACE. \u00a0For that reason, as they write in their paper, one can’t hope to prove P\u2260BQP in the unrelativized world without also proving P\u2260PSPACE.<\/p>\n Let’s move on to another major result from Bernstein and Vazirani’s paper, namely their oracle separation between BPP and BQP.\u00a0 You might wonder: what’s the point of proving such a thing? \u00a0Well, the Bernstein-Vazirani oracle separation gave the first formal evidence that BQP “might” be larger than BPP. \u00a0For if BPP equaled BQP relative to every oracle, then in particular, they’d have to be equal relative to the empty oracle—that is, in the unrelativized world!<\/p>\n (The converse need not hold: it could be the case that BPP=BQP, despite the existence of an oracle that separates them. \u00a0So, again, separating complexity classes relative to an oracle can be thought of as a “baby step” toward separating them in the real world.)<\/p>\n But an even more important motivation for Bernstein and Vazirani’s oracle separation is that it led shortly afterward to a better oracle separation by Simon, and that, in turn, led to Shor’s factoring algorithm.<\/p>\n In a sense, what Shor did was to “remove the oracle” from Simon’s problem. \u00a0In other words, Shor found a concrete problem in the unrelativized world (namely factoring integers), which has a natural function associated with it (namely the modular exponentiation function, f(r) = xr<\/sup> mod N) that one can usefully treat<\/em> as an oracle. \u00a0Treating f as an oracle, one can then use a quantum algorithm related to Simon’s algorithm to find the period of f, and that in turn lets you factor integers in polynomial time.<\/p>\n Of course, Shor’s algorithm became much more famous than Simon’s algorithm, since the implications for computer science, cryptography, etc. were so much more concrete and dramatic than with an abstract oracle separation. \u00a0However, the downside is that the speedup of Shor’s algorithm is no longer unconditional<\/em>: for all anyone knows today, there might also a fast classical algorithm to factor integers. \u00a0By contrast, the speedup of Simon’s algorithm (and of Bernstein-Vazirani before it) is an unconditional one.<\/p>\n","protected":false},"excerpt":{"rendered":" I promised myself I’d stop blogging about controversial issues whose mere mention could instigate a flamewar and permanently get me in trouble.\u00a0 Well, today I’m going to violate that rule, by blogging about the difference relativized and unrelativized complexity classes. Recently a colleague of mine, who works in the foundations of quantum mechanics, sent me […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","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":[5,4],"tags":[],"class_list":["post-451","post","type-post","status-publish","format-standard","hentry","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\/451","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\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=451"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/451\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=451"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=451"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=451"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}