Heisenberg Model

Key: LHP-HbH-001
Hamiltonian: The Heisenberg Hamiltonian $$H=J\displaystyle\sum_{\{i,j\}\in E(G)} \big(X_iX_j + Y_iY_j + Z_iZ_j\big) -\displaystyle\sum_{i\in V(G)} \boldsymbol{B}_i \cdot \boldsymbol{\sigma}_i$$
Problem: Ground state energy
Complexity: QMA–complete
Ref: [SV09]
Conditionals:
  • $J\gt0$ or $J\lt0$
  • $\Lambda$ representing a spatially sparse lattice
  • External fields of the form: $-\displaystyle\sum_{i} \boldsymbol{B}_i \cdot \boldsymbol{\sigma}_i$
  • $G$ is an interaction graph
Reductions:
  • From the general $2$–local Pauli Hamiltonian
  • To the Fermi–Hubbard Hamiltonian with external fields
Gadgets:
  • Pauli Coupling Gadget, Pauli–to–Ising Gadget, Ising–to–$XX$ Gadget
Key: HbM01
Hamiltonian: The Heisenberg Hamiltonian $$H=J\displaystyle\sum_{\{i,j\}\in E(\Lambda)} \big(X_iX_j + Y_iY_j + Z_iZ_j\big) -\displaystyle\sum_{i\in V(\Lambda)} \boldsymbol{B}_i \cdot \boldsymbol{\sigma}_i$$
Problem: Ground state energy
Complexity: QMA–complete
Ref: [SV09]
Conditionals:
  • $J\gt0$ or $J\lt0$
  • $\Lambda$ representing a 2D square lattice
  • External fields of the form: $-\displaystyle\sum_{i\in\Lambda} \boldsymbol{B}_i \cdot \boldsymbol{\sigma}_i$
Reductions:
  • From the Heisenbrg Hamiltonian with external fields on a spatially sparse lattice
  • To the Fermi–Hubbard Hamiltonian with external fields
Gadgets:
  • Erasure
Key: LHP-HbH-101
Hamiltonian: The Heisenberg Hamiltonian $$H=\displaystyle\sum_{\{i,j\}\in E(G)} J_{ij}\big(X_iX_j + Y_iY_j + Z_iZ_j\big)$$
Problem: Ground state energy
Complexity: QMA–complete
Ref: [CM16]
Conditionals:
  • $G$ representing an interaction graph
Reductions:
  • From the weighted (xyz/.) Hamiltonian
  • To the IaF–Heisenberg Hamiltonian or the Heisenberg Hamiltonian on a 2D square lattice
Key: LHP-HbH-102
Hamiltonian: The Heisenberg Hamiltonian $$H=\displaystyle\sum_{\{i,j\}\in E(\Lambda)} J_{ij}\big(X_iX_j + Y_iY_j + Z_iZ_j\big)$$
Problem: Ground state energy
Complexity: QMA–complete
Ref: [CMP18]
Conditionals:
  • $\Lambda$ representing a 2D square lattice
Reductions:
  • From the weighted (xyz/.) Hamiltonian on a 2D square lattice
  • To the Heisenberg Hamiltonian on a 2D triangular lattice
Key: LHP-HbH-105
Hamiltonian: The Heisenberg Hamiltonian $$H=\displaystyle\sum_{\{i,j\}\in E(\Lambda)} J_{ij}\big(X_iX_j + Y_iY_j + Z_iZ_j\big)$$
Problem: Ground state energy
Complexity: QMA–complete
Ref: [CMP18]
Conditionals:
  • $\Lambda$ representing a 2D triangular lattice
Reductions:
  • From the weighted (xyz/.) Hamiltonian on a 2D square lattice
  • To the (xy/.) Hamiltonian on a 2D triangular lattice
Key: LHP-HbH-110
Hamiltonian: The IaF–Heisenberg Hamiltonian $$H=\displaystyle\sum_{\{i,j\}\in E(G)} J_{ij}^{^{(\geq 0)}}\big(X_iX_j + Y_iY_j + Z_iZ_j\big)$$
Problem: Ground state energy
Complexity: QMA–complete
Ref: [PM15]
Conditionals:
  • $J_{ij}\geq 0$
  • $G$ representing an interaction graph
