The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 10 Pith papers
-
A Relativizing MIP for BQP
BQP is contained in MIP relative to every classical oracle via a new PCP construction for BQP^O inspired by Grover-Rudolph state synthesis.
-
Certifying localizable quantum properties with constant sample complexity
A new framework certifies global quantum properties including multipartite entanglement, circuit complexity, and quantum magic on small subsystems with constant sample complexity via local Pauli measurements.
-
Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
Any n-qubit unitary can be implemented approximately with Õ(2^{n/2}) oracle queries or exactly with Õ(2^{n/2}) circuit depth via Grover search reductions, with matching lower bounds for certain implementations.
-
Quantum Finite Temperature Lanczos Method
QFTLM computes thermal expectation values on quantum computers by merging quantum Krylov methods with efficient typical-state preparation for trace estimation.
-
Quantum Circuit Overhead
Introduces QCO and T-QCO measures and numerically shows that the T gate is non-optimal for completing the Clifford set among order-8 gates.
-
A Multi-Level Integrity Evaluation Framework for Quantum Circuits under Controlled Anomaly Injection
A three-metric framework (SIS, OIS, IGS) detects anomalies in quantum circuits more reliably than structural checks alone, as shown by controlled injections where high structural similarity still misses most behaviora...
-
Stringy Effects on Holographic Complexity: The Complete Volume in Dynamical Spacetimes
Gauss-Bonnet corrections to the complete volume introduce a competition effect in static cases and prolong the critical time in two-sided shocks while the complexity growth rate stays governed by conserved momentum.
-
Stringy Effects on Holographic Complexity: The Complete Volume in Dynamical Spacetimes
Gauss-Bonnet corrections to the complete volume proposal introduce a competition effect in static black holes while preserving momentum-governed growth rates and logarithmic scrambling times in dynamical Vaidya geometries.
-
From Fundamental Dynamics to Applied Cryptography: Studies on the Quantum Speed Limit and Fully Passive Quantum Key Distribution
Thesis exploring quantum speed limits on dynamical evolution alongside a fully passive quantum key distribution scheme.
-
Rethinking quantum information in gravity and fields
The paper organizes important open questions in quantum gravity and quantum information into four themes without presenting new results or derivations.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.