CS 259Q — Quantum Computing — Fall 2012

[general info]  [lecture notes] [homeworks] [exams]

what's new

general information

Instructor: Luca 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

Office hours:

References: the main reference for the course will be lecture notes. New lecture notes will be distributed after each lecture. A recommended textbook is

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.

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)).

classes and lecture notes

Some notes on probability and on algebra that I have written for a cryptography class might be useful as a refresher.
  1. 09/25 Introductions, basics of the quantum model.
    Nielsen-Chuang sections 1.1, 1.2

  2. 09/27 Measurements, entanglement, quantum teleportation.
    Nielsen-Chuang sections 1.3, 2.1, 2.2

  3. 10/02 More on quantum teleportation. Review of Turing machines and boolean circuits
    Nielsen-Chuang chapter 3

  4. 10/04 Quantum circuits
    Nielsen-Chuang chapter 4

  5. 10/09 More on quantum circuits
    Nielsen-Chuang chapter 4

  6. 10/11 The quantum Fourier transform
    Nielsen-Chuang sections 5.1, 5.2

  7. 10/16 The quantum Hadamard transform and Simon's algorithm

  8. 10/18 The period-finding algorithm

  9. 10/23 Factoring reduces to period-finding

  10. 10/25 The discrete-log algorithm

  11. 10/30 Grover's algorithm

  12. 11/01 Search lower bound

  13. 11/06 Search lower bound ctd

  14. 11/08 Introduction to quantum information: Bell inequalities, superdense coding

    No class on 11/13 and on 11/15

  15. 11/27 Quantum error-correcting code correcting one bit flip, density matrices

  16. 11/29 operator sum representation, quantum error-correcting code correcting arbitrary one-qubit errors.
Plan for future lectures:


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.

Collaboration policy

  1. Problem Set 1 is due October 11. (Solutions)
  2. Problem Set 2 is due October 18. (Solutions)
  3. Problem Set 3 is due October 25. (Solutions)
  4. Problem Set 4 is due November 16
  5. 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