Complexity measures in QFT and constrained geometric actions

We study the conditions under which, given a generic quantum system, complexity metrics provide actual lower bounds to the circuit complexity associated to a set of quantum gates. Inhomogeneous cost functions - many examples of which have been recently proposed in the literature - are ruled out by our analysis. Such measures are shown to be unrelated to circuit complexity in general and to produce severe violations of Lloyd's bound in simple situations. Among the metrics which do provide lower bounds, the idea is to select those which produce the tightest possible ones. This establishes a hierarchy of cost functions and considerably reduces the list of candidate complexity measures. In particular, the criterion suggests a canonical way of dealing with penalties, consisting in assigning infinite costs to directions not belonging to the gate set. We discuss how this can be implemented through the use of Lagrange multipliers. We argue that one of the surviving cost functions defines a particularly canonical notion in the sense that: i) it straightforwardly follows from the standard Hermitian metric in Hilbert space; ii) its associated complexity functional is closely related to Kirillov's coadjoint orbit action, providing an explicit realization of the complexity equals action idea; iii) it arises from a Hamilton-Jacobi analysis of the quantum action describing quantum dynamics in the phase space canonically associated to every Hilbert space. Finally, we explain how these structures provide a natural framework for characterizing chaos in classical and quantum systems on an equal footing, find the minimal geodesic connecting two nearby trajectories, and describe how complexity measures are sensitive to Lyapunov exponents.

Automated summary

We have found that inhomogeneous cost functions are unrelated to circuit complexity, while selecting metrics that provide the tightest possible lower bounds helps reduce the list of candidate complexity measures. Assigning infinite costs to directions not belonging to the gate set, among other methods, can reduce unnecessary calculations.