Proofs of Two Brown-and-Susskind Complexity Conjectures
In 2017, Adam Brown and Lenny Susskind posed two conjectures about
quantum complexity, the difficulty of preparing a desired many-body state
from a simple tensor product: (1) Under chaotic evolutions, complexity
grows linearly for a time exponential in the system size. (2) A resource
theory for uncomplexity can be defined. (Resource theories are simple
models, developed in quantum information theory, for situations in which
constraints restrict the operations one can perform. Uncomplexity is a lack
of complexity, useful in inputs to quantum computations.) We prove both
conjectures correct, using tools from quantum information theory, algebraic
geometry, and differential topology.
1) Haferkamp, Faist, Kothakonda, Eisert, and NYH, arXiv:2106.05305 (2021).
2) NYH, Kothakonda, Haferkamp, Munson, Faist, and Eisert, arXiv:2110.11371 (2021).