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.
Follow
Comment #1 February 28th, 2006 at 3:14 am
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.
Comment #2 February 28th, 2006 at 7:05 am
“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.
Comment #3 February 28th, 2006 at 8:16 am
horrible snotty cough + laughter from the end of that post = bad idea.
Comment #4 February 28th, 2006 at 8:26 am
Yuck!
Comment #5 February 28th, 2006 at 10:39 am
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.
Comment #6 February 28th, 2006 at 11:12 am
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.
Comment #7 February 28th, 2006 at 1:12 pm
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.
Comment #8 February 28th, 2006 at 1:21 pm
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.
Comment #9 February 28th, 2006 at 2:02 pm
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.
Comment #10 February 28th, 2006 at 3:58 pm
“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.
Comment #11 February 28th, 2006 at 4:26 pm
Are anonymous comments really worth it on blogs?
Comment #12 February 28th, 2006 at 4:29 pm
Try out cosmicvariance.com for a fun explanation of the phenomenon.
Comment #13 February 28th, 2006 at 4:51 pm
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?
Comment #14 February 28th, 2006 at 5:19 pm
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.
Comment #15 February 28th, 2006 at 7:17 pm
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.
Comment #16 February 28th, 2006 at 7:18 pm
Odd, I thought that last comment would show my name.
Jud
Comment #17 March 1st, 2006 at 12:30 am
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)
Comment #18 March 1st, 2006 at 2:34 am
On the matter of hillbilly jokes:
http://dilbertblog.typepad.com/the_dilbert_blog/2006/02/inebriated_hill.html
Comment #19 March 1st, 2006 at 4:49 am
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
Comment #20 March 1st, 2006 at 6:32 am
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.
Comment #21 March 1st, 2006 at 8:05 am
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.
Comment #22 March 1st, 2006 at 12:20 pm
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
Comment #23 March 1st, 2006 at 8:32 pm
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.
Comment #24 March 2nd, 2006 at 11:39 am
Being quantum, everybody hears something different. They should read http://emusician.com/mag/emusic_qualms/index.html
Comment #25 March 16th, 2006 at 9:26 am
Fascinating discourse, people. Special thanks to Paul Kwiat for making a guest appearance! I wonder if /. will hit this with a slashback someday…
Comment #26 March 16th, 2006 at 1:33 pm
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.
Comment #27 November 18th, 2006 at 2:59 am
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?