few concepts from the theory of algorithms (some computer programming
experience may do as well as the formal knowledge). Some topics require
an acquaintance with Lie groups and homology of manifolds — but only at
the level of definitions.
To reduce the amount of information the reader needs to digest at the
first reading, part of the material is given in the form of problems and
solutions. Each problem is assigned a grade according to its diﬃculty: 1
for an exercise in use of definitions, 2 for a problem that requires some
work, 3 for a diﬃcult problem which requires a nontrivial idea. (Of course,
the diﬃculty of a problem is a subjective thing. Also, if several problems
are based on the same idea, only the first of them is marked as diﬃcult).
The grade appears in square brackets before the problem number. Some
problems are marked with an exclamation sign, which indicates that they
are almost as important as the main text. Thus, [1!] means an easy but
important exercise, whereas  is a diﬃcult problem which is safe to skip.
In this book we focus on algorithm complexity (in particular, for quan-
tum algorithms), while many related things are not covered. As a gen-
eral reference on quantum information theory we recommend the book by
Michael Nielsen and Isaac Chuang , which includes such topics as the
von Neumann entropy, quantum communication channels, quantum cryp-
tography, fault-tolerant computation, and various proposed schemes for the
realization of a quantum computer. Another book on quantum computation
and information was written by Josef Gruska . Most original papers on
the subject can be found in the electronic archive at http://arXiv.org,
section “Quantum Physics” (quant-ph).
A. K. thanks Michael Freedman and John Preskill for many inspiring
discussions on the topics included in this book. We are grateful to Andrew
Landahl for providing the solution to Problem 3.6 and pointing to some
inconsistencies in the original manuscript. Among other people who have
helped us to improve the book are David DiVincenzo and Barbara Terhal.
Thanks to the people at AMS, and especially to our patient editor Sergei
Gelfand and the copy-editor Natalya Pluzhnikov, for their help in bringing
this book into reality.
The book was written while A. K. was a member of Microsoft Research
and Caltech, and while A. S. and M. V. were members of Independent Mos-
cow University. The preparation of the original Russian version was started