Classical bounds on quantum partition functions

Barry Simon A

Bingyu Cui

Filippo Cesi

The author considers a class of spin systems whose single-site configuration space is an orbit of a representation of a compact Lie group G. For these models the author gets upper and lower bounds to the quantum partition function in terms of two classical partition functions. If a certain group-theoretic condition is satisfied, then these bounds allow one to prove the convergence of a suitable sequence of quantum partition functions to the 'corresponding' classical one. This condition is shown to be satisfied, in particular, for the D-component rotators when D is odd. The result could be useful for the extension of the Lee-Yang theorem to such models.

L.R. Evangelista, Luís Carlos Malacarne, R.S. Mendes

Keisuke Fujii, Tomoyuki Morimae

Instantaneous quantum polynomial-time (IQP) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal. Nevertheless, it has been shown that if there is a classical algorithm that can simulate IQP efficiently, the polynomial hierarchy collapses to the third level, which is highly implausible. However, the origin of the classical intractability is still less understood. Here we establish a relationship between IQP and computational complexity of calculating the imaginary-valued partition functions of Ising models. We apply the established relationship in two opposite directions. One direction is to find subclasses of IQP that are classically efficiently simulatable by using exact solvability of certain types of Ising models. Another direction is applying quantum computational complexity of IQP to investigate (im)possibility of efficient classical approximations of Ising partition functions with imaginary coupling constants. Specifically, we show that a multiplicative approximation of Ising partition functions is #P-hard for almost all imaginary coupling constants even on planar lattices of a bounded degree.

Penghui Yao, Yitong Yin, Xinyuan Zhang

Zero-free based algorithm is a major technique for deterministic approximate counting. In Barvinok's original framework[Bar17], by calculating truncated Taylor expansions, a quasi-polynomial time algorithm was given for estimating zero-free partition functions. Patel and Regts[PR17] later gave a refinement of Barvinok's framework, which gave a polynomial-time algorithm for a class of zero-free graph polynomials that can be expressed as counting induced subgraphs in bounded-degree graphs. In this paper, we give a polynomial-time algorithm for estimating classical and quantum partition functions specified by local Hamiltonians with bounded maximum degree, assuming a zero-free property for the temperature. Consequently, when the inverse temperature is close enough to zero by a constant gap, we have polynomial-time approximation algorithm for all such partition functions. Our result is based on a new abstract framework that extends and generalizes the approach of Patel and Regts.