Complexity classification of the complex-valued Ising model on bounded-degree graphs in the intermediate annulus

For the Ising partition function $Z_{\mathrm{Ising}}(G;\beta)$ with complex edge interaction $\beta$ on graphs of maximum degree at most $\Delta$, Galanis, Goldberg and Herrera-Poyatos proved an FPTAS for $|(\beta-1)/(\beta+1)|<\tan(\pi/(4(\Delta-1)))$ and #P-hardness of approximating the norm and the argument for non-real algebraic $\beta\notin\{i,-i\}$ with $|(\beta-1)/(\beta+1)|>1/\sqrt{\Delta-1}$, leaving the intermediate region unclassified and proposing the zeros-imply-hardness Conjecture 7. Patel, Regts and Stam later proved a zero-free disk of radius $n_\Delta=(1-1/\sqrt{2(\Delta-1)})^2/(\Delta-1)$, which contains the $\tan(\pi/(4(\Delta-1)))$ disk — and hence makes the inner part of that region tractable — for all sufficiently large $\Delta$; Mann and Minko separately established #P-hardness at certain unit-circle interactions on multigraphs, improving on the $1/\sqrt{\Delta-1}$ threshold for $\Delta\ge7$. Apart from those already-classified points, the surviving open core lies in the annulus $\max\{n_\Delta,\tan(\pi/(4(\Delta-1)))\}<|(\beta-1)/(\beta+1)|\le1/\sqrt{\Delta-1}$: for integer $\Delta\ge3$ and non-real algebraic $\beta\notin\{i,-i\}$ in this annulus, determine the exact computational complexity of IsingNorm$(\beta,\Delta,1.01)$ and IsingArg$(\beta,\Delta,\pi/3)$ — in particular whether a zero of $Z_{\mathrm{Ising}}$ on a graph of maximum degree at most $\Delta$ forces #P-hardness (Conjecture 7), and whether the square-root in the gadget-implementation threshold can be removed so that the complex phase boundary meets the near-optimal zero-free disk.

Background

The Ising model is the canonical two-state spin system on a graph. Given an undirected graph $G=(V,E)$ (possibly with multiple edges or loops) and an edge interaction $\beta$, the partition function is

$$Z_{\mathrm{Ising}}(G;\beta)=\sum_{\sigma:V\to\{0,1\}}\beta^{m(\sigma)},$$

where $m(\sigma)$ is the number of monochromatic edges of $G$ (edges whose two endpoints receive the same spin). It is a polynomial in $\beta$; the classical statistical-mechanics Ising model is the case of real $\beta$ ($\beta>1$ ferromagnetic, $0<\beta<1$ anti-ferromagnetic). Throughout, $\lambda=(\beta-1)/(\beta+1)$ denotes the standard reparametrisation of the edge interaction: this Möbius change of variables maps the $\beta$-plane (minus $\beta=-1$) to the $\lambda$-plane, sends the trivial interaction $\beta=1$ to $\lambda=0$, and is the natural coordinate for zero-location results.

This problem concerns the computational complexity of approximating $Z_{\mathrm{Ising}}$ when the input graph has maximum degree at most a fixed integer $\Delta\ge3$ and $\beta$ is a fixed algebraic number allowed to be complex. Two approximation problems are studied: IsingNorm$(\beta,\Delta,c)$ asks, given a graph $G$ of maximum degree at most $\Delta$, for a multiplicative $c$-approximation of the norm $|Z_{\mathrm{Ising}}(G;\beta)|$, and IsingArg$(\beta,\Delta,\rho)$ asks for an additive $\rho$-approximation of the argument of $Z_{\mathrm{Ising}}(G;\beta)$. #P-hardness means at least as hard as every problem in #P, the class of counting problems such as counting satisfying assignments of a Boolean formula; an FPTAS (fully polynomial-time approximation scheme) is an algorithm whose running time is polynomial in the input size and $1/\varepsilon$ and which approximates within relative error $\varepsilon$.

