Lord, send no sign

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 — without ever running the algorithm.

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.

Readers, my sole ambition in life, outside the purely personal, is to prevent stuff like this from being spouted.

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.”

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?”

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!

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.

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.

Having said that, the original paper 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).

I’ll end with the clearest account of counterfactual computing I’ve seen, courtesy of one Homer J. Simpson.

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.

Thy will be done (munch munch munch).

Update (3/1): Paul Kwiat has written in to the comments section with some helpful clarifications.

27 Responses to “Lord, send no sign”

  1. Greg Kuperberg Says:

    Counterfactual computation, or counterfactual journalism?

    Quantum computers have the potential for solving certain types of problems much faster than classical computers. Speed and efficiency are gained because quantum bits can be placed in superpositions of one and zero, as opposed to classical bits, which are either one or zero.

    Every time I see this type of comment, I get more frustrated. Actually, a randomized classical bit can also be in a superposition of 1 and 0; it’s just a classical superposition rather than a quantum one. Quantum accelerations do not come from superpositions vs no superpositions. They come from better (i.e. reversible or pure) superpositions versus worse (i.e. irreversible, mixed) superpositions.

    On the other hand, every time I see the picture of Sasha Cohen on this blog, I like it better. She is pretty, but not always quite that pretty. It’s just a great photo.

  2. Anonymous Says:

    “On the other hand, every time I see the picture of Sasha Cohen on this blog, I like it better. She is pretty, but not always quite that pretty. It’s just a great photo.”

    Yes, she’s in a super position there.

  3. Anonymous Says:

    horrible snotty cough + laughter from the end of that post = bad idea.

  4. Scott Says:

    Yuck!

  5. Niel Says:

    The linked article just goes to illustrate what I’m calling the Slashdot principle of quantum information: “Anything written about quantum information on Slashdot (or for that matter, almost any technology enthusiast publication) is wrong.”

    I fear that quantum mechanics is the leading argument in the case against “popular science” as a genre, and it’s a pretty compelling one.

  6. Scott Says:

    I fear that quantum mechanics is the leading argument in the case against “popular science” as a genre, and it’s a pretty compelling one.

    Someone said that no science has been better served by its writers than evolution. I would add that no science has been worse served than quantum mechanics.

  7. Greg Kuperberg Says:

    I won’t argue against science journalism. Warts and all, it is clearly better than nothing. It clearly stirs interest in science and mathematics, including quantum mechanics.

    But I agree that science journalism is hobble by perverse pseudo-intellectualism. They ride roughshod over counterintuitive and fairly abstract points of quantum mechanics. But given the opportunity to cover even the simplest and prettiest pure mathematics, for example the famous new result that there are arbitrarily long arithmetic progressions of primes, they say, “Oh, that’s too theoretical! We can’t bore the readers with stuff that they will never understand.”

    It is clear where Ben Green and Terry Tao went wrong in the universe of science journalists. Even though it is substantially easier to explain prime numbers and arithmetic progressions than quantum mechanics, Green and Tao did their work with pen and paper instead of lasers and computers. If they were theoretical physicists, that would perhaps be forgivable. The kiss of death is that you only need pen and paper, not lasers or computers, to confirm them.

  8. Anonymous Says:

    I am not sure I agree with Greg
    Kuperberg’s reasoning regarding the
    Green-Tao theorem. It is perhaps
    not hard to explain the statement
    of the theorem but it is actually
    hard to explain the significance of
    the theorem. It is a beatiful
    theorem but mainly for its technical
    importance and the connections
    to various branches of mathematics.
    How does one convey this easily to
    the man on the street? On the other
    hand the polynomial time deterministic algorithm for primality is easy to state as
    well explain the significance of.
    And this did get a lot of publicity
    in the press.

    Quantum computing gets a lot of
    press because computers have
    lot of direct impact on people and
    there is a starting point for them
    to relate to. I am not saying that
    pure math should’nt be publicized
    but only that it is more difficult
    than it appears to the insiders.

  9. Greg Kuperberg Says:

    It is perhaps not hard to explain the statement of the theorem but it is actually hard to explain the significance of the theorem.

    Except that it isn’t all that hard. All it takes is the cultural leap of faith that readers can care about mathematics for its own sake. At least if it is explained nicely. Martin Gardner was very good at it. Sara Robinson, Larry Gonick, and Dana McKenzie are perfectly competent at it as well. (To name several relevant math journalists.)

    It is also a red herring to demand the average American as the audience. The newspaper science sections are not targeted for the average American anyway, merely for millions of Americans. I’m sure that there are that many who can appreciate the mathematical aesthetic, even if most of them do not have advanced training in mathematics.

    For that matter, the argument that “counterfactual computation” is significant because computers affect people’s daily lives is disingenuous. Useful quantum computers do not exist, and even if they did, counterfactual computation would probably not affect their usefulness. Scientific results like this one are favored by journalists for the broader reason that American culture is more rooted in technocracy than in intellectualism.

  10. Anonymous Says:

    “Scientific results like this one are favored by journalists for the broader reason that American culture is more rooted in technocracy than in intellectualism.”

    Nah, I think it’s a lot simpler than that. Scientific results like counterfactual computation are favored by journalists for the following reason:

    “Shee-oot, Clem, lookee here – ‘puter gives better answers when they turn the dad-blamed thing *off*. Tolja! Haw, haw, haw!”

    - which is also the reason journalists bowdlerize those results: The goal is to go for the broad “‘Shee-oot!’ moment,” rather than to inform accurately.

  11. Greg Kuperberg Says:

    Are anonymous comments really worth it on blogs?

  12. Cheshire Cat Says:

    Try out cosmicvariance.com for a fun explanation of the phenomenon.

  13. Scott Says:

    Greg: I can’t understand why so many people choose to be anonymous — do they just not remember or care to sign their names? Are they embarrassed by what they’ve written? Are they worried that it’ll come back to haunt them in a future political campaign?

    There’s no question that anonymity decreases the quality of the discussion — it’s like talking to people with paper bags over their heads.

    On the other hand, I’m worried that if I turn off anonymous comments, the number of hillbilly jokes will go down dramatically.

    Maybe the masked chickens of the darkness have some insight to share?

  14. Greg Kuperberg Says:

    Scott: I can’t understand why so many people choose to be anonymous — do they just not remember or care to sign their names?

    This kind of question is sometimes floated sarcastically, but I’m going to conjecture that your meaning is straight.

    People are just more comfortable with anonymity, when it is as easy as Blogger makes it. Someone might Google you to find out your personality, and the first hit might be the stupidest thing that you ever said, which could (who knows) have a high Google ranking if a lot of people flamed you for it.

    Personally I think that it is easy to exaggerate the risk, and that rational residual concern is a feature rather than a bug.

    In any case it is easy enough to have a pseudonym in Blogger, even if you do turn off anonymous comments.

  15. Anonymous Says:

    As the author of a vast number (OK, a half-vast number; well, really, exactly one – in a comment on this blog – to be precise) of hillbilly jokes (though actually the intent wasn’t to poke fun at hillbillies, but to explore the motivations of science journalists who may well see their audience as comprised of such folks) I feel compelled to ask: “Masked chickens of the darkness”? I think that’s well past the mixing of metaphors and into Osterization.

  16. Jud Says:

    Odd, I thought that last comment would show my name.

    Jud

  17. secret milkshake Says:

    here commes da hillbilly joke:

    the matzoh stuff, the harboiled eggs shall not do any harm unto ya. (They can be worked out with a pencil)

  18. Luca Says:

    On the matter of hillbilly jokes:

    http://dilbertblog.typepad.com/the_dilbert_blog/2006/02/inebriated_hill.html

  19. Anonymous Says:

    Are they embarrassed by what they’ve written?

    Yes. I agree that anonymous posts are weak, but the other side of the coin is that I’ve regretted nearly every single post to which I’ve ever signed my name (some more than others).

    Since I’m determined to maintain the moral high ground and never post anonymously, the end result is that I hardly ever post.

    Pseudonyms are a viable alternative, but they’re still anonymous. The only difference between the two is that readers can differentiate between different anonymous posters much more easily if they use a pseudonym.

    Maybe the masked chickens of the darkness have some insight to share?

    Not likely, but thanks for letting us cluck from the shadows all the same.

    Gus

  20. Scott Says:

    Luca: Thanks for the link. I agree that ethnic and regional jokes always walk a fine line. For example, I laughed at the one about the Jew who, when he and two friends are asked to throw $100 each into a casket in accordance with the dead man’s last wishes, throws in a $300 check and takes $200 as change. But my reaction to the same joke might change depending on the perceived intentions of the teller.

    Like many commenters on Adams’s post, I’ve never associated the “hee-haw” stereotype with Appalachians in particular. But even if we consider the set of all Americans who do fit the stereotype, jokes at their expense might still be unjustified — since presumably, not all of them vote Republican.

  21. Paul Kwiat Says:

    Hi,

    I’m not normally a Blogger (I also don’t have a cell phone, if you can believe that).
    However, given the plethora of commentary on our article (and on articles *about* our article), I thought a few words might be useful. I’ll try to keep it short…[and fail L ]

    1. There has been quite a bit of confusion over what we’ve actually done (due in large part to reporters that won’t let us read their copy before it goes to print), not to mention *how* we did it. For the record—

    a. we experimentally implemented a proposal made several years ago, showing how one could sometimes get information about the answer to a quantum computation without the computer running. Specifically, we set up an optical implementation of Grover’s search algorithm, and showed how, ~25% of the time, we could *exclude* one of the answers.
    Some further remarks:
    - our implementation of the article is not “scalable”, which means that although we could pretty easily search a database with 5 or 6 elements, one with 100 elements would be unmanageable.
    - however, the techniques we discuss could equally well be applied to approaches that *are* scalable.

    b. by using the Q. Zeno effect, you can push the success probability to 100%, i.e., you can exclude one of the elements as the answer. However, if the element you are trying to exclude actually *is* the answer, then the computer *does* run.
    -The Q. Zeno effect itself is quite interesting. If you want to know more about it, you can check out this tutorial:
    http://www.physics.uiuc.edu/People/Faculty/profiles/Kwiat/Interaction-Free-Measurements.htm
    There’s also a puppy-friendly explanation here:
    http://cosmicvariance.com/2006/02/27/quantum-interrogation/

    c. unless you get really lucky, and the actual answer is the last one (i.e., you’ve excluded all the others without the computer running, and so you know the right answer is the last element, without the computer running), the technique in b doesn’t really help too much, since if you happen to check if the answer wasn’t a particular database element, and it really was, then the computer does run.

    d. By putting the Zeno effect inside of another Zeno effect, you can work it so that even if you are looking to exclude a particular database element, and the answer *is* that element, then the computer doesn’t run (but you still get the answer). Therefore, you can now check each of the elements one by one, to find the answer without the computer running. This was the first main theoretical point of the paper. Contrary to some popular press descriptions, we did not implement this experimentally (nor do we intend to, as it’s likely to be inconveniently difficult).

    e. If you had to use the method of d. to check each database element one-by-one, then you’d lose the entire speedup advantage of a quantum computer. Therefore, we also proposed a scheme whereby the right answer can be determined “bit-by-bit” (i.e., what’s the value of the first bit, what’s the value of the second bit, etc.). This is obviously much faster, and recovers the quantum speedup advantage.

    f. Finally, we proposed a slightly modified scheme that also seems to have some resilience to errors.

    Taken in its present form, the methods are too cumbersome to be much good for quantum error correction. However, it is our hope this article will stimulate some very bright theorists to see if some of the underlying concepts can be used to improve current ideas about quantum error correction.

    2. There have been a number of questions and criticisms, either about the article, or the articles about the article. Here are my thoughts on that:
    a. I guess I should disagree that our article is poorly written (no big surprise there;-), though I agree 10000% that it is not at all easy to read. There are (at least) two reasons for this:
    – there is a tight length constraint for Nature, and so many more detailed explanations had to be severely shortened, put in the supplementary information, or left out entirely. Even so, the paper took over a year just to write, so that at least it was accurate, and contained all the essential information. For example, we were not allowed to include any kind of detailed explanation of how Grover’s algorithm works. [If you want more info on this, feel free to check out: P. G. Kwiat, J. R. Mitchell, P. D. D. Schwindt, and A. G. White, "Grover's search algorithm: An optical approach", J. Mod. Opt. 47, 257 (2000)., which is available here:
    http://www.physics.uiuc.edu/Research/QI/Photonics/publications.html
    - the concepts themselves are, in my opinion, not easy to explain. The basic scheme that we experimentally implemented is easy enough. And even the Zeno effect is not so bad (see that above tutorial). But once it becomes “chained”, the description just gets hard. (I am pointing this out, because I would reserve the criticism “poorly written” for something which *could* be easily [and correctly!] explained, but wasn’t.)

    b. I agree that some of the popular press descriptions left something to be desired, and often used very misleading wording (e.g., quantum computer answers question before it’s asked – nonsense!). Having said this, I do have rather great empathy for the writers – the phenomenon is not trivial for people in the field to understand; how should the writers (who *aren’t* in the field) explain it to readers who also aren’t in the field. Overall, the coverage was not too far off the mark.
    -To my mind, the most accurate description was in an article in Friday’s Chicago Tribune (the author kindly let us review his text for accuracy before going to print).

    Okay, thanks for your attention if you made it this far.
    I hope that these words (and the above web link) will clarify some of the issues in the paper.
    Best wishes,
    Paul Kwiat
    PS Please feel free to post this response (in it’s entirely though) on any other relevant Blogs. Thanks.

  22. Scott Says:

    Paul: Thanks so much for those clarifying remarks! I’m sure my readers will appreciate them too.

    One of the dangers of blogging, I’ve found, is that you risk doing “collateral damage” to people you didn’t intend to criticize at all.

    Even as I read that confused press release, it seemed clear that what had prompted it was a perfectly good piece of experimental work.

    My beef is that, in order to appreciate the experimental result, one first has to get clear on what it could even mean to “get an answer without the computer having been turned on”! Indeed, if I were writing a popular article about your result, I would devote most of it to precisely that conceptual point.

    Best,
    Scott

  23. sigfpe Says:

    There were some other claims in the news articles that seem bogus to me and which I strongly suspect weren’t made up by the journalists. For example, in one it was suggested that “not running” the quantum computer might eliminate decoherence and hence make quantum computers more reliable. I’m not an expert in this field but it seems pretty obvious to me that counterfactual computation makes things worse not better. After all, in order to get useful answers you have to ensure that the “running computer” doesn’t couple to any external state as doing so would eliminate any possibility of it cancelling out at the end.

  24. Anonymous Says:

    Being quantum, everybody hears something different. They should read http://emusician.com/mag/emusic_qualms/index.html

  25. ryran Says:

    Fascinating discourse, people. Special thanks to Paul Kwiat for making a guest appearance! I wonder if /. will hit this with a slashback someday…

  26. tyler Says:

    As a nonscientist interested in almost everything that’s…er…science-y, I’d like to address one particular point raised in this discussion. I read a lot of “popular science” aka science writing for people without science degrees. And over the last few years I have come to the conclusion that this material is only worthwhile when written by working scientists involved in the field in question.

    Journalists working in science try really hard, but there’s a double translation happening: from the scientists and their research paper (or whatever) into the less-technical framework of the journalist’s understanding, and then again through that person’s writing skills into their final book or article. It’s not that they *always* cloud the issue – but when they succeed it’s usually because the subject is rather trivial.

    Thus, my hypothesis: any science subject interesting enough to be worth learning about can only be described accurately by working scientists. Now, of course, many scientists are terrible writers outside of their specialized technical jargon, but some are quite good (or their editors are – which is fine) and great science writing is produced exclusively by such people.

    One brief example is the cosmological concept of inflation. I had understood it in a knuckleheaded way for years – just that it probably happened and it solved a lot of problems – but I never got why or how until I read Alan Guth’s book. Of course his original ideas have been superceded, but his book gave me the basis of understanding I needed to proceed.

    At this point, I actually learn more from reading a book or paper that is 90% over my head than I do from anything written by nonscientists. I may learn something, or I may learn nothing, but I’m unlikely to learn something that simply isn’t true – or, if I do, it’s because of my error in misunderstanding, not some other non-expert’s.

  27. Anonymous Says:

    I’ve got algorithms. I’ve got music. I’ve got my gal. Could I ask for anything more? Could I ask for anything more?