Quantum Algorithm for Ground State Preparation of Ising Models with Applications to Optimization

The Ising model, a cornerstone in statistical mechanics, is a fundamental spin model with diverse applications. It accurately describes the magnetization of both ferromagnetic and antiferromagnetic materials, and computing its ground and thermal state properties helps us understand exotic magnetic phases such as spin glasses. Additionally, complex optimization problems like the max-cut and traveling salesman problems can be mapped onto an Ising model, where finding its ground state would solve the optimization problem. However, due to the exponential size of the Hilbert space, obtaining either ground or thermal state expectation values is computationally challenging on classical computers, except in certain special cases. In this study, we introduce an Ising solver quantum algorithm that efficiently obtains ground state expectation values with quantum resources that scale polynomially with the system size. The circuit structure of our algorithm further reduces the quantum resources compared to current existing methods. We demonstrate the effectiveness of our Ising solver by simulating the Ising model on a triangular lattice with frustration, as well as solving instances of the max-cut and traveling salesman problems of various sizes.