paper

The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes

arXiv:1607.05256

Abstract

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.

arXiv comment111 pages, 10 figures. Includes a special guest lecture by Adam Bouland and Luke Schaeffer. Enormous thanks to them, Anil Ada, Denis Therien, and the scribes, without whom these notes wouldn't have happened. Comments welcome

Cited by in corpus (29)