Physics 219/Computer Science 219

Quantum Computation

(Formerly Physics 229)

2021 (fall term)

2018 (spring term)

2017 (winter and spring terms)

2015-16 (winter term)

2013-14 (fall and winter terms)

2011 (winter term)

2008-09 (three terms)

2006-07 (fall and winter terms)

2005-06 (fall and winter terms)

2004 (spring term)

The first 6 chapters were originally prepared in 1997-98, Chapter 7 was added in 1999, and Chapter 9 was added in 2004. A typeset version of Chapter 8 (on fault-tolerant quantum computation) is not yet available; nor are the figures for Chapter 7. Additional material is available in the form of handwritten notes.

There is also an updated (though incomplete) version of Chapter 4, prepared in 2001.

Chapters 2 and 3 were updated in July 2015. What is now Chapter 5 (also updated July 2015) is a new version of what was previously the first half of Chapter 6.

Chapter 6 was updated in November 2020.

Chapter 10, updated in April 2022, is a revised and expanded version of what was previously Chapter 5.

Chapter
1. Introduction and Overview, 30 pages (Fall 1997).

Chapter 2.
Foundations I: States and Ensembles, 52 pages (July 2015).

Chapter 3.
Foundations II: Measurement and Evolution, 66 pages (July 2015).

Chapter 4. Quantum Entanglement, 70 pages (2001, incomplete).

Chapter
5. Classical and Quantum Circuits, 54 pages (July 2015).

Chapter 6. Quantum Algorithms,
64 pages (November 2020).

Chapter 7. Quantum Error
Correction, 92
pages (Spring 1999).

Chapter 9. Topological Quantum
Computation, 68 pages (June 2004).

Chapter 10. Quantum Shannon Theory, 90 pages (April
2022).

**Here**** are some of the
handwritten notes that have
not yet been typeset**:

Abelian hidden subgroup problem, discrete logarithm (2009 handwritten
notes – see also notes
on non-abelian HSP)

Quantum searching (2009 handwritten
notes – see also 2009 notes
on quantum lower bounds)

Toric code recovery, fault-tolerant recovery,
fault-tolerant gates (2011 handwritten
notes)

Cluster states (2017 handwritten
notes)

Ising anyons and Majorana modes (2018 handwritten
notes)

**Older versions of the typed notes**:

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

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

Chapter 4. Quantum Entanglement, 28 pages.

Chapter 5. Quantum Information Theory, 64 pages.

Chapter 6. Quantum Computation, 91 pages.

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

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.

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.

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

The course was offered as a two term sequence for the first time in 1997-98 by John Preskill, then repeated the following year taught jointly by Preskill and Alexei Kitaev. In 2000-01 a more complete course three-term course was offered. Since then it has been taught multiple times by both Preskill and Kitaev. Links to the course webpages in later years are listed at the top of this page.