In quantum computing, quantum complexity measures the difficulty of realizing a quantum process, such as preparing a quantum state or implementing a unitary evolution.

Quantum complexity is a quantity with increasing relevance for many-body quantum systems. For example, it is believed to approximately quantify the time for which a suitably chaotic quantum system has been evolving for, without knowing what specific Hamiltonian is driving the evolution. This property has been proven rigorously for random quantum circuits, a simplified model of quantum chaotic dynamics.

I will discuss several aspects of how quantum complexity is a useful concept in physics. I will focus on the prototypical task of information erasure, or Landauer erasure, where an n-qubit memory is reset to the all-zero state.

In this setting, the trade-off between the thermodynamic work and computational complexity required for erasure is determined by the complexity entropy. This measure more generally quantifies the entropy a system appears to have to an observer of limited complexity power and which is closely related to complexity distinguishability; it can also quantify long-time growth of complexity in random circuits.

Finally, I will reflect on how quantum complexity might offer an angle to tackle questions around the fundamental limits to quantum fault tolerance as well as some foundational aspects of quantum chaos.