  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.
