{"id":104,"date":"2012-06-28T17:36:54","date_gmt":"2012-06-28T17:36:54","guid":{"rendered":"https:\/\/quisco.org.uk\/?p=104"},"modified":"2012-06-28T18:12:10","modified_gmt":"2012-06-28T18:12:10","slug":"scott-aaronson-talk-schedule","status":"publish","type":"post","link":"https:\/\/quisco.org.uk\/?p=104","title":{"rendered":"Scott Aaronson Talk Schedule"},"content":{"rendered":"

Venue: School of Informatics<\/a>, University of Edinburgh, Room 4.33\/4.31
\nTimes: 15:00 till 16:30<\/p>\n

New Computational Insights from Quantum Optics<\/strong><\/h3>\n

Tuesday 10\/7\/2012<\/p>\n

In work with Aleksandr Arkhipov, we proposed a rudimentary form of quantum computing, based on linear optics with nonadaptive measurements; and used a connection between linear optics and the permanent function to show that even this limited model could solve sampling and search problems that are intractable for classical computers under plausible complexity assumptions.\u00a0 In this talk, I’ll discuss this work in a self-contained way, and mention some of its implications for quantum computing experiments. I’ll also discuss some more general results that emerged from our work. These include a new equivalence between sampling problems and search problems based on Kolmogorov complexity; a new, linear-optics-based proof of Valiant’s famous theorem that the permanent is #P-complete; and a new classical approximation algorithm for the permanent.<\/p>\n

Papers:
\nThe Computational Complexity of Linear Optics<\/a>
\nThe Equivalence of Sampling and Searching<\/a>
\nA Linear-Optical Proof that the Permanent is #P-Hard<\/a><\/p>\n

How Much Information Is In A Quantum State?<\/strong><\/h3>\n

Wednesday 11\/7\/2012<\/p>\n

People often talk about the quantum state of n entangled particles as if it contained an amount of information exponential in n.\u00a0 In this talk, I’ll discuss three results that suggest that, in various senses relevant for computation, prediction, and learning, quantum states
\nactually *don’t* behave as if they contained exponential amounts of information. Specifically, I’ll discuss the limitations of “quantum advice states,”the approximate “learnability” of quantum states from random measurement results, and the simulation of arbitrary quantum state preparation tasks by the preparation of ground states of local Hamiltonians (joint work with Andrew Drucker).<\/p>\n

Papers:
\nLimitations of Quantum Advice and One-Way Communication<\/a>
\nThe Learnability of Quantum States<\/a>
\nA Full Characterization of Quantum Advice<\/a><\/p>\n

Talk #3<\/strong><\/h3>\n

Thursday 12\/7\/2012<\/p>\n

Talk #3 will be determined based on audience interest.<\/p>\n

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

Venue: School of Informatics, University of Edinburgh, Room 4.33\/4.31 Times: 15:00 till 16:30 New Computational Insights from Quantum Optics Tuesday 10\/7\/2012 In work with Aleksandr Arkhipov, we proposed a rudimentary form of quantum computing, based on linear optics with nonadaptive measurements; and used a connection between linear optics and the permanent function to show that … Continue reading Scott Aaronson Talk Schedule<\/span> →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-104","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/quisco.org.uk\/index.php?rest_route=\/wp\/v2\/posts\/104","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/quisco.org.uk\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/quisco.org.uk\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/quisco.org.uk\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/quisco.org.uk\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=104"}],"version-history":[{"count":6,"href":"https:\/\/quisco.org.uk\/index.php?rest_route=\/wp\/v2\/posts\/104\/revisions"}],"predecessor-version":[{"id":110,"href":"https:\/\/quisco.org.uk\/index.php?rest_route=\/wp\/v2\/posts\/104\/revisions\/110"}],"wp:attachment":[{"href":"https:\/\/quisco.org.uk\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=104"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/quisco.org.uk\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=104"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/quisco.org.uk\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=104"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}