Polynomial-Time Approximation of Zero-Free Partition Functions

Penghui Yao , Yitong Yin and Xinyuan Zhang State Key Laboratory for Novel Software Technology, Nanjing University, 163 Xianlin Avenue, Nanjing, Jiangsu Province, China. E-mails: [email protected], [email protected], [email protected]

Abstract.

Zero-free based algorithm is a major technique for deterministic approximate counting. In Barvinok’s original framework [4], by calculating truncated Taylor expansions, a quasi-polynomial time algorithm was given for estimating zero-free partition functions. Patel and Regts [29] 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.

1. Introduction

Let $\Omega=[q]^{V}$ be a finite space of configurations, where $V$ is a set of $n$ variables. Let $H_{1},\ldots,H_{m}$ be a collection of local constraints, where each $H_{j}:\Omega\rightarrow\mathbb{C}$ is independent of all but a small subset of variables, and let $H=\sum_{j=1}^{m}H_{j}$ . The partition function of the given system is defined by

(1)

\displaystyle Z_{H}(\beta)=\sum_{\sigma\in\Omega}\exp(-\beta\cdot H(\sigma)),

where the parameter $\beta$ is usually called the inverse temperature.

The computational complexity of partition functions is one of the central topics in theoretical computer science, which has been found wide applications in computational counting, combinatorics, and statistical physics. To date, numerous algorithms as well as hardnesses of approximation for the partition functions of various systems have been established, to list a few [20, 33, 14, 21, 39, 38, 32, 35, 24, 37, 17, 25, 7, 11, 8]. The most important question here is, what property captures the approximability of partition functions.

It is widely believed that for various classes of partition functions of interests, the hardness of approximation is captured by the locus of complex zeros. The study of the locus of complex zeros has a rich history in statistical physics, for example, in the famous Lee-Yang theorem [27]. In computer science, the absence of complex zeros may imply efficient approximation algorithms for partition functions [4, 29, 31, 19, 26, 25, 30, 10, 15, 16, 18, 36, 9, 12]. This line of research was initiated by Barvinok’s pioneering works [1, 2, 3, 4, 5], which used truncated Taylor expansions to approximate non-vanishing polynomials and established quasi-polynomial time approximations of partition functions with no complex zeros within a region. Later in a seminal work of Patel and Regts [29], this quasi-polynomial running time was improved to polynomial time for a class of graph polynomials which can be expressed as induced subgraph sums in graphs of constant maximum degree. And this polynomial-time framework was further extended by Liu, Sinclair and Srivastava [26] to hypergraph 2-spin systems with no complex-zeros for the external field.

For the quantum version, several (classical) algorithms have been proposed, including [22, 18, 28], to estimate the quantum generalization of the partition function (1) where $H$ is the Hamiltonian. Yet an important question remains to answer is the polynomial-time approximability of the quantum or classic partition function in the form of (1) assuming its zero-freeness.

1.1. Our results.

We show the polynomial-time approximability of zero-free quantum partition functions.

Let $V$ be a set of $n$ sites (also called vertices or particles). Let $q\geq 2$ be an integer. Throughout the paper, we assume that each site $u\in V$ is associated with a $q$ -dimensional Hilbert space $\mathcal{V}_{u}$ , and let $\mathcal{V}=\bigotimes_{u\in V}\mathcal{V}_{u}$ . A Hamiltonian $H$ is a Hermitian matrix in $\mathcal{V}$ . The support of a Hamiltonian $H$ , denoted by $\mathrm{supp}(H)$ , is the minimal set of sites on which $H$ acts non-trivially. Given a Hamiltonian $H$ , $\exp(H)$ is defined by $\exp(H)=\sum_{\ell=1}^{\infty}\frac{1}{\ell!}H^{\ell}$ , and the partition function $Z_{H}:\mathbb{C}\to\mathbb{C}$ induced by $H$ is defined as follows:

(2)

\displaystyle\forall\beta\in\mathbb{C},\quad Z_{H}(\beta)\triangleq\mathbf{Tr}\left[\exp(-\beta H)\right].

We are interested in partition functions induced by local Hamiltonians with bounded maximum degrees.

Definition 1.1 (local Hamiltonian).

A Hamiltonian $H\in\mathcal{V}$ is said to be $k$ -local if $H$ can be expressed as

H=\sum_{j=1}^{m}H_{j},

where each $H_{j}$ acts non-trivially on at most $k$ sites, i.e. $\left|\mathrm{supp}(H_{j})\right|\leq k$ . A Hamiltonian $H\in\mathcal{V}$ called a $(k,d)$ -Hamiltonian if $H$ is $k$ -local and for every $v\in V$ , $\deg(v)\triangleq\left|\left\{j\mid v\in\mathrm{supp}(H_{j})\right\}\right|\leq d$ .

Notice that if all $H_{j}$ ’s are diagonal, then $H$ is diagonal as well. The quantum partition function $Z_{H}(\beta)$ then degenerates to the classical partition function defined in (1). Indeed, in such diagonal case we have

Z_{H}(\beta)=\sum_{\sigma\in[q]^{V}}\exp(-\beta\cdot H(\sigma)),

where $H(\sigma)=\sum_{j=1}^{m}H_{j}(\sigma)$ and $H_{j}(\sigma)$ represents the $\sigma$ -th diagonal entry of $H_{j}$ . Since each $H_{j}$ is diagonal and acts non-trivially on subset $\mathrm{supp}(H_{j})$ of at most $k$ sites, the value of $H_{j}(\sigma)$ is determines by the variables in $\mathrm{supp}(H_{j})$ . Hence the $Z_{H}(\beta)$ above is precisely the classical partition function defined in (1).

The quantum partition functions encode rich information about quantum systems, e.g. the free energy and ground state energy. Meanwhile, the non-diagonal property, especially the non-commutativity of multiplication for non-diagonal matrices, imposes great challenges for the computation of partition functions.

We prove the following zero-free based approximability of quantum partition functions.

Theorem 1.2 (Theorem 3.6, informal).

Let $\Omega\subseteq\mathbb{C}$ be a “well-shaped” complex region (formalized by Definition 3.3) and $k,d\geq 1$ be constants. There is a deterministic algorithm which takes a $(k,d)$ -Hamiltonian $H$ on $n$ sites and a $\beta$ from interior of $\Omega$ as input, and outputs an estimation of the quantum partition function $Z_{H}(\beta)$ in polynomial time in $n$ , if $Z_{H}$ satisfies the zero-free property such that $\left|\log Z_{H}\right|\leq\mathrm{poly}(n)$ on $\Omega$ .

The formal statement (Theorem 3.6) is more general: it further takes into account the measurement of the quantum system. Such generalization may encode broader classes of partition functions, e.g. the ones with external fields, and also enable sampling from Gibbs state. Following a recent major advance for quantum zero-freeness of Harrow et al [18], we give concrete applications (in Section 5), namely, polynomial-time algorithms for approximating the quantum partition function (Theorem 5.1) and sampling from the Gibbs state (Theorem 5.3) in a high-temperature regime (where $\beta$ is close to zero by a constant gap), improving the quasi-polynomial-time algorithms in [18]. A polynomial-time approximation of the quantum partition functions in a slightly bigger high-temperature regime was obtained in [28] using the cluster expansion technique [19], by transforming the quantum partition function to a polymer model and showing the convergence of the cluster expansion assuming high temperature.

We prove polynomial-time approximability of the quantum partition function directly from a black-box property of zero-freeness, without further restricting the parameters of the model. Moreover, our result is proved in a new abstract framework, namely, functions specified by abstract neighborhood structures called dependency graphs. We prove the following general result.

Theorem 1.3 (Theorem 3.5, informal).

Suppose that functions $\{f_{G}\}$ specified by dependency graphs $G$ satisfies certain boundedness property of its Taylor coefficients (formalized in Definition 3.1). Let $\Omega\subseteq\mathbb{C}$ be a “well-shaped” complex region. There is a deterministic algorithm which takes a dependency graph $G$ of $O(1)$ max-degree and $x$ from the interior of $\Omega$ as input, and outputs an estimation of $f_{G}(x)$ in polynomial time in size $n$ of $G$ , if $f_{G}(0)$ is easy to compute and $f_{G}$ satisfies the zero-free property such that $\left|\log f_{G}\right|\leq\mathrm{poly}(n)$ on $\Omega$ .

The abstract framework is described in Definition 3.1. As verified in Section 3, our framework subsumes previous polynomial-time frameworks for zero-free based algorithms ([29] and [26]) as special cases, and more importantly, it extends the previous frameworks to become compatible with infinite-degree polynomials and non-commutative systems, which are crucial for quantum partition functions.

2. Preliminaries

2.1. Local Hamiltonians

Given a Hamiltonian $H$ in $\mathcal{V}$ , we use $\mathrm{supp}(H)$ to denote the support of $H$ , the minimal set of sites on which $H$ acts non-trivially. Formally, if $S$ is the support of $H$ , then $S$ is the minimal subset of $V$ satisfying that $H=H_{S}\otimes I_{V\setminus S}$ , where $H_{S}$ is a Hamiltonian in the space $\bigotimes_{v\in S}\mathcal{V}_{v}$ and $I_{V\setminus S}$ is the identity matrix in the space $\bigotimes_{v\in V\setminus S}\mathcal{V}_{v}$ . Readers may refer to [13, 23] for a thorough treatment.

2.2. Basic facts about complex functions

A complex-valued function $f:\Omega\rightarrow\mathbb{C}$ defined on a complex domain $\Omega\subseteq\mathbb{C}$ is called holomorphic if for every point $z\in\Omega$ , the complex derivative exists in a neighborhood of $z$ . A holomorphic function $f:\Omega\rightarrow\mathbb{C}$ is infinitely differentiable and equals locally to its Taylor series. A biholomorphic function is a bijective holomorphic function whose inverse is also holomorphic Furthermore, a function $f:\mathbb{C}\rightarrow\mathbb{C}$ is called an entire function if it is holomorphic on $\mathbb{C}$ . A region $\Omega\subseteq\mathbb{C}$ is simply connected if $\overline{\mathbb{C}}\setminus\Omega$ is connected, where $\overline{\mathbb{C}}=\mathbb{C}\cup\{\infty\}$ denotes the extended complex plane.

The logarithm of a complex-valued function $f$ , denoted by $g=\log f$ , is a function such that $f(z)=\mathrm{e}^{g(z)}$ . For holomorphic function $f:\Omega\rightarrow\mathbb{C}\setminus\{0\}$ on simply connected region $\Omega\subseteq\mathbb{C}$ , such $\log f$ always exists (see e.g. [34]). Specifically, for an arbitrarily fixed pair $z_{0},c_{0}\in\mathbb{C}$ satisfying that $f(z_{0})=\mathrm{e}^{c_{0}}$ , we have

(3)

\displaystyle\forall z\in\Omega,\quad\log f(z)=\int_{P}\frac{f^{\prime}(w)}{f(w)}\,dw\ +c_{0},

where $P$ is an arbitrary path in $\Omega$ connecting $z$ and $z_{0}$ . Throughout the paper, we mainly deal with such holomorphic $f$ on simply connected $\Omega$ that $0\in\Omega$ and $f(0)\in\mathbb{R}^{+}$ . For such case, the definition of $\log f$ is uniquely determined by $z_{0}=0$ and the real $c_{0}=\ln(f(0))$ .

2.3. Approximation of non-vanishing function

We now recap the polynomial interpolation technique of Barvinok [4] to estimate values of non-vanishing holomorphic functions.

For $b\in\mathbb{R}^{+}$ , we use $\mathbb{D}_{b}$ to denote the complex disc of radius $b$ centered at the origin. Formally,

\mathbb{D}_{b}=\left\{z\in\mathbb{C}|\left|z\right|<b\right\}.

In particular, let $\mathbb{D}=\mathbb{D}_{1}$ denote the unit disc.

For $\beta\in\mathbb{C}$ and $\delta\in\mathbb{R}^{+}$ , we use $S_{\beta,\gamma}$ to denote $\delta$ -strip of interval $[0,\beta]=\{t\beta\mid t\in[0,1]\}$ . Formally,

S_{\beta,\gamma}=\left\{z\in\mathbb{C}\mid\mathrm{dist}(z,[0,\beta])<\delta\right\}.

where $\mathrm{dist}(\cdot,\cdot)$ denotes Euclidean distance. It is clear that both $\mathbb{D}_{b}$ and $S_{\beta,\gamma}$ are simply connected.

The following is the key property of zero-freeness for complex-valued functions.

Definition 2.1 (zero-freeness).

Let $M>0$ be finite positive real. A holomorphic function $f$ on a simply connected region $\Omega\subseteq\mathbb{C}$ is $M$ -zero-free on $\Omega$ if $\left|\log f(z)\right|\leq M$ for all $z\in\Omega$ .

Notice that the zero-freeness of $f$ on $\Omega$ implies that $f$ is non-vanishing on the same region. A definition of $\log f$ is assumed in the context when this concept is used.

For any polynomial $p\in\mathbb{C}[z]$ that does not vanish on $\mathbb{D}$ , the polynomial $p$ automatically exhibits the above zero-freeness property with a bounded gap on $\mathbb{D}_{b}$ for any $b\in(0,1)$ .

Lemma 2.2.

Let $p\in\mathbb{C}[z]$ be a polynomial of degree $d$ , and let $b\in(0,1)$ . If $p(z)\neq 0$ for all $z\in\mathbb{D}$ , then $p$ is $M$ -zero-free on $\mathbb{D}_{b}$ for $M=d\ln\frac{1}{1-b}+\left|\log p(0)\right|$ .

Proof.

