IQC Colloquium

Thursday, April 28, 2022 10:00 am - 10:00 am EDT (GMT -04:00)

From quantum circuit complexity to quantum information thermodynamics

Philippe Faist, Freie Universität Berlin

Quantifying quantum states' complexity is a key problem in various subfields of science, from quantum computing to black-hole physics. My talk will focus on two approaches to understand the behavior and the operational significance of quantum complexity in a many-body physical quantum system. First, I'll consider a simple model on n quantum bits: We create a random quantum circuit by randomly sampling the gates that compose it. In this model, quantum complexity can be shown to grow linearly in the number of gates until saturating at a value that is exponential in n. This result proves a version of a conjecture by Brown and Susskind in the context of quantum gravity. Second, I'll discuss how quantum complexity manifests itself in the operational processes that we can carry out on an n-qubit system. What thermodynamic resources are necessary to reset an n-qubit memory register to the pure all-zero computational basis state? This approach reveals a close connection between entropy and complexity, as we exhibit a trade-off between the thermodynamic work cost that is necessary for the reset procedure and the complexity cost of the procedure. The general trade-off is quantified by a new measure of entropy that quantifies the amount of randomness that a system appears to have to an observer whose observations are limited in complexity. Beyond applications in many-body physics, our methods aim at developing a deep understanding of the set of quantum states that can be reached with a fixed number of gates; we anticipate our methods to be relevant more broadly for quantum pseudorandomness, quantum error correction, and tasks in quantum information and quantum thermodynamics subject to computational limitations.

Joint work with: Jonas Haferkamp, Teja Naga Bhavia Kothakonda, Anthony Munson, Jens Eisert, Nicole Yunger Halpern

Join the in-person colloquium in QNC 0101.