Theory of Real Time Krylov Subspace Diagonalization for Quantum Computing Algorithms*

Here we explore the theoretical and numerical aspects of a generalized Krylov subspace method where the underlying Krylov subspace is built through parameterized real time evolution. We establish an exponential bound on the convergence of the spectral approximation for a gapped target operator. Even in the single step limit, we find that the overlap of approximated low-lying eigenstates with the high energy sector of the operator spectrum undergoes a signature suppression due to favorable cancellation of time evolved phases. As the number of steps increases, phase cancellation gives rise to persistently growing features in the overlap and we show that the convergence of our spectral approximation has a native dependence on the size of spectral gap. For implementation efficiency, we compare the performances of real time evolution with fixed and updated references separately, where optimal time parametrization is examined and analyzed. We also consider the performance when stochasticity gets cast to our target operator via the form of spectral statistics. To demonstrate the practicality of such real time evolution, we discuss application of the scheme to fundamental problems in quantum computation such as unstructured searches and electronic structure predictions for strongly correlated systems.