Research Director: Hiroshi Imai
(Professor, Graduate School of Information Science and Technology, The University of Tokyo)
Research Term: 2000-2005

Along with the very rapid development of computer technology – memory capabilities and central processing speeds – there are also significant advances taking places in the algorithm design and information theory being used. These new approaches are adopting advanced theory from fields like physics from a computational point of view. Efforts are not only producing a more sophisticated discipline, but are giving more meaning to the term “computer science.”

The basis of the current computer is the combination of 1s and 0s: “0″ is represented as 0; “1″ as 1; “2″ as 10; “3″ as 11; etc. All numbers as well as all letters are represented as 0s and 1s, and, significantly, all computations are made based on information stored as the 0′s and 1′s.

However, this situation started to change after a breakthrough in 1994, made by computer scientist Peter Shor of AT&T Bell Laboratories. He showed that factoring integers can be performed efficiently by a “quantum computer,” which presently refers to a mathematical algorithm, not an existing physical machine. This algorithm will run on a forthcoming quantum machine based on quantum mechanics, while making certain types of calculations much faster by fully using quantum mechanics algorithmically. One of the important aspects of factoring integers is the basis for current Information Technology, as when important information or money is transmitted over the Internet. Today’s encryption is based on very large integers that are extremely difficult to factor.

The quantum computer algorithm is based on entities that are vague, like the spin of an electron. If the spin is upwards, it is 1; if downward it is 0. But, spin can exist in three dimensional space and can have ‘complex’ values between 0 and 1 in a quantum setting. By superimposing this situation it becomes possible to factor integers very efficiently. When using 20 bits, 220 is about one million, and only 20 bits can be used to represent a number from 0 to 1 million. In the quantum setting 20 quantum bits can be superimposed in a clever manner to represent useful information on such one million numbers. This may be physically done by using 20 electron spins; this method is extraordinarily compact. By using just 30 electron spins it is possible to handle problems with a size of 109 and so on. The quantum algorithm performs unitary operations on these representations, which may be regarded as ideal parallel processing for all states, to derive final significant results very rapidly.

One important point regarding this evolution of new approaches to computer computations is that it might allow the computer industry to overcome restrictions on computational speed. Though this has been doubling every 1.5 years, the situation is rapidly reaching a physical limit: elements on a chip can no longer be squeezed closer together. Quantum computing could provide a breakthrough to this barrier by using physical laws in completely new ways.

Other interesting concepts of physics are also entering computer science for advanced communication. For example, quantum mechanics allows systems such as two entangled electrons. Amazingly, even after they are far apart, if an experiment is done to identify the state of one electron, the state of the other is immediately known. Using this concept it is possible to make yet another type of cryptographic system, called quantum cryptography. This new system should make it possible to send test strings of information to see whether someone is trying to intercept the message; if this is so, the encryption method can be quickly changed.

Research Results

The Imai Quantum Computation and Information project aims to develop new quantum computing paradigms by investigating and unifying advanced methodologies in quantum computation and quantum information to overcome the current barriers of quantum computing methods. Both experimental and theoretical research on quantum cryptography are being performed. While carrying out the agenda, efforts are also being made to reinforce the word “science” in computer science. Research efforts are divided into the following three areas:

One major research area is to design new quantum algorithms for computations. Although a few powerful quantum algorithms already exist, their number is few. Thus, without new exploration in the theory of quantum algorithms, even if a ‘physical quantum computer’ is near, it may become nothing but a special-purpose computer for integer factoring. These efforts are being made while searching for second-generation Information Technologies.

Another area is quantum complexity, which is theoretically oriented, and exploring the basic mathematical concepts involved in the concepts of computational complexity, such as circuit complexity, of mathematical algorithms and their abilities to solve problems. A quantum computer simulation is also being developed to support physical experiments and to analyze the detailed behavior of quantum algorithms.

Quantum communication is also being explored using both theory and experiments. Experiments are being made in such fields as quantum optics. A prototype of a photon-based cryptosystem is being developed.