Srinivasan Arunachalam, Sergey Bravyi, et al.
QIP 2023
We consider a family of quantum spin systems which includes, as special cases, the ferromagnetic XY model and ferromagnetic Ising model on any graph, with or without a transverse magnetic field. We prove that the partition function of any model in this family can be efficiently approximated to a given relative error ϵ using a classical randomized algorithm with runtime polynomial in ϵ-1, system size, and inverse temperature. As a consequence, we obtain a polynomial time algorithm which approximates the free energy or ground energy to a given additive error. We first show how to approximate the partition function by the perfect matching sum of a finite graph with positive edge weights. Although the perfect matching sum is not known to be efficiently approximable in general, the graphs obtained by our method have a special structure which facilitates efficient approximation via a randomized algorithm due to Jerrum and Sinclair.
Srinivasan Arunachalam, Sergey Bravyi, et al.
QIP 2023
Sergey Bravyi, David Gosset, et al.
Science
Srinivasan Arunachalam, Sergey Bravyi, et al.
TQC 2022
Sergey Bravyi, Robert König
Commun. Math. Phys.