Chapter 8: Quantum Computation

A mathematical model of present computers (classical computers) was invented by Alan Turing in 1930s, and it is called the Turing Machine. The procedure to solve problems on a classical computer is given as “instructions” on the Turing machine. The combination of these instructions is called “algorithm”. Examples of the simplest algorithms are the arithmetic operations such as addition and subtraction. Among these algorithms, the multiplication is relatively fast, while those for division and chess game are rather slow. A typical one among slow algorithms is the factorization. It is an important subject for the model of computers to invent an effective algorithm for a certain problem. The effective algorithms mean that the instructions are finished in polynomial time. When one tries to solve the problem of factorization on a classical computer, the computational time increases exponentially, and it becomes practically impossible to solve the problem with a large number of digits. There is a problem called RSA139 in which the number to be solved has 139digits. It took ten years to solve this RSA139 problem. The public key cryptography, one of the most advanced system of cryptography today, is based upon the difficulty of factorization…