The cluster expansion is a technique for representing the power series of the logarithm of the partition function. An important question when studying such a series is to define the radius of convergence. One way to bound the radius is by studying the clusters associated with the underlying elements. In order to communicate the idea of a cluster expansion we will first introduce the concept of a polymer model. Polymer models naturally have a standard form of a partition function. Such a formulation is a useful construction for studying more physically motivated mathematical structures. One such idea, which we will briefly discuss, is probability amplitudes. In general this is known to be a #P–hard problem [GG17]. However, it can be shown that specific instances of quantum circuits admit efficient approximation algorithms. The review of this technique shows how the cluster expansion can be applied to Hamiltonians in the context of determining the statistical partition function. It is well known that this problem is #P–hard and so the cluster expansion is a useful tool for approximating solutions to specific instances. Note that the cluster expansion is not always guaranteed to converge absolutely. An informal metric for achieving convergence is to show that the polymer weights are sufficiently small. This analysis closely follows the works of [MH21] and [MM24].

Polymer Model

Two polymers $\gamma, \gamma' \in C$ are said to be compatible if $\gamma \sim \gamma'$. A admissible polymer family for a given polymer model is a subset of polymers $\Gamma \subset C$ such that all distinct $\gamma, \gamma' \in \Gamma$ are compatible, i.e. $\gamma \sim \gamma'$. All possible families form a set $\mathcal{F}$; we say $\mathcal{F}$ is the set of all admissible polymer collections from $C$.

