Improved sample-based quantum diagonalization via randomized Hamiltonian simulation

Quantum computing has emerged as a new computing paradigm capable of solving problems that have unfavorable scaling on classical computers. Quantum chemistry represents one of the main and most impactful avenues for applications of these new machines. However, the current landscape of algorithms suffers from a fundamental roadblock created by the trade-off between the limited resources of today's noisy quantum hardware and algorithmic performance guarantees. In this work, we introduce an algorithm that allows this trade-off to be flexibly adjusted based on the available resources, offering both theoretical robustness and practical compatibility with near-term hardware. Our approach, based on a combination of Hamiltonian simulation via qDRIFT and the recently introduced scheme of sample-based quantum diagonalization, paves the way for enabling efficient quantum chemistry simulations on quantum computers and Krylov-based quantum diagonalization approaches for chemistry.