Steven G. Krantz
David Saltman (Chair)
A. Kitaev, A. Xen, M. Vlyi
KLASSIQESKIE I KVANTOVYE VYQISLENI
MCNMO–QeRo, Moskva, 1999
Translated from the Russian by Lester J. Senechal
2000 Mathematics Subject Classification. Primary 81–02, 68–02;
Secondary 68Qxx, 81P68.
Abstract. The book is an introduction to a new rapidly developing topic: theory of quantum
computing. The authors begin with a brief description of complexity theory for classical compu-
tations. Then they give a detailed presentation of the basics of quantum computing, including all
known eﬃcient quantum algorithms.
The book can be used by graduate and advanced undergraduate students and by researchers
working in mathematics, quantum physics, and communication.
For additional information and updates on this book, visit
Library of Congress Cataloging-in-Publication Data
Kitaev, A. Yu. (Alexei Yu.), 1963–
Classical and quantum computation / A. Yu. Kitaev, A. H. Shen, M. N. Vyalyi ; [translated
from the Russian by Lester J. Senechal].
p. cm. — (Graduate studies in mathematics, ISSN 1065-7339 ; v. 47)
Includes bibliographical references and index.
ISBN 0-8218-2161-X (acid-free paper) ISBN 0-8218-3229-8 (softcover)
1. Machine theory. 2. Computational complexity. 3. Quantum computers. I. Shen, A.
(Alexander), 1958– II. Vyalyi, M. N. (Mikhail N.), 1961– III. Title. IV. Series.
Copying and reprinting. Individual readers of this publication, and nonprofit libraries
acting for them, are permitted to make fair use of the material, such as to copy a chapter for use
in teaching or research. Permission is granted to quote brief passages from this publication in
reviews, provided the customary acknowledgment of the source is given.
Republication, systematic copying, or multiple reproduction of any material in this publication
is permitted only under license from the American Mathematical Society. Requests for such
permission should be addressed to the Acquisitions Department, American Mathematical Society,
201 Charles Street, Providence, Rhode Island 02904-2294 USA. Requests can also be made by
e-mail to firstname.lastname@example.org.
c 2002 by the American Mathematical Society. All rights reserved.
The American Mathematical Society retains all rights
except those granted to the United States Government.
Printed in the United States of America.
∞ The paper used in this book is acid-free and falls within the guidelines
established to ensure permanence and durability.
Visit the AMS home page at http://www.ams.org/
10 9 8 7 6 5 4 3 2 18 17 16 15 14 13