Appears in collection : Complexity as a kaleidoscope / Le kaleidoscope de la complexité

In these three lectures on quantum information and complexity, we will (1) review the basic concepts of quantum information processing units (QPUs), (2) prove a version of the claim that almost all quantum circuits are very complex in the sense that they are exponentially expensive to realize in the quantum circuit model of computation and (3) that the quantum complexity of a random quantum circuit grows linearly with the size of the circuit up to exponentially large circuits.

The underlying proof technique uses a versatile proof strategy from high-dimensional probability theory that can (and has been) readily extended to other problems within quantum computing theory and beyond.