Hardness conjecture from zeros of the complex-valued Ising partition function

From papers

Let Δ\Delta be an integer with Δ3\Delta \ge 3 and let βCA\beta\in \mathbb{C}_{\mathbb{A}} with β∉R{i,i}\beta \not \in \mathbb{R}\cup \{i, -i\}. Let GG be a graph with maximum degree at most Δ\Delta, and let ZIsing(G;β)Z_{\mathrm{Ising}}(G; \beta) denote its Ising partition function. The approximation problems \textscIsingNorm(β,Δ,1.01)\textsc{IsingNorm}(\beta, \Delta, 1.01) and \textscIsingArg(β,Δ,π/3)\textsc{IsingArg}(\beta, \Delta, \pi/3) concern, respectively, approximating the norm and argument of this partition function. Hardness conjecture from zeros. If there is a graph GG with maximum degree at most Δ\Delta such that

ZIsing(G;β)=0,Z_{\mathrm{Ising}}(G; \beta) = 0,

then the problems

\textscIsingNorm(β,Δ,1.01)and\textscIsingArg(β,Δ,π/3)\textsc{IsingNorm}(\beta, \Delta, 1.01) \quad\text{and}\quad \textsc{IsingArg}(\beta, \Delta, \pi/3)

are #P\mathrm{\#P}-hard. The surrounding discussion explains that a zero of the partition function can typically be used to implement the edge interaction 1-1, which yields hardness through the preceding lemma; the conjecture concerns the case where terminal-degree conditions are not established.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Andreas Galanis, Leslie Ann Goldberg and Andrés Herrera-Poyatos, “The complexity of approximating the complex-valued Ising model on bounded degree graphs”, arXiv:2105.00287 (2022).

Solutions 0

No solutions have been posted yet.