We study the computational complexity of approximating the partition function of the ferromagnetic Ising model in the Lee-Yang circle of zeros given by |\lambda|=1, where \lambda is the external field of the model . Complex-valued parameters for the Ising model are relevant for quantum circuit computations and phase transitions in statistical physics, but have also been key in the recent deterministic approximation scheme for all |\lambda|\neq 1 by Liu, Sinclair, and Srivastava. Here, we focus on the unresolved complexity picture on the unit circle, and on the tantalising question of what happens in the circular arc around \lambda=1, where on one hand the classical algorithm of Jerrum and Sinclair gives a randomised approximation scheme on the real axis suggesting tractability, and on the other hand the presence of Lee-Yang zeros alludes to computational hardness. Our main result establishes a sharp computational transition at the point \lambda=1 ; in fact, our techniques apply more generally to the whole unit circle|\lambda|=1. We show #P-hardness for approximating the partition function on graphs of maximum degree \Delta when b, the edge-interaction parameter, is in the interval (0,\frac{\Delta-2{\Delta}}%DIFDELCMD < ] %%% and \lambda is a non-real on the unit circle . This result contrasts with known approximation algorithms when |\lambda|\neq 1 or b\in (\frac{\Delta-2{\Delta},}  1 ), and shows that the Lee-Yang circleof zeros is computationally intractable, even on bounded-degree graphs.
We study the computational complexity of approximating the partition function of the ferromagnetic Ising model with the external field parameter \lambda on the unit circle in the complex plane . Complex-valued parameters for the Ising model are relevant for quantum circuit computations and phase transitions in statistical physics, but have also been key in the recent deterministic approximation scheme for all |\lambda|\neq 1 by Liu, Sinclair, and Srivastava. Here, we focus on the unresolved complexity picture on the unit circle, and on the tantalising question of what happens around \lambda=1, where on one hand the classical algorithm of Jerrum and Sinclair gives a randomised approximation scheme on the real axis suggesting tractability, and on the other hand the presence of Lee-Yang zeros alludes to computational hardness. Our main result establishes a sharp computational transition at the point \lambda=1 , and more generally on the entire unit circle. For an integer \Delta\geq 3 and edge interaction parameter b\in (0,1) we show #P-hardness for approximating the partition function on graphs of maximum degree \Delta {\Delta}}%DIFDELCMD < ] %%% on the arc of the unit circle where the Lee-Yang zeros are dense . This result contrasts with known approximation algorithms when |\lambda|\neq 1 or {\Delta},} when \lambda is in the complementary arc around 1 of the unit circle. Our work thus gives a direct connection between the presence/absence of Lee-Yang zeros and the tractability of efficiently approximating the partition function on bounded-degree graphs.
R
in the Lee-Yang circle of zeros given by |\lambda|=1, where \lambda is the external field of the model
with the external field parameter \lambda on the unit circle in the complex plane
D
in the circular arc
R
; in fact, our techniques apply more generally to the whole unit circle|\lambda|=1. We
, and more generally on the entire unit circle. For an integer \Delta\geq 3 and edge interaction parameter b\in (0,1) we
D
when b, the edge-interaction parameter, is in the interval (0,\frac{\Delta-2
R
and \lambda is a non-real on the unit circle
on the arc of the unit circle where the Lee-Yang zeros are dense
D
b\in (\frac{\Delta-2
A
when \lambda is in the complementary arc around
R
), and shows that the Lee-Yang circleof zeros is computationally intractable, even
of the unit circle. Our work thus gives a direct connection between the presence/absence of Lee-Yang zeros and the tractability of efficiently approximating the partition function