Hamiltonian: The Transverse Ising model $$H=\displaystyle\sum_{\{i,j\}\in E(G)}L_{ij}Z_iZ_j + \displaystyle\sum_{i\in V(G)}f_iX_i$$

Problem: Ground state energy

Complexity: StoqMA–complete

Ref: [BH16]

Conditionals:

• $L_{ij}$ and $f_i$ are real
• $f_i \geq 0$
• $G$ is an interaction graph

Reductions:

• From the 2–local Hamiltonian
• To the Ising model

Hamiltonian: The Classical Ising model $$H=\displaystyle\sum_{\{i,j\}\in E(\Lambda)}L_{ij}S_iS_j$$

Problem: Ground state energy

Complexity: NP–complete

Ref: [Bar82]

Conditionals:

• $L_{ij}\in\{-1,0,1\}$
• $S_i \in \{-1,1\}$
• $\Lambda$ representing a $2$–level grid

Reductions:

• From the TIM

Hamiltonian: The Classical Ising model $$H=\displaystyle\sum_{\{i,j\}\in E(G)} S_iS_j + \displaystyle\sum_{i\in V(G)} S_i$$

Problem: Ground state energy

Complexity: NP–hard

Ref: [Bar82]

Conditionals:

• Antiferromagnetic interactions
• $S_i \in \{-1,1\}$
• $G$ representing a planar graph

Reductions:

• From the TIM

Hamiltonian: The IaF–Transverse Ising model $$H=\displaystyle\sum_{\{i,j\}\in E(G)}L_{ij}^{^{(\geq 0)}}Z_iZ_j + \displaystyle\sum_{i\in V(G)}f_iX_i$$

Problem: Ground state energy

Complexity: StoqMA–complete

Ref: [PM15]

Conditionals:

• $L_{ij} \geq 0$
• $G$ representing an interaction graph

Reductions:

• From the general Transverse Ising Model

---

Gadgets:

• Basic Gadget

Hamiltonian: The IF–Transverse Ising model $$H=\displaystyle\sum_{\{i,j\}\in E(G)}L_{ij}^{^{(\leq 0)}}Z_iZ_j + \displaystyle\sum_{i\in V(G)}f_iX_i$$

Problem: Ground state energy

Ref: [BH16]

Conditionals:

• $L_{ij} \leq 0$
• $G$ representing an interaction graph

Reductions:

• From the general Transverse Ising Model

Hamiltonian: The Ising model $$H_{MC}(G) = \frac{1}{2} \sum_{\{i,j\} \in E(G)} w_{ij} \left(\mathbb{I} - S_i \cdot S_j\right)$$

Problem: Max–Cut

Complexity: NP–complete

Ref: [GW95]

Conditionals:

• The graph $G$ has egde weights $w_{ij}$
• $w_{ij}\geq 0$ and $w_{ij} = O(1/\mathsf{poly}(n))$
• $S_i \in \{\pm 1\}$

Hamiltonian: Ferromagnetic Ising model $$H = -\sum_{\{i,j\}\in E(G)} L_{ij}Z_iZ_j - B\sum_{i \in V(G)}Z_i$$

Problem: Partition function

Ref: [JS93]

Conditionals:

• $J_{ij} \in \mathbb{R}\backslash \{0\}$
• $B \in \mathbb{R}$
• $\beta \in \mathbb{R}^+$
• $G$ represents a graph

Hamiltonian: Antiferromagnetic Ising Hamiltonian $$H = \sum_{\{i,j\}\in E(G)} J_{ij} Z_iZ_j + \sum_{i \in V(G)} h_i Z_i$$

Problem: Partition function

Ref: [SST14]

Conditionals:

• $J_{ij} \in \mathbb{R}^+$
• $G$ has maximum degree $\Delta$
• Parameters in the interior of the uniqueness region of the infinite $(\Delta – 1)$–regular tree
• $\beta \in \mathbb{R}^+$

Hamiltonian: Antiferromagnetic Ising Hamiltonian $$H = \sum_{\{i,j\}\in E(G)} J_{ij} Z_iZ_j + \sum_{i \in V(G)} h_i Z_i$$

Problem: Partition function

Complexity: No FRPAS

Ref: [SS14], [GSV16]

Conditionals:

• $J_{ij} \in \mathbb{R}^+$
• $G$ has maximum degree $\Delta$
• Parameters in the interior of the non–uniqueness region of the infinite $(\Delta – 1)$–regular tree
• $\beta \in \mathbb{R}^+$
• No FPRAS unless RP=NP.