Seiichiro Tani, Innovative Communication Laboratory
Quantum computers, which are expected to emerge in a few decades, are totally novel computing devices that make effective use of quantum-mechanical phenomena. It has been revealed by extensive studies that they will be able to solve quite a few problems significantly faster than conventional computers or their extensions. As probably the most famous example of such problems, the integer factorization problem has often been discussed in the literature and in meetings. It does not, however, seem desirable to most people to solve this problem fast, for factoring large integers fast would lead to the breaking of many cryptosystems that are being used on the Internet. This talk will briefly outline the theory and applications of quantum search to show that the potential advantages of quantum computing are not limited to integer factorization.