Quantum computations: algorithms and error correction

The first part of the article ( 1- 6) is devoted mainly to one goal, namely, to showing the computational capacity of a quantum computer using the problem of a stabilizer in the group Z(k) as an example. The discrete logarithm and decomposition into prime factors can be reduced to this problem. The formal definition of a quantum computer (more precisely, a quantum scheme) appears in 4. All necessary information from computing theory and quantum mechanics is contained in 2 and 3. The reading of the second part can begin with the theory of one-to-one quantum codes ( 8.1, 8.2 and 9). This theory is sufficiently complete, simple and self-contained. However, in the present paper it is considered as a means of solving the perturbation problem, that is, constructing a quantum computer from unreliable (inaccurate, being subject to perturbations) elements. To this topic we devote 7, 8.3, 10 and 11. Interesting results are obtained in 10.1 and 11. The rest is a rather tedious technical preparation. (So far the problem in hand has been considered only at the physical level of rigour. The formal approach revealed one subtle point where a naive argument may lead to an error, see 10.1.) The initial formulation of the problem is not rigorous and rests on an intuitive picture of the way a real-world computational device might work. This is formalized in 7, but the final formulation of the problem (the so-called polynomial error correction system, see Definition 10.4) appears only in the middle of 10.1.