Course on Quantum Computation, Spring 2003, Courant Institute of Mathematical Sciences
This course provides an introduction to quantum computation. Topics include universal quantum computation, the Solovay-Kitaev theorem, quantum algorithms (Shor’s algorithm, Grover’s algorithm), quantum complexity theory, quantum cryptography, quantum error correction and quantum adiabatic algorithms.
Reading:
We will use some material/exercises from the following book that I recommend buying:
- Quantum Computation and Quantum Information Theory by M.A. Nielsen and I.L. Chuang (NC), Cambridge University Press (675 pages), available as paperback at amazon.com.
Other literature that may be of use:
- Classical and Quantum Computation by A. Yu. Kitaev, A. Shen and M.N. Vyalyi (KSV), AMS monograph (272 pages), available at amazon.com.
- Preskill's lecture notes available at http://www.theory.caltech.edu/people/preskill/ph229
- Many research papers are available in preprint form at http://lanl.arxiv.org/archive/quant-ph/
Overview of Course:
- Lecture 1: History. Quantum mechanics: states, density matrices, operations. Entanglement and Bell's inequalities. NC Reading 1.1-1.3.2.1-2.6. Problem Set
- Lecture 2: Universal Quantum Computation I. Classical and Quantum circuits. Universal Gates. NC Reading 4.1-4.5. Problem Set
- Lecture 3: Universal Quantum Computation II. Solovay-Kitaev Theorem. NC Reading Appendix 3. Problem Set
- Lecture 4: Complexity classes, P, BPP, NP and BQP, BQNP. Some known problems. NC Reading 3.1, 3.2.Problem Set
- Lecture 5: Quantum Algorithms I. Deutsch-Jozsa algorithm. Grover's search algorithm. Optimality proof. NC Reading 1.4, 6.1, 6.6.Problem Set
- Lecture 6: Quantum Algorithms II. Quantum Fourier Transform. Phase estimation. Shor's algorithm. NC Reading Chapter 5.Problem Set
- Lecture 7: The Number Theory in the Shor's Factoring Algorithm. NC Reading Appendix 4.
- Lecture 8: Quantum Error Correction I. NC Reading 8.1, 8.2, 8.3, 10.1, 10.2 Problem Set
- Lecture 9: Quantum Error Correction II. NC Reading 10.3, 10.4, 10.5, 10.6 Problem Set
- Lecture 10: The idea of fault-tolerance. Quantum Key Distribution I. NC Reading 12.6Problem Set
- Lecture 11: Quantum Key Distribution II. NC Reading 12.6 Problem Set
- Lecture 12: Quantum Adiabatic Algorithms.Problem Set
- Lecture 13: Quantum Random Walks.
- Lecture 14: Discussion of some research problems.
Research Problems (will be updated during course)