A Quantum Complexity Lowerbound from Differential Geometry

Understand

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.