2016 Barbados Workshop on Computational Complexity

2016 Barbados Workshop on Computational Complexity


The 28th McGill Invitational Workshop on Computational Complexity will be held at Bellairs Research Institute of McGill University, Holetown, St. James, Barbados, West Indies from February 19th to 26th, 2016. Participants can arrive either on February 19th or the 20th. Lectures will start February 21st and end on the 25th. The subject of this year's workshop will be The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes.



Speaker:
Scott Aaronson
MIT
The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes

This mini-course will introduce participants to an exciting frontier for quantum computing theory: namely, questions involving the computational complexity of preparing a certain quantum state or applying a certain unitary transformation. Traditionally, such questions were considered in the context of the Nonabelian Hidden Subgroup Problem and quantum interactive proof systems, but they are much broader than that. One important application is the problem of "public-key quantum money" -- that is, quantum states that can be authenticated by anyone, but only created or copied by a central bank -- as well as related problems such as copy-protected quantum software. A second, very recent application involves the black-hole information paradox, where physicists realized that for certain conceptual puzzles in quantum gravity, they needed to know whether certain states and operations had exponential quantum circuit complexity. These two applications (quantum money and quantum gravity) even turn out to have connections to each other! A recurring theme of the course will be the quest to relate these novel problems to more traditional computational problems, so that one can say, for example, "this quantum money is hard to counterfeit if that cryptosystem is secure," or "this state is hard to prepare if PSPACE is not in PP/poly." Numerous open problems and research directions will be suggested, many requiring only minimal quantum background. Some previous exposure to quantum computing and information will be assumed, but a brief review will be provided.


Important Information for Participants