{"id":6129,"date":"2021-11-19T15:48:06","date_gmt":"2021-11-19T21:48:06","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=6129"},"modified":"2021-11-19T15:48:06","modified_gmt":"2021-11-19T21:48:06","slug":"the-acrobatics-of-bqp","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=6129","title":{"rendered":"The Acrobatics of BQP"},"content":{"rendered":"\n

Just in case anyone is depressed this afternoon and needs something to cheer them up, students William Kretschmer<\/a>, DeVon Ingram<\/a>, and I have finally put out a new paper:<\/p>\n\n\n\n

The Acrobatics of BQP<\/a><\/strong><\/p>

Abstract:<\/strong> We show that, in the black-box setting, the behavior of quantum polynomial-time (BQP) can be remarkably decoupled from that of classical complexity classes like NP. Specifically:<\/p>

– There exists an oracle relative to which NPBQP<\/sup>\u2284BQPPH<\/sup>, resolving a 2005 problem of Fortnow. Interpreted another way, we show that AC0<\/sup>\u00a0circuits cannot perform useful homomorphic encryption on instances of the Forrelation problem. As a corollary, there exists an oracle relative to which P=NP but BQP\u2260QCMA.<\/p>

– Conversely, there exists an oracle relative to which BQPNP<\/sup>\u2284PHBQP<\/sup>.<\/p>

– Relative to a random oracle, PP=PostBQP is not contained in the “QMA hierarchy” QMAQMA^QMA^…<\/sup>, and more generally PP\u2284(MIP*)(MIP*)^(MIP*)^…<\/sup>\u00a0(!), despite the fact that MIP*=RE in the unrelativized world. This result shows that there is no black-box quantum analogue of Stockmeyer’s approximate counting algorithm.<\/p>

– Relative to a random oracle, \u03a3k+1<\/sub>\u2284BQP\u03a3_k<\/sup>\u00a0for every k.<\/p>

– There exists an oracle relative to which BQP=P#P<\/sup>\u00a0and yet PH is infinite. (By contrast, if NP\u2286BPP, then PH collapses relative to all oracles.)<\/p>

– There exists an oracle relative to which P=NP\u2260BQP=P#P<\/sup>.<\/p>

To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which BQP\u2284PH, and associated results about the Forrelation problem. We also introduce new tools that might be of independent interest. These include a “quantum-aware” version of the random restriction method, a concentration theorem for the block sensitivity of AC0<\/sup> circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.<\/p><\/blockquote>\n\n\n\n

Incidentally, particularly when I’ve worked on a project with students, I’m often tremendously excited and want to shout about it from the rooftops for the students’ sake … but then I also don’t want to use this blog to privilege my own papers “unfairly.” Can anyone suggest a principle that I should follow going forward?<\/p>\n","protected":false},"excerpt":{"rendered":"

Just in case anyone is depressed this afternoon and needs something to cheer them up, students William Kretschmer, DeVon Ingram, and I have finally put out a new paper: The Acrobatics of BQP Abstract: We show that, in the black-box setting, the behavior of quantum polynomial-time (BQP) can be remarkably decoupled from that of classical […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","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":true,"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-6129","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\/6129","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=6129"}],"version-history":[{"count":1,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/6129\/revisions"}],"predecessor-version":[{"id":6130,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/6129\/revisions\/6130"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=6129"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=6129"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=6129"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}