CS 259Q — Quantum Computing — Fall 2012

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

what's new

12/02 Correction to problem set 5
11/30 Problem set 5
There will be no class on November 13 and 15
11/11 A draft of the notes for lecture 13
11/10 Problem set 4
11/08 Solutions to problem sets 1, 2, and 3
11/06 In the midterm, work with m greater than or equal to 3 in Problem 3
11/06 Correction in notes for lecture 7
10/30 The midterm is due on November 8
10/29 Notes for lecture 9 and lecture 10
10/23 Another revision of Problem set 3
10/22 Notes for lecture 8
10/22 Corrections to Problem set 3
10/19 We have a Piazza discussion forum
10/19 Problem set 3 is due October 25
10/17 Notes for lecture 7
10/17 Notes for lecture 6
10/11 Problem Set 2 is due October 18
10/04 Problem Set 1 is due October 11.
10/01 Notes for lecture 2
09/24 page created

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:

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 textbook is

Michael Nielsen and Isaac Chuang. Quantum Computation and Quantum Information, Cambridge.

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.

09/25 Introductions, basics of the quantum model.
Nielsen-Chuang sections 1.1, 1.2
[Notes]
09/27 Measurements, entanglement, quantum teleportation.
Nielsen-Chuang sections 1.3, 2.1, 2.2
[Notes]
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
[notes]
10/16 The quantum Hadamard transform and Simon's algorithm
[notes]
10/18 The period-finding algorithm
[notes]
10/23 Factoring reduces to period-finding
[notes]
10/25 The discrete-log algorithm
[notes]
10/30 Grover's algorithm
11/01 Search lower bound
11/06 Search lower bound ctd
[notes]
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, density matrices
11/29 operator sum representation, quantum error-correcting code correcting arbitrary one-qubit errors.

Plan for future lectures:

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

homeworks

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

Problem Set 1 is due October 11. (Solutions)
Problem Set 2 is due October 18. (Solutions)
Problem Set 3 is due October 25. (Solutions)
Problem Set 4 is due November 16
Problem Set 5 is due December 6

exams

The midterm is due November 8.

The final will be a study project. Here is a list of possible projects