  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.
