viii Foreword

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 [3] is a diﬃcult problem which is safe to skip.

Further reading

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 [51], 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 [30]. Most original papers on

the subject can be found in the electronic archive at http://arXiv.org,

section “Quantum Physics” (quant-ph).

Acknowledgements

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