Testing, analysis, and refinement of the quantum Metropolis algorithm

The classical Metropolis algorithm has been adapted into a quantum algorithm [Temme et al., Nature 471, 87 (2011)] with three important drawbacks: (1) long-time Hamiltonian evolution is needed for precise phase estimation of system energies, (2) many repetitions are needed to successfully reject a Metropolis update with a low failure rate, and (3) thermal-state observables are not measured during the thermalization process. We present a revised quantum Metropolis algorithm that partially mitigates these drawbacks as evidenced by a combination of numerical experiments and theoretical analysis.