Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs

Abstract

We study the problem of approximating the Ising model partition function with complex parameters on bounded degree graphs. We establish a deterministic polynomial-time approximation scheme for the partition function when the interactions and external fields are absolutely bounded close to zero. Furthermore, we prove that for this class of Ising models the partition function does not vanish. Our algorithm is based on an approach due to Barvinok for approximating evaluations of a polynomial based on the location of the complex zeros and a technique due to Patel and Regts for efficiently computing the leading coefficients of graph polynomials on bounded degree graphs. Finally, we show how our algorithm can be extended to approximate certain output probability amplitudes of quantum circuits.

arXiv comment12 pages, 0 figures, published version

References in corpus (13)

• Characterizing Quantum Supremacy in Near-Term Devices
• Simulating quantum computation by contracting tensor networks
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Instantaneous Quantum Computation
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Architectures for quantum simulation showing a quantum speedup
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Quantum algorithms for classical lattice models
• Low Depth Quantum Circuits for Ising Models

Cited by in corpus (6)

• Classical algorithms for quantum mean values
• Fisher zeros and correlation decay in the Ising model
• Efficient Algorithms for Approximating Quantum Partition Functions
• Algorithmic Cluster Expansions for Quantum Problems
• Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature
• Quantum estimation bound of Gaussian matrix permanent