{"id":3816,"date":"2018-05-19T07:45:45","date_gmt":"2018-05-19T12:45:45","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=3816"},"modified":"2019-01-28T15:12:24","modified_gmt":"2019-01-28T21:12:24","slug":"pdqp-qpoly-all","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=3816","title":{"rendered":"PDQP\/qpoly = ALL"},"content":{"rendered":"<p>I&#8217;ve put up a <a href=\"https:\/\/www.scottaaronson.com\/papers\/dqpqpoly.pdf\">new paper<\/a>.&nbsp; Unusually for me these days, it&#8217;s a very short and simple one (8 pages)&#8212;I should do more like this!&nbsp; Here&#8217;s the abstract:<\/p>\n<ul>We show that combining two different hypothetical enhancements to quantum computation&#8212;namely, quantum advice and non-collapsing measurements&#8212;would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable codes.<\/ul>\n<p>I welcome discussion in the comments.&nbsp; The <em>real<\/em> purpose of this post is simply to fulfill a <a href=\"https:\/\/scottaaronson.blog\/?p=3766#comment-1764593\">request<\/a> by James Gallagher, in the comments of my Robin Hanson post:<\/p>\n<p style=\"padding-left: 30px;\">The probably last chance for humanity involves science progressing, can you apply your efforts to quantum computers, which is your expertise, and stop wasting many hours of you [sic] time with this [expletive deleted]<\/p>\n<p>Indeed, I just returned to Tel Aviv, for the very tail end of my sabbatical, from a weeklong visit to Google&#8217;s quantum computing group in LA.&nbsp; While we mourned tragedies&#8212;multiple members of the quantum computing community lost loved ones in recent weeks&#8212;it was great to be among so many friends, and great to talk and think for once about actual progress that&#8217;s happening in the world, as opposed to people saying mean things on Twitter.&nbsp; Skipping over its plans to build a 49-qubit chip, Google is now going straight for 72 qubits.&nbsp; And we now have some viable things that one can do, or try to do, with such a chip, beyond simply proving quantum supremacy&#8212;I&#8217;ll say more about that in subsequent posts.<\/p>\n<p>Anyway, besides discussing this progress, the other highlight of my trip was going from LA to Santa Barbara on the back of Google physicist Sergio Boixo&#8217;s motorcycle&#8212;weaving in and out of rush-hour traffic, the tightness of my grip the only thing preventing me from flying out onto the freeway.&nbsp; I&#8217;m glad to have tried it once, and probably won&#8217;t be repeating it.<\/p>\n<hr>\n<p><b><font color=\"red\">Update:<\/font><\/b> I posted a new version of the PDQP\/qpoly=ALL paper, which includes an observation about communication complexity, and which&#8212;inspired by the comments section&#8212;clarifies that when I say &#8220;all languages,&#8221; <i>I really do mean &#8220;all languages&#8221;<\/i> (even the halting problem).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I&#8217;ve put up a new paper.&nbsp; Unusually for me these days, it&#8217;s a very short and simple one (8 pages)&#8212;I should do more like this!&nbsp; Here&#8217;s the abstract: We show that combining two different hypothetical enhancements to quantum computation&#8212;namely, quantum advice and non-collapsing measurements&#8212;would let a quantum computer solve any decision problem whatsoever in polynomial [&hellip;]<\/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":[10,5,4],"tags":[],"class_list":["post-3816","post","type-post","status-publish","format-standard","hentry","category-adventures-in-meatspace","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\/3816","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=3816"}],"version-history":[{"count":3,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/3816\/revisions"}],"predecessor-version":[{"id":4112,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/3816\/revisions\/4112"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3816"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3816"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3816"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}