A Quantum Complexity Lowerbound from Differential Geometry
arXiv:2112.05724 · doi:10.1038/s41567-022-01884-6
Abstract
The Bishop-Gromov bound -- a cousin of the focusing lemmas that Hawking and Penrose used to prove their black hole singularity theorems -- is a differential geometry result that upperbounds the rate of growth of volume of geodesic balls in terms of the Ricci curvature. In this paper, I apply the Bishop-Gromov bound to Nielsen's complexity geometry to prove lowerbounds on the quantum complexity of a typical unitary. For a broad class of penalty schedules, the typical complexity is shown to be exponentially large in the number of qubits. This technique gives results that are tighter than all known lowerbounds in the literature, as well as establishing lowerbounds for a much broader class of complexity geometry metrics than has hitherto been bounded. For some metrics, I prove these lowerbounds are tight. This method realizes the original vision of Nielsen, which was to apply the tools of differential geometry to study quantum complexity.
References in corpus (18)
- Complexity Equals Action
- Complexity and Shock Wave Geometries
- Complexity, action, and black holes
- Quantum Computation as Geometry
- Circuit complexity in quantum field theory
- Towards Complexity for Quantum Field Theory States
- The Second Law of Quantum Complexity
- Circuit Complexity in Fermionic Field Theory
- Circuit complexity for free fermions
- Quantum Complexity and Negative Curvature
- Optimal control, geometry, and quantum computing
- Quantum Complexity of Time Evolution with Chaotic Hamiltonians
- The Complexity Geometry of a Single Qubit
- Complexity Growth in Integrable and Chaotic Models
- Quantum Complexity as Hydrodynamics
- Quantum Control via Geometry: An explicit example
- Sectional curvatures distribution of complexity geometry
- How smooth is quantum complexity?