In recent years interest in what is called “quantum computers” has grown
extraordinarily. The idea of using the possibilities of quantum mechanics in
organizing computation looks all the more attractive now that experimental
work has begun in this area.
However, the prospects for physical realization of quantum computers
are presently entirely unclear. Most likely this will be a matter of several
decades. The fundamental achievements in this area bear at present a purely
This book is intended for a first acquaintance with the mathematical
theory of quantum computation. For the convenience of the reader, we give
at the outset a brief introduction to the classical theory of computational
complexity. The second part includes the descriptions of basic effective
quantum algorithms and an introduction to quantum codes.
The book is based on material from the course “Classical and quan-
tum computations”, given by A. Shen (classical computations) and A. Kitaev
(quantum computations) at the Independent Moscow University in Spring of
1998. In preparing the book we also used materials from the course Physics
229 — Advanced Mathematical Methods of Physics (Quantum Computa-
tion) given by John Preskill and A. Kitaev at the California Institute of
Technology in 1998–99 (solutions to some problems included in the course
were proposed by Andrew Landahl). The original version of this book was
published in Russian , but the present edition extends it in many ways.
The prerequisites for reading this book are modest. In essence, it is
enough to know the basics of linear algebra (as studied in a standard uni-
versity course), elementary probability, basic notions of group theory, and a