Algorithmic Cluster Expansions for Quantum Problems

June 16, 2023

Romy Minko and I have just uploaded to arXiv our paper "Algorithmic Cluster Expansions for Quantum Problems". In this paper we establish a general framework for developing approximation algorithms and hardness of approximation results for a class of counting problems. By applying this framework, we are able to obtain efficient approximation algorithms and hardness of approximation results for several quantum problems under certain algorithmic conditions.

Our algorithmic framework is based on the cluster expansion of abstract polymer models formalism of Kotecký and Preiss. We consider polymers that are connected subgraphs of bounded-degree bounded-rank multihypergraphs with compatibility relations defined by vertex disjointness. The key insight underlying our framework is that when the polymer weights decay sufficiently fast, computing the truncated cluster expansion to sufficiently high order allows us to obtain a multiplicative approximation to the abstract polymer model partition function. Our framework can be viewed as a straightforward generalisation of the framework of Helmuth, Perkins, and Regts, and Borgs et al. from the case of bounded-degree graphs to bounded-degree bounded-rank multihypergraphs.

By applying this framework, we are able to obtain efficient algorithms for (1) approximating probability amplitudes of a class of quantum circuits close to the identity, (2) approximating expectation values of a class of quantum circuits with operators close to the identity, (3) approximating partition functions of a class of quantum spin systems at high temperature, and (4) approximating thermal expectation values of a class of quantum spin systems at high temperature with positive-semidefinite operators. Our approach offers a simpler and sharper analysis compared to existing algorithms.

Our hardness of approximation framework is based on reductions from the Ising model partition function. We apply this framework to obtain hardness of approximation results for approximating probability amplitudes of quantum circuits and partition functions of quantum spin systems. This establishes a computational complexity transition for these problems and shows that our algorithmic conditions are optimal under complexity-theoretic assumptions. Further, we show that our algorithmic condition is almost optimal for expectation values and optimal for thermal expectation values in the sense of zero freeness.