{"id":94,"date":"2006-06-17T06:15:00","date_gmt":"2006-06-17T06:15:00","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=94"},"modified":"2006-06-17T06:15:00","modified_gmt":"2006-06-17T06:15:00","slug":"back-to-safe-territory","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=94","title":{"rendered":"Back to safe territory"},"content":{"rendered":"<p>When you see me getting chased across the blogosphere by livid, paintbrush-wielding artistes, it can only mean one thing: that I&#8217;ve once again abandoned my <a href=\"https:\/\/scottaaronson.blog\/?p=76\">&#8220;promise&#8221;<\/a> to stick to the Serious Complexity Theory That I&#8217;m Actually Qualified To Discuss.  So I&#8217;ll tell you what, whistling-pig-lovers: answer me the following; then come back for more.<\/p>\n<blockquote><p>Given a set of n-by-n real matrices, is there a nonzero linear combination of those matrices with rank 1?  Equivalently, given a subspace S of a bipartite n-by-n Hilbert space, does S contain a separable state?<\/p><\/blockquote>\n<p>I&#8217;d like (1) a proof of NP-hardness for the exact version, and (2) more importantly, whether or not there&#8217;s a decent approximation algorithm.  (For instance, an algorithm that finds a rank-1 matrix, with the sum of the squares of the entries equal to 1, whose L<sub>2<\/sub>-distance from the subspace of interest is at most a small additive constant more than optimal.)<\/p>\n<p>So get cracking!  If you do find a decent approximation algorithm, you&#8217;ll have shown, among other things, that QMA(2) (QMA with two unentangled yes-provers) is in EXP.  Incredibly, right now we don&#8217;t have any upper bound better than NEXP.<\/p>\n<p>Oh, yes: while my brain is closed, and while I can barely turn theorems into coffee, I will offer $20 for a solution to (2).<\/p>\n<p>American.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>When you see me getting chased across the blogosphere by livid, paintbrush-wielding artistes, it can only mean one thing: that I&#8217;ve once again abandoned my &#8220;promise&#8221; to stick to the Serious Complexity Theory That I&#8217;m Actually Qualified To Discuss. So I&#8217;ll tell you what, whistling-pig-lovers: answer me the following; then come back for more. Given [&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_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_hide_featured_image":false,"_jetpack_featured_image_duplicate_dismissed":0,"_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-94","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\/94","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=94"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/94\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=94"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=94"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=94"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}