Reductions:
  • From the Heisenberg Hamiltonian
  • To the IaF–Heisenberg Hamiltonian on a 2D triangular lattice
Key: LHP-HbH-113
Hamiltonian: The IaF–Heisenberg Hamiltonian $$H=\displaystyle\sum_{\{i,j\}\in E(\Lambda)} J_{ij}^{^{(\geq 0)}}\big(X_iX_j + Y_iY_j + Z_iZ_j\big)$$
Problem: Ground state energy
Complexity: StoqMA
Ref: [PM15]
Conditionals:
  • $J_{ij}\geq 0$
  • $\Lambda$ representing a 2D bipartite lattice
Reductions:
  • From the IaF–Heisenberg Hamiltonian on a general graph
  • To the ferromagnetic Heisenberg Hamiltonian on a bipartite lattice
Key: LHP-HbH-114
Hamiltonian: The IaF–Heisenberg Hamiltonian $$H=\displaystyle\sum_{\{i,j\}\in E(\Lambda)} J_{ij}^{^{(\geq 0)}}\big(X_iX_j + Y_iY_j + Z_iZ_j\big)$$
Problem: Ground state energy
Complexity: QMA–complete
Ref: [PM15]
Conditionals:
  • $J_{ij}\geq 0$
  • $\Lambda$ representing a 2D triangular lattice
Reductions:
  • From the IaF weighted (xyz/.) Hamiltonian on a 2D triangular lattice
  • To the IaF–(xy/.) Hamiltonian on a 2D triangular lattice
Gadgets:
  • Positive and Negative subdivision
Key: LHP-HbH-115
Hamiltonian: The Ferromagnetic Heisenberg Hamiltonian $$H=\displaystyle\sum_{\{i,j\}\in E(\Lambda)} J_{ij}^{^{(\leq 0)}}\big(X_iX_j + Y_iY_j + Z_iZ_j\big)
Problem: Local Hamiltonian
Complexity: StoqMA
Ref: [PM15]
Conditionals:
  • $J_{ij}\leq 0$
  • $\Lambda$ representing a 2D bipartite lattice
Reductions:
  • From the IaF weighted (xyz/.) Hamiltonian
Key: HbM501
Hamiltonian: The Heisenberg Hamiltonian $$H_{QMC_S}(G) = \frac{1}{2} \sum_{\{i,j\} \in E(G)} w_{ij} \left(\mathbb{I} - \frac{1}{S^2}\;\boldsymbol{S}_i \cdot \boldsymbol{S}_j \right)$$
Problem: Quantum Max–Cut
Complexity: QMA–complete
Ref: [BP24]
Conditionals:
  • The graph $G$ has egde weights $w_{ij}$
  • $w_{ij}\geq 0$ and $w_{ij} = O(\mathsf{poly}(n))$
  • $\boldsymbol{S} = (S^1,S^2,S^3)$ denote the spin–$S$ operators
  • $S\rightarrow\infty$
Reductions:
  • To the antiferromagnetic Heisenberg model
Key: HbM901
Hamiltonian: The Heisenberg Hamiltonian $$H_{QMC}(G) = \frac{1}{2} \sum_{\{i,j\} \in E(G)} w_{ij} \left(\mathbb{I} - \frac{1}{S^2}\;\boldsymbol{S}_i \cdot \boldsymbol{S}_j \right)$$
Problem: Quantum Max–Cut product states
Complexity: NP–complete
Ref: [KPT+24]
Conditionals:
  • The graph $G$ has egde weights $w_{ij}$
  • $w_{ij}\geq 0$ and $w_{ij} = O(\mathsf{poly}(n))$
  • $\boldsymbol{S} = (S^1,S^2,S^3)$ denote the spin–$\frac{1}{2}$ operators
Reductions:
  • To the antiferromagnetic Heisenberg model and to Max–Cut$_3$
Key: APXSIM-HbH-001
Hamiltonian: Heisenberg Hamiltonian and a $4$-local observable $A$ $$H = \sum_{u,v} X_uX_v + Y_uY_v + Z_uZ_v$$
Problem: Approximate Simulation
Complexity: PQMA[log]–complete
Ref: [GPY19]
Conditionals:
  • $2$–local Heisenberg interactions
  • $4$–local observable $A$
Techniques:
  • Perturbative gadget reductions