EUVIMEDEUVIMED entdecken
Crossref

The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs

Andreas Galanis, Leslie A. Goldberg, Andres Herrera-Poyatos

SIAM Journal on Discrete Mathematics · 2022-09 · 36 (3) · 2159-2204

DOI: 10.1137/21m1454043 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 06.09.2022. Verfasst von Andreas Galanis und 2 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 42 Literaturangaben. Gefördert von: Engineering and Physical Sciences Research Council, University of Oxford.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the complexity of approximating the partition function $Z_{\mathrm{Ising}}(G; \beta)$ of the Ising model in terms of the relation between the edge interaction $\beta$ and a parameter $\Delta$ which is an upper bound on the maximum degree of the input graph $G$. Following recent trends in both statistical physics and algorithmic research, we allow the edge interaction $\beta$ to be any complex number. Many recent partition function results focus on complex parameters, both because of physical relevance and because of the key role of the complex case in delineating the tractability/intractability phase transition of the approximation problem. In this work we establish both new tractability results and new intractability results. Our tractability results show that $Z_{\mathrm{Ising}}(-; \beta)$ has an FPTAS when $\lvert \beta - 1 \rvert / \lvert \beta + 1 \rvert < \tan(\pi / (4 \Delta - 4))$. The core of the proof is showing that there are no inputs $G$ that make the partition function $0$ when $\beta$ is in this range. Our result significantly extends the known zero-free region of the Ising model (and hence the known approximation results). Our intractability results show that it is $\mathrm{\#P}$-hard to multiplicatively approximate the norm and to additively approximate the argument of $Z_{\mathrm{Ising}}(-; \beta)$ when $\beta \in \mathbb{C}$ is an algebraic number such that $\beta \not \in \mathbb{R} \cup \{i, -i\}$ and $\lvert \beta - 1\rvert / \lvert \beta + 1 \rvert > 1 / \sqrt{\Delta - 1}$. These are the first results to show intractability of approximating $Z_{\mathrm{Ising}}(-, \beta)$ on bounded degree graphs with complex $\beta$. Moreover, we demonstrate situations in which zeros of the partition function imply hardness of approximation in the Ising model.

Förderung

  • Engineering and Physical Sciences Research Council
  • University of Oxford

Zitieren

APA

Galanis, A., Goldberg, L. A., & Herrera-Poyatos, A. (2022). The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs. SIAM Journal on Discrete Mathematics, 36(3), 2159-2204. https://doi.org/10.1137/21m1454043

Vancouver

Galanis A, Goldberg LA, Herrera-Poyatos A. The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs. SIAM Journal on Discrete Mathematics. 2022;36(3):2159-2204. doi:10.1137/21m1454043

BibTeX
@article{Galanis2022,
  author = {Galanis, Andreas and Goldberg, Leslie A. and Herrera-Poyatos, Andres},
  title = {The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs},
  journal = {SIAM Journal on Discrete Mathematics},
  year = {2022},
  volume = {36},
  number = {3},
  pages = {2159--2204},
  doi = {10.1137/21m1454043}
}
Kostenlos starten →