AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution

Classical and Quantum Computation

About this Title

A. Yu. Kitaev, California Institute of Technology, Pasadena, CA, A. H. Shen, Independent University of Moscow, Moscow, Russia and M. N. Vyalyi, Independent University of Moscow, Moscow, Russia

Publication: Graduate Studies in Mathematics
Publication Year: 2002; Volume 47
ISBNs: 978-0-8218-3229-5 (print); 978-1-4704-1800-7 (online)
DOI: https://doi.org/10.1090/gsm/047
MathSciNet review: MR1907291
MSC: Primary 81-02; Secondary 68-02, 68Q05, 68Q15, 81P68

View full volume as PDF

Read more about this volume

Table of Contents

Download chapters as PDF

Front/Back Matter

• View this volume's front and back matter

Chapters

• Introduction

Classical computation

• 1. Turing machines
• 2. Boolean circuits
• 3. The class NP: Reducibility and completeness
• 4. Probabilistic algorithms and the class BPP
• 5. The hierarchy of complexity classes

Quantum computation

• 6. Definitions and notation
• 7. Correspondence between classical and quantum computation
• 8. Bases for quantum circuits
• 9. Definition of quantum computation. Examples.
• 10. Quantum probability
• 11. Physically realizable transformations of density matrices
• 12. Measuring operators
• 13. Quantum algorithms for Abelian groups
• 14. The quantum analogue of NP: the class BQNP
• 15. Classical and quantum codes

Part 3. Solutions

• S1. Problems of Section 1
• S2. Problems of Section 2
• S3. Problems of Section 3
• S5. Problems of Section 5
• S6. Problems of Section 6
• S7. Problems of Section 7
• S8. Problems of Section 8
• S9. Problems of Section 9
• S10. Problems of Section 10
• S11. Problems of Section 11
• S12. Problems of Section 12
• S13. Problems of Section 13
• S15. Problems of Section 15
• Appendix A. Elementary Number Theory