Okay, well apparently the paper arXiv:0804.3076 which I mentioned in the last post is being picked up by other bloggers (see here and here as well as here) as a legitimate criticism of quantum computing. So before anymore jump on this bad wagon let me explain exactly what is wrong with this paper.

THE PAPER DOESN’T USE FAULT TOLERANT CIRCUITS.

Hm, did you get that? Yeah a paper which claims that

We will show, however, that if even a small amount of imprecision is present in every gate, then all qubits in every code block will be affected, and more importantly the error in any given qubit propagates to all other qubits.

does this by working with error correcting code circuits which are not fault-tolerant. This sort of paper would have been fine, in oh, say, 1995, when quantum error correction was just being invented, but completely and totally misses any further development which was pretty much squarely aimed at this problem. Doh. Great big doh.

For those of you who don’t know what I’m talking about, let me explain. Quantum error correction is a procedure for protecting information encoded across multiple subsystems from independent errors on this subsystem. Or at least, this is how it works in its most basic form. A good way to think about it is in a communication setting. If you want to send some quantum information from Seattle to New York, but there is someone in the middle (evil flyover staters) who corrupts this information, then you won’t get good fidelity in transmitting your quantum information. But, if the corruption in this communication isn’t totally debilitating, one can use some tricks to use such a setup to send quantum information robustly. One does this by encoding the quantum information into a quantum error correcting code. Then you send each qubit of the code across the country, and after a decoding procedure the original quantum state can be reconstructed with higher fidelity (its less destroyed) by an appropriate error correction procedure. Indeed one can make the quantum information basically as protected as one wants using more and more qubits, in a scaling that is actually really good.

Now what does this have to do with quantum computing? Well in quantum computing we need to use quantum error correction to protect our quantum information from environmental disturbances, but we also need to make sure that all of our procedures themselves don’t introduce disturbance which will destroy the quantum information. In other words you need to develop protocols which are fault-tolerant for all the things you need to do quantum computation: state preparation, quantum gates, quantum error recovery routines, and measurement. And of course in doing this you need to worry about all of the components you use in these protocols failing. Like for instance your gates in your error recovery routine. Doing this was the work of a lot of bright people, who came up with a series of fault-tolerant protocols which ensure that quantum computing can be done, even when there are errors not just induced by an environment but also when there are errors in all the things you use to construct your quantum computer. If these error rates are small enough, then using these protocols allows one to perform quantum computation to a desired accuracy with an overhead which is polylogarithmic in one over the error in the computation. This result is known as the threshold theorem for quantum computation and is one of the biggest results in quantum computing.

So what the above paper does is ignore absolutely everything about fault-tolerant quantum computation (note the only references after 1996 are for papers for efficiently simulating small classes of quantum computations.) Indeed they basically rediscover *why* all that hard work was done in the first place. I suppose this could be forgiven, except for the fact that the basic ideas of fault-tolerant quantum computation are well known enough and important enough to appear in the standard text on the subject “Quantum Computation and Quantum Information” by Nielsen and Chuang.

On the other hand the fact that more and more cryptographers latch on to every single paper that claims that quantum computers are bunk makes me think we’ve finally gotten their attention. Now if only we could teach them some quantum information science…