Algorithmic Cluster Expansions for Quantum Problems

Abstract

We establish a general framework for developing approximation algorithms for a class of counting problems. Our framework is based on the cluster expansion of abstract polymer models formalism of Kotecký and Preiss. We apply our framework 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. Further, we 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. Finally, we show that our algorithmic condition is almost optimal for expectation values and optimal for thermal expectation values in the sense of zero freeness.

arXiv comment22 pages, 0 figures, published version

References in corpus (11)

• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Cluster expansion for abstract polymer models. New bounds from an old approach
• Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature
• Classical algorithms for quantum mean values
• Classical simulation of short-time quantum dynamics
• On the complexity of quantum partition functions
• Efficient Algorithms for Approximating Quantum Partition Functions
• Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs
• Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature

Cited by in corpus (6)

• Fault-tolerant quantum algorithms for quantum molecular systems: A survey
• Clustering theorem in 1D long-range interacting systems at arbitrary temperatures
• Provably Efficient Simulation of 1D Long-Range Interacting Systems at Any Temperature
• High-temperature partition functions and classical simulatability of long-range quantum systems
• Gibbs state sampling via cluster expansions
• Efficient Algorithms for Weakly-Interacting Quantum Spin Systems