Let $\zeta_{1},\zeta_{2},\ldots,\zeta_{d}\in\mathbb{C}$ denote the roots of polynomial $p$ . For any $z\in\mathbb{D}_{b}$ ,

\displaystyle\left|\log p(z)\right|=\left|\log p(0)+\sum_{j=1}^{d}\log\left(1-\frac{z}{\zeta_{j}}\right)\right|\leq\left|\log p(0)\right|-\sum_{j=1}^{d}\ln\left(1-\left|\frac{z}{\zeta_{j}}\right|\right)\leq\left|\log p(0)\right|+d\ln\frac{1}{1-b}.

The two inequalities are due to that all $\left|\zeta_{j}\right|>1$ since $p(z)\neq 0$ for all $z\in\mathbb{D}$ . ∎

The following lemma of Barvinok says that any holomorphic function on $\mathbb{D}$ can be approximated by its truncated Taylor expansion if it is zero-free on $\mathbb{D}$ .

Lemma 2.3 ([4]).

Let $g:\mathbb{D}\to\mathbb{C}$ be holomorphic and $M>0$ . If $|g(z)|\leq M$ for all $z\in\mathbb{D}$ , then for any $z\in\mathbb{D}$ and any $m\in\mathbb{N}^{+}$ ,

\displaystyle\left|g(z)-\sum_{k=0}^{m}\frac{g^{(k)}(0)}{k!}z^{k}\right|\leq\frac{M}{\delta}(1-\delta)^{m+1},

where $\delta=\mathrm{dist}(z,\partial\mathbb{D})$ represents the Euclidean distance between $z$ and the boundary of unit disc.

In particular, when the above lemma is applied to $g=\log f$ for some holomorphic $f:\mathbb{D}\to\mathbb{C}\setminus\{0\}$ , one can obtain a multiplicative approximation of $f$ on $\mathbb{D}$ assuming zero-freeness of $f$ on $\mathbb{D}$ . To make such approximation effective, we should be able to compute the Taylor coefficients of $g=\log f$ .

The following Newton’s identity relates the Taylor coefficients of $g=\log f$ to those of $f$ .

Lemma 2.4 (Newton’s identity).

Let $f(z)=\sum_{k=0}^{+\infty}f_{k}z^{k}$ be an entire function such that $f(z)\neq 0$ for all $z\in\mathbb{D}$ . Then $g(z)=\log f(z)=\sum_{k=0}^{+\infty}g_{k}z^{k}$ is well-defined on $\mathbb{D}$ , and

ng_{n}=nf_{n}-\sum_{k=1}^{n-1}kg_{k}f_{n-k}.

Proof.

By the definition of $g=\log f$ , we have $f^{\prime}=g^{\prime}f$ . Therefore,

\displaystyle nf_{n}=\frac{1}{(n-1)!}f^{(n)}(0)=\frac{1}{(n-1)!}\sum_{k=0}^{n-1}\binom{n-1}{k}f^{(k)}(0)g^{(n-k)}(0)=\sum_{k=0}^{n-1}(n-k)g_{n-k}f_{k}=\sum_{k=1}^{n}kg_{k}f_{n-k}.

∎

When the zero-free region is not unit disc, some preprocessing is needed. The following polynomial transformation from $\mathbb{D}$ to any $S_{\beta,\gamma}$ is known.

Lemma 2.5 ([4]).

For any $\beta\in\mathbb{C}$ , $\delta\in(0,1)$ , there is an explicitly constructed polynomial $p_{\beta,\delta}$ of degree $d=d(\beta,\delta)$ satisfying

•

$p_{\beta,\delta}(0)=0$ and $p_{\beta,\delta}(1-\delta_{0})=\beta$ for some $\delta_{0}\in(0,1)$ ;
•

$p_{\beta,\delta}(\mathbb{D})\subseteq S_{\beta,\gamma}$ ;

The proof of Lemma 2.5 is deferred to Appendix A.

3. Approximation of Zero-Free Holomorphic Function

We now introduce an abstraction for partition functions, namely, multiplicative holomorphic functions specified by a class of abstract structures called dependency graphs.

A dependency graph is a vertex-labeled graph $G=(V,E,\mathcal{L})$ , where $(V,E)$ is an undirected simple graph, and $\mathcal{L}=(L_{v})_{v\in V}$ assigns each vertex $v\in V$ a label $L_{v}$ . Two labeled graphs $G=(V,E,\mathcal{L})$ and $G^{\prime}=(V^{\prime},E^{\prime},\mathcal{L}^{\prime})$ are isomorphic if there is a bijection $\phi:V\to V^{\prime}$ such that the two simple graphs $(V,E)$ and $(V^{\prime},E^{\prime})$ are isomorphic under $\phi$ and $L_{v}=L^{\prime}_{\phi(v)}$ for all $v\in V$ . Furthermore, we say that two labeled graphs $G=(V,E,\mathcal{L})$ and $G^{\prime}=(V^{\prime},E^{\prime},\mathcal{L}^{\prime})$ are disjoint if $V\cap V^{\prime}=\varnothing$ . A family $\mathcal{G}$ of dependency graphs is called downward-closed if for any $G=(V,E,\mathcal{L})\in\mathcal{G}$ and any $S\subseteq V$ we have $G[S]\in\mathcal{G}$ , where $G[S]$ stands for the subgraph of $G$ induced by subset $S\subseteq V$ preserving labels.

We use $f_{\cdot}$ to denote an operator that maps each dependency graph $G$ in $\mathcal{G}$ to an entire function $f_{G}:\mathbb{C}\to\mathbb{C}$ (i.e. $f_{G}$ is holomorphic on $\mathbb{C}$ ), such that $f_{G}$ gives the same entire function for isomorphic dependency graphs $G$ . Such an $f_{\cdot}$ is multiplicative if for any $G$ that is disjoint union of $G_{1},G_{2}$ , we have $f_{G}=f_{G_{1}}f_{G_{2}}$ .

Definition 3.1 (boundedness).

Let $\mathcal{G}$ be a downward-closed family of dependency graphs. Let $\alpha,\beta\geq 1$ . A multiplicative $f_{\cdot}$ is called $(\alpha,\beta)$ -bounded on $\mathcal{G}$ if for any $G=(V,E,\mathcal{L})\in\mathcal{G}$ , we have $f_{G}(0)\in\mathbb{R}^{+}$ and

\displaystyle f_{G}(z)=f_{G}(0)+\sum_{\ell=1}^{+\infty}\left(\sum_{S\subseteq V}\lambda_{G[S],\ell}\right)z^{\ell},

where the complex coefficients $(\lambda_{H,\ell})_{H\in\mathcal{G},\ell\in\mathbb{N}^{+}}$ are invariant for isomorphic dependency graphs $H$ , and satisfy that $\lambda_{H,\ell}\neq 0$ only if $|V_{H}|\leq\alpha\ell$ , and each $\lambda_{H,\ell}$ can be calculated within $\beta^{\ell}\cdot\mathrm{poly}(\ell)$ time.

For $(\alpha,\beta)$ -bounded $f_{\cdot}$ , it always holds that $f_{G}(0)\in\mathbb{R}^{+}$ . Then we always fix the definition of $\log f$ to be the one uniquely defined by Eq.(3) with $z_{0}=0$ and $c_{0}=\ln(f(0))$ being real. Such $\log f$ is well defined within a neighborhood of the origin.

As we will formally verify in Section 3.2, this notion of bounded holomorphic functions specified by dependency graphs generalizes the bounded induced graph counting polynomials (BIGCPs) of Patel and Regts [29]. A major difference here is that $f_{G}$ may not be a polynomial of finite degree.

We show that for $(\alpha,\beta)$ -bounded $f_{\cdot}$ , the approach of Patel and Regts [29] based on Newton’s identity and local enumeration of connected subgraphs can efficiently compute Taylor coefficients of $\log f_{G}$ , even though the function $f_{G}$ can now encode problems far beyond counting subgraphs.

Theorem 3.2 (efficient coefficient computing).

Let $\mathcal{G}$ be a downward-closed family of dependency graphs, and $f_{\cdot}$ be $(\alpha,\beta)$ -bounded on $\mathcal{G}$ for $\alpha,\beta\geq 1$ . There exists a deterministic algorithm which given any $G\in\mathcal{G}$ and $\ell\in\mathbb{N}^{+}$ as input, outputs the $\ell$ -th coefficient of the Taylor series of $\log f_{G}$ at the origin in time $\widetilde{O}\left(n(8\mathrm{e}\beta\Delta)^{\alpha\ell}\right)$ , where $n$ is the number of vertices, $\Delta$ is the maximum degree of $G$ , and $\widetilde{O}(\cdot)$ hides $\mathrm{poly}(\Delta,\ell,\log(n))$ .

The theorem will be proved in Section 4.

Due to Riemann mapping theorem in complex analysis, for any proper and simply connected region $\Omega\subset\mathbb{C}$ and any point $z_{0}\in\Omega$ , there is a biholomorphic function $h$ from $\mathbb{D}$ to $\Omega$ such that $h(0)=z_{0}$ . We are interested in those good regions $\Omega\subseteq\mathbb{C}$ such that a transformation $h$ from $\mathbb{D}$ to $\Omega$ does not only exist but also has efficiently computable Taylor coefficients.

Definition 3.3 (good region).

Let $\gamma\geq 1$ . A simply connected region $\Omega\subseteq\mathbb{C}$ is $\gamma$ -good if $0\in\Omega$ and given any $x\in\Omega$ , there exists a holomorphic function $h_{x}$ on $\mathbb{D}$ along with a $z_{x}\in\mathbb{D}$ such that:

(1)

$h_{x}(\mathbb{D})\subseteq\Omega$ , $h_{x}(0)=0$ and $h_{x}(z_{x})=x$ ;
(2)

for every $\ell\in\mathbb{N}^{+}$ , the $\ell$ -th Taylor coefficient $h_{x,\ell}$ of $h_{x}$ at 0 can be determined in $\gamma^{\ell}\mathrm{poly}(\ell)$ time.

Given a $\gamma$ -good region $\Omega\subseteq\mathbb{C}$ and $\delta\in(0,1)$ , we use $\Omega_{\delta}$ to denote the set of all $x\in\Omega$ with $z_{x}\in\mathbb{D}_{1-\delta}$ .

Any convex region is $1$ -good, given access to an oracle that determines the distance to its boundary, which will be formally proved in Appendix A.

Fact 3.4.

Let $\Omega\subseteq\mathbb{C}$ be a convex region. Suppose that for any $z\in\Omega$ , $\mathrm{dist}(z,\partial\Omega)$ can be determined in $O(1)$ time. Then $\Omega$ is $1$ -good.

Applying our Theorem 3.2 to $\log f_{G}$ , combining with Barvinok’s approximation (Lemma 2.3) and our notion of good region, we obtain the following theorem for multiplicative approximation of zero-free $f_{G}$ ’s.

Theorem 3.5 (efficient $\varepsilon$ -approximation).

Let $\alpha,\beta,\gamma\geq 1$ . Let $\mathcal{G}$ be a downward-closed family of dependency graphs, and $f_{\cdot}$ be $(\alpha,\beta)$ -bounded on $\mathcal{G}$ . Let $\Omega\subset\mathbb{C}$ be a $\gamma$ -good region.

For any $\delta\in(0,1)$ , there is a deterministic algorithm which takes $G\in\mathcal{G}$ , $x\in\Omega_{\delta}$ and an error bound $\varepsilon\in(0,1)$ as input, and outputs an estimation $\widehat{f_{G}(x)}$ of $f_{G}(x)$ within $\varepsilon$ -multiplicative error:

1-\varepsilon\leq\frac{\left|\widehat{f_{G}(x)}\right|}{\left|f_{G}(x)\right|}\leq 1+\varepsilon,

in $\widetilde{O}\left(n\left(\frac{M}{\delta\varepsilon}\right)^{C}\right)$ time with $C=\frac{\alpha}{\delta}\ln(8\mathrm{e}\Delta(\beta+\gamma))$ , where $\Delta$ is the maximum degree of $G$ , if provided that $f_{G}$ is $M$ -zero-free on $\Omega\subset\mathbb{C}$ and the value of $f_{G}(0)$ is also provided to the algorithm.

Note that in above theorem, the zero-freeness property can be verified on any particular class of dependency graphs, although the boundedness property should be guaranteed on a downward-closed family. When applying this theorem, the value of $f_{G}(0)$ is usually trivial to compute (e.g. $f_{G}(0)=1$ ), and the $M$ -zero-freeness is usually established for some $M=\mathrm{poly}(n)$ (e.g. $M=O(n)$ ) on $n$ -vertex dependency graphs. In such typical cases, the running time in Theorem 3.5 is bounded as $\left(\frac{n}{\delta\varepsilon}\right)^{O\left(\frac{1}{\delta}\log\Delta\right)}$ .

Proof of Theorem 3.5.

Let $h=h_{x}$ be a holomorphic function that transforms $\mathbb{D}$ to the $\gamma$ -good region $\Omega$ with $h(z_{x})=x$ , where $z_{x}\in\mathbb{D}_{1-\delta}$ since $x\in\Omega_{\delta}$ . And let $f^{h}_{G}=f_{G}\circ h$ .

First, observe that $f_{G}^{h}$ is $M$ -zero-free on $\mathbb{D}$ , because $\left|\log f_{G}^{h}(z)\right|=\left|\log f_{G}(h(z))\right|\leq M$ holds for all $z\in\mathbb{D}$ since $h(\mathbb{D})\subseteq\Omega$ and $f_{G}$ is $M$ -zero-free on $\Omega$ . Then by Lemma 2.3, for any $z\in\mathbb{D}$ , the difference between $\log f^{h}_{G}(z)$ and the truncated Taylor expansion at $0$ is bounded by

