Naturally enough, one could believe that a task requiring exponential amount of computational steps in a classical computer could be solved in polynomial time using a quantum computer. The power of a quantum computer would lie in the possibility to follow many computational paths simultaneously as a nondeterministic automaton does. However, according to quantum mechanics, we can observe only one of the outcomes, probabilistically chosen by the measurement procedure. Mathematically the most interesting question in quantum computation may be that how much information about those exponentially many computational paths one can recover in or after an observation, using a procedure smart enough.
The earliest formalism of quantum computation (exploiting the full power of quantum computers) was introduced by Deutsch [2] in 1985, when he defined a quantum physical analogue of a probabilistic Turing machine, but the first surprising powerful result came almost ten years later. In 1994 Peter W. Shor demonstrated how the quantum computation can be used for factoring integers into prime factors probabilistically in polynomial time [3]. This invention is naturally interesting theoretically, but also practically if a quantum computer could be really constructed, since the securities of the RSA cryptosystem and many protocols is based on the assumed non-tractability of the factoring problem. However, presently it is unknown whether a large-scale quantum computer can be built.
The research on quantum computation naturally can be divided into physical
and mathematical part, although the border between these parts is not clear
and stable. The physical research concentrates more on the possibility
of the implementation of quantum computers and quantum cryptography, while
the mathematical part will be interested in the classification of quantum
complexity classes and the relations between classical ones. For instance,
from Shor's result we know that factoring problem that is in FNP but is
not known nor believed to be in FP, belongs to quantum class QFZPP. Moreover,
it turns out that the family of languages accepted by quantum Turing machines
equals to the family of recursively enumerable languages (showing that
RE is included in QRE uses Bennet's result in paper [4]) and that the classical
deterministic complexity classes are included in the corresponding quantum
ones, but the interesting question if the inclusions are strict, is presently
obscure. This question is studied in papers [5]-[8]. Clicking here
you find an online database including numbers of articles on quantum computation.
You can also find
information on NMR-quantum computation and related links here..
References