Models of quantum complexity growth

Abstract: The quantum complexity of a unitary or state is defined as the size of the shortest quantum computation that implements the unitary or prepares the state. The notion has far-reaching implications spanning computer science, quantum many-body physics, and high energy theory. Complexity growth in time is a phenomenon expected to occur in holographic theories and strongly-interacting many-body systems more generally, but deriving lower bounds on the complexity of a state or unitary is notoriously difficult. By establishing a rigorous relation between quantum complexity and unitary designs, ensembles which emulate fully Haar random unitaries, we will prove statements about complexity growth in various models. Specifically, we prove a linear growth of complexity in random quantum circuits, using a recent result about their design growth. ______________________________________________ Zoom meeting details Topic: Quantum Information and Quantum Computing Working Group Time: Apr 16, 2020, 04:00 PM Warsaw Join Zoom Meeting: QIQCWG-ZOOM Meeting ID: 640 279 690Password: tp4C,kERx If you encounter any problems with connecting to the Zoom meeting, please email filip.b.maciejewski@gmail.com directly.