(4)

\displaystyle\left|\log f^{h}_{G}(z)-\sum_{k=0}^{m}\frac{\left(\log f_{G}^{h}\right)^{(k)}(0)}{k!}z^{k}\right|\leq\frac{M}{\delta}(1-\delta)^{m+1}<\varepsilon,

for $m=\lceil\frac{1}{\delta}\ln\frac{M}{\delta\varepsilon}\rceil$ .

It remains to verify that $f^{h}_{\cdot}$ is $(\alpha,\beta+\gamma)$ -bounded on $\mathcal{G}$ . By Theorem 3.2, this will prove the theorem.

For $\ell\in\mathbb{N}^{+}$ , let $h_{k}^{(\ell)}$ denote the $k$ -th Taylor coefficient of $h(z)^{\ell}$ at $z=0$ . Since $h(0)=0$ , we have

h(z)^{\ell}=\left(\sum_{k=1}^{+\infty}h_{k}z\right)^{\ell}=\sum_{k=\ell}^{+\infty}h_{k}^{(\ell)}z^{k}

Since $f_{G}$ is $(\alpha,\beta)$ -bounded and $h(0)=0$ , we have

	$\displaystyle f^{h}_{G}(z)$	$\displaystyle=f_{G}(0)+\sum_{\ell=1}^{+\infty}\left(\sum_{S\subseteq V}\lambda_{G[S],\ell}\right)h(z)^{\ell}$
		$\displaystyle=f_{G}(0)+\sum_{\ell=1}^{+\infty}\left(\sum_{S\subseteq V}\lambda_{G[S],\ell}\right)\left(\sum_{k=\ell}^{+\infty}h_{k}^{(\ell)}z^{k}\right)$
		$\displaystyle=f_{G}(0)+\sum_{k=1}^{+\infty}\sum_{S\subseteq V}\left(\sum_{\ell=1}^{k}h_{k}^{(\ell)}\lambda_{G[S],\ell}\right)z^{k}$
		$\displaystyle=f_{G}(0)+\sum_{k=1}^{+\infty}\left(\sum_{S\subseteq V}\lambda^{h}_{G[S],k}\right)z^{k},$

where $\lambda^{h}_{H,k}$ for any $H\in\mathcal{G}$ and $k\in\mathbb{N}^{+}$ is defined as

\lambda^{h}_{H,k}\triangleq\sum_{\ell=1}^{k}h_{k}^{(\ell)}\lambda_{H,\ell}.

Clearly, $\lambda^{h}_{H,k}=0$ if $|V_{H}|>\alpha k$ , where $V_{H}$ denotes the vertex set of $H$ , since $\lambda_{H,\ell}=0$ if $|V_{H}|>\alpha\ell$ . And it can be verified that any $\lambda^{h}_{H,k}$ can be determined within $(\beta+\gamma)^{k}\mathrm{poly}(k)$ time. This is because within $\beta^{k}\mathrm{poly}(k)$ time, one can list all $\lambda_{H,1},\ldots,\lambda_{H,k}$ , and for each $1\leq\ell\leq k$ , $h_{k}^{(\ell)}$ is just the coefficient of $z^{k}$ in $\left(h_{1}z+h_{2}z^{2}+\cdots+h_{k}z^{k}\right)^{\ell}$ , which can be calculated in $\mathrm{poly}(k)$ time given all $h_{1},\ldots,h_{k}$ , which can be listed beforehand in $\gamma^{k}\mathrm{poly}(k)$ time. Overall, this takes at most $(\beta+\gamma)^{k}\mathrm{poly}(k)$ time.

Therefore, $f^{h}_{\cdot}$ is $(\alpha,\beta+\gamma)$ -bounded. ∎

3.1. Quantum partition functions

We formally prove Theorem 1.2. Recall the definition of quantum partition function $Z_{H}$ in (2). We extend this definition by considering measurement.

Recall that $\mathcal{V}=\bigotimes_{u\in V}\mathcal{V}_{u}$ where $V$ is the set of $n$ sites and each $\mathcal{V}_{u}$ is a $q$ -dimensional Hilbert space. A measurement $\mathcal{O}$ is a positive operator in $\mathcal{V}$ . The quantum partition function induced by Hamiltonian $H$ under measurement $\mathcal{O}$ , both in $\mathcal{V}$ , is defined by

(5)

\displaystyle Z_{H,\mathcal{O}}(\beta)\triangleq\mathbf{Tr}\left[\exp(\beta H)\mathcal{O}\right].

Furthermore, a measurement $\mathcal{O}$ is tensorized if $\mathcal{O}=\bigotimes_{v\in V}\mathcal{O}_{v}$ where $\mathrm{supp}(\mathcal{O}_{v})=\{v\}$ .

We show that under tensorized measurement $\mathcal{O}$ , the quantum partition functions $Z_{H,\mathcal{O}}$ defined by local Hamiltonians with $O(1)$ maximum degree are $(1,O(1))$ -bounded. Together with Theorem 3.5 we obtain the following theorem.

Theorem 3.6.

Let $\Omega\subset\mathbb{C}$ be a $\gamma$ -good region for $\gamma\geq 1$ . For any $\delta\in(0,1)$ , there is a deterministic algorithm such that given any $(k,d)$ -Hamiltonian $H$ and tensorized measurement $\mathcal{O}$ , provided that $\frac{1}{\mathbf{Tr}\left[\mathcal{O}\right]}Z_{H,\mathcal{O}}$ is $M$ -zero-free on $\Omega$ , for any temperature $\beta\in\Omega_{\delta}$ and error bound $\varepsilon\in(0,1)$ , the algorithm outputs an estimation of $Z_{H,\mathcal{O}}(\beta)$ within $\varepsilon$ -multiplicative error in $\widetilde{O}\left(n\left(\frac{M}{\delta\varepsilon}\right)^{C}\right)$ time with $C=\frac{1}{\delta}\ln\left(8\mathrm{e}d\left(2q^{3k}+\gamma\right)\right)$ .

Note that when the measurement $\mathcal{O}$ is the identity, $Z_{H,\mathcal{O}}$ is precisely the partition function $Z_{H}$ , which implies Theorem 1.2. As discussed in the introduction, Theorem 3.6 covers all classical partition functions (with or without external field) when temperature is the complex variable.

Following a recent work of Harrow, Mehraban and Soleimanifar [18], Theorem 3.6 gives polynomial-time approximations of quantum partition functions defined by local Hamiltonians with $O(1)$ maximum degree when the inverse temperature $\beta$ is close to zero. And following a standard routine of self-reduction, in the same regime, we have a polynomial-time approximate sampler from the quantum Gibbs state after the measurement in the computational basis. These applications are given in Section 5.

Proof of Theorem 3.6.

Given a $(k,d)$ -Hamiltonian $H=\sum_{j=1}^{m}H_{j}$ , we can construct a dependency graph $G_{H}=(U,E,\mathcal{L})$ as follows:

(1)

$U=[m]$ is the vertex set;
(2)

$E=\left\{\{x,y\}\in{\binom{U}{2}}\mid\mathrm{supp}(H_{x})\cap\mathrm{supp}(H_{y})\neq\varnothing\right\}$ ;
(3)

for any $x\in U$ , its label is given by $L_{x}=H_{x}$ .

Let $\mathcal{G}_{k}$ denote the family of all such $G_{H}$ where $H$ is a $k$ -local Hamiltonian. It is obvious that such $\mathcal{G}_{k}$ is downward-closed.

Let $\mathcal{O}=\bigotimes_{v\in V}\mathcal{O}_{v}$ be a tensorized measurement. For any $G=G_{H}\in\mathcal{G}_{k}$ , where $H=\sum_{j=1}^{m}H_{j}$ , define:

\displaystyle f_{G}(z)=\frac{1}{\mathbf{Tr}\left[\mathcal{O}\right]}Z_{H,\mathcal{O}}(z)=\frac{1}{\mathbf{Tr}\left[\mathcal{O}\right]}\mathbf{Tr}\left[\exp\left(-z\sum_{j=1}^{m}H_{j}\right)\mathcal{O}\right].

The rest of the proof verifies that such $f_{\cdot}$ is $(1,2q^{3k})$ -bounded on $\mathcal{G}_{k}$ , which is sufficient to prove the theorem by Theorem 3.5.

We first verify that such $f_{\cdot}$ is multiplicative. For any $G=(U,E,\mathcal{L})\in\mathcal{G}_{k}$ that is the disjoint union of $G_{1}=(U_{1},E_{1},\mathcal{L}_{1})$ and $G_{2}=(U_{2},E_{2},\mathcal{L}_{2})$ , there exists a bipartition $V=V_{1}\uplus V_{2}$ such that $\mathrm{supp}(H_{x})\subseteq V_{1}$ for all $x\in U_{1}$ and $\mathrm{supp}(H_{y})\subset V_{2}$ for all $y\in U_{2}$ . Let $H_{U_{i}}=\sum_{x\in U_{i}}H_{x}$ for $i=1,2$ . We have,

	$\displaystyle f_{G}(z)$	$\displaystyle=\frac{1}{\mathbf{Tr}[\mathcal{O}]}\mathbf{Tr}\left[\exp\left(-z(H_{U_{1}}+H_{U_{2}})\right)\mathcal{O}\right]$
		$\displaystyle=\frac{1}{\mathbf{Tr}[\mathcal{O}]}\mathbf{Tr}[\exp(-zH_{U_{1}})\exp(-zH_{U_{2}})\mathcal{O}]$
		$\displaystyle=\frac{1}{\mathbf{Tr}[\mathcal{O}]}\mathbf{Tr}_{V_{1}}\left[\exp(-zH_{U_{1}})\bigotimes_{v\in V_{1}}\mathcal{O}_{v}\right]\mathbf{Tr}_{V_{2}}\left[\exp(-zH_{U_{2}})\bigotimes_{v\in V_{2}}\mathcal{O}_{v}\right]$
		$\displaystyle=\frac{1}{\mathbf{Tr}^{2}[\mathcal{O}]}\mathbf{Tr}[\exp(-zH_{U_{1}})\mathcal{O}]\mathbf{Tr}[\exp(-zH_{U_{2}})\mathcal{O}]$
		$\displaystyle=f_{G_{1}}(z)f_{G_{2}}(z)$

Here the subscripts $V_{1},V_{2}$ in $\mathbf{Tr}_{V_{1}},\mathbf{Tr}_{V_{2}}$ indicates the sets of sites that the operators act on. Therefore, $f_{\cdot}$ is multiplicative.

For any $G=(U,E,\mathcal{L})\in\mathcal{G}_{k}$ and any $\ell\in\mathbb{N}^{+}$ , define

(6)

\lambda_{G,\ell}=\frac{1}{\ell!}\frac{1}{\mathbf{Tr}[\mathcal{O}]}\sum_{f:[\ell]\stackrel{{\scriptstyle\mathrm{onto}}}{{\to}}U}\mathbf{Tr}\left[\left(\prod_{j=1}^{\ell}H_{f(j)}\right)\mathcal{O}\right].

Observe that $\lambda_{G,\ell}=0$ if $\left|U\right|>\ell$ as there is no surjection from $[\ell]$ to $U$ . Moreover, for $H=\sum_{x\in U}H_{x}$ ,

\displaystyle f_{G}(z)

\displaystyle=1+\sum_{\ell=1}^{+\infty}\frac{\beta^{\ell}}{\ell!}\mathbf{Tr}\left[H^{\ell}\mathcal{O}\right]=1+\sum_{\ell=1}^{+\infty}\frac{z^{\ell}}{\ell!}\sum_{x_{1},x_{2},\ldots,x_{\ell}\in U}\mathbf{Tr}\left[\left(\prod_{j=1}^{\ell}H_{x_{j}}\right)\mathcal{O}\right]=1+\sum_{\ell=1}^{+\infty}\left(\sum_{S\subseteq U}\lambda_{G[S],\ell}\right)z^{\ell}.

It remains to show that $\lambda_{G,\ell}$ can be determined within $(2q^{3k})^{\ell}\mathrm{poly}(\ell)$ time.

Fix a $G=(U,E,\mathcal{L})\in\mathcal{G}_{k}$ . For any $S\subseteq U$ , define

\displaystyle H_{S,\ell}\triangleq\sum_{f:[\ell]\stackrel{{\scriptstyle\mathrm{onto}}}{{\to}}S}\prod_{j=1}^{\ell}H_{f(j)}.

Clearly, $\lambda_{G,\ell}=\frac{1}{\ell!}\frac{1}{\mathbf{Tr}[\mathcal{O}]}\mathbf{Tr}\left[H_{U,\ell}\mathcal{O}\right]$ . Moreover, the following recurrence holds for $H_{S,\ell}$ :

(7)

\displaystyle H_{S,\ell}=\sum_{j\in S}H_{j}\left(H_{S,\ell-1}+H_{S\setminus\{j\},\ell-1}\right),

where the boundary cases are given by $H_{\varnothing,0}=I$ , and $H_{S,\ell}=\bm{0}$ (the 0-matrix) if $\ell<|S|$ , or $S=\varnothing$ but $\ell>0$ . Note that $H_{S,\ell}$ acts non-trivially on at most $k\left|S\right|$ sites, where each site corresponds to a $q$ -dimensional Hilbert space, thus $H_{S,\ell}$ can be represented as a matrix of size at most $q^{k|S|}\times q^{k|S|}$ and the recursion step (7) can be evaluated in time $O(|S|q^{3k|S|})$ . Therefore, for any $S\subseteq U$ that $1\leq|S|\leq\ell$ , $H_{S,\ell}$ can be computed in time $O(2^{|S|}\ell|S|q^{3k|S|})=O(\ell^{2}2^{\ell}q^{3k\ell})$ by a dynamic programming that constructs a $2^{S}\times[\ell]$ table according to the recurrence (7). And finally, $\lambda_{G,\ell}=\frac{1}{\ell!}\frac{1}{\mathbf{Tr}[\mathcal{O}]}\mathbf{Tr}\left[H_{U,\ell}\mathcal{O}\right]$ can be computed from $H_{U,\ell}$ in $O(q^{3k\ell})$ time because $H_{U,\ell}$ acts non-trivially on at most $k|U|\leq k\ell$ sites and $\mathcal{O}$ is tensorized. ∎

