Quantum Markov chain Monte Carlo method with programmable quantum simulators

In this work, we present a quantum Markov chain algorithm for many-body systems that utilizes a special phase of matter known as the Many-Body Localized (MBL) phase. We show how the properties of the MBL phase enable one to address the conditions for ergodicity and sampling from distributions of quantum states. We demonstrate how to exploit the thermalized-to-localized transition to tune the acceptance rate of the Markov chain, and apply the algorithm to solve a range of combinatorial optimization problems of quadratic order and higher. The algorithm can be implemented on any quantum processing unit capable of simulating the Floquet dynamics of a one-dimensional Ising chain with nearest-neighbor interactions, providing a practical way of sampling from thermal distributions of Hamiltonians that cannot be natively implemented on the quantum hardware.