måndag 18 april 2011

Quantum Computing Since Democritus

Quantum Computing Since Democritus is a serie of lectures by Scott Aaronson, University of Waterloo, Fall 2006. Much appreciated.

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. Suggested Readings See also:
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.
Other works here.

Inga kommentarer:

Skicka en kommentar