Foreword

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

mathematical character.

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 [37], 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

vii