Paul Kwiat on quantum computation

By Sean Carroll | February 28, 2006 8:59 pm

The quantum puppies post below was written in response to some excitement generated by recent work from Paul Kwiat’s group at UIUC; specifically, this paper in Nature (which is sadly only available to subscribers). Paul was nice enough to write a little clarification about what they actually did, which we’re reproducing here as a guest post.


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 :-( ]

  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—

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

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

    3. 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 2. 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.
    4. 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).
    5. If you had to use the method of 4. 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.
    6. 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 criticisms, either about the article, or the articles about the article. Here are my thoughts on that:
    1. 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.

      – 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.)

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

CATEGORIZED UNDER: Guest Post, Science
  • Pingback: Quantum interrogation | Cosmic Variance()

  • Elliot

    Gee there seems to be a common theme over the last few days. This response and Joanne’s indicate that perhaps there is a substantial gap between what is happening in the laboratory and the results and what gets written about those activities.

  • Sean

    Well, it’s often true that the view you get from reading just the popular press is different in important ways from what might actually be happening. On the other hand, I think that we all very much appreciate the work that is done by good science journalists. It’s hard enough for experts to keep up with all of the exciting developments in their own fields; to understand developments in areas in which you are not an expert, and then explain them to a wide audience, is incredibly difficult. I hope that any journalists who might be reading take our commentary on their work as a contribution to a wider conversation, not just as sniping from the sidelines.

    One issue is what Paul alluded to above, the willingness of writers and editors to allow scientists to check what they are writing for factual mistakes. This kind of procedure is antithetical to the tenets of ordinary journalism, as it should be — you don’t want politicians to be reading over everything that is written about them before it gets published. But science is different, and should be treated that way. The subject of the article shouldn’t have veto power over the content or opinions expressed in a news piece, but it’s really helpful to let them check for simple mistakes. It’s important for journalists to be able to take into account the unique nature of science as a subject matter.

  • R.R.Tucci

    According to Sean, passive observation by a puppy affects the outcome of a food measurement. But what if we replace the puppy by a more mysterious character(Revered Bayes). Here is an artist’s rendition.

  • Eric

    I always request that I see the article. Often the science writer waffles, frequently citing some deadline as an excuse to avoid letting me see the article. While offer to help them create an accurate story, I understand deadlines. In those cases, I request that they at least verify all sentances which quote me. Usually, they will agree to that. However, many times the science writer has agreed to one of those terms, and yet they still proceed to go to print without checking anything with me. I am very annoyed by this practice. I keep a record of which science writers and publications have not kept their word, and consult it when deciding what to say to whom.

    That said, I have had positive interactions with several science writers. Several do have an impressive breadth of knowledge.

    Local press offices usually have the time to do a good job. I try to put in extra effort to get these as polished as possible, realizing that others will draw from the press release. Also, popular science publications (e.g., Sky & Telescope, New Scientist) often put in the effort to do a really good job, so I want to help them.

    Unfortunately, I have found that some well respected large mass media outlets frequently make simple factual mistakes. Obviously, that affects how much I trust them on non-science topics.

  • Pingback: e pur si muove » Blog Archive » Quantum computers: answers without running the program()

  • Elliot


    My point was not that the journalists were the problem. This is a complex issue. While we all like to believe that science journalism is about reporting the truth, the reality is that it is often about 1)simplifying the often complex and non-intutitive (for example QM) and driven by marketplace factors as well as accuracy. I think one common theme in this blog is that it is vitally important that the public at large be made aware of what is happening in various scientific venues and I would suggest that this is a very challenging objective with myriad hurdles in both the translation from the science to the popular medium and the interpretation by the public at large.

  • http://http::/ Daryl McCullough

    My quick Google search does not find the reference, but I remember hearing recently about a possible medical application of the quantum zeno effect. The rough idea was this: Taking x-rays to diagnose disease is a risky procedure, because x-rays themselves can cause cellular damage. Somehow, the quantum zeno effect can be used to reduce the exposure necessary to get an x-ray down to an arbitrarily small dosage.

    Does anybody remember an article about this? Or a URL?

  • todd.

    I’m not sure if this is the appropriate place to mention this, but I got “The system cannot find the file specified.” while trying to load the referenced paper on Grover’s algorithm ( ?).

  • Sean

    Todd, the paper should be available now.

  • Ambitwistor


    Maybe you’re thinking of Schroedinger’s Rabbits? I wouldn’t expect any practical medical applications anytime soon, though …

  • http://http::/ Daryl McCullough


    Yes, I think I was thinking of this reference (cited in “Schroedinger’s Rabbits?”)
    Kent, A., and D. Wallace. Quantum interrogation and the safer X-ray

  • Plato

    The Tao of Quantum Interrogation

    If, on the other hand, a single photon hits the element, well then by definition there is a loud explosion, and the detective knows that this was a good bomb. There seems to be no way to find the good bombs without always exploding them.

    This seems really confusing to me.

    In collision processes, “resulting evidence” is from the interactive process, while in consideration above? How would you know the particles inherent state, without making the interactive process, the result?

    You assume then, the energy needed, and from that, the emission spectrumally enhanced? You know this, before hand, as an entangled state?

    Layman scratching head.

  • PK

    Once, after explaining at length to a journalist a very nice paper on quantum holography, my quoted comment became: “it’s a cute idea. It follows the laws of physics.”

    However, I just talked to another journalist who put a lot of effort into understanding my work. So I am hopeful…

  • Plato

    Layman wondering.

    Would Ingoing/outgoing states on the horizon would be a wonderfull thing to be able to read?

    Maybe a way in which to use the olympics(onion view in calorimetric perspective)? Of course, I tend to think of entangled states but at such energies?

    Who has gotten the closest? Glast maybe? LHC?:)Maybe something happens with superfluid states that was unexpected?

    The very high radiation output also creates new experimental environments to help validate computer codes responsible for maintaining a reliable nuclear weapons stockpile safely and securely — the principal mission of the Z facility.

  • Pingback: Waleed Alrodhan - Information Security Blog ãÏæäÉ æáíÏ ÇáÑæÖÇä áÃãä ÇáãÚáæãÇÊ » Blog Archive » Future computers based on “Quantum Computing” will work even when they’re off!!()

  • Count Iblis

    The limits of counterfactual computation

    We show that the protocol recently proposed by Hosten et al. does not allow all possible results of a computation to be obtained counterfactually, as was claimed. It only gives a counterfactual outcome for one of the computer outputs. However, we confirm the observation that the protocol gives some protection against decoherence. In some situations, though, it may be more effective simply to run the computer several times.

  • Pingback: Foundational Questioners Announced | Cosmic Variance()


Discover's Newsletter

Sign up to get the latest science news delivered weekly right to your inbox!

Cosmic Variance

Random samplings from a universe of ideas.

About Sean Carroll

Sean Carroll is a Senior Research Associate in the Department of Physics at the California Institute of Technology. His research interests include theoretical aspects of cosmology, field theory, and gravitation. His most recent book is The Particle at the End of the Universe, about the Large Hadron Collider and the search for the Higgs boson. Here are some of his favorite blog posts, home page, and email: carroll [at] .


See More

Collapse bottom bar