How smooth is quantum complexity?

Abstract

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. We use ideas from Diophantine approximation theory and sub-Riemannian geometry to rigorously quantify this lack of smoothness. Implications for the physical meaning of quantum complexity are discussed.

arXiv commentv2: minor revisions, remarks added on difference between nilpotent and unitary groups from a complexity viewpoint. 10 pages, 1 figure

References in corpus (10)

• Complexity Equals Action
• Complexity, action, and black holes
• Quantum Computation as Geometry
• Open XXZ spin chain: Nonequilibrium steady state and strict bound on ballistic transport
• The Second Law of Quantum Complexity
• Efficient Discrete Approximations of Quantum Gates
• The Complexity Geometry of a Single Qubit
• Super-Golden-Gates for PU(2)
• Cayley graphs and complexity geometry
• The Complexity of Translationally-Invariant Low-Dimensional Spin Lattices in 3D

Cited by in corpus (7)

• Quantum chaos and the complexity of spread of states
• Bounds on quantum evolution complexity via lattice cryptography
• Crystalline Quantum Circuits
• A Quantum Complexity Lowerbound from Differential Geometry
• Circuit Complexity in Topological Quantum Field Theory
• Universality in long-distance geometry and quantum complexity
• Polynomial Equivalence of Complexity Geometries