Quantum computing is to computation as quantum cryptography is to encryption: it tries to take advantage of quantum mechanical properties of the world to enable things that were not possible before. Here, the central idea is that of quantum parallelism, namely, the fact that ``entangled'' states can be thought of as probabilistic superpositions of classical states. An algorithm could carry out computations on all possible inputs at the same time. The idea and foundations for this hypothetical machines were laid out during the early nineties ([9], [3]), and P. Shor's 1994 paper [19] brought it to the spotlight with his quantum algorithm for factoring integer numbers in polynomial time. This work shocked the cryptography world as well, because today's better security protocols rely upon the difficulty of factoring large integers.
Quantum cryptography, quantum computation, quantum information are nowadays hot research areas, both in the theory, foundations and algorithms aspects as in actual devices to implement them. In this respect, quantum cryptography and transmission are far ahead: there have been already several demonstrations of quantum communications channels spanning distances of several kilometers ([18], [6]). Quantum computing lags behind, and only primitive demonstrations of one or two quantum bits have taken place [15]. It seems that quantum key distribution could be of practical use very soon, whereas the quantum computer is farther away in the future, if it ever becomes a reality.