**PHYS771 Quantum Computing Since Democritus**

University of Waterloo, Fall 2006

Tuesdays and Thursdays, 1:00-2:30pm

BFG Building, 2nd floor seminar room (BFG2125)

**Instructor:** Scott Aaronson

3141 Davis Centre
**Email:** scott at scottaaronson dot com
**Office hours:** After class or by appointment

**Description:** This course tries to connect quantum
computing to the wider intellectual world. We'll start out with various
scientific, mathematical, or philosophical problems that predate
quantum computing: for example, the measurement problem, P versus NP,
the existence of secure cryptography, the Humean problem of induction,
or the possibility of closed timelike curves. We'll then examine in
what ways, if any, quantum computing affects how we should think about
the problem. To keep things grounded, each session will end with a
concrete puzzle that students will be expected to have thought about
(if not solved) by the next session. The class format will strongly
encourage participation, discussion, and debate.

**Prerequisites:** Mathematical maturity and some previous exposure to
quantum computing.

**Responsibilities:** The main one is to scribe one or two sessions; we might experiment with using audio recordings to help with this. Besides
that, students are expected to

- show up,
- actively participate in discussion,
- work on the puzzles,
- do the readings (which will generally be light), and
- turn in one or two problem sets (having either solved the problems or else explained why they couldn't solve them).

*Quantum Computing Since Democritus* Book Is Now Available!

[Order from Amazon.com]

[Order from Amazon.co.uk]

[Kindle edition] [UK Kindle edition]

- Lecture 1 (9/12): Atoms and the Void
- Lecture 2 (9/14): Sets
- Lecture 3 (9/19): Gödel, Turing, and Friends
- Lecture 4 (9/21): Minds and Machines
- Lecture 5 (9/26): Paleocomplexity
- Lecture 6 (9/28): P, NP, and Friends
- Lecture 7 (10/3): Randomness
- Lecture 8 (10/5): Crypto
- Lecture 9 (10/19): Quantum
- Lecture 10 (10/24): Quantum Computing
- Lecture 10.5 (10/24): Penrose
- Lecture 11 (10/26): Decoherence and Hidden Variables
- Lecture 12 (10/31): Proof
- Lecture 13 (11/2): How Big Are Quantum States?
- Lecture 14 (11/7): Skepticism of Quantum Computing
- Lecture 15 (11/9): Learning
- Lecture 16 (11/14): Interactive Proofs
- Lecture 17 (11/16): Fun With The Anthropic Principle
- Lecture 18 (11/21): Free Will
- Lecture 19 (11/23): Time Travel
- Lecture 20 (11/28): Cosmology and Complexity
- Lecture 21 (11/30): Ask Me Anything

- Democritus (from Stanford Encyclopedia of Philosophy)
- David Deutsch, Quantum theory as a universal physical theory
(unfortunately, can only be accessed from within the university). Pages
32-37 describe the notorious thought experiment. See also Chapter 1 of
*Minds, Machines, and the Multiverse*by Julian Brown - Alan Turing, On Computable Numbers
- Alan Turing, Computing Machinery and Intelligence
- Roger Penrose, The Emperor's New Mind (our "textbook")
- Sanjeev Arora and Boaz Barak, Complexity Theory: A Modern Approach (free draft available on the web)
- Lucien Hardy, Quantum theory from five simple axioms