{"id":401,"date":"2009-05-05T13:55:49","date_gmt":"2009-05-05T17:55:49","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=401"},"modified":"2021-10-12T18:29:33","modified_gmt":"2021-10-12T23:29:33","slug":"the-qis-workshop","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=401","title":{"rendered":"The QIS workshop"},"content":{"rendered":"

As promised, here’s my report on the Quantum Information Science Workshop<\/a> in Virginia, only a week or so behind schedule.<\/p>\n

I tried<\/em> to be cynical—really I did.  But despite my best efforts, somehow I went home more excited about quantum than I’ve been in a long time.<\/p>\n

The highlight of the workshop was of course the closed, invitation-only, late-night meeting in the basement of NSF headquarters, at which a group of us hidebound quantum computing reactionaries plotted to keep the field focused on irrelevant mathematical abstractions, and to ostracize the paradigm-smashing entrepreneurial innovators who threaten our status.  I don’t think I’ve ever heard so much cackling in the space of a single evening, or so much clinking of bone goblets.  Stuff like that is why I entered the field in the first place.<\/p>\n

But there were some other highlights as well:<\/p>\n

[Full list of talks iz heer]<\/a><\/p>\n

1. In his talk<\/a> on quantum algorithms with polynomial speedups, Andris Ambainis called attention to a spectacular recent paper<\/a> by Ben Reichardt, which characterizes<\/em> the quantum query complexity of any partial or total Boolean function f (up to a logarithmic factor) as the optimal witness size of a span program for f, and also as the negative-weight quantum adversary lower bound for f.  Assuming this result is correct, it seems possible that the remaining open problems in quantum query complexity will be pulverized, one after another, by solving the associated SDPs for the optimal span programs.  (Incidentally, using Reichardt’s result, it must be possible to prove, e.g., a \u03a9(n1\/3<\/sup>\/log(n)) lower bound for the quantum query complexity of the collision problem using the adversary method.  This was a longstanding open problem.  Can one say, explicitly, what the adversary matrices are in this case?)  Alas, it also seems possible that span programs will turn out to be almost as hard to analyze as quantum algorithms were…<\/p>\n

(1+\u221a5)\/2. Despite the obvious danger to the future funding of the entire field, by some clerical error I was released from my padded cell to speak about “Quantum Complexity and Fundamental Physics”<\/a>.  My “talk,” if it can be called that, was in my opinion neither rational nor integral to the workshop.<\/p>\n

2. In her talk<\/a> on blind quantum computation, Anne Broadbent (who’s also visiting MIT this week) described some beautiful new results that partly answer my Aaronson $25.00 Challenge<\/a> from a year and a half ago.  The Challenge, if you recall, was whether a quantum computer can always “prove its work” to a classical skeptic who doesn’t believe quantum mechanics—or more formally, whether every problem in BQP<\/strong> admits an interactive protocol where the prover in BQP<\/strong> and the verifier is in BPP<\/strong>.  Anne, Joe Fitzsimons, and Elham Kashefi haven’t quite answered this question, but in a recent paper<\/a> they’ve come close: they’ve shown that a quantum computer can prove its work to someone who’s almost<\/em> completely classical, her only “quantum” power being to prepare individual polarized photons and send them over to the quantum computer.  Furthermore, their protocol has the amazing property that the quantum computer learns nothing whatsoever<\/em> about which particular quantum computation it’s performing!  (Aharonov, Ben-Or, and Eban independently gave a protocol<\/a> with the same amazing properties, except theirs requires the “classical” verifier to have a constant-sized quantum computer.)  Anne et al. also show that two<\/em> quantum computers, who share entanglement but can’t communicate with each other, can prove their work to a completely classical verifier (while, again, remaining completely oblivious to what they computed).<\/p>\n

On top of everything else, these results appear to be the first complexity-theoretic application of the measurement-based quantum computing<\/a> paradigm, as well as the first “inherently quantum” non-relativizing results.  (Admittedly, we don’t yet have an oracle relative to which the blind quantum computing protocols don’t<\/em> work—but the protocols rely essentially on the gate structure of the quantum circuits, and I conjecture that such an oracle exists.)<\/p>\n

Rereading my Challenge, I noticed that “the [one-member] Committee may also choose to award smaller prizes for partial results.”  And thus, yesterday I had the pleasure of awarding Anne a crumpled $10 bill, with an additional $5 contributed by Seth Lloyd, for a grand total of $15.00 to be shared equally among Anne, Joe, and Elham.  (Update:<\/strong><\/span> Since I wrote that, Anne has elected to trade in for three signed and doodled-upon $5 bills.)  (Another Update:<\/strong><\/span> A $12, or $15-$O(1), prize shall be awarded to Dorit Aharonov, Michael Ben-Or, and Elad Eban the next time I see them.)  This is, I believe, the first time a monetary reward offered on Shtetl-Optimized<\/em> has actually been paid out.<\/p>\n

3. In a talk<\/a> that was so good, you almost forgot it involved chemistry<\/em>, Al\u00e1n Aspuru-Guzik discussed applications of quantum complexity theory to understanding photosynthesis and the design of efficient solar cells (!).  To give you a sense of how mindblowing that is, it briefly made me wonder whether I should reread some of John Sidles’ cheerful ramblings about the coming merger of quantum systems engineering with biology in the 21st<\/sup> century (of which, I predict, this very sentence will inspire dozens more).<\/p>\n

So what then is the connection between quantum complexity theory and photosynthesis?  Well, a few of you might remember my post “Low-Hanging Fruit from Two Conjoined Trees”<\/a> from years ago, which discussed the lovely result<\/a> of Childs et al. that a quantum walk on two conjoined binary trees can reach a designated end vertex exponentially faster than a classical walk on the same graph.  That result interested me, among other things, because it can be shown to lead to an oracle relative to which BQP<\/strong> \u2284 SZK<\/strong>, which at the time I didn’t know how to find otherwise.  But especially given the bizarre nature of the graph needed to produce the oracle separation, I thought of this result as pretty much the prototype<\/em> of an irrelevant complexity-theoretic curiosity (which, naturally, made me like it all the more).<\/p>\n

You can probably guess where this is going.<\/p>\n

<\/p>\n

Shown above is a light-harvesting molecule (image snagged from Al\u00e1n’s slides), which apparently is efficient at concentrating light at its center for essentially the same reason the Childs et al. quantum walk reaches the target vertex exponentially faster than a classical walk: namely, because of destructive interference between the paths that point backward, toward the leaves.  According to Al\u00e1n, what plants do to harvest sunlight is not entirely unrelated either (it also involves quantum coherence), and fully understanding these mechanisms in quantum information terms might conceivably be useful in designing better solar cells.  To be fair, a part of me always did<\/em> suspect that quantum oracle separations would turn out to be the key to solving the world energy crisis.  I’ll point you here<\/a> or here<\/a> if you want to know more.<\/p>\n

Incidentally, Al\u00e1n’s talk had another, also extremely interesting part, which was about coming up with precise numerical estimates of the number of qubits you’d need to simulate the wavefunctions of (say) benzene, caffeine, and cholesterol.  (Many of us have long thought that simulating physics and chemistry will be the real application for scalable quantum computers if we ever build them, practical long before breaking RSA and ultimately more useful too.  But it’s not something we often talk about—ostensibly for lack of meaty things to say, really because we don’t know chemistry.)<\/p>\n

4. In her talk<\/a>, Dorit Aharonov posed an open problem that I now have no choice but to inflict on others, if I don’t want to feel forced to think about it myself.  So here’s her problem: how hard is it to find the ground state of a local Hamiltonian H=H1<\/sub>+…+Hm<\/sub> (that is, a sum of k-qubit interactions, for some constant k), if we impose the constraint that the Hi<\/sub>‘s all commute with each other?  Clearly it’s somewhere between NP<\/strong> and QMA<\/strong>.  It might seem obvious that this problem should be in NP<\/strong>—to which I can only respond, prove it!<\/p>\n

There were also lots of great talks by the experimentalists.  Having attended them, I can report with confidence that (1) they’re still trying to build a quantum computer but (2) decoherence is still a big problem.  If you want to know even more<\/em> detail than I’ve just provided—or you want to know about the theory talks I didn’t mention, or more about the ones I did mention—ask away in the comments.  I can’t promise that no one will know the answer.<\/p>\n

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

As promised, here’s my report on the Quantum Information Science Workshop in Virginia, only a week or so behind schedule. I tried to be cynical—really I did.  But despite my best efforts, somehow I went home more excited about quantum than I’ve been in a long time. The highlight of the workshop was of course […]<\/p>\n","protected":false},"author":2,"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_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},"_wpas_customize_per_network":false},"categories":[10,5,30,4],"tags":[],"class_list":["post-401","post","type-post","status-publish","format-standard","hentry","category-adventures-in-meatspace","category-complexity","category-mirrored-on-csail-blog","category-quantum"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/401","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\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=401"}],"version-history":[{"count":1,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/401\/revisions"}],"predecessor-version":[{"id":5959,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/401\/revisions\/5959"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=401"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=401"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=401"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}