The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes
These are lecture notes from a weeklong course in quantum complexity theory taught at the Bellairs Research Institute in Barbados, February 21 25, 2016. The focus is quantum circuit complexity i.e. the minimum number of gates needed to prepare a given quantum state or apply a given unitary transformation as a unifying theme tying together several topics of recent interest in the field. Those topics include the power of quantum proofs and advice states; how to construct quantum money schemes secure against counterfeiting; and the role of complexity in the black hole information paradox and the AdS/CFT correspondence (through connections made by Harlow Hayden, Susskind, and others) The course was taught to a mixed audience of theoretical computer scientists and quantum gravity string theorists, and starts out with a crash course on quantum information and computation in general.
Electron. Colloquium Comput. Complex.