Analysis of quantum Krylov algorithms with errors

Abstract: This work provides an error analysis of quantum Krylov algorithms based on real-time evolutions, subject to generic errors in the outputs of the quantum circuits. We establish a collective noise rate to summarize those errors, and prove that the resulting errors in the ground state energy estimates are leading-order linear in that noise rate. This resolves a misalignment between known numerics, which exhibit this linear scaling, and prior theoretical analysis, which only provably obtained square-root scaling. Our main technique is expressing generic errors in terms of an effective target Hamiltonian studied in an effective Krylov space. These results provide a theoretical framework for understanding the main features of quantum Krylov errors.