Two-State Spin Systems with Negative Interactions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912540096724992 |
|---|---|
| author | Fei, Yumou Goldberg, Leslie Ann Lu, Pinyan |
| author_facet | Fei, Yumou Goldberg, Leslie Ann Lu, Pinyan |
| contents | We study the approximability of computing the partition functions of two-state spin systems. The problem is parameterized by a $2\times 2$ symmetric matrix. Previous results on this problem were restricted either to the case where the matrix has non-negative entries, or to the case where the diagonal entries are equal, i.e. Ising models. In this paper, we study the generalization to arbitrary $2\times 2$ interaction matrices with real entries. We show that in some regions of the parameter space, it's \#P-hard to even determine the sign of the partition function, while in other regions there are fully polynomial approximation schemes for the partition function. Our results reveal several new computational phase transitions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_04735 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Two-State Spin Systems with Negative Interactions Fei, Yumou Goldberg, Leslie Ann Lu, Pinyan Computational Complexity We study the approximability of computing the partition functions of two-state spin systems. The problem is parameterized by a $2\times 2$ symmetric matrix. Previous results on this problem were restricted either to the case where the matrix has non-negative entries, or to the case where the diagonal entries are equal, i.e. Ising models. In this paper, we study the generalization to arbitrary $2\times 2$ interaction matrices with real entries. We show that in some regions of the parameter space, it's \#P-hard to even determine the sign of the partition function, while in other regions there are fully polynomial approximation schemes for the partition function. Our results reveal several new computational phase transitions. |
| title | Two-State Spin Systems with Negative Interactions |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2309.04735 |