Second law of quantum complexity

By Adam R. Brown, L. Susskind. 2017

346 citations recorded by the source corpus.

We give arguments for the existence of a thermodynamics of quantum complexity that includes a “second law of complexity.” To guide us, we derive a correspondence between the computational (circuit) complexity of a quantum system of K qubits, and the positional entropy of a related classical system with 2K degrees of freedom. We also argue that the kinetic entropy of the classical system is equivalent to the Kolmogorov complexity of the quantum Hamiltonian. We observe that the expected pattern of growth of the complexity of the quantum system parallels the growth of entropy of the classical system. We argue that the property of having less-than-maximal complexity (uncomplexity) is a resource that can be expended to perform directed quantum computation. Although this paper is not primarily about black holes, we find a surprising interpretation of the uncomplexity resource as the accessible volume of spacetime behind a black hole horizon.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/318cc52fe76d6d5fc19fc717fb7d27324f8eb6b3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. A. Nahum
2. Shira Chapman
3. H. Marrochio
4. R. Myers
5. B. Skinner
6. J. Ruhman
7. Hsin-Yuan Huang
8. Lucas Hackl

In Atomic and Molecular Physics, and Optics

1. R. Myers
2. A. Nahum
3. Shira Chapman
4. H. Marrochio
5. B. Skinner
6. J. Ruhman
7. Dean Carmi
8. Ro Jefferson

Citations in the corpus

• Linear growth of quantum circuit complexity (2021, methodology): “Recently, close connections have been discovered between gate complexity and holography in high-energy physics, in the context of the anti-de-Sitter-space/conformalfield-theory (AdS/CFT) correspondence [7, 10, 12, 52, 55].”
• On the time dependence of holographic complexity (2017, background): “In fact, the complexity is conjectured to continue growing until a time scale which is exponential in the number of degrees of freedom in the system [23].”
• Complexity and entanglement for thermofield double states (2018, background): “theories. In fact, the time evolution of the complexity of the TFD in these theories is predicted to initially show linear growth, i.e., @tC˘M, and to saturate only on a time scale of the order eS BH [13,113,114]. This expectation is based on the fact that these CFTs are fast scramblers and the evol”
• On the evolution of operator complexity beyond scrambling (2019, background): “Quantum complexity has been proposed as a new entry in the holographic dictionary (see for instance [2, 3] and references therein).”
• Emergent Quantum State Designs from Individual Many-Body Wave Functions (2021, background): “There may even be connections to the quantum complexity of a state evolving by chaotic dynamics, which likewise grows long after thermalization has occurred [52,62].”
• Measurement-Induced Phase Transitions in the Dynamics of Entanglement (2018, background): “[89] Adam R Brown and Leonard Susskind.”
• Circuit complexity in quantum field theory (2017, background): “An alternative approach [54] would be to simply assign each gate the cost N d−1 2 .”