Commuting Models

Key: CLHP-2LH-001
Hamiltonian: $(2,d)$ Commuting Hamiltonian $$H=\displaystyle\sum_{j} h_{j}$$
Problem: Commuting local Hamiltonian
Complexity: NP
Ref: [BV03]
Conditionals:
  • $[ h_j, h_k ] = 0$ for all $j,k$
  • Each Hamiltonian $H_{j}$ is $2$–local
  • Each Hamiltonian acts on qudits of dimension $d$
Reductions:
  • From the common eigenspace problem
Techniques:
  • C$^*$–algebra
Key: CLHP-2LH-002
Hamiltonian: $(3,2)$ Commuting Hamiltonian $$H=\displaystyle\sum_{j} h_{j}$$
Problem: Commuting local Hamiltonian
Complexity: NP
Ref: [AE11]
Conditionals:
  • $[ h_j, h_k ] = 0$ for all $j,k$
  • Each Hamiltonian $H_{j}$ is $3$–local
  • Each Hamiltonian acts on qudits of dimension $2$
Techniques:
  • C$^*$–algebra
Key: CLHP-2LH-003
Hamiltonian: $(3,3)$ Commuting Hamiltonian $$H=\displaystyle\sum_{j} h_{j}$$
Problem: Commuting local Hamiltonian
Complexity: NP
Ref: [AE11]
Conditionals:
  • $[ h_j, h_k ] = 0$ for all $j,k$
  • Each Hamiltonian $H_{j}$ is $3$–local
  • Each Hamiltonian acts on qudits of dimension $3$
  • The interaction graph is a (nearly Euclidean) planar graph
Techniques:
  • C$^*$–algebra
Key: CLHP-2LH-101
Hamiltonian: $(4,2)$ Commuting Hamiltonian $$H=\displaystyle\sum_{p\in\mathcal{P}_B} h_{p} + \displaystyle\sum_{q\in\mathcal{P}_W} h_{q}$$
Problem: Commuting local Hamiltonian
Complexity: NP
Ref: [Sch11]
Conditionals:
  • $[ h_p, h_q ] = 0$ for all $p,q$
  • Each Hamiltonian term is $4$–local acting over the plaquettes of a square lattice
  • Each Hamiltonian acts on qudits of dimension $2$
  • The interaction graph is square lattice (black and white plaquettes in a checkerboard pattern)
Techniques:
  • C$^*$–algebra
Key: CLHP-2LH-004
Hamiltonian: $(k\geq 2,d \geq 2)$ Commuting Hamiltonian $$H=\displaystyle\sum_{j} h_{j}$$
Problem: Commuting local Hamiltonian (approximate)
Complexity: NP–hard
Ref: [AE14]
Conditionals:
  • $[ h_j, h_k ] = 0$ for all $j,k$
  • Approximate the commuting local Hamiltonian problem within a factor $\gamma(\epsilon) = 2dk\epsilon \lt 1/3$
  • The interaction graph is a bipartite $\epsilon$ locally–expanding graph
Techniques:
  • C$^*$–algebra
Key: CLHP-2LH-005
Hamiltonian: $(k,2)^*$ Commuting Hamiltonian $$H=\displaystyle\sum_{s} h_{s} + \displaystyle\sum_{p} h_{p}$$
Problem: Commuting local Hamiltonian
Complexity: NP
Ref: [AKV18]
Conditionals:
  • $[ h_j, h_k ] = 0$ for all $j,k$
  • The interaction graph is $2$D polygonal complex $\mathcal{K}$
  • The complex is quasi–Euclidean
Techniques:
  • C$^*$–algebra
Key: CLHP-2LH-102
Hamiltonian: $(4,3)$ Commuting Hamiltonian $$H=\displaystyle\sum_{p\in\mathcal{P}_B} h_{p} + \displaystyle\sum_{q\in\mathcal{P}_W} h_{q}$$
Problem: Commuting local Hamiltonian
Complexity: NP
Ref: [IJ23]
Conditionals:
  • $[ h_p, h_q ] = 0$ for all $p,q$
  • The Hamiltonian terms are $4$–local acting over the plaquettes of a square lattice
  • Each Hamiltonian acts on qudits of dimension $3$
  • The interaction graph is a square lattice (black and white plaquettes in a checkerboard pattern)
Techniques:
  • C$^*$–algebra