Ryan Mann

Quantum Physics, Complexity Theory, & Combinatorics

Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature

Tyler Helmuth and I have just uploaded to arXiv our paper "Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature". In this paper we establish an efficient approximation algorithm for the partition functions of a class of quantum spin systems at low temperature, which can be viewed as stable quantum perturbations of classical spin systems.

These spin systems can be informally introduced as quantum spin systems with Hamiltonians \(H=H_\Phi+\lambda H_\Psi\) where \(H_\Phi\) is diagonal in a basis indexed by a classical spin system, \(H_\Psi\) is local, and \(|\lambda|\) is small. The adjective stable implies that the set \(\Xi\) of classical ground states (i.e., when \(\lambda=0\)) is also the set of ground states for small \(|\lambda|>0\). Let \(Z^{\varphi}_G(\beta,\lambda)\) be the partition function of such a model on a finite subgraph \(G\) of \(\mathbb{Z}^\nu\) with boundary condition \(\varphi\in\Xi\). Our main result may be stated informally as follows.

Theorem 1   Let \(G\) be a finite induced subgraph of \(\mathbb{Z}^\nu\). There exists constants \(\beta^\star\) and \(\lambda^\star\), such that, for all \(\varphi\in\Xi\), all \(\beta\geq\beta^\star\), and all \(|\lambda|\leq\lambda^\star\), there is an efficient algorithm for approximating the partition function \(Z^{\varphi}_G(\beta,\lambda)\).

Our algorithm is based on combining the contour representation of quantum spin systems of this type due to Borgs, Kotecký, and Ueltschi with the algorithmic framework developed by Helmuth, Perkins, and Regts, and Borgs et al.