{"id":60,"date":"2006-02-27T22:13:00","date_gmt":"2006-02-27T22:13:00","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=60"},"modified":"2006-02-27T22:13:00","modified_gmt":"2006-02-27T22:13:00","slug":"lord-send-no-sign","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=60","title":{"rendered":"Lord, send no sign"},"content":{"rendered":"

Lars Johansson asks me to comment on a press release<\/a> entitled “Quantum computer solves problem, without running.” Alright, what have we got this time?<\/p>\n

CHAMPAIGN, Ill. — By combining quantum computation and quantum interrogation, scientists at the University of Illinois at Urbana-Champaign have found an exotic way of determining an answer to an algorithm — without ever running the algorithm.<\/p>\n

Using an optical-based quantum computer, a research team led by physicist Paul Kwiat has presented the first demonstration of “counterfactual computation,” inferring information about an answer, even though the computer did not run.<\/p><\/blockquote>\n

Readers, my sole ambition in life, outside the purely personal, is to prevent stuff like this from being spouted.<\/p>\n

I’m serious. You see, I have no “philosophy” to offer the world, no unifying theory, no startling new idea. All I have is a long howl of rage, which admittedly tends to take the form of STOC\/FOCS papers. But if you read those papers, you’ll see that almost every one of them was born when I came across some specific claim and said, “No. Dammit. No. That can’t possibly be right.”<\/p>\n

Look — if you tell a layperson that a computer has solved a problem without ever having been switched on, then not only have you not explained anything, you haven’t even asserted anything. All you’ve done is pose a question: namely, “what’s the catch?”<\/p>\n

In this case, the catch is simple. Say you’ve got two programs, Dif and Doof, running in the Windows taskbar. Dif is performing some enormous calculation, while Doof (being a Doof) is doing nothing. If Dif’s calculation returns any answer other than 5, then Dif closes Doof. You come back to your computer and find that Doof is still running. Even though Doof didn’t calculate anything, and even though Dif never did anything to Doof, you can immediately conclude — from Doof alone — that the answer you wanted was 5. Mindblowing! Unbelievable!<\/p>\n

Now let Dif and Doof run, not in different windows, but in different branches of the wavefunction — that is, in quantum superposition. And instead of Dif using an operating system to close Doof, have Dif’s branch of the wavefunction interfere destructively with Doof’s branch, thereby preventing Doof’s branch from being observed. That’s the idea of counterfactual quantum computing.<\/p>\n

I suppose this is “mysterious,” in the same way that a dog claiming to hate doggie-treats would be mysterious. In the former case, the mystery is quantum mechanics. In the latter case, the mystery is a talking dog.<\/p>\n

Having said that, the original paper<\/a> by Jozsa and Mitchison is actually lovely and well worth reading. It proves some nontrivial results about limits of counterfactual computing, and it also gives a good introduction to the Vaidman bomb (which I think of as a precursor to Grover’s algorithm).<\/p>\n

I’ll end with the clearest account of counterfactual computing I’ve seen, courtesy of one Homer J. Simpson.<\/p>\n

Dear Lord, the gods have been good to me. As an offering, I present these milk and cookies. If you wish me to eat them instead, please give me no sign whatsoever.<\/p>\n

…<\/p>\n

Thy will be done (munch munch munch).<\/p><\/blockquote>\n

Update (3\/1): Paul Kwiat has written in to the comments section with some helpful clarifications.<\/p>\n","protected":false},"excerpt":{"rendered":"

Lars Johansson asks me to comment on a press release entitled “Quantum computer solves problem, without running.” Alright, what have we got this time? CHAMPAIGN, Ill. — By combining quantum computation and quantum interrogation, scientists at the University of Illinois at Urbana-Champaign have found an exotic way of determining an answer to an algorithm — […]<\/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_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_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":[4,16],"tags":[],"class_list":["post-60","post","type-post","status-publish","format-standard","hentry","category-quantum","category-rage-against-doofosity"],"jetpack_publicize_connections":[],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/60","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=60"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/60\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=60"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=60"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=60"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}