3.2. Induced subgraph counting

Our framework (Definition 3.1) subsumes bounded induced graph counting polynomials (BIGCP) defined by Patel and Regts [29].

A BIGCP $p_{\cdot}$ defines multiplicative graph polynomials $p_{G}$ for all graphs $G=(V,E)$ . Moreover, there exists integer $\alpha\geq 1$ and sequence $\lambda_{H,\ell}$ of complex values such that the following conditions are satisfied.

(1)

For any graph $G=(V,E)$ , $p_{G}$ can be expressed as

\displaystyle p_{G}(z)=1+\sum_{\ell=1}^{m(G)}\left(\sum_{\begin{subarray}{c}H=(V_{H},E_{H})\\ \left|V_{H}\right|\leq\alpha\ell\end{subarray}}\lambda_{H,\ell}\cdot\mathrm{ind}(H,G)\right)z^{\ell},

where $\mathrm{ind}(H,G)$ represents the number of induced subgraphs $G[S]$ , $S\subseteq V$ , isomorphic to $H$ .

(2)

$\lambda_{H,\ell}$ can be determined in $O(\beta^{\ell})$ time for some constant $\beta\geq 1$ .

For any $G=(V,E)$ , we define a dependency graph $G^{*}=(V,E,\mathcal{L})$ where $\mathcal{L}$ labels every $v\in V$ with a trivial symbol $*$ . Let $\mathcal{G}$ denote the family of all $G^{*}$ , which is clearly downward-closed. We define $f_{G^{*}}=p_{G}$ .

Note that

\displaystyle\sum_{\begin{subarray}{c}H=(V_{H},E_{H})\\ \left|V_{H}\right|\leq\alpha\ell\end{subarray}}\lambda_{H,\ell}\mathrm{ind}(H,G)=\sum_{\begin{subarray}{c}S\subseteq V\\ \left|S\right|\leq\alpha\ell\end{subarray}}\lambda_{G[S],\ell}.

Therefore, any BIGCP $p_{\cdot}$ corresponds to an $f_{\cdot}$ that is $(\alpha,\beta)$ -bounded on $\mathcal{G}^{*}$ .

3.3. Boolean CSP with external field

A Boolean-variate constraint satisfaction problem (Boolean CSP) is specified by a $\Phi=(V,E,\bm{\phi})$ , where $H=(V,E)$ is a hypergraph and $\bm{\phi}=(\phi_{e})_{e\in E}$ such that each $\phi_{e}:\{0,1\}^{e}\to\mathbb{C}$ is a Boolean-variate complex-valued constraint function. Furthermore, $\Phi=(V,E,\bm{\phi})$ is a $(k,d)$ -formula if $\left|e\right|\leq k$ for every $e\in E$ and $\mathrm{deg}(v)=\left|\{e\in E\mid v\in e\}\right|\leq d$ for every $v\in V$ .

The partition function for a Boolean CSP $\Phi=(V,E,\bm{\phi})$ of external field $\lambda$ is defined as:

\displaystyle Z_{\Phi}(\lambda)=\sum_{\sigma\in\{0,1\}^{V}}\left(\prod_{e\in E}\phi_{e}(\sigma|_{e})\right)\lambda^{\left\|\sigma\right\|_{1}}.

In [26], Liu, Sinclair and Srivastava formulated the above partition function as counting hypergraph insects and gave a polynomial-time algorithm for such a partition function assuming its zero-freeness. We will see that such a partition function is also subsumed by our framework.

Given a Boolean CSP $\Phi=(V,E,\bm{\phi})$ , we can construct a dependency graph $G_{\Phi}=(V_{\Phi},E_{\Phi},\mathcal{L}_{\Phi})$ as follows.

(1)

$V_{\Phi}=V$ ;
(2)

for any distinct $u,v\in V_{\Phi}=V$ , $\{u,v\}\in E_{\Phi}$ iff $\{u,v\}\subseteq e$ for some $e\in E$ ;
(3)

for any $v\in V_{\Phi}=V$ , its label $L_{v}=(\phi_{e})_{e\in E,v\in e}$ .

Note that each constraint $\phi_{e}$ appears in labels of all $v\in e$ , and the maximum degree of $G_{\Phi}$ is bounded by $\Delta\leq(k-1)d$ for a $(k,d)$ -formula $\Phi$ .

Let $\mathcal{G}_{k,d}$ denote the family of all such dependency graphs $G_{\Phi}$ , where $\Phi=(V,E,\bm{\phi})$ is a $(k,d)$ -formula, and all their induced subgraphs. Obviously, such $\mathcal{G}_{k,d}$ is downward-closed.

Let $G\in\mathcal{G}_{k,d}$ . Without loss of generality, suppose that $G=G_{\Phi}[U]$ is the subgraph of the dependency graph $G_{\Phi}$ induced by $U\subseteq V$ , where $\Phi=(V,E,\bm{\phi})$ is a Boolean CSP.

We define

\displaystyle f_{G}(\lambda)=\sum_{\sigma\in\{0,1\}^{U}}\prod_{\begin{subarray}{c}e\in E\\ e\cap U\neq\varnothing\end{subarray}}\phi^{U}_{e}(\sigma|_{U\cap e})\lambda^{\left\|\sigma\right\|_{1}},

where $\phi^{U}_{e}:U\cap e\rightarrow\mathbb{C}$ is defined as that for any $\tau\in\{0,1\}^{U\cap e}$ ,

\displaystyle\phi^{U}_{e}(\tau)=\phi_{e}(\tau^{*}),

where $\tau^{*}\in\{0,1\}^{e}$ extends $\tau$ and assigns all $v\in e\setminus U$ with 0. It is easy to verify that such definition $f_{G}$ uses only the information stored in the dependency graph $G$ , thus it is well defined. Meanwhile, it is also easy to verify that $f_{\cdot}$ is multiplicative and $f_{G}(\lambda)=Z_{\Phi}(\lambda)$ if $G=G_{\Phi}$ .

For $G=G_{\Phi}[U]$ where $\Phi=(V,E,\bm{\phi})$ and $U\subseteq V$ , define $\lambda_{G,\ell}$ , as

\lambda_{G,\ell}=\begin{cases}\prod_{\begin{subarray}{c}e\in E\\ e\cap U\neq\varnothing\end{subarray}}\phi_{e}^{U}(\bm{1}_{U\cap e}),&\left|U\right|=\ell\\ 0,&o.w.\end{cases}

Each $\lambda_{G,\ell}$ can be determined in $\mathrm{poly}(k,d,\ell)$ time.

Observe that,

	$\displaystyle f_{G}(\lambda)$	$\displaystyle=1+\sum_{\ell=1}^{\left\|U\right\|}\sum_{\begin{subarray}{c}\sigma\in\{0,1\}^{U}\\ \left\\|\sigma\right\\|_{1}=\ell\end{subarray}}\prod_{\begin{subarray}{c}e\in E\\ e\cap U\neq\varnothing\end{subarray}}\phi^{U}_{e}(\sigma\|_{U\cap e})\lambda^{\ell}$
		$\displaystyle=1+\sum_{\ell=1}^{\left\|U\right\|}\sum_{\begin{subarray}{c}S\subseteq U\\ \left\|S\right\|=\ell\end{subarray}}\prod_{\begin{subarray}{c}e\in E\\ e\cap S\neq\varnothing\end{subarray}}\phi^{S}_{e}(\bm{1}_{S\cap e})\lambda^{\ell}$
		$\displaystyle=1+\sum_{\ell=1}^{+\infty}\left(\sum_{\begin{subarray}{c}S\subseteq U\end{subarray}}\lambda_{G[S],\ell}\right)\lambda^{\ell}.$

Therefore, $f_{\cdot}$ is a $(1,1)$ -bounded on $\mathcal{G}_{k,d}$ .

Applying Theorem 3.5, we immediately obtain the following corollary. Similar bound has been proved in [26], but here we only need to encode the problem using our framework.

Corollary 3.7.

Let $\Omega\subseteq\mathbb{C}$ be a $\gamma$ -good region for $\gamma\geq 1$ . For any $\delta\in(0,1)$ , there is a deterministic algorithm such that given any $(k,d)$ -formula $\Phi$ for Boolean CSP, provided that $Z_{\Phi}$ is $M$ -zero-free on $\Omega$ , for any external field $\lambda\in\Omega_{\delta}$ and error bound $\varepsilon\in(0,1)$ , the algorithm outputs an estimation of $Z_{\Phi}(\lambda)$ within $\varepsilon$ -multiplicative error in $\widetilde{O}\left(n\left(\frac{M}{\delta\varepsilon}\right)^{C}\right)$ time with $C=\frac{1}{\delta}\ln\left(8\mathrm{e}kd(1+\gamma)\right)$ .

Since such $Z_{\Phi}(\lambda)$ is a polynomial with finite degree, by 3.4 and Lemma 2.2, if $\Omega\subseteq\mathbb{C}$ is a convex region and $Z_{\Phi}$ does not vanish on a slightly larger region $\Omega^{\prime}=\{(1+\delta)z\mid z\in\Omega\}$ for some constant gap $\delta\in\mathbb{R}^{+}$ , then $M=O_{\delta}(n)$ and hence the algorithm in Corollary 3.7 runs in ${\left(\frac{n}{\varepsilon}\right)^{O(\ln\left(kd\right))}}$ time.

3.4. A barrier to non-multiplicative functions

Our framework based on functions $f_{G}$ induced by dependency graphs $G$ is fairly expressive. However, the current technique crucially relies on the multiplicative property of $f_{\cdot}$ . It would meet a barrier when dealing with systems lacking such multiplicative property.

We explain this using a concrete example. Consider the following generalization of (1):

(8)

\displaystyle\forall\beta\in\mathbb{C},\quad Z_{H,H^{\prime}}(\beta)\triangleq\mathbf{Tr}\left[\exp(-\beta H+H^{\prime})\right].

Here, $H$ and $H^{\prime}$ are two Hamiltonians in $\mathcal{V}$ . It encompasses the transverse Ising model and XXZ model. Unfortunately, this partition function fails to fit in our framework due to the lack of multiplicative property even when $H^{\prime}$ is a tensorized operator. For Hamiltonians $H_{1},H_{2}$ such that $\mathrm{supp}(H_{1})\cap\mathrm{supp}(H_{2})=\varnothing$ and a tensorized operator $H^{\prime}=\bigotimes_{v\in V}H^{\prime}_{v}$ , the following equality fails to hold in general:

\displaystyle Z_{H_{1}+H_{2},H^{\prime}}(\beta)=\frac{1}{\mathbf{Tr}\left[\exp(-H^{\prime})\right]}Z_{H_{1},H^{\prime}}(\beta)Z_{H_{2},H^{\prime}}(\beta).

For example, for $\beta=1$ , $H_{1}=I\bigotimes\left(\begin{matrix}1&0\\ 1&1\\ \end{matrix}\right)$ , $H_{2}=\left(\begin{matrix}1&1\\ 0&1\\ \end{matrix}\right)\bigotimes I$ and $H^{\prime}=\left(\begin{matrix}1&0\\ 0&2\end{matrix}\right)\bigotimes\left(\begin{matrix}2&0\\ 0&1\end{matrix}\right)$ , it holds that

\displaystyle\mathbf{Tr}\left[\exp(-H^{\prime})\right]\approx 0.6869,\mathbf{Tr}\left[\exp(-H_{i}-H^{\prime})\right]\approx 0.2416,i\in\{1,2\}\text{ and }\mathbf{Tr}\left[\exp(-H_{1}-H_{2}-H^{\prime})\right]\approx 0.1316.

Hence, $\mathbf{Tr}\left[\exp(-H^{\prime})\right]\mathbf{Tr}\left[\exp(H_{1}+H_{2}+H^{\prime})\right]\approx 0.09040$ and $\mathbf{Tr}\left[\exp(-H_{1}-H^{\prime})\right]\mathbf{Tr}\left[\exp(-H_{2}-H^{\prime})\right]\approx 0.05837$ . The main obstacle comes from the non-commutativity of Hamiltonians and it remains open to design a polynomial-time algorithm for such partition function assuming only zero-freeness.

4. Efficient Coefficient Computing

In this section we prove Theorem 3.2. First we need to establish the following lemma.

Lemma 4.1.

Let $\mathcal{G}$ be a downward-closed family of dependency graphs, and $f_{\cdot}$ be $(\alpha,\beta)$ -bounded on $\mathcal{G}$ for $\alpha,\beta\geq 1$ . Recursively define the sequence $(\zeta_{H,i})_{H\in\mathcal{G},\ell\in\mathbb{N}^{+}}$ of complex numbers as follows: for any $H=(V_{H},E_{H},\mathcal{L}_{H})\in\mathcal{G}$ and any $\ell\in\mathbb{N}^{+}$ ,

(9)

\displaystyle\zeta_{H,\ell}=\lambda_{H,\ell}-\sum_{s=1}^{\ell-1}\frac{s}{\ell}\sum_{\begin{subarray}{c}S,T\subseteq V_{H}\\ S\cup T=V_{H}\end{subarray}}\zeta_{H[S],s}\lambda_{H[T],\ell-s}.

