【Paper Sharing】 The Grammar of the Ising Model - A New Complexity Hierarchy

Title: The Grammar of the Ising Model: A New Complexity Hierarchy

Authors: Tobias Reinhart, Gemma De las Cuevas

Citation: Tobias Reinhart, & Gemma De las Cuevas (2022). The Grammar of the Ising Model: A New Complexity Hierarchy.

To explore the complexity of the Ising model, an effective approach is to analyze the complexity of its Ground State Energy (GSE) problem. Specifically, the GSE problem is defined as follows: given an interaction graph and a specific energy value, determine whether there exists an Ising spin configuration such that the system’s energy is lower than the given value.

The decidability of the GSE problem fundamentally depends on the planarity of the interaction graph of Ising sites, which divides the complexity of the Ising model into two categories. However, this classification method only considers the planarity of the interaction graph, which has certain limitations. To address this, Tobias Reinhart and colleagues, in their study, proposed an analysis method for the Ising model based on formal language modeling, from the perspectives of formal languages, generative grammars, and computational complexity theory. By associating the language of the Ising model with its position in the Chomsky hierarchy, they classified the complexity of the Ising model. Additionally, the study provided detailed discussions and proofs of related theorems and the complexity of seven Ising models as learning cases.

Personally, I believe this research offers a fascinating approach to studying natural phenomena and their complexity using formal and generative tools. Generativity is a relatively important principle underlying many natural phenomena, arising from variation and difference. Even in minimal difference systems composed of yin and yang, or 0 and 1, their interactions can produce complex structures, driving the evolution of all things. The Ising model, under the minimal difference system of 0 and 1, models the macroscopic phenomena arising from interaction structures, while formal grammars and computational complexity theory provide a formal method for discussing the generativity and complexity of these structures.

As a proposal, in this work, the authors define the language $L_{\mathcal{M}}$ of the Ising model $\mathcal{M}$ as the set of all valid configurations and their corresponding Hamiltonians, i.e.,
$$
L_{\mathcal{M}} = {(x, H_\mathcal M(x)) \mid x \text{ is a configuration of } \mathcal{M}},
$$
where $x$ is a configuration of the Ising model, and $H_\mathcal M(x)$ is the Hamiltonian of configuration $c$ under model $\mathcal{M}$. In short, the language of the Ising model $L_{\mathcal{M}}$ is the set of sentences composed of all valid configurations and their corresponding Hamiltonians. Additionally, the authors define the language of edges $E_\mathcal M$ with respect to the interaction graph:
$$
E_\mathcal M := {0^{i-1}10^{j-i-1}10^{n-j}|n\in N_\mathcal M, (i,j) \in (E_\mathcal M)_n}
$$
where $\mathcal{M}$ is a class of Ising models, $N_\mathcal M$ is the set of possible site numbers, $n$ is the number of sites in the Ising model, and $E_n$ represents the edge connections under model $\mathcal{M}$ when the number of sites is $n$.

Here, $(i, j)$ denotes the connection between sites $i$ and $j$.

By classifying $L_{\mathcal{M}}$ and $E_\mathcal M$ into the appropriate levels of the Chomsky hierarchy,

the authors discuss the complexity of the Ising model and prove the following four main results:

1. $L_{\mathcal{M}}$ is regular if and only if $\mathcal{M}$ is finite.
2. ${L}_{\mathcal{M}}$ is constructive context-free if and only if $\mathcal{M}$ is linear and $E_\mathcal M$ is regular.
3. ${L}_{\mathcal{M}}$ is constructive context-sensitive if and only if $\mathcal{M}$ is context-sensitive.
4. ${L}_{\mathcal{M}}$ is decidable if and only if $\mathcal{M}$ is decidable.

Based on these main results, the authors take seven classes of Ising models as examples and discuss the complexity of each class (as shown in Table 1, which is a reproduction of Table 1 from the original text).

Table 1: Summary of seven classes of Ising models, their language classification, edge language classification, finiteness, limitations, and linearity classification.

Ising Model $\mathcal M$	$L_\mathcal M$	$E_\mathcal M$	Finite	Limited	Linear
$\mathcal M_{1d}$	Constructive context free	Regular	No	Yes	Yes
$\mathcal M_{circ}$	Constructive context free	Regular	No	Yes	Yes
$\mathcal M_{ladder}$	Constructive context free	Regular	No	Yes	Yes
$\mathcal M_{layer}$	Constructive context free	Regular	No	Yes	Yes
$\mathcal M_{2d}$	Constructive context sensitive	Context sensitive	No	No	Yes
$\mathcal M_{all}$	Constructive context sensitive	Regular	No	No	No
$\mathcal M_{tree}$	Constructive context sensitive	Context sensitive	No	No	Yes

• $\mathcal{M}$ is defined as finite if the set of possible node numbers $\mathbb{N}$ is finite.
• $\mathcal{M}$ is defined as limited if there exists a natural number $k$ such that for all $n \in \mathbb{N}$ and for any connection pair $(i, j)$, if $|i - j| > k$, then $i$ is in the first block or $j$ is in the last block of a continuous graph partition scheme with block size $k$.
• $\mathcal{M}$ is defined as linear if there exists a natural number $k$ such that for all $n \in \mathbb{N}$, $|E_n| \leq kn$. That is, for a class of Ising models $\mathcal{M}$, for any instance with $n$ nodes, the number of interaction edges has a linear upper bound $kn$.

It is worth noting that the authors extended the Chomsky hierarchy by introducing constructive context-free grammars and constructive context-sensitive grammars (as shown in Figure 1, which is a reproduction of Figure 1 from the original text). The expressive power of grammars increases from regular grammars to decidable grammars.

Figure 1: The Chomsky hierarchy as presented by the authors.

This study provides a new perspective on the complexity analysis of the Ising model through the tools of formal languages and generative grammars. By linking the language $\mathcal{L}_{\mathcal{M}}$ and the edge language $\mathcal{L}_E$ of the Ising model to the Chomsky hierarchy, the authors not only reveal the intrinsic structure of the Ising model’s complexity but also provide an important theoretical framework for studying the generativity and computational complexity of other complex systems.