Physics 219/Computer Science 219

Quantum Computation

(Formerly Physics 229)

Go to the home page of Ph219/CS219 for 2011.

Go to the home page of Ph219/CS219 for 2008-09.

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.

- Course Description
- Class Meetings
- Instructors
- Course Requirements
- Prerequisites
- References
- Course Overview
- Course Outline
- Lecture Notes
- Homework
- Other Useful Links

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

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.

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

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: ???

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

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.

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:

- Quantum Cryptography,
by Richard Hughes,
*et al*. - Quantum Computing, by Andrew Steane
- Quantum Gates and Circuits, by David DiVincenzo
- Quantum Algorithms and the Fourier Transform, by Richard Josza
- Quantum Algorithms
Revisited, by Richard Cleve,
*et al.* - Reliable Quantum Computers, by John Preskill
- Fault-Tolerant Quantum Computation, by John Preskill
- What Makes Quantum Computers Powerful?, by the Quantum Computation Collective

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

- Quantum Computing; Pro and Con, by John Preskill

Here are some lists of key papers on specialized topics:

- Quantum information theory
- Quantum entanglement
- Quantum gates
- Quantum algorithms
- Quantum error-correcting codes
- The quantum channel capacity
- Fault-tolerant quantum computation

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

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

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.

The first 6 chapters were originally prepared in 1997-98. They were last
updated on

Chapter 1. Introduction and Overview, 30
pages.

Chapter 2. Foundations of Quantum Theory I: States and
Ensembles, 40 pages.

New: Updated
Chapter 2. Foundations I: States and Ensembles, 48 pages (14 November
2013).

Chapter 3. Foundations of Quantum Theory II: Measurement and
Evolution, 62 pages.

Chapter 4. Quantum Entanglement, 28 pages.

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

Chapter 5. Quantum Information Theory, 64 pages.

Chapter 6. Quantum Computation, 91 pages.

New : Updated Chapter 5. Classical and Quantum Circuits, 55 pages (12 November 2013).

Chapters 1-6 in one file, 321 pages (ps
format)

Chapter 7. Quantum Error
Correction, 92
pages

Chapter 9. Topological Quantum
Computation, 68 pages.

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

Problem
Set 6, due

Problem
Set 7, due

Problem
Set 8, due

Problem
Set 9, due

Problem
Set 10, due

Problems assigned during 1998-99:

Problem
Set 1, due

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

Problem
Set 7, due

Problem
Set 8, due

Problems assigned during 1997-98:

Chapter
2 Problems, updated

Chapter
2 Solutions, updated

Chapter
3 Problems, updated

Chapter
3 Solutions, updated

Chapter
5 Problems, updated

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.

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