Complex parameters matter here for two reasons. Physically, zeros of the partition function at complex parameters are the mechanism of phase transitions: in the Lee–Yang circle theorem and its successors, phase boundaries in the thermodynamic limit are traced by loci of zeros in the complex plane. Algorithmically, Barvinok's method converts zero-freeness into approximability: if $Z_{\mathrm{Ising}}(G;\beta)\neq0$ for every input $G$ throughout a region containing the parameter, a truncated Taylor series of $\log Z_{\mathrm{Ising}}$ yields an FPTAS. So the location of complex zeros and the complexity of approximate counting are two views of a single computational phase transition, and the field's goal is a complete tractability/hardness classification of the $(\Delta,\beta)$ plane. On the real axis the picture is essentially complete — approximation is tractable above the tree uniqueness threshold $\beta=(\Delta-2)/\Delta$, which corresponds to $|\lambda|=1/(\Delta-1)$, and intractable below it — and Goldberg and Guo had classified the unbounded-degree complex case completely. The bounded-degree complex case is the remaining frontier.

Galanis, Goldberg and Herrera-Poyatos pinned down this frontier up to a gap. Their Theorem 1 shows $Z_{\mathrm{Ising}}(G;\beta)\neq0$ for all graphs of maximum degree at most $\Delta$ whenever $|\lambda|<\tan(\pi/(4(\Delta-1)))$, giving an FPTAS there; their Theorem 3 shows that for non-real algebraic $\beta\notin\{i,-i\}$ with $|\lambda|>1/\sqrt{\Delta-1}$, IsingNorm$(\beta,\Delta,1.01)$ and IsingArg$(\beta,\Delta,\pi/3)$ are #P-hard — the first intractability results for approximating the Ising model on bounded-degree graphs with complex $\beta$. The hardness machinery is gadget implementation: a graph $\hat G$ with two terminals $s,t$ $\beta$-implements an edge interaction $\lambda'$ if a ratio of partition functions of $\hat G$ with the terminals' spins pinned (the restricted partition functions $Z^{ij}_{st}$, $i,j\in\{0,1\}$) equals $\lambda'$; rich enough implementation power lets one encode exact computation into approximate computation. Their Lemma 5 shows that the pair $(\Delta,\beta)$ implements the entire complex plane whenever $|\lambda|>1/\sqrt{\Delta-1}$; the square root in this threshold is an artifact of the edge-style gadget construction, and the authors explicitly leave its removal as a tantalising open problem. Between the two thresholds, the region

$$\tan\!\left(\frac{\pi}{4(\Delta-1)}\right)\le\left|\frac{\beta-1}{\beta+1}\right|\le\frac{1}{\sqrt{\Delta-1}}$$

(denoted region (1) in the paper) was left unclassified, even though zeros of $Z_{\mathrm{Ising}}$ exist inside it. The paper conjectures (Conjecture 7) that zeros always imply hardness: if there is a graph of maximum degree at most $\Delta$ with $Z_{\mathrm{Ising}}(G;\beta)=0$, then IsingNorm$(\beta,\Delta,1.01)$ and IsingArg$(\beta,\Delta,\pi/3)$ are #P-hard. This is proven only under side conditions: Lemma 46 needs terminals of degree at most $\Delta-1$ with a non-vanishing restricted partition function, and Corollary 48 needs the zero to occur already on a graph of maximum degree at most $\Delta-1$.

