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

2016/07/18 by Scott Aaronson, Aaronson, Scott · 1 voice · 52 citations
Computer Science · Mathematics · Physics and Astronomy · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Computer science #FOS: Computer and information sciences #FOS: Physical sciences #General Relativity and Quantum Cosmology (gr-qc) #Mathematics #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum algorithm #Quantum circuit #Quantum computer #Quantum information #Quantum mechanics #Quantum network #Theoretical physics #Tying #cs.CC #gr-qc #quant-ph

paper · pdf · doi:10.48550/arxiv.1607.05256

published in arXiv (Cornell University) 23, 109 (Cornell University) · 111 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

arxiv created 2016/07/18 · openalex publication_date 2016/07/18 · arxiv published 2016/07/18 · arxiv updated 2016/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

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?
• On estimating the entropy of shallow circuit outputs
• Mutual Correlation
• Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
• Physical complexity and black hole quantum computers
• Quantifying complexity of continuous-variable quantum states via Wehrl entropy and Fisher information
• Quantum Circuit Overhead
• Rethinking quantum information in gravity and fields
• Almost Public Quantum Coins
• Public-Key Quantum Fire and Key-Fire From Classical Oracles
• On the time dependence of holographic complexity in a dynamical Einstein-dilaton model
• Semi-device-independent quantum money
• Continuous-Variable Quantum Encoding Techniques: A Comparative Study of Embedding Techniques and Their Impact on Machine Learning Performance
• Group Order is in QCMA

Discussions

• Awesome lectures on the complexity of preparing and transforming quantum states, and black holes. http://arxiv.org/pdf/1607.05256.pdf … [bsky, 0 points, 0 comments]

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