Course Information for 
Physics 219/Computer Science 219
Quantum Computation
(Formerly Physics 229)

John Preskill

Go to the home page of Ph219/CS219 for 2006-07.
Go to the home page of Ph219/CS219 for 2005-06.
Go to the home page of Ph219/CS219 for 2004.

Contents

Go directly to course outline, references, lecture notes, or homework . 

Course Description

The theory of quantum information and quantum computation. Overview of classical information theory, compression of quantum information, transmission of quantum information through noisy channels, quantum entanglement, quantum cryptography. Overview of classical complexity theory, quantum complexity, efficient quantum algorithms, quantum error-correcting codes, fault-tolerant quantum computation, physical implementations of quantum computation.

Class Meetings

Mondays and Wednesdays and  1:00 to 2:30 in 269 Lauritsen, first, second, and third terms. The first class meeting is on Monday, September 25, 2000..

Instructors

John Preskill
459 Lauritsen Laboratory
Telephone: 626-395-6691
email: preskill@theory.caltech.edu

Teaching assistant:
Jim Harrington
453 Lauritsen
Telephone: 626-395-6650
email: jimh@theory.caltech.edu
office hours: ???

Course Requirements

There will be regularly assigned problem sets. The grading is pass/fail.

Prerequisites

The course material should be of interest to physicists, mathematicians, computer scientists, and engineers, so we hope to make the course accessible to people with a variety of backgrounds.

Certainly it would be useful to have had a previous course on quantum mechanics, though this may not be essential. It would also be useful to know something about (classical) information theory,  (classical) coding theory,  and (classical) complexity theory, since a central goal of the course will be generalize these topics to apply to quantum information. But we will review this material when we get to it, so you don't need to worry if you haven't seen it before. In the discussion of quantum coding, we will use some rudimentary group theory.

References

There is no required textbook. Much of the material in the course is based on quite recent research that has not yet appeared in any book. Many relevant research articles can be accessed through the quant-ph eprint archive maintained by Los Alamos National Laboratory. One good reference is the lecture notes that were originally prepared for this course when it was taught for the first time in 1997-98. An excellent textbook, Quantum Computation and Quantum Information by Michael Nielsen and Isaac Chuang, will be available in the fall of 2000.

In the early part of the course, we'll review the conceptual foundations of quantum mechanics and the theory of measurement. Good books relating to this material are Quantum Theory: Concepts and Methods by Asher Peres (on reserve in Millikan Library) and The Interpretation of Quantum Mechanics by Roland Omnes. Also, there is a good discussion of measurement and decoherence in Quantum Optics by D. F. Walls and G. J. Milburn.

Later, we'll develop the quantum theory of information, coding, and complexity. Good books on the corresponding classical theory are Elements of Information Theory by Thomas Cover and Joy Thomas, The Theory of Error-Correcting Codes by F. J. MacWilliams and N. J. A. Sloane, Computers and Intractability by Michael Garey and David Johnson, and Computational Complexity by Christos Papadimitriou.

Here are some accessible articles on quantum computation and related topics:

For an overview of the status of current theoretical research on quantum computation, see:

Here are some lists of key papers on specialized topics:

You'll find further references under the heading "Other Useful Links" below.

Course Overview

Information is something that can be encoded in the state of a physical system, and a computation is a task that can be performed with a physically realizable device. Therefore, since the physical world is fundamentally quantum mechanical, the foundations of information theory and computer science should be sought in quantum physics.

In fact, quantum information -- information stored in the quantum state of a physical system -- has weird properties that contrast sharply with the familiar properties of "classical" information. And a quantum computer -- a new type of machine that exploits the quantum properties of information -- could perform certain types of calculations far more efficiently than any foreseeable classical computer.

In this course, we will study the properties that distinguish quantum information from classical information. And we will see how these properties can be exploited in the design of quantum algorithms that solve certain problems faster than classical algorithms can.

A quantum computer will be much more vulnerable than a conventional digital computer to the effects of noise and of imperfections in the machine. Unavoidable interactions of the device with its surroundings will damage the quantum information that it encodes, a process known as decoherence. Schemes must be developed to overcome this difficulty if quantum computers are ever to become practical devices.

In this course, we will study quantum error-correcting codes that can be exploited to protect quantum information from decoherence and other potential sources of error. And we will see how coding can enable a quantum computer to perform reliably despite the inevitable effects of noise.

Building a quantum computer that really works will not be easy. Experimental physicists are now just beginning to build and operate hardware that can coherently process quantum information.

In this course, we will learn about the pioneering efforts to operate quantum computing hardware, using ion traps, cavity quantum electrodynamics, and nuclear magnetic resonance.

