CS 259Q — Quantum Computing — Fall 2012
[lecture notes] [homeworks] [exams]
Trevisan, Gates 474, Tel. 650 723-8879, email trevisan at stanford dot edu
TA: Joongyeub Yeo, email yeo at stanford dot edu
Classes are Tue-Th, 2;15-3:30pm in 200-002
- Luca: Tuesdays, 4-5pm, or by appointment, Gates 474
- Joongyeub: Mondays3-4pm, Wednesdays 10-11am, Gates B26A (except on 9/26 in Gates B26B)
References: the main reference for the course will be
lecture notes. New
lecture notes will be distributed after each lecture. A recommended
About this course: if they can be built, quantum computers can factor large integers and solve the discrete log problem efficiently, thus breaking all currently deployed public-key cryptosystems, and they can solve unstructured search problems faster than classical computers, although there is some evidence that they cannot solve NP-complete problems in polynomial time. The main engineering problem in building quantum computers is scaling up the current prototype that are able to handle only a constant number of qbits up to architectures with several thousands, possibly billions, qbits. An important theoretical result is that once we have basic components that have a certain level of fault-tolerance, then they can be scaled up to a self-correcting architecture than can be arbitrarily large and still be fault-tolerant. Quantum information transmission enables applications that are classically impossible, including certain unconditional cryptographic security guarantees, and the theory of quantum information transmission differs in subtle ways from classical information theory.
- Michael Nielsen and Isaac Chuang. Quantum Computation and Quantum Information, Cambridge.
Syllabus: In this course we will study the mathematical model of quantum computers, review the two main algorithms (factoring/ discrete log and search), the evidence against polynomial time algorithms for NP-complete problems, and the construction of fault-tolerant large-scale quantum computers from faulty components. In the last part of the course we will see the basics of quantum information theory.
Prerequisites: the basics of linear algebra (vectors, matrices, eigenvalues, eigenvectors, determinant) and discrete probability (Bayes rule, the notion of independence, random variables) and the ability to reason about the correctness and the running time of an algorithm (say, having seen that mergesort runs in time O(n log n) and that binary search runs in time O(log n)).
Some notes on probability and on algebra that I have written for a cryptography class might be useful as a refresher.
Plan for future lectures:
- 09/25 Introductions, basics of the quantum model.
Nielsen-Chuang sections 1.1, 1.2
- 09/27 Measurements, entanglement, quantum teleportation.
Nielsen-Chuang sections 1.3, 2.1, 2.2
- 10/02 More on quantum teleportation. Review of Turing machines
and boolean circuits
Nielsen-Chuang chapter 3
- 10/04 Quantum circuits
Nielsen-Chuang chapter 4
- 10/09 More on quantum circuits
Nielsen-Chuang chapter 4
- 10/11 The quantum Fourier transform
Nielsen-Chuang sections 5.1, 5.2
- 10/16 The quantum Hadamard transform and Simon's algorithm
- 10/18 The period-finding algorithm
- 10/23 Factoring reduces to period-finding
- 10/25 The discrete-log algorithm
- 10/30 Grover's algorithm
- 11/01 Search lower bound
- 11/06 Search lower bound ctd
- 11/08 Introduction to quantum information: Bell inequalities, superdense coding
No class on 11/13 and on 11/15
- 11/27 Quantum error-correcting code correcting one bit flip,
- 11/29 operator sum representation, quantum error-correcting
code correcting arbitrary one-qubit errors.
- 12/04 more on quantum error-correcting codes
- 12/06 Fault tolerance
- Make up lectures (will be posted as videos): quantum coin flipping and quantum key agreement
Late policy: homeworks emailed by end of day on Friday will
receive 10 points off their score; homeworks emailed or handed in
by 2:15pm of the Tuesday after they are due will receive 20 points
off their score. No homework is accepted after beginning of class
of the Tuesday after they are due.
- Problem Set 1 is due October 11.
- Problem Set 2 is due October 18.
- Problem Set 3 is due October 25.
- Problem Set 4 is due November 16
- Problem Set 5 is due December 6
The midterm is due November 8.
The final will be a study project. Here is a list of possible projects