# 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

### Table of Contents

**Download chapters as PDF**

**Front/Back Matter**

**Chapters**

- 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

- 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