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).