Ryan Mann

Quantum Physics, Complexity Theory, & Combinatorics

Efficient Algorithms for Approximating Quantum Partition Functions

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.

Definition 1 (Quantum spin system)   A quantum spin system is modelled by a graph \(G=(V,E)\). At each vertex \(v\) of \(G\) there is a finite-dimensional Hilbert space \(\mathcal{H}_v\). The Hilbert space on the graph is given by \(\mathcal{H}_G:=\bigotimes_{x \in X}\mathcal{H}_x\). An interaction \(\Phi\) assigns a self-adjoint operator \(\Phi(e)\) on \(\mathcal{H}_e:=\bigotimes_{v \in e}\mathcal{H}_v\) to each edge \(e\) of \(G\). The Hamiltonian on \(G\) is defined by \(H_G:=\sum_{e \in E(G)}\Phi(e)\).

We are interesting in the following function.

Definition 2 (Quantum partition function)   The quantum partition function \(Z_G(\beta)\) at inverse temperature \(\beta\) is defined by $$Z_G(\beta) := \text{Tr}\left[e^{-\beta H_G}\right].$$

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.

Theorem 1   Fix \(\Delta\in\mathbb{Z}^+\). There is a fully polynomial-time approximation scheme for the partition function \(Z_G(\beta)\) for all graphs \(G\) of maximum degree at most \(\Delta\) and all complex numbers \(\beta\) such that \(|\beta|\leq\frac{1}{e^4\Delta}\).

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.