# Paul Kwiat on quantum computation

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.

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 ]

- 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—

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

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

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

- There have been a number of questions criticisms, either about the article, or the articles about the article. Here are my thoughts on that:

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

- 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 KwiatPS Please feel free to post this response (in it’s entirely though) on any other relevant Blogs. Thanks.

Pingback: Quantum interrogation | Cosmic Variance

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

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

Pingback: Foundational Questioners Announced | Cosmic Variance