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

2016/07/18 by Scott Aaronson, Aaronson, Scott · 9 citations
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #General Relativity and Quantum Cosmology (gr-qc) #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.1607.05256

openalex publication_date 2016/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Spread and circuit complexity as a measure of particle content and phase space fluctuations
• Quantum Relative Entropy Decay Composition Yields Shallow, Unstructured k-Designs
• On Limits on the Provable Consequences of Quantum Pseudorandomness
• State complexity and phase identification in adaptive quantum circuits
• Data Complexity: a threshold between Classical and Quantum Machine Learning -- Part I
• A 1.5-Query Lower Bound for the Unitary Synthesis Problem
• Quantum Circuits for Matrix-Product Unitaries
• How to Copy-Protect Malleable-Puncturable Cryptographic Functionalities Under Arbitrary Challenge Distributions
• Wigner's friend's black hole adventure: an argument for complementarity?

Related

• Three Lectures on Complexity and Black Holes
• Quantum Computational Complexity
• One Complexity Theorist's View of Quantum Computing
• Quantum complexity in gravity, quantum field theory, and quantum information science
• Quantum Complexity: restrictions on algorithms and architectures