{"id":570,"date":"2011-03-09T17:17:15","date_gmt":"2011-03-09T22:17:15","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=570"},"modified":"2017-01-13T06:56:50","modified_gmt":"2017-01-13T11:56:50","slug":"valiants-valiance-recognized","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=570","title":{"rendered":"Valiant’s valiance recognized"},"content":{"rendered":"

Update (March 25):<\/span><\/strong> I have a new paper called A Linear-Optical Proof that the Permanent is #P-Hard<\/a>, which is dedicated to Les Valiant on the occasion of his Turing Award.\u00a0 Here’s the abstract:<\/p>\n

One of the crown jewels of complexity theory is Valiant’s 1979 theorem that computing the permanent of an n*n matrix is #P-hard. Here we show that, by using the model of linear-optical quantum computing<\/em>—and in particular, a universality theorem due to Knill, Laflamme, and Milburn—one can give a different and arguably more intuitive proof of this theorem.<\/p>\n

\n

For decades, Harvard’s\u00a0Leslie Valiant<\/a> has obviously deserved a Turing Award—and today, the ACM\u00a0most excellently announced its agreement<\/a> with the obvious. \u00a0I have little to add to the prize citation<\/a> (see also Lance’s post<\/a>): from launching new fields whose reach extends beyond theory (PAC-learning),\u00a0to proving epochal results (#P-completeness of the permanent), to asking hugely influential questions (permanent vs. determinant), Valiant has been a creative powerhouse of theoretical computer science for longer than I’ve been alive.<\/p>\n

One thing the prize citation doesn’t<\/em> mention is that Valiant is now the third Turing Award winner (after Andy Yao and Len Adleman) to have made a major contribution to quantum computing theory. \u00a0Valiant’s 2001 paper Quantum Computers that can be Simulated Classically in Polynomial Time<\/a> introduced the beautiful computational model that computer scientists now know as “matchgates,” <\/em>and that physicists know as “noninteracting fermions.”<\/a> It still amazes that Valiant proposed this model for purely mathematical reasons—hitting physical relevance straight between the eyes despite (as far as I can tell) not having that target anywhere in his sights.<\/p>\n

To put the point in terms that my physicist friends will understand, that Valiant himself would probably dispute, but that I would defend:<\/p>\n

Valiant’s work has shown that, even if our universe hadn’t been made of bosons and fermions, theoretical computer scientists would have had compelling reasons of their own to invent those particles or something equivalent to them—and furthermore, that at least one theoretical computer scientist would have had the imagination to do so.<\/em><\/p>\n

Certainly<\/em> Valiant has had a huge influence on me, both through his work and as someone who made time to talk to me as an obscure grad student a decade ago. \u00a0 Three of my papers—The Learnability of Quantum States<\/a>, A Full Characterization of Quantum Advice<\/a>, and The Computational Complexity of Linear Optics<\/a>—would collapse entirely without Valiant-laid foundations.<\/p>\n

Congratulations, Les!<\/p>\n","protected":false},"excerpt":{"rendered":"

Update (March 25): I have a new paper called A Linear-Optical Proof that the Permanent is #P-Hard, which is dedicated to Les Valiant on the occasion of his Turing Award.\u00a0 Here’s the abstract: One of the crown jewels of complexity theory is Valiant’s 1979 theorem that computing the permanent of an n*n matrix is #P-hard. […]<\/p>\n","protected":false},"author":1,"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":[31,5,15,4],"tags":[],"class_list":["post-570","post","type-post","status-publish","format-standard","hentry","category-announcements","category-complexity","category-csphysics-deathmatch","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\/570","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=570"}],"version-history":[{"count":5,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/570\/revisions"}],"predecessor-version":[{"id":3148,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/570\/revisions\/3148"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=570"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=570"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=570"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}