Krylov complexity and Nielsen complexity are successful approaches to quantifying quantum evolution complexity that have been actively pursued without much contact between the two lines of research. The two quantities are motivated by quantum chaos and quantum computation, respectively, while the relevant mathematics is as different as matrix diagonalization algorithms and geodesic flows on curved manifolds. We demonstrate that, despite these differences, there is a relation between the two quantities. Namely, the time average of Krylov complexity of state evolution can be expressed as a trace of a certain matrix, which also controls an upper bound on Nielsen complexity with a specific custom-tailored penalty schedule adapted to the Krylov basis.
We ask whether Krylov complexity is mutually compatible with the circuit and Nielsen definitions of complexity. We show that the Krylov complexities between three states fail to satisfy the triangle inequality and so cannot be a measure of distance: there is no possible metric for which Krylov complexity is the length of the shortest path to the target state or operator. We show this explicitly in the simplest example, a single qubit, and in general. Published by the American Physical Society 2024
We develop a geometric approach to operator growth and Krylov complexity in many-body quantum systems governed by symmetries. We start by showing a direct link between a unitary evolution with the Liouvillian and the displacement operator of appropriate generalized coherent states. This connection maps operator growth to a purely classical motion in phase space. The phase spaces are endowed with a natural information metric. We show that, in this geometry, operator growth is represented by geodesics, and Krylov complexity is proportional to a volume. This geometric perspective also provides two novel avenues toward computation of Lanczos coefficients, and it sheds new light on the origin of their maximal growth. We describe the general idea and analyze it in explicit examples, among which we reproduce known results from the Sachdev-Ye-Kitaev model, derive operator growth based on SU(2) and Heisenberg-Weyl symmetries, and generalize the discussion to conformal field theories. Finally, we use techniques from quantum optics to study operator evolution with quantum information tools such as entanglement and Renyi entropies, negativity, fidelity, relative entropy, and capacity of entanglement.
Nielsen's geometric approach offers a powerful framework for quantifying the complexity of unitary transformations. In this formulation, complexity is defined as the length of the minimal geodesic in a suitably constructed geometric space associated with the Lie group of relevant operators. Despite its conceptual appeal, determining geodesic distances on Lie group manifolds is generally challenging, and existing treatments often rely on perturbative expansions in the structure constants. In this work, we circumvent these limitations by employing a finite-dimensional matrix representation of the generators, which enables an exact computation of the geodesic distance and hence a precise determination of the complexity. We focus on the
su(1,1) Lie algebra, relevant for quantum scalar fields evolving on homogeneous and isotropic cosmological backgrounds. The resulting expression for the complexity is applied to de Sitter spacetime as well as to asymptotically static cosmological models undergoing contraction or expansion.
This paper proves the polynomial equivalence of a broad class of definitions of quantum computational complexity. We study right-invariant metrics on the unitary group—often called `complexity geometries' following the definition of quantum complexity proposed by Nielsen—and delineate the equivalence class of metrics that have the same computational power as quantum circuits. Within this universality class, any unitary that can be reached in one metric can be approximated in any other metric in the class with a slowdown that is at-worst polynomial in the length and number of qubits and inverse-polynomial in the permitted error. We describe the equivalence classes for two different kinds of error we might tolerate: Killing-distance error, and operator-norm error. All metrics in both equivalence classes are shown to have exponential diameter; all metrics in the operator-norm equivalence class are also shown to give an alternative definition of the quantum complexity class BQP. My results extend those of Nielsen et al., who in 2006 proved that one particular metric is polynomially equivalent to quantum circuits. The Nielsen et al. metric is incredibly highly curved. I show that the greatly enlarged equivalence class established in this paper also includes metrics that have modest curvature. I argue that the modest curvature makes these metrics more amenable to the tools of differential geometry, and therefore makes them more promising starting points for Nielsen's program of using differential geometry to prove complexity lowerbounds. In a previous paper my collaborators and I—inspired by the UV/IR decoupling that happens in the phenomenon of renormalization—conjectured that high- dimensional metrics that look very different at short scales will often nevertheless give rise at long scales to the same emergent effective geometry. The results of this paper provide evidence for those conjectures, since many complexity metrics that have radically different penalty factors and therefore radically different short- distance properties are shown to belong to the same long-distance equivalence class.
Nielsen \cite{Nielsen05} recently asked the following question: "What is the minimal size quantum circuit required to exactly implement a specified
-qubit unitary operation
U, without the use of ancilla qubits?" Nielsen was able to prove that a lower bound on the minimal size circuit is provided by the length of the geodesic between the identity
I and
U, where the length is defined by a suitable Finsler metric on
SU(2n). We prove that the minimum circuit size that simulates
U is in linear relation with the geodesic length and simulation parameters, for the given Finsler structure
F. As a corollary we prove the highest lower bound of $O(\frac{% n^{4}}{p}d_{F_{p}}^{2}(I,U)L_{F_{p}}(I,\tilde{U})) $and the lowest upper bound of
Ω(n4dFp3(I,U)), for the standard simulation technique. Therefore, our results show that by standard simulation one can not expect a better then
n2 times improvement in the upper bound over the result from Nielsen, Dowling, Gu and Doherty \cite{Nielsen06}. Moreover, our equivalence result can be applied to the arbitrary path on the manifold including the one that is generated adiabatically.