How smooth is quantum complexity?

Understand

The "quantum complexity" of a unitary operator measures the difficulty of its construction from a set of elementary quantum gates.

• While the notion of quantum complexity was first introduced as a quantum generalization of the classical computational complexity, it has since been argued to hold a fundamental significance in its own right, as a physical quantity analogous to the thermodynamic entropy.
• In this paper, we present a unified perspective on various notions of quantum complexity, viewed as functions on the space of unitary operators.
• One striking feature of these functions is that they can exhibit non-smooth and even fractal behaviour.