{"id":235,"date":"2007-05-02T10:11:33","date_gmt":"2007-05-02T18:11:33","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=235"},"modified":"2007-05-02T10:11:33","modified_gmt":"2007-05-02T18:11:33","slug":"the-most-trivial-theorem-ive-ever-written-up","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=235","title":{"rendered":"The most trivial theorem I&#8217;ve ever written up"},"content":{"rendered":"<p><strong>Theorem:<\/strong> Suppose NP-complete problems are efficiently solvable by quantum computers.  Then either the polynomial hierarchy collapses, or else BQP \u2284 AM (that is, quantum computations can&#8217;t be efficiently simulated by Arthur-Merlin protocols).<\/p>\n<p><strong>Proof:<\/strong> Suppose NP \u2286 BQP and BQP \u2286 AM.  Then coNP \u2286 BQP \u2286 AM, and hence the polynomial hierarchy collapses to the second level by a result of <a href=\"http:\/\/portal.acm.org\/citation.cfm?id=31202\">Boppana, H\u00e5stad, and Zachos<\/a>.<\/p>\n<p><strong>Note:<\/strong> If only we could delete the weasel phrase &#8220;or else BQP \u2284 AM&#8221; from my Most Trivial Theorem, we would&#8217;ve achieved a long-sought breakthrough in quantum computing theory.  In particular, we would&#8217;ve shown that any fast quantum algorithm to solve NP-complete problems would imply an unlikely collapse of <em>classical<\/em> complexity classes.  But while the weasel phrase is weaselly enough to make the Most Trivial Theorem a triviality, I don&#8217;t think it&#8217;s <em>infinitely <\/em>weaselly.  The reason is my growing suspicion that BQP \u2286 AM in the unrelativized world.<\/p>\n<p><strong>Second Note:<\/strong> When I call this my &#8220;Most Trivial Theorem,&#8221; obviously I&#8217;m excluding homework exercises.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Theorem: Suppose NP-complete problems are efficiently solvable by quantum computers. Then either the polynomial hierarchy collapses, or else BQP \u2284 AM (that is, quantum computations can&#8217;t be efficiently simulated by Arthur-Merlin protocols). Proof: Suppose NP \u2286 BQP and BQP \u2286 AM. Then coNP \u2286 BQP \u2286 AM, and hence the polynomial hierarchy collapses to the [&hellip;]<\/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_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","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},"categories":[5,18,4,17],"tags":[],"class_list":["post-235","post","type-post","status-publish","format-standard","hentry","category-complexity","category-embarrassing-myself","category-quantum","category-speaking-truth-to-parallelism"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/235","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=235"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/235\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=235"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=235"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=235"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}