{"id":2852,"date":"2016-07-17T15:46:49","date_gmt":"2016-07-17T19:46:49","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=2852"},"modified":"2017-01-12T16:23:19","modified_gmt":"2017-01-12T21:23:19","slug":"the-complexity-of-quantum-states-and-transformations-from-quantum-money-to-black-holes","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=2852","title":{"rendered":"The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes"},"content":{"rendered":"

On February 21-25, I taught a weeklong mini-course at the Bellairs Research Institute in Barbados, where I tried to tell an integrated story about everything from quantum proof and advice complexity classes to quantum money to AdS\/CFT and the firewall problem—all through the unifying lens of quantum circuit complexity.\u00a0 After a long effort—on the part of me, the scribes, the guest lecturers, and the organizers—the 111-page lecture notes are finally available, right here<\/a>.<\/p>\n

Here’s the summary:<\/p>\n

This mini-course will introduce participants to an exciting frontier for quantum computing theory: namely, questions involving the computational complexity of preparing a certain quantum state or applying a certain unitary transformation. Traditionally, such questions were considered in the context of the Nonabelian Hidden Subgroup Problem and quantum interactive proof systems, but they are much broader than that. One important application is the problem of \u201cpublic-key quantum money\u201d \u2013 that is, quantum states that can be authenticated by anyone, but only created or copied by a central bank \u2013 as well as related problems such as copy-protected quantum software. A second, very recent application involves the black-hole information paradox, where physicists realized that for certain conceptual puzzles in quantum gravity, they needed to know whether certain states and operations had exponential quantum circuit complexity. These two applications (quantum money and quantum gravity) even turn out to have connections to each other! A recurring theme of the course will be the quest to relate these novel problems to more traditional computational problems, so that one can say, for example, \u201cthis quantum money is hard to counterfeit if that cryptosystem is secure,\u201d or \u201cthis state is hard to prepare if PSPACE is not in PP\/poly.\u201d Numerous open problems and research directions will be suggested, many requiring only minimal quantum background. Some previous exposure to quantum computing and information will be assumed, but a brief review will be provided.<\/div>\n

If you still haven’t decided whether to tackle this thing: it’s basically a quantum complexity theory textbook (well, a textbook for certain themes<\/em> within quantum complexity theory) that I’ve written and put on the Internet for free.\u00a0 It has explanations of lots of published results both old and new, but also some results of mine (e.g., about private-key quantum money, firewalls, and AdS\/CFT) that I shamefully haven’t yet written up as papers, and that therefore aren’t currently available anywhere else.\u00a0 If you’re interested in certain specific topics—for example, only quantum money, or only firewalls—you should be able to skip around in the notes without too much difficulty.<\/p>\n

Thanks so much<\/em> to Denis Therien for organizing the mini-course, Anil Ada for managing the scribe notes effort, my PhD students Adam Bouland and Luke Schaeffer for their special guest lecture (the last one), and finally, the course attendees for their constant questions and interruptions, and (of course) for scribing.<\/p>\n

And in case you were wondering: yes, I’ll do absolutely anything<\/em> for science, even if it means teaching a weeklong course in Barbados!\u00a0 Lest you consider this a pure island boondoggle, please know that I spent probably 12-14 hours per day either lecturing (in two 3-hour installments) or preparing for the lectures, with little sleep and just occasional dips in the ocean.<\/p>\n

And now I’m headed to the Perimeter Institute for their It from Qubit summer school<\/a>, not at all unrelated to my Barbados lectures.\u00a0 This time, though, it’s thankfully other people’s turns to lecture…<\/p>\n","protected":false},"excerpt":{"rendered":"

On February 21-25, I taught a weeklong mini-course at the Bellairs Research Institute in Barbados, where I tried to tell an integrated story about everything from quantum proof and advice complexity classes to quantum money to AdS\/CFT and the firewall problem—all through the unifying lens of quantum circuit complexity.\u00a0 After a long effort—on the part […]<\/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":[5,15,4],"tags":[],"class_list":["post-2852","post","type-post","status-publish","format-standard","hentry","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\/2852","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=2852"}],"version-history":[{"count":4,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2852\/revisions"}],"predecessor-version":[{"id":2859,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2852\/revisions\/2859"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2852"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2852"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2852"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}