Cheap quantum cryptography

Quantum information theory is a fascinating subject. By applying the simple computational rules of quantum mechanics it is often possible to process information much better than with just classical devices. A famous example being Shor's algorithm for the factorisation of integers relevant for breaking many popular public key encryption schemes such as RSA. The speed up is not exponential but "only" by a square root but this can already be substantial. Formal computer scientists amuse themselves by investigating how the many complexity classes change if you have access to some quantum computations, the Complexity Zoo gives a nice overview.

A beatiful introduction into the subject are the lecture notes by John Preskill. A more formal aspect (investigating which quantum machines can be constructed, how does the impossible quantum copier differ from possible devices and that in the language of operator algebras) is treated in the notes by Reinhard Werner.

However, all this, much like string theory, is only theory and does not have real world applications. As far as real experiments go, IBM has been able to factor 15 with a quantum computer in 2001.

Another potentially applicabel area of application is cryptography: It is possible to construct quantum channels that are immune to eavesdropping: If somebody in the middle listens in the information does not reach the intended recipient anymore. This has been demonstrated in a real experiment by Anton Zeilinger: He managed to transmit the keys of a classical encryption scheme via entangled photons (with a bitrate of 400-800bit/s and 3% error).

This still involves a considerable experimental set-up and remember: You only transmit the keys, as the quantum channel is my far too slow to transmit real data (you probably read much faster than 400bit/s). But there are cheap alternatives (not in the theoretical but in the practical sense) which are as well impossible to crack: One-time pads. Assume I have 1GB of data which I want to transmit to you securely. All I need are 1GB of random numbers which I share with you beforehand and then I xor the data with the random numbers transmit the result (which is just noise for anybody in between) and xor the encrypted message to recover the original data.

This is not elegant as we have to share the random numbers beforehand, we have to share as many bits as we want to transmit. But for many practical applications this is easily possible (headquater of some company who want to transmit construction plans to factory, a spy who wants to phone home, you name it): Cheap small harddrives have more room than all the information you would like to transmit secretly in all you life. When you construct the factory you just bring there the harddrive in a sealed box and practially all future communication is secure, the spy carries a sealed usb-stick and has more shared randomness than all the secret pictures he is goint to take and all the reports he has to send. This is not elegant but dead cheap and efficient.

And if you like you can even produce the randomness using quantum physics to make it physically safe: For example you could sample the timing of the ticks of a Geiger counter and have pure quantum randomness.

Here is a small homework: Take t1, t2,...,tN to be the times of N clicks. By themselves, they are not pure random numbers but the time difference follows a Poisson distribution. Assume that the ti are specified with B bits each, so the possible time resolution is dt and the decay constant of the probe is lambda. How many bits of pure randomness can you extract and how do you do it?