Aaronson homepage. Scott's research interests center around fundamental limits on what can efficiently be computed in the physical world. Member of the Theory of Computation and Complexity Theory groups.
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.
It weaves together seemingly disparate topics into a cohesive whole, including quantum mechanics, complexity, free will, time travel, the anthropic principle and many others.
Lecture Notes expected to be published as a book by Cambridge University Press.
- 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
S. Aaronson. Quantum Computing and Hidden Variables [PS] [PDF], Physical Review A 71:032325, March 2005. quant-ph/0408035 and quant-ph/0408119.
- This paper initiates the study of hidden variables from a quantum computing perspective. For us, a hidden-variable theory is simply a way to convert a unitary matrix that maps one quantum state to another, into a stochastic matrix that maps the initial probability distribution to the final one in some fixed basis. We list five axioms that we might want such a theory to satisfy, and then investigate which of the axioms can be satisfied simultaneously. Toward this end, we propose a new hidden-variable theory based on network flows. In a second part of the paper, we show that if we could examine the entire history of a hidden variable, then we could efficiently solve problems that are believed to be intractable even for quantum computers. In particular, under any hidden-variable theory satisfying a reasonable axiom, we could solve the Graph Isomorphism problem in polynomial time, and could search an N-item database using O(N1/3) queries, as opposed to O(N1/2) queries with Grover's search algorithm. On the other hand, the N1/3 bound is optimal, meaning that we could probably not solve NP-complete problems in polynomial time. We thus obtain the first good example of a model of computation that appears slightly more powerful than the quantum computing model.
Inga kommentarer:
Skicka en kommentar