Course Outline

The course has been offered twice before as a two-term course. In 1997-98, it  followed this outline, but covered only part of it.

In 1998-99, it was taught jointly by Preskill and Alexei Kitaev following this outline:

30 September - 23 October (4 weeks):
Overview and introductory material, quantum measurement, decoherence, quantum entanglement.
(Drawn from chapters 1-4 of the lecture notes.)
Instructor: Preskill

28 October - 4 December (5 1/2 weeks):
Classical and quantum complexity, quantum algorithms.
(Corresponds roughly to chapter 6 of the lecture notes, but from a different perspective.)
Instructor: Kitaev

6 January - 10 February (5 1/2 weeks):
Quantum error-correcting codes, entanglement measures, quantum channel capacity.
Instructor: Preskill

12 February - 10 March (4 weeks):
Fault tolerant quantum computation, topological quantum codes, quantum computing with anyons.
Instructor: Kitaev
 

The second time there was more emphasis on quantum error correction and fault tolerance, less on quantum information theory.

In 2000-01, since it will be a three-term course, it should be possible to cover most of both outlines, plus some new material.

Lecture Notes

These are PostScript files.  If you need help configuring your computer to view PostScript, try this site.

The first 6 chapters were originally prepared in 1997-98. They were last updated on 2 October 1998. ("Half-size" means landscape two-column format, with two text pages side-by-side on each printed page.) Chapter 7 was added in 1999 and was last updated on 23 February 1999. (Sorry, the figures for Chapter 7 are not available.)  Chapter 8 (Fault-tolerant quantum computation) is not yet available. Chapter 9 was added in 2004. There is also an updated (though incomplete) version of Chapter 4, prepared in 2001.

Chapter 1. Introduction and Overview, 30 pages.   Half-size.
Chapter 2. Foundations of Quantum Theory I: States and Ensembles, 40 pages. Half-size.
Chapter 3. Foundations of Quantum Theory II: Measurement and Evolution, 62 pages.   Half-size.
Chapter 4. Quantum Entanglement, 28 pages.   Half-size.
Chapter 5. Quantum Information Theory,  64 pages.   Half-size.
Chapter 6. Quantum Computation,   91 pages.   Half-size.

Chapters 1-6 in one file,  321 pages.   Half-size.

Chapter 7. Quantum Error Correction,  92 pages.

Chapter 9. Topological Quantum Computation, 68 pages.
Note: some printers may choke on the .ps file because of its large size (2.0 MB). If you have trouble, try the .pdf file (0.4 MB).

Updated (but incomplete) Chapter 4. Quantum Entanglement, 57 pages.

Homework

Problems assigned during 2000-01 (in ps format):

Problem Set 1, due October 23, 2000.  Solution Set 1  (in ps format).  Solution Set 1 (in pdf format)
Problem Set 2, due November 6, 2000.  Solution Set 2  (in ps format).  Solution Set 2 (in pdf format)
Problem Set 3, due November 20, 2000. Solution Set 3  (in ps format).  Solution Set 3 (in pdf format)
Problem Set 4, due November 29, 2000. Solution Set 4  (in ps format).  Solution Set 4 (in pdf format)

Problem Set 5, due February 5, 2001.
Problem Set 6, due February 26, 2001.
Problem Set 7, due March 7, 2001.

Problem Set 8, due May 7, 2001.
Problem Set 9, due May 23, 2001.
Problem Set 10, due May 30, 2001.

Problems assigned during 1998-99:

Problem Set 1, due October 16, 1998.   Solution Set 1
Problem Set 2, due October 23, 1998.   Solution Set 2
Problem Set 3, due November 6, 1998.  Solution Set 3
Problem Set 4, due November 25, 1998.  Solution Set 4
Problem Set 5, due December 4, 1998.  Solution Set 5

Problem Set 6, due February 5, 1999.  Solution Set 6
Problem Set 7, due February 19, 1999.  Solution Set 7
Problem Set 8, due March 10, 1999.

Problems assigned during 1997-98:

Chapter 2 Problems, updated October 21, 1997.
Chapter 2 Solutions, updated October 31, 1997.
Chapter 3 Problems, updated November 20, 1997. (Problems due 5 December.)
Chapter 3 Solutions, updated December 11, 1997.
Chapter 5 Problems, updated January 26, 1998. (Problems due 10 February.)
Chapter 5 Solutions, updated March 6, 1998.
Chapter 6 Problems, updated March 9, 1998. (Problems due 13 March.)
Chapter 6 Solutions, updated March 20, 1998.

Other Useful Links

Here are some other links to sites concerning quantum information and computation:

preskill@theory.caltech.edu