After the source paper, the inner boundary of the gap moved for large $\Delta$. Patel, Regts and Stam proved a zero-free disk of radius $n_\Delta=(1-1/\sqrt{2(\Delta-1)})^2/(\Delta-1)=(1-o_\Delta(1))/(\Delta-1)$ in the $\lambda$-plane, which their paper notes contains the previous zero-free disk of radius $\tan(\pi/(4(\Delta-1)))$ only for $\Delta$ large enough (the inclusion fails for small $\Delta$: e.g. $n_3=(1-1/2)^2/2=0.125<\tan(\pi/8)\approx0.414$), and which yields an FPTAS; they show that a zero-free disk of radius $c/(\Delta-1)$ with $c>1$ is impossible unless P=NP (via real anti-ferromagnetic hardness), and ask whether the radius can be improved to exactly $1/(\Delta-1)$ and whether the disk is optimal in the imaginary direction. On the hardness side, Mann and Minko — who write the partition function in the edge-coupled form $\sum_\sigma\prod_e e^{-i\theta\sigma_u\sigma_v}$ with spins $\sigma_v\in\{-1,1\}$, corresponding in the source parametrization to unit-circle interactions $\beta=e^{-2i\theta}$ with $|\lambda|=|\tan\theta|$ — proved #P-hardness for multigraphs of maximum degree at most $\Delta$ with $|\theta|\ge3\pi/(5(\Delta-2))$, that is, on the principal branch $|\theta|<\pi/2$, at $|\lambda|\ge\tan(3\pi/(5(\Delta-2)))=\Theta(1/\Delta)$; as they remark, this improves on the source paper's threshold $|\theta|>\arctan(1/\sqrt{\Delta-1})$ only for $\Delta\ge7$, and in all cases it applies only at these unit-circle points and only for multigraphs. The region between the outer of the two known zero-free radii, $\max\{n_\Delta,\tan(\pi/(4(\Delta-1)))\}$, and the hardness threshold $1/\sqrt{\Delta-1}$ is not known to be zero-free or known hard in general — the real-axis neighbourhood of Liu, Sinclair and Srivastava, a zero-free region that is not a disk, reaches into it near the real axis — and classifying the remaining parameters is the open problem stated here.

Problem Statement

Fix an integer $\Delta\ge3$ and let $\lambda=(\beta-1)/(\beta+1)$. Complete the tractability/hardness classification of approximating the complex-valued Ising partition function on graphs of maximum degree at most $\Delta$ in the intermediate annulus: for every algebraic $\beta\notin\mathbb{R}\cup\{i,-i\}$ with

$$\max\left\{\frac{\left(1-\frac{1}{\sqrt{2(\Delta-1)}}\right)^2}{\Delta-1},\ \tan\!\left(\frac{\pi}{4(\Delta-1)}\right)\right\}<\left|\frac{\beta-1}{\beta+1}\right|\le\frac{1}{\sqrt{\Delta-1}},$$

determine the computational complexity of IsingNorm$(\beta,\Delta,1.01)$ — the task of computing, on input a (multi)graph $G$ of maximum degree at most $\Delta$, a multiplicative $1.01$-approximation of $|Z_{\mathrm{Ising}}(G;\beta)|$ — and IsingArg$(\beta,\Delta,\pi/3)$ — the task of computing an additive $\pi/3$-approximation of the argument of $Z_{\mathrm{Ising}}(G;\beta)$: does an FPTAS exist, are the problems #P-hard, or does the computational phase boundary fall strictly inside the annulus? (This annulus is the part of the intermediate region (1) posed in the source paper that lies outside the two zero-free disks: the part of region (1) with $|\lambda|\le n_\Delta$, $n_\Delta=(1-1/\sqrt{2(\Delta-1)})^2/(\Delta-1)$, became tractable by the zero-free disk of Patel, Regts and Stam, while the part with $|\lambda|<\tan(\pi/(4(\Delta-1)))$ was already tractable by the source paper's zero-free disk; since the Patel–Regts–Stam disk contains the source disk only for $\Delta$ large enough, the operative inner boundary is the larger of the two radii. The points of the annulus already classified include the specific zeros covered by the source paper's Lemma 46 and Corollary 48, and — for $\Delta\ge7$ — the unit-circle multigraph points of Mann and Minko; the two zero-free disks do not exhaust the known zero-free regions either, since the source paper also records a zero-free neighbourhood of the real uniqueness interval $((\Delta-2)/\Delta,\Delta/(\Delta-2))$ due to Liu, Sinclair and Srivastava (its Theorem 18) and the diamond of Barvinok and Barvinok (its Theorem 19); the neighbourhood of Liu, Sinclair and Srivastava already reaches non-real parameters inside the annulus near the real axis, at $|\lambda|$ up to about $1/(\Delta-1)$ with small non-zero imaginary part, and the diamond of Barvinok and Barvinok does so for large $\Delta$, so that an FPTAS is available at those parameters; settling the classification at the remaining parameters of the annulus is the task here.) The central concrete target is the zeros-imply-hardness conjecture of Galanis, Goldberg and Herrera-Poyatos (Conjecture 7): if there exists a graph $G$ of maximum degree at most $\Delta$ with $Z_{\mathrm{Ising}}(G;\beta)=0$, then IsingNorm$(\beta,\Delta,1.01)$ and IsingArg$(\beta,\Delta,\pi/3)$ are #P-hard — without the currently required side conditions (a zero already on a graph of maximum degree at most $\Delta-1$, or terminals of degree at most $\Delta-1$ with non-vanishing restricted partition function). A full resolution would determine whether the hard region can be extended down to the near-optimal zero-free disk, so that the complex phase boundary coincides with the tree uniqueness circle $|\lambda|=1/(\Delta-1)$ as it does on the real axis — the question the source paper poses as removing the square root in the implementation threshold $1/\sqrt{\Delta-1}$ of Lemma 5.

