Quantum Computing. 18.435 / 2.111. Fall 2008

Prerequisites:

Understanding of linear algebra.

Book:

I recommend the book of Nielsen and Chuang, and will be using it to prepare some of my lectures with. There is also an excellent set of lecture notes from John Preskill's course online. David Mermin's book is fairly good for learning this material with a background of computer science, and the lecture notes that eventually became this book are online at this site.

You can see the webpages for the 2003, the 2006 and the 2007 versions of this class on the web.

Office hours:

I am adding extra office hours, since a number of people cannot make Tuesdays after class. I will try to make it here on Wednesday at 1:30; I don't guarantee to make it every week, but if I don't I will announce it in class and post it here.
My office hours are
Tuesday, 2:40 - 4:00,
Wednesday, 1:30 - 2:30,
Room 2-369
email: shor@math.mit.edu
Extra office hours for the last homework set:
Friday, Dec. 5, 11:00-12:00
Monday, Dec. 8, 1:30-3:00.

Tutorial/Recitation:

I will be holding one or more tutorials in the first few weeks to let the students who haven't seen quantum mechanics (or classical computer science) before catch up. The first one of these, covering quantum mechanics, will be on Friday, Sept. 12, from 2:00 to 3:00 in room 2-132. The next will be on Friday, Sept. 19, from 1:00 to 2:15 in my office (moved because of my daughter's birthday party. We will have a tutorial on Friday Sept. 26, in room 2-132, from 2:00 to 3:30.

Topics to be covered include:

Grading Information:

I will give one in-class exam, which will make up 35% of the grade. This will be on Thursday, Nov. 6.
Homework assignments will determine 65% of the grade.
There will be weekly homework, most of the problems will be fairly easy, although I plan to put one or two harder problems on each homework assignment. I find that doing examples really helps to see what is going on in quantum computation, so I'm not making you do all these matrix manipulations just to torment you.
This year, as in 2006, to make up for the lack of a final, the last two problem sets are going to be harder, will cover the entire term, and will count more than the rest of the assignments. These last two homework assignments will count roughly double the normal ones.

Homework Assignments

The first homework assignment is here. Due on Sept. 18th.
NOTE: I made a mistake in problem 4, where I wrote 2 instead of √2 for the state (1/√2) ( |01⟩ + |10⟩ ). This is now corrected.
Solutions are now posted. Some of them are quite sketchy, but you should be able to figure out all the details with a little work.

The second homework assignment is here. Due on Sept. 25th.
NOTE: Typos in problem 1 are now fixed, and the problem has been made clearer.
Solutions are now posted.

The third homework assignment is here. Due on Oct. 2.
NOTE: You may use controlled U±1/k gates as well in Problem NC 4.28.
Most of the solutions are now posted. More to come.

The fourth homework assignment is here. Due on Oct. 9.
The solutions are now posted.

The fifth homework assignment is here. Due on Oct. 16.
Solutions are now posted.

The sixth homework assignment is here. Due on Oct. 23.
Mistake: I wrote Simon where I meant Grover. Fixed now.

The seventh homework assignment is here. Due on Oct. 30.
Mistake: I wrote 1 where I meant 0 in problem 2.
Solutions are now posted.

The eighth homework assignment is here. Due on Nov. 25. Note that, as I promised at the beginning of the course, the last two homeworks will be somewhat longer and will count more.
Mistake: To get my hint to work in problem 9, you need to add more states to the set of states you are trying to distinguish between. See revised homework.
Exam solutions are here. I only have the first three solutions written up so far, but I figure I might as well post what I have to date.

The last homework, Homework 9, will be due Dec. 9. It is here. Sorry for the late posting.

Lectures

I will try to announce the sections of Nielsen and Chuang (NC) or Preskill that contain the material we're covering here. I'm not following the book exactly, so I will skip over some material from these chapters, and may include some extra material, but for those who want to look at the textbook before class, this will give an idea of what I'll be covering. I'm also posting a brief summary of the lectures. Since I know Nielsen and Chuang better, I'm giving the sections from NC (and leaving out Preskill's notes, which are excellent) unless NC doesn't cover it.
Thur., Sept. 4: Basics of quantum mechanics.
NC 2.1.3, 2.1.7, 2.2.1 through 2.2.5

Lectures

