Efficient quantum Monte Carlo algorithm on quantum computers with robust Matchgate shadows*

Solving the electronic structure problem of molecules and solids to high accuracy is one of the big challenges in quantum chemistry and condensed matter physics. The rapid emergence and development of quantum computers offer a promising route to systematically tackle this problem. Recent work by Huggins, et al [1] introduced a hybrid quantum-classical quantum Monte Carlo (QC-QMC) algorithm using Clifford classical shadows to compute the ground state of a Fermionic Hamiltonian. This approach displayed inherent noise resilience and the potential for improved accuracy compared to its purely classical counterpart. Nevertheless, the use of Clifford shadows introduces an exponentially scaling post-processing cost. In this work, we investigate an improved QC-QMC scheme utilizing the recently developed Matchgate shadows technique [2], which removes the exponential bottleneck. We also formulate a robust variant of Matchgate shadows, with connections to randomized benchmarking. Finally, we observe that even without the robust protocol, the use of Matchgate shadows is still noise resilient-but with a much more subtle origin than in the case of Clifford classical shadows. Our work strengthens the outlook for the QC-QMC approach, and the viability of achieving practical quantum advantage in the NISQ regime.