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.
References:
1) Haferkamp, Faist, Kothakonda, Eisert, and NYH, arXiv:2106.05305 (2021).
2) NYH, Kothakonda, Haferkamp, Munson, Faist, and Eisert, arXiv:2110.11371 (2021).