Towards the Physical Realization of Quantum Computers

1. Overview
In 1985, David Deutsch introduced quantum Turing machines (QTMs for short) as Turing machines which can perform so called quantum parallel computations. Then, in 1994, Peter Shor showed that QTM can factor integers with arbitrary small error probability in polynomial time. Since it is widely believed that any deterministic Turing machines cannot factor integers in polynomial time, it is very likely that QTM is an essentially new model of computation.

2. NMR Quantum Computation
Until now, many researchers have been studying how to physically　implement quantum computers based on QTM. Among others, NMR (Nuclear Magnetic Resonance) offers an appealing prospect for implementation of quantum computers because of a number of reasons. But, quantum computation performed on NMR is slightly different from those performed on QTMs. So, we first developed a theory of bulk quantum computation including NMR quantum computation. For this purpose, we introduced bulk quantum Turing machine (BQTM for short) as a model of bulk quantum computation.

3. Quantum Neural Networks
Recently, in the field of theory of quantum computation, various kinds of quantum neural networks are proposed. But, it seemed that most of them are not reasonable models of quantum computations. Thus, we also proposed a quantum threshold gate as a basic component of our quantum neural network model. Then, we showed that the circuits which consist of these quantum threshold gates can be simulated by ordinary QTMs. Therefore, we can conclude that our quantum neural network model is a reasonable model of quantum computation. Then, we showed that the EXOR function can be learned by a one layer quantum perceptron by using BQTM. It is well known that the EXOR function cannot be learned by a one layer ordinary perceptron. Furthermore, we obtained some other results on the general computational capabilities of our quantum neural networks.