Efficient Algorithms for Approximating Quantum Partition Functions
April 27, 2020
Tyler Helmuth and I have just uploaded to arXiv our paper "Efficient Algorithms for Approximating Quantum Partition Functions". In this paper we establish a polynomial-time approximation algorithm for partition functions of quantum spin models at high temperature.
We are interesting in the following function.
We shall assume that \(\|\Phi(e)\|\leq1\) for every \(e \in E\), where \(\|\;\cdot\;\|\) denotes the operator norm. Note that this is always possible by a rescaling of \(\beta\). Our main result is the following.
Our algorithm is based on combining the abstract cluster expansion for quantum spin systems of Netočný and Redig with the algorithmic framework of Helmuth, Perkins, and Regts. Note that the condition \(|\beta|=O\left(\frac{1}{\Delta}\right)\) is optimal under the assumption that \(\text{RP}\neq\text{NP}\) due to the hardness results of Sly and Sun and Galanis, Štefankovič, and Vigoda. These results concern real values of \(\beta\); however it is possible to obtain similar complexity transitions for complex \(\beta\) from \(\text{P}\) to \(\text{BQP-hard}\) and \(\text{P}\) to \(\text{#P-hard}\).
Similar algorithms have previously been obtained by related methods: for \(|\beta|\leq(10e^2\Delta)^{-1}\) with quasi-polynomial runtime [Harrow, Mehraban, and Soleimanifar] and for \(|\beta|\leq(16e^3\Delta)^{-1}\) with polynomial runtime [Kuwahara, Kato, and Brandão]. While our results represent a slight improvement in the bound for \(\beta\), we view our main contribution as being the simplicity of our analysis.