A useful interpretation of a polymer model $(C,w,\sim)$ is via graphical representations. Define a graph $G_C = (V,E)$ where $V = C$ and $E = \{(\gamma,\gamma') : \gamma \nsim \gamma'\}$, i.e. each edge occurs between incompatible polymers. It turns out, the independent sets of $G_C$ are in one-to-one correspondence with the polymer families of the polymer model. All possible independent sets form $\mathcal{F}$. Consider the simple example shown in figure.

The polymer model is a useful tool for studying the partition function and the cluster expansion. Two important quantities we define for a given graph include the order and the size. The order of a graph is the number of vertices denoted $|G|:= |V(G)|$, and the size is the number of edges denoted $||G||:= |E(G)|$. For a strong and concise review of the polymer model and its applications we refer the reader to [MM24].

The Partition Function

The partition function has a succinct definition in terms of the polymer model. For a given model, we define the standard form partition function as $$ \mathcal{Z}(C,w,\sim) := \sum_{\Gamma \in \mathcal{F}} \prod_{\gamma \in \Gamma} w(\gamma). $$ Note that $\Gamma = \emptyset$ has a valid contribution of $+1$ to the partition function. A simple observation shows that the graphical representation of the polymer model renders the partition function as a weighted counting game over all possible independent sets. This makes intuitive sense recalling that the partition function problem is #P–hard.

Using the polymer model we can express $\log(\mathcal{Z})$ as a formal power series. We call this the cluster expansion. If the cluster expansion is absolutely convergent then it is equivalent to $\log(\mathcal{Z})$ up to a rearrangement of terms. In order to find this series we perform a manipulation of the partition function to into the form $\mathcal{Z} = \exp(\dots)$. We will not analyse all the details of this manipulation but simply state the result and some key elements. Recall that $\Gamma$ represents a family of distinct polymers. Let $G_\Gamma$ be the incompatibility graph of $\Gamma$, i.e. the graph with vertex set $\Gamma$ and edge set $\{(\gamma,\gamma') : \gamma \nsim \gamma'\}$. If $G_\Gamma$ is connected then we call $\Gamma$ a cluster. Let $\mathcal{G}_C$ denote the set of all polymer clusters. The cluster expansion is then $$ \log(\mathcal{Z}) := \sum_{\Gamma \in \mathcal{G}_C} \varphi(G_\Gamma) \prod_{\gamma \in \Gamma} w(\gamma), $$ where $\varphi(G_\Gamma)$ is the Ursell function on the incompatibility graph $G_\Gamma$: $$ \varphi(G_\Gamma) := \frac{1}{|G_\Gamma|!} \sum_{\substack{S \subseteq E(G_\Gamma) \\ \text{spanning} \\ \text{connected}}} (-1)^{|S|}. $$ A Theorem due to Kotecký and Preiss gives conditions necessary for absolute convergence of the cluster expansion [KP86] An improved version was given by Fernández and Procacci [Theorem 1, FP07]. We do not state the theorem here but mention that imposing appropriate conditions on the weights of the polymers is sufficient to guarantee absolute convergence.

A Simple Cluster Expansion

To demonstrate how the cluster expansion works we consider a simple example of a polymer model. Let $C = \{\gamma\}$ and $w(\gamma) = z$. Clearly the partition function is $\mathcal{Z} = 1+z$. The incompatibility relation is $\gamma \sim \gamma$ and so the only cluster is $\Gamma = \{\gamma\}$. The incompatibility graph is a single vertex and so $\varphi(G_\Gamma) = 1$. The series expansion for $\log(\mathcal{Z})$ is well-known and given by $$ \begin{align} \log(\mathcal{Z}) &= z - \frac{z^2}{2} + \frac{z^3}{3} - \dots, \notag\\ &= \sum_{n=1}^\infty \frac{(-1)^{n-1}}{n}\;z^n. \end{align} $$ The goal of this example is to show how the cluster expansion gives the same result and argue a bound to give absolute convergence. The series above shows \begin{equation} \begin{split} \log(\mathcal{Z}) &= \varphi(G_{\Gamma_1})\prod_{\gamma \in \Gamma_1} w(\gamma) + \varphi(G_{\Gamma_2})\prod_{\gamma \in \Gamma_2} w(\gamma) \\ &\qquad+ \varphi(G_{\Gamma_3})\prod_{\gamma \in \Gamma_3} w(\gamma) + \dots, \end{split} \end{equation} where $\Gamma_n$ is the $n$-th cluster. Since there is only one polymer, each cluster is the complete graph on $n$ vertices. One slight issue however is the value of the Ursell function for a given complete graph. A non-trivial combinatorial equivalence exists for the Ursell function $\varphi_n := \varphi(\gamma, \dots, \gamma)$, specifically, \begin{equation} \varphi_n = \frac{1}{n!}(-1)^{n-1}(n-1)! = \frac{(-1)^{n-1}}{n}. \end{equation} Additionally the product of weights for the $n$-th cluster is $z^n$. It is not hard to see then how we recover the series expansion of $\log(\mathcal{Z})$. To guarantee absolute convergence we require [Theorem 5.4, FV17] $$ |z|e^{a(\gamma)} \leq a(\gamma), $$ where $a(\gamma)\gt0$ is some constant. It is not hard to see that $ae^{-a}$ is maximal when $a=1$ and so the condition for convergence is $|z| \leq e^{-1}$. This is in contrast to the radius of convergence of the series expansion in the equation above, which is $|z| \leq 1$. The arguments for convergence we used on the cluster expansion are clearly not as strong as the conventional argument. Nevertheless, the bound still lies within the appropriate region and so the cluster expansion is absolutely convergent.

Polymer Model of a Quantum Circuit

Consider a simple quantum circuit on $n$ qubits, comprising of a sequence of $m$ unitary unitary gates, $U_1, \dots, U_m$. The probability amplitude $\mathcal{A}:=\bra{0^n} {U_m \dots U_1} \ket{0^n}$ has a nice abstract polymer model representation [Lemma 12, MM24]. Using the inclusion–exclusion principle we can translate each unitary $U_j$ in the following way: $$ \widetilde{U}_j := U_j - \mathbb{I}. $$ A simple calculation shows that $(\widetilde{U}_j + \mathbb{I})(\widetilde{U}_k + \mathbb{I})= U_jU_k$ and by direction substitution we find that $$ \mathcal{A}=\bra{0^n}{\prod_{j=1}^m U_j}\ket{0^n} = \bra{0^n}{\prod_{j=1}^m (\widetilde{U}_j + \mathbb{I})}\ket{0^n}. $$ A further simple manipulation shows that $$ \bra{0^n}{\prod_{j=1}^m (\widetilde{U}_j + \mathbb{I})}\ket{0^n} = \sum_{S \subseteq [m]} \bra{0^n}{\prod_{s \in S} \widetilde{U}_s}\ket{0^n}. $$ Each $S$ partitions the circuit into a subset of gates. For that given subset it is trivial to see some may act on common qubits and other may act on another disjoint set. We can therefore partition the instance into groups of maximally connected components. See the circuit figure above for a simple example. For a given $S$ we denote $\Gamma_S$ as the set of maximally connected components. Associating the problem to a polymer model this way allows a factorisation over $\Gamma_S$. Note that for a given string of operators $\gamma = \prod \widetilde{U}_j$ only the qubits in the support of the string are non-trivially affected and hence $\ket{0^n} \mapsto \ket{0^{|\gamma|}}$. This gives the simple expression $$ \mathcal{A}=\sum_{S\subseteq [m]} \prod_{\gamma \in \Gamma_S} \bra{0^{|\gamma|}}{\prod_{j\in\gamma} \widetilde{U}_j}\ket{0^{|\gamma|}}. $$ By associating the weight of polymer $\gamma$ with the amplitude $\bra{0^{|\gamma|}}{\prod_{j\in\gamma} \widetilde{U}_j}\ket{0^{|\gamma|}}$, the ampltidue admits a abstract polymer model representation. The partition function of this model is then the amplitude of the quantum circuit. Notice that the set of all maximally connected components is the set of all polymer clusters $\mathcal{G}_C$ where $C$ is the set of polymers. $$ \mathcal{Z} = \sum_{\Gamma \in \mathcal{G}_C} \prod_{\gamma \in \Gamma} w(\gamma), $$ where $$ w(\gamma) = \bra{0^{|\gamma|}}{\prod_{j\in\gamma} (U_j - \mathbb{I})}\ket{0^{|\gamma|}}. $$ Notice for $||U_j - \mathbb{I}|| \ll 1$ the weight $w(\gamma)$ is small and so the cluster expansion is expected to be absolutely convergent.

By covering this example we gain some intuition for how the inclusion–exclusion principle is used to simplify the problem. Additionally we also see how to simplify the problem by considering the set of maximally connected components, i.e. the terms that contribute to the amplitude. This is specifically important when dealing with the partition function of a Hamiltonian.

One slight issue is that the inclusion–exclusion method employed here does not always extend to Hamiltonians — specifically those with terms that do not commute. We will see in the next section how the inclusion–exclusion principle can be used in a more abstract way to simplify the problem of finding the partition function of a local Hamiltonian.

Polymer Model of a Local Hamiltonian

Previously we saw how mapping $\widetilde{U} = U - \mathbb{I}$ allowed us to represent the amplitude of a quantum circuit as a polymer model. We briefly sketch where this idea can be used in the context of a local Hamiltonian. First, consider a classical Hamiltonian with a kinetic term and a two-body potential term. The form of the Hamiltonian roughly follows $$ H(r,p) = \sum_{i=1}^N \frac{p_i^2}{2m} + \sum_{i\lt j}^N \phi(r_i,r_j), $$ where $\phi(r_i,r_j) = \phi(i,j)$ is the potential between particles $i$ and $j$ dependent on their positions. The partition function of this system is given by $$ \begin{align} Z_N(\beta) &= \frac{1}{\mathcal{N}} \int \text{d}^3r\;\text{d}^3p\; e^{-\beta H(r,p)}, \\ &= Z_N^{(0)}(\beta) Q_N(\beta), \end{align} $$ where $Z_N^{(0)}(\beta)$ is the partition function of the non-interacting system and $Q_N(\beta)$ is the partition function of the interacting system termed the configuration integral. We define the Mayer function as $f_{ij} := e^{-\beta \phi(i,j)} - 1$ [Sal58]. Using the Mayer function it is easy to see the configuration integral can be expressed as $$ Q_N(\beta) = \int \text{d}^3r\; \prod_{i\lt j} \left(1 + f_{ij}\right). $$ Expanding this product for a simple case of two particles we easily recover the expected form. The reason this happens is due to the fact that the two-body terms commute! This is not the case for a local quantum Hamiltonian where in general the terms do not commute. So while it is possible to use the inclusion–exclusion method in a straightforward way for a classical Hamiltonian, it is not so for a quantum Hamiltonian. We assume no vanishing commutative properties and so we must use a more abstract method to simplify the problem. We also now define the local Hamiltonian based on the interaction graph.

We have already outlined the equation for the partition function of a Hamiltonian as given by statistical mechanics. We restate this here in the context of the interaction graph. Define $$ \mathcal{Z}(G) = \text{Tr}\left(e^{-\beta H(G)}\right), $$ as the partition function of a local Hamiltonian $H(G)$ on an interaction (hyper)graph $G$. Let $H$ be $k$-local in that $$ H(G) := \sum_{e\in E(G)} h(e), $$ where $h(e) \in \mathbf{L}(\bigotimes_{u\in e}\mathcal{H}_u) \otimes \mathbb{I}$ is a non-trivial self-adjoint $k$-local operator acting on the qubit interaction edge $e$. Since no underling commutative properties are present $\exp(\sum h(e)) \neq \prod \exp(h(e))$. To employ inclusion–exclusion on this problem there is a neat, well-known, lemma that formalises the inclusion–exclusion principle; we use the prescription from [MM24].

By identifying the finite set of objects $A$ as the edge set of the interaction graph $G$ we can use this lemma to find a polymer model representation of the partition function. Note that $f(E(G)) = \mathcal{Z}(G)$ and therefore, $$ \mathcal{Z}(G) = \sum_{S\subseteq E(G)} (-1)^{|S|} \sum_{T\subseteq S} (-1)^{|T|}\text{Tr}\left(e^{-\beta \sum_{e\in T} h(e)}\right) . $$ Again, we define $\Gamma_S$ as the set of maximally connected components for a given subset $S \subseteq E(G)$. For each $\gamma \in \Gamma_S$ we define an edge set $E(\gamma) \subseteq E(G)$ and recall that $||\gamma||$ represents the size of the corresponding subgraph $\gamma$ is associated with. Factorising over $\Gamma_S$ we find $$ \begin{equation} \mathcal{Z}(G) = \sum_{S\subseteq E(G)} \prod_{\gamma \in \Gamma_S}(-1)^{||\gamma||} \sum_{T\subseteq E(\gamma)} (-1)^{|T|}\text{Tr}\left(e^{-\beta \sum_{e\in T} h(e)}\right). \end{equation} $$ Defining the weight of a polymer $\gamma$ as $$ w(\gamma) = (-1)^{||\gamma||} \sum_{T\subseteq E(\gamma)} (-1)^{|T|}\text{Tr}\left(e^{-\beta \sum_{e\in T} h(e)}\right), $$ we recover the standard form of the partition function of a polymer model. To guarantee convergence for the cluster expansion of $\log(\mathcal{Z})$ we require a bound on the inverse temperature $\beta$. An example of such a bound is $|\beta| \leq (e^4 \Delta)^{-1}$ for the case where $G$ is a bounded degree graph of maximum degree $\Delta$ [Theorem 1, MH21].