  We propose a class of randomized quantum Krylov diagonalization (rQKD)
algorithms capable of solving the eigenstate estimation problem with modest
quantum resource requirements. Compared to previous real-time evolution quantum
Krylov subspace methods, our approach expresses the time evolution operator,
$e^{-i\hat{H} \tau}$, as a linear combination of unitaries and subsequently
uses a stochastic sampling procedure to reduce circuit depth requirements.
While our methodology applies to any Hamiltonian with fast-forwardable
subcomponents, we focus on its application to the explicitly double-factorized
electronic-structure Hamiltonian. To demonstrate the potential of the proposed
rQKD algorithm, we provide numerical benchmarks for a variety of molecular
systems with circuit-based statevector simulators, achieving ground state
energy errors of less than 1~kcal~mol$^{-1}$ with circuit depths orders of
magnitude shallower than those required for low-rank deterministic
Trotter-Suzuki decompositions.