It holds that $\zeta_{H,\ell}\neq 0$ only if $H$ is connected and $|V_{H}|\leq\alpha\ell$ . Moreover, for any $G=(V,E,\mathcal{L})\in\mathcal{G}$ ,

(10)

\displaystyle\log f_{G}(z)=\log f_{G}(0)+\sum_{\ell=1}^{+\infty}\left(\sum_{S\subseteq V}\zeta_{G[S],\ell}\right)z^{\ell}.

As in [29, 26], the following result of Borgs et al. [6] is used.

Fact 4.2 (Lemma 2.1 (c) in [6]).

Let $G=(V,E)$ be a graph with maximum degree $\Delta$ , $v\in V$ be a vertice and $\ell\in\mathbb{N}_{\geq 1}$ . Then the number of connected subgraphs of size $\ell$ containing $v$ is at most $\frac{(\mathrm{e}\Delta)^{\ell-1}}{2}$ .

With this fact, we can enumerate all connected induced subgraphs $G[S]$ of $\left|S\right|\leq\ell$ vertices efficiently.

Lemma 4.3.

There exists a deterministic algorithm which takes a dependency graph $G=(V,E,\mathcal{L})$ on $n=|V|$ vertices with maximum degree $\Delta$ and a positive integer $\ell\in\mathbb{N}^{+}$ as input, and outputs

(11)

\displaystyle\mathcal{C}_{\leq\ell}=\{S\subseteq V\mid\left|S\right|\leq\ell,G[S]\text{ is connected}\},

in time $\widetilde{O}(n(\mathrm{e}\Delta)^{\ell})$ , where $\widetilde{O}(\cdot)$ hides $\mathrm{poly}(\Delta,\ell,\log(n))$ .

Proof.

Let $\mathcal{C}_{=\ell}^{v}$ denote the collection of such $S\subseteq V$ containing $v\in V$ that $|S|=\ell$ and $G[S]$ is connected. Clearly $\mathcal{C}_{\leq\ell}=\bigcup_{\begin{subarray}{c}v\in V\\ j\leq\ell\end{subarray}}\mathcal{C}_{=j}^{v}$ . Now construct each $\mathcal{C}_{=\ell}^{v}$ inductively. When $\ell=1$ , $\mathcal{C}_{=1}^{v}=\{\{v\}\}$ . For $\ell\geq 2$ , we enumerate all $S\in\mathcal{C}_{=\ell-1}^{v}$ and $u\in V\setminus S$ such that $G[S\cup\{u\}]$ is connected, and include $S\cup\{u\}$ into $\mathcal{C}_{=\ell}^{v}$ . It is easy to see that this correctly constructs $\mathcal{C}_{=\ell}^{v}$ . By 4.2, $\left|\mathcal{C}^{v}_{=\ell}\right|\leq(\mathrm{e}\Delta)^{\ell-1}/2$ . Representing each set $S$ as a string of vertices in $S$ sorted in increasing order of vertices, the set $\mathcal{C}^{v}_{=\ell}$ can be stored by a standard dynamic data structure such as prefix trees, so that it takes $O(\Delta\ell(\mathrm{e}\Delta)^{\ell-1})$ time to iterate over all $(S,u)\in\mathcal{C}_{=\ell-1}^{v}\times V$ such that $G[S\cup\{u\}]$ may be connected, and for each such $(S,u)$ pair it takes $\mathrm{poly}(\Delta,\ell,\log n)$ time to check weather $G[S\cup\{u\}]$ is connected or $S\cup\{u\}$ is already in $\mathcal{C}_{=\ell}^{v}$ , and insert $S$ into $\mathcal{C}_{=\ell}^{v}$ if necessary. Overall, it takes $\widetilde{O}(n(\mathrm{e}\Delta)^{\ell})$ time to construct $\mathcal{C}_{\leq\ell}$ . ∎

Combining the above algorithm with (9), we can compute coefficients $\zeta_{H,\ell}$ for $\log f_{G}$ efficiently.

Lemma 4.4.

Let $\mathcal{G}$ be a downward-closed family of dependency graphs, and $f_{\cdot}$ be $(\alpha,\beta)$ -bounded on $\mathcal{G}$ for $\alpha,\beta\geq 1$ . There exists a deterministic algorithm which takes a dependency graph $G=(V,E,\mathcal{L})\in\mathcal{G}$ on $n=|V|$ vertices with maximum degree $\Delta$ and a positive integer $\ell\in\mathbb{N}^{+}$ as input, and outputs $(\zeta_{G[S],\ell})_{S\in\mathcal{C}_{\leq\alpha\ell}}$ within $\widetilde{O}\left(n(8\mathrm{e}\beta\Delta)^{\alpha\ell}\right)$ time, where $\mathcal{C}_{\leq\alpha\ell}$ is defined in Eq. (11).

The lemma follows by first enumerating all $S\in\mathcal{C}_{\leq\alpha\ell}$ , which takes $\widetilde{O}\left(n(\mathrm{e}\Delta)^{\alpha\ell}\right)$ time according to Lemma 4.3, and second for every $S\in\mathcal{C}_{\leq\alpha\ell}$ , taking $H=G[S]$ and computing $\zeta_{H,\ell}$ using a dynamic programming given by Eq. (9), which takes $\widetilde{O}(8^{\alpha\ell}\beta^{\ell})$ time.

Let $\log f_{G}(z)=\log f_{G}(0)+\sum_{\ell=1}^{+\infty}g_{G,\ell}z^{\ell}$ . Due to Lemma 4.1, $\zeta_{G[S],\ell}=0$ if $G[S]$ is disconnected or $|S|>\alpha\ell$ , thus due to Eq. (9), the $\ell$ -th Taylor coefficient of $\log f_{G}$ is given by

g_{G,\ell}=\sum_{S\subseteq V}\zeta_{G[S],\ell}=\sum_{S\in\mathcal{C}_{\leq\alpha\ell}}\zeta_{G[S],\ell}.

Therefore, Theorem 3.2 is proved. It only remains to prove Lemma 4.1.

Proof of Lemma 4.1.

Fix an arbitrary $G\in\mathcal{G}$ , and consider $f_{G}$ . Let $\log f_{G}=\log f_{G}(0)+\sum_{\ell=1}^{+\infty}g_{G,\ell}z^{\ell}$ denote the Taylor’s expansion of $\log f_{G}$ at the origin, and $f_{G}(z)=f_{G}(0)+\sum_{\ell=1}^{+\infty}f_{G,\ell}z^{\ell}$ denote the Taylor’s expansion of $f_{G}$ at the origin. We prove by induction on $\ell\geq 1$ that

(12)

\displaystyle g_{G,\ell}=\sum_{S\subseteq V}\zeta_{G[S],\ell},

which implies (10).

For the induction basis, when $\ell=1$ , by Lemma 2.4 we have $g_{G,1}=f_{G,1}$ . by the definition of bounded graph function in Definition 3.1, $f_{G,1}=\sum_{S\subseteq V}\lambda_{G[S],1}$ ; and it follows from (9) that $\lambda_{G[S],1}=\zeta_{G[S],1}$ . Altogether, we have

\displaystyle g_{G,1}=f_{G,1}=\sum_{S\subseteq V}\lambda_{G[S],1}=\sum_{S\subseteq V}\zeta_{G[S],1}.

Now suppose that the induction hypothesis (12) holds for all $\ell^{\prime}<\ell$ . We have

$\displaystyle\sum_{S\subseteq V}\zeta_{G[S],\ell}$	$\displaystyle=\sum_{S\subseteq V}\left(\lambda_{G[S],\ell}-\sum_{s=1}^{\ell-1}\frac{s}{\ell}\sum_{\begin{subarray}{c}L,R\subseteq V\\ L\cup R=S\end{subarray}}\zeta_{G[L],s}\cdot\lambda_{G[R],\ell-s}\right)$
	$\displaystyle=\sum_{S\subseteq V}\lambda_{G[S],\ell}-\sum_{s=1}^{\ell-1}\frac{s}{\ell}\left(\sum_{L\subseteq V}\zeta_{G[L],s}\right)\left(\sum_{R\subseteq V}\lambda_{G[R],\ell-s}\right)$
	$\displaystyle=f_{G,\ell}-\sum_{s=1}^{\ell-1}\frac{s}{\ell}g_{G,s}f_{G,\ell-s}$	(Induction Hypothesis)
	$\displaystyle=g_{G,\ell}.$	(Lemma 2.4)

This finishes the inductive proof of (12).

Next, we prove that $\zeta_{H,\ell}=0$ if $H=(V_{H},E_{H},\mathcal{L}_{H})\in\mathcal{G}$ is disconnected or $\left|V_{H}\right|>\alpha\ell$ . Recall that $f_{\cdot}$ is $(\alpha,\beta)$ -bounded, we have $\lambda_{H,\ell}=0$ for $\left|V_{H}\right|>\alpha\ell$ . Then the fact that $\zeta_{H,\ell}=0$ for $\left|V_{H}\right|>\alpha\ell$ can be verified by induction on $\ell\geq 1$ . Specifically, by Eq. (9),

\zeta_{H,\ell}=\lambda_{H,\ell}-\sum_{s=1}^{\ell-1}\frac{s}{\ell}\sum_{\begin{subarray}{c}S,T\subseteq V_{H}\\ S\cup T=V_{H}\end{subarray}}\zeta_{H[S],s}\lambda_{H[T],\ell-s}.

For the basis, $\zeta_{H,1}=\lambda_{H,1}=0$ when $|V_{H}|>\alpha$ . In general, observe that assuming $\left|V_{H}\right|>\alpha\ell$ , for any $S\cup T=V_{H}$ , it must hold that either $|S|>\alpha s$ or $|T|>\alpha(\ell-s)$ . Therefore, assuming $\left|V_{H}\right|>\alpha\ell$ , $\zeta_{H,\ell}=0$ follows from the induction hypothesis.

Finally, it remains to verify that $\zeta_{H,\ell}=0$ if $H$ is disconnected, which follows from the multiplicative property of $f_{\cdot}$ . By contradiction, assume that $\zeta_{H,\ell}\neq 0$ for some disconnected $H\in\mathcal{G}$ . Let $S^{*}\subseteq V_{H}$ be a minimal subset of $V$ such that $H[S^{*}]$ is disconnected and $\zeta_{H[S^{*}],\ell}\neq 0$ . Since $H[S^{*}]$ is disconnected, there exist nonempty $L,R\subseteq S^{*}$ such that $L\cup R=S^{*}$ and $L,R$ are disconnected in $H[S^{*}]$ . Due to the multiplicative property of $f_{\cdot}$ , we have $f_{G[S^{*}]}=f_{G[L]}\cdot f_{G[R]}$ . Therefore,

(13)

\displaystyle g_{G[S^{*}],\ell}=g_{G[L],\ell}+g_{G[R],\ell}=\sum_{S\subseteq L}\zeta_{G[S],\ell}+\sum_{S\subseteq R}\zeta_{G[S],\ell},

where the first equation can be formally verified for any disjoint dependency graphs $G_{1},G_{2}\in\mathcal{G}$ and any $z$ in the neighborhood of the origin, such that for an arbitrary path $P$ in $\Omega$ connecting $z$ and the origin,

	$\displaystyle\log f_{G_{1}\cup G_{2}}(z)$	$\displaystyle=\log f_{G_{1}\cup G_{2}}(0)+\int_{P}\frac{f^{\prime}_{G_{1}\cup G_{2}}(z)}{f_{G_{1}\cup G_{2}}(z)}\,dz\$
		$\displaystyle=\log f_{G_{1}}(0)+\log f_{G_{2}}(0)+\int_{P}\left(\frac{f^{\prime}_{G_{1}}(z)}{f_{G_{1}}(z)}+\frac{f^{\prime}_{G_{2}}(z)}{f_{G_{2}}(z)}\right)\,dz\$
		$\displaystyle=\log f_{G_{1}}(z)+\log f_{G_{2}}(z).$

On the other hand,

(14)

\displaystyle g_{G[S^{*}],\ell}=\sum_{S\subseteq S^{*}}\zeta_{G[S],\ell}=\zeta_{G[S^{*}],\ell}+\sum_{S\subset S^{*}}\zeta_{G[S],\ell}=\zeta_{G[S^{*}],\ell}+\sum_{S\subseteq L}\zeta_{G[S],\ell}+\sum_{S\subseteq R}\zeta_{G[S],\ell},

where the last equation is due to the minimality of $S^{*}$ . Combining (13) and (14), we have $\zeta_{G[S^{*}],\ell}=0$ , a contradiction. ∎

5. Applications

In this section, we prove that any zero-free partition function of local Hamiltonians with bounded maximum degree is polynomial-time approximable if the temperature is close enough to 0. This is formally stated by the following theorem. Recall the definition of the partition function $Z_{H,\mathcal{O}}$ induced by Hamiltonian $H$ under measurement $\mathcal{O}$ in (5).

Theorem 5.1.

Let $k,d\in\mathbb{N}^{+}$ , $h>0$ , $\delta\in(0,1)$ and $\beta_{0}=\frac{1}{5kdh}$ . There is a deterministic algorithm such that given any $(k,d)$ -Hamiltonian $H=\sum_{j=1}^{m}H_{j}$ on $n$ sites satisfying $\left\|H_{j}\right\|\leq h$ and tensorized measurement $\mathcal{O}$ , for any temperature $\beta\in\mathbb{D}_{(1-\delta)\beta_{0}}$ and error bound $\varepsilon\in(0,1)$ , the algorithm outputs an estimation of $Z_{H,\mathcal{O}}(\beta)$ within $\varepsilon$ -multiplicative error in $\widetilde{O}\left(\left(\frac{n}{\delta\varepsilon}\right)^{C}\right)$ time with $C=\frac{1}{\delta}\left(\ln 8\mathrm{e}d+3k\ln q\right)+1$ .

