{"id":139,"date":"2006-10-06T04:44:00","date_gmt":"2006-10-06T04:44:00","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=139"},"modified":"2006-10-06T04:44:00","modified_gmt":"2006-10-06T04:44:00","slug":"the-quantum-pcp-manifesto","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=139","title":{"rendered":"The Quantum PCP Manifesto"},"content":{"rendered":"

Behold the PCP Theorem<\/a>, one of the crowning achievements of complexity theory:<\/p>\n

Given a 3SAT formula \u03c6, it’s NP-hard to decide whether (1) \u03c6 is satisfiable or (2) at most a 1-\u03b5 fraction of the clauses are satisfiable, promised that one of these is the case. Here \u03b5 is a constant independent of n.<\/p><\/blockquote>\n

In recent weeks, I’ve become increasingly convinced that a Quantum PCP Theorem like the following will one day be a crowning achievement of quantum complexity theory:<\/p>\n

Given a set of local measurements on an n-qubit register, it’s QMA-hard to decide whether (1) there exists a state such that all of the measurements accept with probability 1, or (2) for every state, at most a 1-\u03b5 fraction of the measurements accept with probability more than 1-\u03b4, promised that one of these is the case. Here a “local” measurement is one that acts on at most (say) 3 qubits, and \u03b5 and \u03b4 are constants independent of n.<\/p><\/blockquote>\n

I’m 99% sure that this theorem (alright, conjecture) or something close to it is true. I’m 95% sure that the proof will require a difficult adaptation of classical PCP machinery (whether Iritean<\/a> or pre-Iritean<\/a>), in much the same way that the Quantum Fault-Tolerance Theorem<\/a> required a difficult adaptation of classical fault-tolerance machinery. I’m 85% sure that the proof is achievable in a year or so, should enough people make it a priority. I’m 75% sure that the proof, once achieved, will open up heretofore undreamt-of vistas of understanding and insight. I’m 0.01% sure that I can prove it. And that is why I hereby bequeath the actual proving part to you, my readers.<\/p>\n

Notes:<\/p>\n

    \n
  1. By analogy to the classical case, one expects that a full-blown Quantum PCP Theorem would be preceded by weaker results (“quantum assignment testers”, quantum PCP’s with weaker parameters, etc). So these are obviously the place to start.<\/li>\n
  2. Why hasn’t anyone tackled this question yet? Well, one reason is that it’s hard. But a second reason is that people keep getting hung up on exactly how to formulate the question. To forestall further nitpicking, I hereby declare it obvious that a “Quantum PCP Theorem” means nothing more or less than a robust version of Kitaev’s QMA-completeness theorem<\/a>, in exactly the same sense that the classical PCP Theorem was a robust version of the Cook-Levin Theorem. Any formulation that captures this spirit is fine; mine was only one possibility.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

    Behold the PCP Theorem, one of the crowning achievements of complexity theory: Given a 3SAT formula \u03c6, it’s NP-hard to decide whether (1) \u03c6 is satisfiable or (2) at most a 1-\u03b5 fraction of the clauses are satisfiable, promised that one of these is the case. Here \u03b5 is a constant independent of n. In […]<\/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-139","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\/139","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=139"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/139\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=139"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=139"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=139"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}