I will try to announce the sections of Nielsen and Chuang (NC) or Preskill that contain the material we're covering here. I'm not following the book exactly, so I will skip over some material from these chapters, and may include some extra material, but for those who want to look at the textbook before class, this will give an idea of what I'll be covering. I'm also posting a brief summary of the lectures. Since I know Nielsen and Chuang better, I'm giving the sections from NC (and leaving out Preskill's notes, which are excellent) unless NC doesn't cover it.
Thur., Sept. 4: Basics of quantum mechanics.
NC 2.1.3, 2.1.7, 2.2.1 through 2.2.5
Tues., Sept. 9: More basics, the EPR "paradox" and the Bell inequality
NC 2.6
Thur., Sept. 11: No-cloning theorem and teleportation.
Notes for lecture 3.
NC 1.3.5-1.3.7, 2.3
Tues., Sept. 16: A tiny bit of classical complexity theory, and classical circuits, gates, and reversible computation.
Notes for lecture 3.
some of NC 3.1, and some of NC 3.2, and 3.2.5.
Thurs., Sept. 18: Quantum circuits and gates.
Start of NC chapter 4.
Tues., Sept. 23: More on quantum circuits and gates, density matrices.
This and the previous lecture should cover 4.1 - 4.5.2. We are also doing 2.5 and 2.6, but this might spill over into the next class.
Thurs., Sept. 25: Finite sets of gates that are universal for quantum computing and the Solovay Kitaev theorem.
NC chapter 4.5.3 and 4.5.4, Appendix 3.
Tues., Sept. 30: Deutsch-Jozsa algorithm and Simon's algorithm
See Preskill's lecture notes> Section 6.3.
Thurs., Oct. 2: Start on factoring algorithm
NC 5.1, some of 5.3.2
Tues., Oct 7: Finish factoring algorithm.
NC 5.2, 5.3
Thurs., Oct 9: Phase estimation and other applications of periodicity. I should write up notes on the hidden shift, since that's not in the book. See this paper as well.
NC 5.2, 5.3.
Thurs., Oct 16: Grover's algorithm
NC 6.1
Tues, Oct. 21: Amplitude amplification originally presented in quant-ph/0005055 I should write up notes on this, too. and start of POVM's
Thurs, Oct. 23: POVM's (continued) NC 2.2.6
Here are my old notes about POVM's and a first attempt at a revision.
Tues, Oct. 28: one-d Schroedinger equation, harmonic oscillator, coherent states.
Thurs, Oct. 30: POVM review and "measurement without interaction"
Tues, Nov. 4 (Election Day) Test review.
Thurs, Nov. 13 Quantum Error Correcting Codes NC 10.1-10.2
Tues, Nov. 18 Quantum Error Correcting Codes NC 10.4
Thurs, Nov. 20 Quantum Error Correcting Codes NC 10.3
Tues, Nov. 25, Quantum Cryptography, NC 12.6

2006 Lectures

The following are links to last years lecture notes. I will improve these lecture notes and put them up for this year, but right now, I have been too busy to keep up to date.
Thur. 09/07, 2006:
NC 3.1.2 to 3.2.3;
Tues. 09/12, 2006:
NC 3.2.5; 2.2.1; 2.2.2; 4.2;
Thur. 09/14, 2006:
NC 2.2.3 to 2.2.5; 4.2; 2.2.7, 2.2.8
Tues. 09/19, 2006:
NC 2.6; 1.3.6
Thurs. 09/21, 2006:
NC 1.3.5, 2.3, 1.3.7, 2.6 (no-cloning theorem, superdense coding, teleportation)
Tues. 09/26, 2006:
NC 2.2.5, 2.2.6, 4.1, 4.2, 4.3; projective measurements and POVM's, and the circuit model of quantum computing, part I.
Thurs. 09/28, 2006:
NC 4.4, 4.5; gates for the circuit model.
Tues. 10/03, 2006:
NC 4.4, 4.5; more gates for the circuit model.
Thurs. 10/05:
Simon's algorithm. Not in NC. See Preskill 6.3, pp. 43-45.
Thurs. 10/12:
the quantum Fourier transform. NC 5.1, 5.2
Tues. 10/17:
Phase estimation and factoring. NC 5.3, 5.4
Thurs. 10/19:
Last piece of factoring (reduction from phase estimation to periodicity), discrete logarithms. Hidden subgroup problem.
Tues. 10/24:
Grover's algorithm.
Thur. 10/26:
More on Grover's algorithm/review for exam.
Thur. 11/2:
Operators x and p for quantum mechanics on the line.
Tues. 11/7:
The harmonic oscillator.
Thurs. 11/9:
Density matrices and quantum operations.
Tues. 11/14:
Guest lecture (Seth Lloyd): electromagnetic resonance.
Thurs. 11/16:
More on density matrices and quantum operations.
Tues. 11/21:
Lecture on Peres-Wootters and the discovery of teleportation.
Tues. 11/28:
Quantum error-correcting codes NC 10.1-10.3
Thurs. 11/30:
Quantum error-correcting codes NC 10.4
Tues. 12/03:
Quantum cryptography NC 12.6
Thurs. 12/05:
Quantum fault tolerance, part 1 NC 10.6
Tues. 12/10:
Quantum fault tolerance, part 2 NC 10.6