It was established in [18] that the partition function exhibits zero-freeness property when the inverse temperature $\beta$ is close to the $0$ . Similarly, we have the following lemma.

Lemma 5.2.

Let $h\in\mathbb{R}^{+}$ , $H=\sum_{j=1}^{m}H_{j}$ be a $(k,d)$ -Hamiltonian on $n$ sites, and $\mathcal{O}$ be a tensorized measurement. If $\left|H_{j}\right|\leq h$ for all $1\leq j\leq m$ , then for any $\beta\in\mathbb{D}_{\beta_{0}}$ where $\beta_{0}=\frac{1}{5edkh}$ , it holds that

\displaystyle\left|\log\frac{Z_{H,\mathcal{O}}(\beta)}{\mathbf{Tr}[\mathcal{O}]}\right|\leq n.

Theorem 5.1 follows directly from Lemma 5.2 and Theorem 3.6.

Besides estimation of partition function, another related important computational problem is to sample according to the Gibbs state.

The quantum Gibbs state specified by Hamiltonian $H\in\mathcal{V}$ and inverse temperature $\beta\in\mathbb{R}^{+}$ is:

\displaystyle\rho_{H}(\beta)=\frac{\exp(-\beta H)}{Z_{H}(\beta)}.

The classical distribution $\mu_{H,\beta}$ over $[q]^{V}$ is the quantum Gibbs state $\rho_{H}(\beta)$ after measurement in the computational basis, i.e.

\displaystyle\forall\sigma\in[q]^{V},\quad\mu_{H,\beta}(\sigma)=\frac{Z_{H,\mathcal{O}_{\sigma}}(\beta)}{Z_{H}(\beta)},

where $\mathcal{O}_{\sigma}=\lvert\sigma\rangle\langle\sigma\rvert$ . Note that $\mu_{H,\beta}$ is a well-defined distribution over $[q]^{V}$ . To see this, first note that $\sum_{\sigma}\mathcal{O}_{\sigma}=I$ is the identity matrix in $\mathcal{V}$ , and hence $\sum_{\sigma}Z_{H,\mathcal{O}_{\sigma}}(\beta)=Z_{H}(\beta)$ ; and second, both $\mathcal{O}_{\sigma}$ and $\exp(\beta H)$ are positive semidefinite since $H$ is Hermitian and $\beta\in\mathbb{R}^{+}$ , and hence $Z_{H,\mathcal{O}_{\sigma}}(\beta)=\mathbf{Tr}\left[\exp(\beta H)\mathcal{O}_{\sigma}\right]\geq 0$ .

In the same regime as Theorem 5.1, we have a polynomial-time approximate sampler from $\mu_{H,\beta}$ , the classical distribution obtained after measurement of the quantum Gibbs state in the computational basis.

Theorem 5.3.

Let $k,d\in\mathbb{N}^{+}$ , $h>0$ , $\delta\in(0,1)$ and $\beta_{0}=\frac{1}{5kdh}$ . There is a randomized algorithm such that given any $(k,d)$ -Hamiltonian $H=\sum_{j=1}^{m}H_{j}$ on $n$ sites satisfying $\left\|H_{j}\right\|\leq h$ , for any temperature $\beta\in\mathbb{D}_{(1-\delta)\beta_{0}}$ and error bound $\varepsilon\in(0,1)$ , the algorithm outputs an approximate sample $\sigma\in[q]^{V}$ within $\varepsilon$ total variation distance from the distribution $\mu_{H,\beta}$ , in $\widetilde{O}\left(\left(\frac{n}{\delta\varepsilon}\right)^{C}\right)$ time with $C=\frac{1}{\delta}\left(2\log 8\mathrm{e}d+6k\log q\right)+3$ .

Proof.

We leverage the algorithm in Theorem 5.1 as a subroutine, and give the following classical algorithm for approximate sampling from $\mu_{H,\beta}$ .

Without loss of generality, we may assume that $V=[n]$ . Let $\mathcal{M}_{j}=\lvert j\rangle\langle j\rvert$ for $1\leq j\leq q$ , and $\mathcal{M}_{v,j}=\left(\bigotimes_{\ell=1}^{v-1}I\right)\otimes\mathcal{M}_{j}\otimes\left(\bigotimes_{\ell=v+1}^{n}I\right)$ . Our procedure for sampling $\sigma\in[q]^{V}$ is as follows.

(1)

Initialize $\mathcal{O}$ with the identity operator on Hilbert space $\mathcal{H}$ ;
(2)

Iterate $v$ from $1$ to $n$ ;
(3)

For each $j$ from $1$ to $n$ , estimate $z_{v,j}=Z_{H,\mathcal{O}_{v-1}\mathcal{M}_{v,j}}(\beta)$ within $\varepsilon_{0}=\frac{\varepsilon}{10n}$ -multiplicative error.
(4)

samples $j\in[q]$ proportional to $\tilde{z}_{v,j}$ , the estimation of $z_{v,j}$ , updates $\mathcal{O}$ with $\mathcal{O}\mathcal{M}_{v,j}$ , and assigns $\sigma(v)$ with $j$ .

Note that $\mathcal{O}$ is a tensorized measurement during the process. Hence, Theorem 5.1 guarantees an estimation of $z_{v,j}$ within $\varepsilon_{0}$ -multiplicative error in $\widetilde{O}(\left(\frac{n}{\varepsilon\delta}\right)^{C})$ time with $C=\frac{1}{\delta}\left(2\log 8\mathrm{e}d+6k\log q\right)+2$ . Furthermore, note that for each configuration $\sigma\in[q]^{V}$ ,

\displaystyle\frac{\mathbf{Pr}[\sigma\text{ is generated}]}{\mu_{H,\mathcal{O}}(\sigma)}=\prod_{v=1}^{n}\frac{z_{v,\sigma(v)}}{\sum_{j\in[q]}z_{v,j}}\frac{\sum_{j=1}^{q}\tilde{z}_{v,j}}{\tilde{z}_{v,\sigma(v)}},

and for each $v\in V$ and $j\in[q]$ ,

\displaystyle 1-\varepsilon_{0}\leq\frac{\tilde{z}_{v,j}}{z_{v,j}}\leq 1+\varepsilon_{0}.

Hence,

\displaystyle 1-\varepsilon\overset{(*)}{<}\left(\frac{1-\varepsilon}{1+\varepsilon}\right)^{n}\leq\frac{\mathbf{Pr}[\sigma\text{ is generated}]}{\mu_{H,\mathcal{O}}(\sigma)}\leq\left(\frac{1+\varepsilon_{0}}{1-\varepsilon_{0}}\right)^{n}\overset{(\star)}{<}1+\varepsilon,

where $(\star)$ follows from $\left(\frac{1+\varepsilon_{0}}{1-\varepsilon_{0}}\right)\leq(1+3\varepsilon_{0})^{n}<\exp(\frac{3}{10}\varepsilon)<1+\varepsilon$ , and $(*)$ follows from $(\star)$ and $\frac{1}{1+\varepsilon}>1-\varepsilon$ . Therefore, the total varaince distance between $\mu_{H,\mathcal{O}}$ and the output from our sampler will differ at most $\varepsilon$ .

We conclude the proof by observing that our algorithm calls the subrountine $O(nq)$ times with parameter $\varepsilon_{0}=\frac{\varepsilon}{10n}$ , which takes $\widetilde{O}\left(\left(\frac{n}{\varepsilon}\right)^{C}\right)$ time with $C=\frac{1}{\delta}\left(2\log 8\mathrm{e}d+6k\log q\right)+3$ in total. ∎

5.1. Proof of Lemma 5.2

We now give a proof of Lemma 5.2. This result extends the zero-freeness result proved in [18] to the case that allows tensorized measurement. We will see that the same inductive proof based on cluster expansion works for this more general case.

Let $H=\sum_{i=1}^{m}H_{i}$ be a $(k,d)$ -Hamiltonian, $\mathcal{O}=\bigotimes_{v\in V}\mathcal{O}_{v}$ be a tensorized measurement, and $X\subseteq V$ be an arbitrary subset.

Define $H_{X}$ the Hamiltonian $H$ restricted on $X$ as

\displaystyle H_{X}=\sum_{\begin{subarray}{c}i\in[m]\\ \mathrm{supp}(H_{i})\subseteq X\end{subarray}}H_{i},

and define the partition function $Z_{H,\mathcal{O}}$ restricted on $X$ as

\displaystyle Z^{X}_{H,\mathcal{O}}(\beta)=\mathbf{Tr}_{X}[\exp(-\beta H_{X})\mathcal{O}_{X}],

where $O_{X}=\bigotimes_{v\in X}\mathcal{O}_{v}$ . And $Z^{\varnothing}_{H,\mathcal{O}}=1$ . Here the subscript $X$ in $\mathbf{Tr}_{X}$ indicates that the operators act on the sites in $X$ .

Moreover, recall the dependency graph $G_{H}=(U,E,\mathcal{L})$ defined in the proof of Theorem 3.6:

(1)

$U=[m]$ ;
(2)

$E=\{(x,y)\in U\times U\mid x\neq y,\mathrm{supp}(H_{x})\cap\mathrm{supp}(H_{y})\neq\varnothing\}$ ;
(3)

$L_{x}=H_{x}$ for any $x\in U$ .

We are now ready to introduce the cluster expansions of partition functions. The following lemma was an extension of [18, Lemma 26] with tensorized measurement $\mathcal{O}$ .

Lemma 5.4 (high temperature expansion [18]).

Let $h\in\mathbb{R}^{+}$ , $H=\sum_{i=1}^{m}H_{i}$ be a $(k,d)$ -Hamiltonian, and $\mathcal{O}$ be a tensorized measurement. If $\left\|H_{i}\right\|\leq h$ , then the following holds for all $\Lambda\subseteq V$ , $x\in\Lambda$ and $\beta\in\mathbb{D}_{\beta_{0}}$ .

\displaystyle Z^{\Lambda}_{H,\mathcal{O}}(\beta)=\mathbf{Tr}[\mathcal{O}_{x}]Z^{\Lambda\setminus\{x\}}_{H,\mathcal{O}}(\beta)+\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected}\end{subarray}}W_{S}(\beta)Z^{\Lambda\setminus R_{S}}_{H,\mathcal{O}}(\beta),

where

	$\displaystyle W_{S}(\beta)$	$\displaystyle=\sum_{l=\left\|S\right\|}^{+\infty}\frac{(-\beta)^{l}}{l!}\sum_{\begin{subarray}{c}(i_{1},i_{2},\ldots,i_{l})\in S^{l}\\ \cup_{j=1}^{l}\{i_{j}\}=S\end{subarray}}\mathbf{Tr}_{R_{S}}\left[\prod_{j=1}^{l}H_{i_{j}}\mathcal{O}_{R_{S}}\right],$
	$\displaystyle R_{S}$	$\displaystyle=\bigcup_{j\in S}\mathrm{supp}(H_{j}),$
	$\displaystyle\beta_{0}$	$\displaystyle=\frac{1}{\mathrm{e}(\mathrm{e}-1)dh}.$

Proof.

Without lose of generality, we assume that $\Lambda=V$ . Directly from the definition, we have

	$\displaystyle Z_{H,\mathcal{O}}(\beta)$	$\displaystyle=\mathbf{Tr}_{V}\left[\sum_{\ell=0}^{+\infty}\frac{(-\beta)^{\ell}}{\ell!}\left(\sum_{j=1}^{m}H_{j}\right)^{\ell}\mathcal{O}\right]$
		$\displaystyle\overset{(\star)}{=}\sum_{\ell=0}^{+\infty}\frac{(-\beta)^{\ell}}{\ell!}\mathbf{Tr}_{V}\left[H_{V\setminus\{x\}}^{\ell}\mathcal{O}+\sum_{\begin{subarray}{c}(i_{1},i_{2},\ldots,i_{\ell})\in[m]^{\ell}\\ \exists j\in[\ell],x\in\mathrm{supp}(H_{i_{j}})\end{subarray}}\prod_{j=1}^{\ell}H_{i_{j}}\mathcal{O}\right]$
		$\displaystyle=\mathbf{Tr}[\mathcal{O}_{x}]Z^{V\setminus\{x\}}_{H,\mathcal{O}}(\beta)+\sum_{\ell=0}^{+\infty}\sum_{\begin{subarray}{c}(i_{1},i_{2},\ldots,i_{\ell})\in[m]^{\ell}\\ \exists j\in[\ell],x\in\mathrm{supp}(H_{i_{j}})\end{subarray}}\frac{(-\beta)^{\ell}}{\ell!}\mathbf{Tr}_{V}\left[\prod_{j=1}^{\ell}H_{i_{j}}\mathcal{O}\right],$

where $(\star)$ follows from the fact that $H=H_{V\setminus\{x\}}+\sum_{\begin{subarray}{c}j\in[m]\\ x\in\mathrm{supp}(H_{j})\end{subarray}}H_{j}$ .

For each $\ell$ -tuple $\bm{i}=(i_{1},i_{2},\ldots,i_{\ell})$ satisfying that there exists $j^{*}\in[\ell]$ such that $x\in\mathrm{supp}(H_{i_{j^{*}}})$ , let $S_{\bm{i}}\subseteq\{i_{1},i_{2},\ldots,i_{\ell}\}$ be the minimum subset such that $i_{j^{*}}\in S_{\bm{i}}$ and $\left(\bigcup_{j\in S_{\bm{i}}}\mathrm{supp}(H_{j})\right)\cap\left(\bigcup_{j\in\{i_{1},i_{2},\ldots,i_{\ell}\}\setminus S_{\bm{i}}}\mathrm{supp}(H_{j})\right)=\varnothing$ . Note that

