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



Nicole Yunger Halpern


NIST & University of Maryland