{"id":2943,"date":"2016-10-25T18:50:18","date_gmt":"2016-10-25T22:50:18","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=2943"},"modified":"2017-01-12T09:08:17","modified_gmt":"2017-01-12T14:08:17","slug":"my-5-minute-quantum-computing-talk-at-the-white-house","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=2943","title":{"rendered":"My 5-minute quantum computing talk at the White House"},"content":{"rendered":"

(OK, technically it was in the Eisenhower Executive Office Building, which is not exactly the White House itself, but is adjacent to the West Wing in\u00a0the White House complex. \u00a0And President Obama wasn’t there—maybe, like Justin Trudeau, he already knows everything about quantum computing? \u00a0But lots of people from the Office of Science and Technology Policy<\/a> were! \u00a0And some\u00a0of us talked with\u00a0Valerie Jarrett<\/a>, Obama’s adviser, when she passed us\u00a0on her way to the\u00a0West Wing.<\/em><\/p>\n

The occasion was a Quantum Information Science policy workshop that OSTP held, and which the White House explicitly gave us permission to discuss on social media. \u00a0Indeed, John Preskill already tweeted photos<\/a> from the event. \u00a0Besides me and Preskill, others in attendance included Umesh Vazirani, Seth Lloyd, Yaoyun Shi, Rob Schoelkopf, Krysta Svore, Hartmut Neven, Stephen Jordan…<\/em><\/p>\n

I don’t know whether this is the first time that the polynomial hierarchy, or the notion\u00a0of variation distance, were ever invoked\u00a0in a speech at the White House. \u00a0But in any case, I was proud to receive a box of Hershey Kisses bearing the presidential seal. \u00a0I thought of not eating them, but then I got hungry, and realized that I can simply refill the box later if desired.<\/em><\/p>\n

For\u00a0regular readers of Shtetl-Optimized, my talk won’t have all that much that’s new, but in any case it’s short.<\/i><\/p>\n

Incidentally, during the workshop, a guy from OSTP told me that, when he and others at the White House were asked to prepare materials about quantum computing, posts on Shtetl-Optimized (such as Shor I’ll Do It<\/a>) were a huge help.\u00a0 Honored though I was to have “served my country,” I winced, thinking about all the puerile doofosities I might’ve self-censored had I had any idea who might read them.\u00a0 I didn’t dare ask whether anyone at the White House also reads the comment sections!
\n<\/em><\/p>\n

Thanks so much to all the other participants and to the organizers for a great workshop. \u00a0–SA)<\/em><\/p>\n

\n

Quantum Supremacy<\/b><\/p>\n

by Scott Aaronson (UT Austin)<\/p>\n

October 18, 2016<\/p>\n

Thank you; it’s great to be here. \u00a0There are lots of directions that excite me enormously right now in quantum computing theory, which is what I work on. \u00a0For example, there’s the use of quantum computing to get new insight into classical computation<\/a>, into condensed matter physics<\/a>, and recently, even into the black hole information problem<\/a>.<\/p>\n

But since I have five minutes, I wanted to talk here about one particular direction—one that, like nothing else that I know of, bridges theory and experiment in the service of what we hope will be a spectacular result in the near future. \u00a0This direction is what’s known as “Quantum Supremacy”—John [Preskill], did you help popularize that term? \u00a0[John nods yes]—although some people have been backing away from the term recently, because of the campaign of one of the possible future occupants of this here complex.<\/p>\n

But what quantum supremacy means to me, is demonstrating a quantum speedup for some<\/em> task as confidently as possible. \u00a0Notice that I didn’t say a useful<\/em> task! \u00a0I like to say that for me, the #1 application of quantum computing—more than codebreaking, machine learning, or even quantum simulation—is just disproving the people who say quantum computing is impossible! \u00a0So, quantum supremacy targets that<\/em> application.<\/p>\n

What is<\/em> important for quantum supremacy is that we solve a clearly defined problem, with some relationship between inputs and outputs that’s independent of whatever hardware we’re using to solve the problem. \u00a0That’s part of why it doesn’t cut it to point to some complicated, hard-to-simulate molecule and say “aha! \u00a0quantum supremacy!”<\/p>\n

One discovery, which\u00a0I and others stumbled on 7 or 8 years ago, is that quantum supremacy seems to become much easier to demonstrate if we switch from problems with a single valid output to sampling<\/em> problems: that is, problems of sampling exactly or approximately from some specified probability distribution.<\/p>\n

Doing this has two advantages. \u00a0First, we no longer need a full, fault-tolerant quantum computer—in fact, very rudimentary types of quantum hardware appear to suffice. \u00a0Second, we can design sampling problems for which we can arguably be more<\/em> confident that they really are hard for a classical computer, than we are that (say) factoring is classically hard. \u00a0I like to say that a fast classical factoring algorithm might collapse the world’s electronic commerce, but as far as we know, it wouldn’t collapse the polynomial hierarchy! \u00a0But with sampling problems, at least with exact sampling, we can<\/em> often show the latter implication, which is about the best evidence you can possibly get for such a problem being hard in the present state of mathematics.<\/p>\n

One example of these sampling tasks that we think are classically hard is BosonSampling<\/a>, which Alex Arkhipov and I proposed in 2011. \u00a0BosonSampling uses a bunch of identical photons that are sent through a network of beamsplitters, then measured to count the number of photons in each output mode. \u00a0Over the past few years, this proposal has\u00a0been experimentally demonstrated by quantum optics groups around the world, with the current record being a 6-photon demonstration<\/a> by the O’Brien group in\u00a0Bristol, UK. \u00a0A second example is the IQP (“Instantaneous Quantum Polynomial-Time”) or Commuting Hamiltonians<\/a> model of Bremner, Jozsa, and Shepherd.<\/p>\n

A third example—no doubt the simplest—is just to sample from the output distribution of a random quantum circuit, let’s say on a 2D square lattice of qubits with nearest-neighbor interactions. \u00a0Notably, this last task is one that the Martinis group at Google is working toward achieving<\/a> right now, with 40-50 qubits. \u00a0They say that they’ll achieve it in as little as one or two years, which translated from experimental jargon, means maybe five years? \u00a0But not infinity years.<\/p>\n

The challenges on the experimental side are clear: get enough qubits with long enough coherence times to achieve this. \u00a0But there are also some huge theoretical challenges remaining.<\/p>\n

A first is, can we still solve classically hard sampling problems even in the presence of realistic experimental imperfections? \u00a0Arkhipov and I already thought about that problem—in particular, about sampling from a distribution that’s merely close<\/em> in variation distance to the BosonSampling one—and got results that admittedly weren’t as satisfactory as the results for exact sampling. \u00a0But I’m delighted to say that, just within the last month or two, there have been some excellent<\/a> new papers<\/a> on the arXiv that tackle exactly this question, with both positive and negative results.<\/p>\n

A second theoretical challenge is, how do we verify the results of a quantum supremacy experiment? \u00a0Note that, as far as we know today, verification could itself require classical exponential time. \u00a0But\u00a0that’s not the showstopper that some people think, since we could target the “sweet spot” of 40-50 qubits, where classical verification is difficult (and in particular, clearly “costlier” than running the experiment itself), but also far from impossible with cluster computing resources.<\/p>\n

If I have any policy advice, it’s this: recognize that a clear demonstration of quantum supremacy is at least as big a deal as (say) the discovery of the Higgs boson. \u00a0After this scientific milestone is achieved, I predict that the whole discussion of commercial applications of quantum computing will shift to a new plane, much like the Manhattan Project shifted to a new plane after Fermi built his pile under the Chicago stadium in 1942. \u00a0In other words: at this point, the most “applied” thing to do might be to set applications aside temporarily, and just achieve this quantum supremacy milestone—i.e., build the quantum computing Fermi pile—and thereby show the world that quantum computing speedups are a reality. \u00a0Thank you.<\/p>\n","protected":false},"excerpt":{"rendered":"

(OK, technically it was in the Eisenhower Executive Office Building, which is not exactly the White House itself, but is adjacent to the West Wing in\u00a0the White House complex. \u00a0And President Obama wasn’t there—maybe, like Justin Trudeau, he already knows everything about quantum computing? \u00a0But lots of people from the Office of Science and Technology […]<\/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":[10,5,4],"tags":[],"class_list":["post-2943","post","type-post","status-publish","format-standard","hentry","category-adventures-in-meatspace","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\/2943","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=2943"}],"version-history":[{"count":7,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2943\/revisions"}],"predecessor-version":[{"id":2951,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/2943\/revisions\/2951"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2943"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2943"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2943"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}