\displaystyle\left(\prod_{j=1}^{\ell}H_{i_{j}}\right)\mathcal{O}=\left(\prod_{\begin{subarray}{c}1\leq j\leq\ell\\ i_{j}\in S_{\bm{i}}\end{subarray}}H_{i_{j}}\right)\mathcal{O}_{R_{S}}\left(\prod_{\begin{subarray}{c}1\leq j\leq\ell\\ i_{j}\not\in S_{\bm{i}}\end{subarray}}H_{i_{j}}\right)\mathcal{O}_{V\setminus R_{S}},

where $R_{S}=\bigcup_{j\in S}\mathrm{supp}(H_{j})$ .

Therefore,

	$\displaystyle\sum_{\ell=0}^{+\infty}\sum_{\begin{subarray}{c}(i_{1},i_{2},\ldots,i_{\ell})\in[m]^{\ell}\\ \exists j\in[\ell],x\in\mathrm{supp}(H_{i_{j}})\end{subarray}}\frac{(-\beta)^{\ell}}{\ell!}\mathbf{Tr}_{V}\left[\prod_{j=1}^{\ell}H_{i_{j}}\mathcal{O}\right]$
	$\displaystyle=\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\end{subarray}}\sum_{\ell=0}^{+\infty}\sum_{\begin{subarray}{c}\bm{i}=(i_{1},i_{2},\ldots,i_{k})\in[m]^{k}\\ S=S_{\bm{i}}\end{subarray}}\frac{(-\beta)^{\ell}}{\ell!}\mathbf{Tr}_{V}\left[\prod_{j=1}^{\ell}H_{i_{j}}\mathcal{O}\right]$
	$\displaystyle=\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists i\in S,x\in\mathrm{supp}(H_{i})\\ G_{H}[S]\text{ is connected}\end{subarray}}\sum_{l=\left\|S\right\|}^{+\infty}\sum_{r=0}^{+\infty}\frac{(-\beta)^{l+r}}{l!r!}\left(\sum_{\begin{subarray}{c}(i_{1},i_{2},\ldots,i_{l})\in S^{l}\\ \cup_{j=1}^{l}\{i_{j}\}=S\end{subarray}}\mathbf{Tr}_{R_{S}}\left[\prod_{j=1}^{l}H_{i_{j}}\mathcal{O}_{R_{S}}\right]\right)\left(\sum_{\begin{subarray}{c}(i_{1},i_{2},\ldots,i_{r})\in[m]^{l}\\ \mathrm{supp}(H_{i_{l}})\subseteq V\setminus R_{S}\end{subarray}}\mathbf{Tr}_{V\setminus R_{S}}\left[\prod_{j=1}^{r}H_{i_{j}}\mathcal{O}_{V\setminus R_{S}}\right]\right)$
	$\displaystyle=\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected}\end{subarray}}\left(\sum_{l=\left\|S\right\|}^{+\infty}\frac{(-\beta)^{l}}{l!}\sum_{\begin{subarray}{c}(i_{1},i_{2},\ldots,i_{l})\in S^{l}\\ \cup_{j=1}^{l}\{i_{j}\}=S\end{subarray}}\mathbf{Tr}_{R_{S}}\left[\prod_{j=1}^{l}H_{i_{j}}\mathcal{O}_{R_{S}}\right]\right)Z^{V\setminus R}_{H,\mathcal{O}}(\beta)$
	$\displaystyle=\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected}\end{subarray}}W_{S}(\beta)Z^{V\setminus R_{S}}_{H,\mathcal{O}}(\beta),$

where these identities hold by Fubini’s theorem assuming that the summation converges absolutely. Hence, it remains to verify that $\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected}\end{subarray}}\left|W_{S}(\beta)Z^{V\setminus R}_{H,\mathcal{O}}(\beta)\right|<+\infty$ .

Note that

	$\displaystyle\left\|W_{S}(\beta)\right\|$	$\displaystyle\leq\sum_{l=\left\|S\right\|}^{+\infty}\frac{\left\|\beta\right\|^{l}}{l!}\sum_{\begin{subarray}{c}(i_{1},i_{2},\ldots,i_{l})\in S^{l}\\ \cup_{j=1}^{l}\{i_{j}\}=S\end{subarray}}\mathbf{Tr}_{R_{S}}\left[\left\|\prod_{j=1}^{l}H_{i_{j}}\mathcal{O}_{R_{S}}\right\|\right]$
		$\displaystyle\leq\mathbf{Tr}_{R_{S}}[\mathcal{O}_{R_{S}}]\sum_{l=\left\|S\right\|}^{+\infty}\frac{(\left\|\beta\right\|h)^{l}}{l!}\left\|\{(i_{1},i_{2},\ldots,i_{l})\in S^{l}\mid\cup_{j=1}^{l}\{i_{j}\}=S\}\right\|$
		$\displaystyle=\mathbf{Tr}_{R_{S}}[\mathcal{O}_{R_{S}}]\sum_{l=\left\|S\right\|}^{+\infty}\frac{(\left\|\beta\right\|h)^{l}}{l!}\sum_{\begin{subarray}{c}j_{1},j_{2},\ldots,j_{\left\|S\right\|}\geq 1\\ j_{1}+j_{2}+\ldots+j_{\left\|S\right\|}=l\end{subarray}}\frac{l!}{j_{1}!j_{2}!\ldots j_{\left\|S\right\|}!}$
(15)			$\displaystyle=\mathbf{Tr}_{R_{S}}[\mathcal{O}_{R_{S}}]\left(\exp(\left\|\beta\right\|h)-1\right)^{\left\|S\right\|},$

where the two inequalities follow from triangle inequality and Hölder’s inequality respectively. Similarly,

\displaystyle\left|Z_{V\setminus R_{S}}^{H,\mathcal{O}}(\beta)\right|\leq\mathbf{Tr}_{V\setminus R_{S}}\left[\mathcal{O}_{V\setminus R_{S}}\right]\exp(\left\|\beta H_{V\setminus R_{S}}\right\|)\leq\mathbf{Tr}_{V\setminus R_{S}}\left[\mathcal{O}_{V\setminus R_{S}}\right]\exp(\left|\beta\right|hdn),

where the last inequality follows from the fact that $m\leq dn$ . Hence,

	$\displaystyle\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected}\end{subarray}}\left\|W_{S}(\beta)Z^{V\setminus R_{S}}_{H,\mathcal{O}}(\beta)\right\|$	$\displaystyle\leq\mathbf{Tr}[\mathcal{O}]\exp(\left\|\beta\right\|hdn)\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected }\end{subarray}}\left(\exp(\left\|\beta\right\|h)-1\right)^{\left\|S\right\|}$
		$\displaystyle\leq\mathbf{Tr}[\mathcal{O}]\exp(\left\|\beta\right\|hdn)\sum_{\ell=0}^{+\infty}(\mathrm{e}d)^{\ell}\left(\exp(\left\|\beta\right\|h)-1\right)^{\ell},$

where the last inequality follows from 4.2 that there exists at most $(\mathrm{e}d)^{\ell}$ connected subgraph of size $\ell$ in dependency graph $G_{H}$ which contains vertice $j\in U$ such that $x\in\mathrm{supp}(H_{j})$ . Since $\left|\beta\right|<\frac{1}{\mathrm{e}(\mathrm{e}-1)dh}$ ,

\displaystyle\mathrm{e}d\left(\exp(\left|\beta\right|h)-1\right)<\mathrm{e}(\mathrm{e}-1)dh\left|\beta\right|<1,

concluding the proof of Lemma 5.4. ∎

At last, we need the following technical lemma [18, Lemma 27] in order to prove Lemma 5.2.

Lemma 5.5 ([18]).

Let $H=\sum_{i=1}^{m}H_{i}$ be a $(k,d)$ -Hamiltonian, and $\beta_{0}=\frac{1}{5\mathrm{e}dkh}$ , then for $\left|\beta\right|<\beta_{0}$

\displaystyle\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected}\end{subarray}}\left(\mathrm{e}^{\left|\beta\right|h}-1\right)^{\left|S\right|}\exp(dh\mathrm{e}^{2}\left|\beta\right|\left|R_{S}\right|)\leq\mathrm{e}(\mathrm{e}-1)dh\left|\beta\right|.

Proof of Lemma 5.2.

Let $\Lambda\subseteq V$ . As observed in [18], it suffices to prove that removal of single site $x\in\Lambda$ can only produce bounded additive overhead to $\log Z_{H,\mathcal{O}}^{\Lambda}(\beta)$ . Formally, we are going to prove that, for any $x\in\Lambda$ ,

\displaystyle\log\left|\frac{1}{\mathbf{Tr}[\mathcal{O}_{x}]}\frac{Z^{\Lambda}_{H,\mathcal{O}}(\beta)}{Z^{\Lambda\setminus\{x\}}_{H,\mathcal{O}}(\beta)}\right|\leq\mathrm{e}^{2}dh\left|\beta\right|,

\displaystyle\left|\beta\right|<\beta_{0}.

We will prove the result by induction on $\left|\Lambda\right|$ . By Lemma 5.4,

	$\displaystyle\left\|\log\left\|\frac{1}{\mathbf{Tr}[\mathcal{O}_{x}]}\frac{Z^{\Lambda}_{H,\mathcal{O}}(\beta)}{Z^{\Lambda\setminus\{x\}}_{H,\mathcal{O}}(\beta)}\right\|\right\|$	$\displaystyle=\left\|\log\left\|1+\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected}\end{subarray}}W_{S}(\beta)\left(\frac{1}{\mathbf{Tr}[\mathcal{O}_{x}]}\frac{Z^{\Lambda\setminus R_{S}}_{H,\mathcal{O}}(\beta)}{Z^{\Lambda\setminus\{x\}}_{H,\mathcal{O}}(\beta)}\right)\right\|\right\|$
		$\displaystyle\leq-\log\left(1-\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected}\end{subarray}}\left\|W_{S}(\beta)\right\|\left\|\frac{1}{\mathbf{Tr}[\mathcal{O}_{x}]}\frac{Z^{\Lambda\setminus R_{S}}_{H,\mathcal{O}}(\beta)}{Z^{\Lambda\setminus\{x\}}_{H,\mathcal{O}}(\beta)}\right\|\right)$
		$\displaystyle\overset{(*)}{\leq}-\log\left(1-\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected}\end{subarray}}\left\|W_{S}(\beta)\right\|\left(\frac{1}{\mathbf{Tr}[\mathcal{O}_{R_{S}}]}\exp(-\mathrm{e}^{2}dh\left\|\beta\right\|)\right)\right)$
		$\displaystyle\overset{(\star)}{\leq}-\log\left(1-\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected}\end{subarray}}\left(\exp(\left\|\beta\right\|h)-1\right)^{\left\|S\right\|}\exp(-\mathrm{e}^{2}dh\left\|\beta\right\|)\right),$

where $(*)$ follows from induction hypothesis and $(\star)$ follows from (15). Together with Lemma 5.5, we have

\displaystyle-\log\left(1-\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected}\end{subarray}}\left(\exp(\left|\beta\right|h)-1\right)^{\left|S\right|}\exp(-\mathrm{e}^{2}dh\left|\beta\right|)\right)\leq-\log(1-\mathrm{e}(\mathrm{e}-1)dh\left|\beta\right|)\leq\mathrm{e}^{2}dh\left|\beta\right|,

where the last inequality follows from the fact that $-\log\left(1-\frac{\mathrm{e}-1}{\mathrm{e}}y\right)\leq y$ for all $y\in[0,1]$ . ∎

6. Acknowledgements

This research was supported by National Natural Science Foundation of China (Grant No. 61972191) and the Program for Innovative Talents and Entrepreneur in Jiangsu.

References