References

1. Andreas Galanis, Leslie Ann Goldberg, Andrés Herrera-Poyatos, 'The complexity of approximating the complex-valued Ising model on bounded degree graphs', SIAM Journal on Discrete Mathematics 36(3):2159-2204 (2022), DOI 10.1137/21M1454043, https://doi.org/10.1137/21M1454043 (arXiv:2105.00287, https://arxiv.org/abs/2105.00287)
2. Viresh Patel, Guus Regts, Ayla Stam, 'A near-optimal zero-free disk for the Ising model', Combinatorial Theory 4 (2024), DOI 10.5070/c64264237, https://doi.org/10.5070/c64264237 (arXiv:2311.05574, https://arxiv.org/abs/2311.05574)
3. Ryan L. Mann, Romy M. Minko, 'Algorithmic Cluster Expansions for Quantum Problems', PRX Quantum 5, 010305 (2024), DOI 10.1103/PRXQuantum.5.010305, https://doi.org/10.1103/PRXQuantum.5.010305 (arXiv:2306.08974, https://arxiv.org/abs/2306.08974)
4. Pjotr Buys, Andreas Galanis, Viresh Patel, Guus Regts, 'Lee-Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs', Forum of Mathematics, Sigma 10 (2022), DOI 10.1017/fms.2022.4, https://doi.org/10.1017/fms.2022.4 (arXiv:2006.14828, https://arxiv.org/abs/2006.14828)
5. Leslie Ann Goldberg, Heng Guo, 'The complexity of approximating complex-valued Ising and Tutte partition functions', computational complexity 26:765-833 (2017), DOI 10.1007/s00037-017-0162-2, https://doi.org/10.1007/s00037-017-0162-2 (arXiv:1409.5627, https://arxiv.org/abs/1409.5627)
6. Andreas Galanis, Leslie Ann Goldberg, Andrés Herrera-Poyatos, 'The complexity of approximating the complex-valued Potts model', computational complexity 31 (2022), DOI 10.1007/s00037-021-00218-x, https://doi.org/10.1007/s00037-021-00218-x (arXiv:2005.01076, https://arxiv.org/abs/2005.01076)
7. Ferenc Bencs, Chiara Piombi, Guus Regts, 'On the complex zeros and the computational complexity of approximating the reliability polynomial', arXiv:2512.11504 (2025), https://arxiv.org/abs/2512.11504
8. Ferenc Bencs, Jeroen Huijben, Guus Regts, 'Approximating the chromatic polynomial is as hard as computing it exactly', arXiv:2211.13790 (2022), https://arxiv.org/abs/2211.13790
9. Jingcheng Liu, Alistair Sinclair, Piyush Srivastava, 'Fisher zeros and correlation decay in the Ising model', Journal of Mathematical Physics 60(10):103304 (2019), DOI 10.1063/1.5082552, https://doi.org/10.1063/1.5082552 (arXiv:1807.06577, https://arxiv.org/abs/1807.06577)
10. Alexander Barvinok, Nicholas Barvinok, 'More on zeros and approximation of the Ising partition function', Forum of Mathematics, Sigma 9 (2021) e46, DOI 10.1017/fms.2021.40, https://doi.org/10.1017/fms.2021.40 (arXiv:2005.11232, https://arxiv.org/abs/2005.11232)