{"id":1489,"date":"2007-04-11T09:04:06","date_gmt":"2007-04-11T16:04:06","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=1489"},"modified":"2007-04-11T09:04:06","modified_gmt":"2007-04-11T16:04:06","slug":"the-np-complete-dog-and-pony-show-comes-to-seattle","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2007\/04\/11\/the-np-complete-dog-and-pony-show-comes-to-seattle\/","title":{"rendered":"The NP-complete Dog and Pony Show Comes to Seattle"},"content":{"rendered":"

Scott’s<\/a> coming to town:<\/p>\n

\nCSE Colloquium, 04\/12\/2007 3:30 pm, EE-105
\nTalk:<\/b> The Limits of Quantum Computers
\nSpeaker:<\/b> Scott Aaronson (University of Waterloo)
\nAbstract:<\/b> In the popular imagination, quantum computers would be almost magical devices, able to “solve impossible problems in an instant” by trying exponentially many solutions in parallel. In this talk, I’ll describe four results in quantum computing theory that directly challenge this view.
\nFirst, I’ll show that any quantum algorithm to decide whether a function f:[n]->[n] is one-to-one or two-to-one needs to query the function at least n^{1\/5} times. This provides strong evidence that collision-resistant hash functions, and hence secure electronic commerce, would still be possible in a world with quantum computers.
\nSecond, I’ll show that in the “black-box” or “oracle” model that we know how to analyze, quantum computers could not solve NP-complete problems in polynomial time, even with the help of nonuniform “quantum advice states.”
\nThird, I’ll show that quantum computers need exponential time to find local optima — and surprisingly, that the ideas used to prove this result also yield new classical lower bounds for the same problem.
\nFinally, I’ll show how to do “pretty-good quantum state tomography” using a number of measurements that increases only linearly, not exponentially, with the number of qubits. This illustrates how one can sometimes turn the limitations of quantum computers on their head, and use them to develop new techniques for experimentalists.
\nNo quantum computing background will be assumed.\n<\/p><\/blockquote>\n

Since no quantum computing background is assumed, I<\/em> may even be able to follow this one!<\/p>\n","protected":false},"excerpt":{"rendered":"

Scott’s coming to town: CSE Colloquium, 04\/12\/2007 3:30 pm, EE-105 Talk: The Limits of Quantum Computers Speaker: Scott Aaronson (University of Waterloo) Abstract: In the popular imagination, quantum computers would be almost magical devices, able to “solve impossible problems in an instant” by trying exponentially many solutions in parallel. In this talk, I’ll describe four … <\/p>\n

Continue reading “The NP-complete Dog and Pony Show Comes to Seattle”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","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}},"categories":[20,63,70,75],"tags":[],"class_list":["post-1489","post","type-post","status-publish","format-standard","hentry","category-computer-science","category-quantum","category-science","category-seattle"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/1489","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/comments?post=1489"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/1489\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=1489"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=1489"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=1489"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}