Bar [15] Alexander Barvinok. Computing the partition function for cliques in a graph. Theory of Computing, 11(13):339–355, 2015.
Bar [16] Alexander Barvinok. Computing the permanent of (some) complex matrices. Foundations of Computational Mathematics, 16(2):329–342, 2016.
[3] Alexander Barvinok. Approximating permanents and hafnians. Discrete Analysis, page 1244, 2017.
[4] Alexander Barvinok. Combinatorics and Complexity of Partition Functions. Springer Publishing Company, Incorporated, 1st edition, 2017.
[5] Alexander Barvinok. Computing the partition function of a polynomial on the boolean cube. In A Journey Through Discrete Mathematics, pages 135–164. Springer, 2017.
BCKL [13] Christian Borgs, Jennifer Chayes, Jeff Kahn, and László Lovász. Left and right convergence of graphs with bounded degree. Random Struct. Algorithms, 42(1):1–28, January 2013.
BGGŠ [20] Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič. Inapproximability of the independent set polynomial in the complex plane. SIAM J. Comput., 49(5), 2020.
BGGŠ [21] Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Štefankovič. The complexity of approximating the matching polynomial in the complex plane. ACM Trans. Comput. Theory, 13(2):13:1–13:37, 2021.
BGPR [21] Pjotr Buys, Andreas Galanis, Viresh Patel, and Guus Regts. Lee-yang zeros and the complexity of the ferromagnetic ising model on bounded-degree graphs. In SODA, pages 1508–1519. SIAM, 2021.
CDK⁺ [20] Matthew Coulson, Ewan Davies, Alexandra Kolla, Viresh Patel, and Guus Regts. Statistical physics approaches to unique games. In 35th Computational Complexity Conference (CCC), volume 169 of LIPIcs, pages 13:1–13:27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
[11] Zongchen Chen, Kuikui Liu, and Eric Vigoda. Optimal mixing of glauber dynamics: Entropy factorization via high-dimensional expansion. In STOC, pages 1537–1550, 2021.
[12] Zongchen Chen, Kuikui Liu, and Eric Vigoda. Spectral independence via stability and applications to holant-type problems. arXiv preprint arXiv:2106.03366, 2021.
GHLS [15] Sevag Gharibian, Yichen Huang, Zeph Landau, and Seung Woo Shin. Quantum hamiltonian complexity. Found. Trends Theor. Comput. Sci., 10(3):159–282, 2015.
GJP [03] Leslie Ann Goldberg, Mark Jerrum, and Mike Paterson. The computational complexity of two-state spin systems. Random Structures Algorithms, 23(2):133–154, 2003.
GLL [20] Heng Guo, Jingcheng Liu, and Pinyan Lu. Zeros of ferromagnetic 2-spin systems. In SODA, pages 181–192. SIAM, 2020.
GLLZ [20] Heng Guo, Chao Liao, Pinyan Lu, and Chihao Zhang. Zeros of holant problems: locations and algorithms. ACM Transactions on Algorithms (TALG), 17(1):1–25, 2020.
GŠV [15] Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region. J. ACM, 62(6):Art. 50, 60, 2015.
HMS [20] Aram W Harrow, Saeed Mehraban, and Mehdi Soleimanifar. Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. In STOC, pages 378–386, 2020.
HPR [20] Tyler Helmuth, Will Perkins, and Guus Regts. Algorithmic pirogov–sinai theory. Probability Theory and Related Fields, 176(3):851–895, 2020.
JS [93] Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM Journal on Computing, 22(5):1087–1116, 1993.
JSV [04] Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM (JACM), 51(4):671–697, 2004.
KKB [20] Tomotaka Kuwahara, Kohtaro Kato, and Fernando GSL Brandão. Clustering of conditional mutual information for quantum gibbs states above a threshold temperature. Physical review letters, 124(22):220601, 2020.
KSVV [02] Alexei Yu Kitaev, Alexander Shen, Mikhail N Vyalyi, and Mikhail N Vyalyi. Classical and quantum computation. Number 47. American Mathematical Soc., 2002.
LLY [13] Liang Li, Pinyan Lu, and Yitong Yin. Correlation decay up to uniqueness in spin systems. In SODA, pages 67–84. SIAM, 2013.
[25] Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava. Correlation decay and partition function zeros: Algorithms and phase transitions. arXiv preprint arXiv:1906.01228, 2019.
[26] Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava. The ising partition function: Zeros and deterministic approximation. Journal of Statistical Physics, 174:287–315, 2019.
LY [52] Tsung-Dao Lee and Chen-Ning Yang. Statistical theory of equations of state and phase transitions. ii. lattice gas and ising model. Physical Review, 87(3):410, 1952.
MH [21] Ryan L Mann and Tyler Helmuth. Efficient algorithms for approximating quantum partition functions. Journal of Mathematical Physics, 62(2):022201, 2021.
PR [17] Viresh Patel and Guus Regts. Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM Journal on Computing, 46(6):1893–1919, Jan 2017.
PR [19] Han Peters and Guus Regts. On a conjecture of sokal concerning roots of the independence polynomial. Michigan Math. J., 68(1):33–35, 2019.
Reg [18] Guus Regts. Zero-free regions of partition functions with applications to algorithms and graph limits. Combinatorica, 38(4):987–1015, 2018.
Sly [10] Allan Sly. Computational transition at the uniqueness threshold. In FOCS, pages 287–296, 2010.
SS [97] Jesús Salas and Alan D Sokal. Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem. J. Stat. Phys., 86(3):551–579, 1997.
SS [10] E.M. Stein and R. Shakarchi. Complex Analysis. Princeton lectures in analysis. Princeton University Press, 2010.
SS [12] Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. In FOCS, pages 361–369, 2012.
SS [20] Shuai Shao and Yuxin Sun. Contraction: A unified perspective of correlation decay and zero-freeness of 2-spin systems. In ICALP, volume 168 of LIPIcs, pages 96:1–96:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
SST [14] Alistair Sinclair, Piyush Srivastava, and Marc Thurley. Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. Journal of Statistical Physics, 155(4):666–686, 2014. (conference version in SODA’12).
ŠVV [09] Daniel Štefankovič, Santosh S. Vempala, and Eric Vigoda. Adaptive simulated annealing: A near-optimal connection between sampling and counting. J. ACM, 56(3):18:1–18:36, 2009.
Wei [06] Dror Weitz. Counting independent sets up to the tree threshold. In STOC, pages 140–149, 2006.

Appendix A Region Transformation

We give a proof of Lemma 2.5 which says that the convex region $\Omega\subseteq\mathbb{C}$ is a $1$ -good region, so long as $\mathrm{dist}(\Omega,z)$ can be determined in $O(1)$ time for all $z\in\Omega$ .

The following result proved in [4, Lemma 2.2.3] explicitly gives a polynomial that maps a disk with radius slightly larger than $1$ to a strip.

Lemma A.1 ([4]).

Let $\delta\in(0,1)$ be a constant. Define $q_{\delta}\in\mathbb{C}[z]$ as follows:

\displaystyle q_{\delta}(z)=\frac{1}{\sum_{k=1}^{n}\frac{C^{k}}{k}}\sum_{k=1}^{n}\frac{(Cz)^{k}}{k},

where $C=1-\exp\left(-\frac{1}{\delta}\right)$ , $n=\left\lfloor\left(1+\frac{1}{\delta}\right)\exp(1+\frac{1}{\delta})\right\rfloor$ . Then for all $\left|z\right|<\rho$ , where $\rho=\frac{1-\exp\left(-1-\frac{1}{\delta}\right)}{1-\exp\left(-\frac{1}{\delta}\right)}>1$ ,

(1)

$q_{\delta}(0)=0$ , $q_{\delta}(1)=1$ ,
(2)

$\mathbf{Re}\left(q_{\delta}(z)\right)\in[-\delta,1+2\delta]$ and $\left|\mathbf{Im}\left(q_{\delta}(z)\right)\right|\leq 2\delta$ .

We now can prove Lemma 2.5.

Proof of Lemma 2.5.

Without loss of generality, we assume that $\beta\neq 0$ . Note that the polynomial $q_{\delta}$ defined in Lemma A.1 satisfies

(1)

$q_{\delta}(\mathbb{D}_{\rho})\subseteq S_{1,4\delta}$ ;
(2)

$q_{\delta}(0)=0$ , $q_{\delta}(1)=1$ .

Therefore, we can set $p_{\beta,\delta}(z)=\beta q_{\delta^{\prime}}(\rho^{\prime}z)$ , where $\delta_{0}=\frac{\delta}{4\left|\beta\right|}$ and $\rho^{\prime}=\frac{1-\exp\left(-1-\frac{1}{\delta^{\prime}}\right)}{1-\exp\left(-\frac{1}{\delta^{\prime}}\right)}$ . We conclude our proof by observing that:

(1)

$p_{\beta,\delta}(\mathbb{D})\subseteq S_{\beta,\gamma}$ ;
(2)

$p_{\beta,\delta}(0)=0$ , $p_{\beta,\delta}\left(\frac{1}{\rho^{\prime}}\right)=\beta$ .

∎

Here we give a proof of 3.4, which is a direct application of Lemma 2.5.

Proof of 3.4.

The convexity of $\Omega$ implies that $\mathrm{dist}([z_{l},z_{r}],\partial\Omega)=\mathrm{min}(\mathrm{dist}(z_{l}),\mathrm{dist}(z_{r}))$ for arbitrary complex values $z_{l},z_{r}\in\Omega$ , where $[z_{l},z_{r}]=\{z_{l}+t(z_{r}-z_{l})\mid t\in[0,1]\}$ . Hence, for each $x\in\Omega$ , we set $f_{x}=p_{x,\delta}$ , a polynomial defined in Lemma A.1. We conclude the proof by observing that the $k$ -th coefficient of $p_{x,\delta}$ can be determined in $O(k)$ time. ∎

	$\displaystyle\left\|W_{S}(\beta)\right\|$	$\displaystyle\leq\sum_{l=\left\|S\right\|}^{+\infty}\frac{\left\|\beta\right\|^{l}}{l!}\sum_{\begin{subarray}{c}(i_{1},i_{2},\ldots,i_{l})\in S^{l}\\ \cup_{j=1}^{l}\{i_{j}\}=S\end{subarray}}\mathbf{Tr}_{R_{S}}\left[\left\|\prod_{j=1}^{l}H_{i_{j}}\mathcal{O}_{R_{S}}\right\|\right]$
		$\displaystyle\leq\mathbf{Tr}_{R_{S}}[\mathcal{O}_{R_{S}}]\sum_{l=\left\|S\right\|}^{+\infty}\frac{(\left\|\beta\right\|h)^{l}}{l!}\left\|\{(i_{1},i_{2},\ldots,i_{l})\in S^{l}\mid\cup_{j=1}^{l}\{i_{j}\}=S\}\right\|$
		$\displaystyle=\mathbf{Tr}_{R_{S}}[\mathcal{O}_{R_{S}}]\sum_{l=\left\|S\right\|}^{+\infty}\frac{(\left\|\beta\right\|h)^{l}}{l!}\sum_{\begin{subarray}{c}j_{1},j_{2},\ldots,j_{\left\|S\right\|}\geq 1\\ j_{1}+j_{2}+\ldots+j_{\left\|S\right\|}=l\end{subarray}}\frac{l!}{j_{1}!j_{2}!\ldots j_{\left\|S\right\|}!}$
(15)			$\displaystyle=\mathbf{Tr}_{R_{S}}[\mathcal{O}_{R_{S}}]\left(\exp(\left\|\beta\right\|h)-1\right)^{\left\|S\right\|},$

	$\displaystyle\left\|\log\left\|\frac{1}{\mathbf{Tr}[\mathcal{O}_{x}]}\frac{Z^{\Lambda}_{H,\mathcal{O}}(\beta)}{Z^{\Lambda\setminus\{x\}}_{H,\mathcal{O}}(\beta)}\right\|\right\|$	$\displaystyle=\left\|\log\left\|1+\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected}\end{subarray}}W_{S}(\beta)\left(\frac{1}{\mathbf{Tr}[\mathcal{O}_{x}]}\frac{Z^{\Lambda\setminus R_{S}}_{H,\mathcal{O}}(\beta)}{Z^{\Lambda\setminus\{x\}}_{H,\mathcal{O}}(\beta)}\right)\right\|\right\|$
		$\displaystyle\leq-\log\left(1-\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected}\end{subarray}}\left\|W_{S}(\beta)\right\|\left\|\frac{1}{\mathbf{Tr}[\mathcal{O}_{x}]}\frac{Z^{\Lambda\setminus R_{S}}_{H,\mathcal{O}}(\beta)}{Z^{\Lambda\setminus\{x\}}_{H,\mathcal{O}}(\beta)}\right\|\right)$
		$\displaystyle\overset{(*)}{\leq}-\log\left(1-\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected}\end{subarray}}\left\|W_{S}(\beta)\right\|\left(\frac{1}{\mathbf{Tr}[\mathcal{O}_{R_{S}}]}\exp(-\mathrm{e}^{2}dh\left\|\beta\right\|)\right)\right)$
		$\displaystyle\overset{(\star)}{\leq}-\log\left(1-\sum_{\begin{subarray}{c}S\subseteq[m]\\ \exists j\in S,x\in\mathrm{supp}(H_{j})\\ G_{H}[S]\text{ is connected}\end{subarray}}\left(\exp(\left\|\beta\right\|h)-1\right)^{\left\|S\right\|}\exp(-\mathrm{e}^{2}dh\left\|\beta\right\|)\right),$

Polynomial-Time Approximation of Zero-Free Partition Functions

Abstract.

1. Introduction

1.1. Our results.

Definition 1.1 (local Hamiltonian).

Theorem 1.2 (Theorem 3.6, informal).

Theorem 1.3 (Theorem 3.5, informal).

2. Preliminaries

2.1. Local Hamiltonians

2.2. Basic facts about complex functions

2.3. Approximation of non-vanishing function

Definition 2.1 (zero-freeness).

Lemma 2.2.

Proof.

Lemma 2.3 ([4]).

Lemma 2.4 (Newton’s identity).

Proof.

Lemma 2.5 ([4]).

3. Approximation of Zero-Free Holomorphic Function

Definition 3.1 (boundedness).

Theorem 3.2 (efficient coefficient computing).

Definition 3.3 (good region).

Fact 3.4.

Theorem 3.5 (efficient ε\varepsilon-approximation).

Proof of Theorem 3.5.

3.1. Quantum partition functions

Theorem 3.6.

Proof of Theorem 3.6.

3.2. Induced subgraph counting

3.3. Boolean CSP with external field

Corollary 3.7.

3.4. A barrier to non-multiplicative functions

4. Efficient Coefficient Computing

Lemma 4.1.

Fact 4.2 (Lemma 2.1 (c) in [6]).

Lemma 4.3.

Proof.

Lemma 4.4.

Proof of Lemma 4.1.

5. Applications

Theorem 5.1.

Lemma 5.2.

Theorem 5.3.

Proof.

5.1. Proof of Lemma 5.2

Lemma 5.4 (high temperature expansion [18]).

Proof.

Lemma 5.5 ([18]).

Proof of Lemma 5.2.

6. Acknowledgements

References

Appendix A Region Transformation

Lemma A.1 ([4]).

Proof of Lemma 2.5.

Proof of 3.4.

Theorem 3.5 (efficient $\varepsilon$ -approximation).