Hamiltonian: The $6$–Local Stoquastic Hamiltonian $$H = \displaystyle\sum_{j=1}^m H_j$$

Problem: Ground state energy

Complexity: StoqMA–complete

Ref: [BBT06]

Conditionals:

• Each Hamiltonian term $H_j$ is stoquastic
• Each $H_j$ acts on at most $6$ of the $n$ qubits
• $m = O(\mathsf{poly}(n))$

Reductions:

• To the $2$–local stoquastic Hamiltonian

Hamiltonian: The $2$–Local Stoquastic Hamiltonian $$H = \displaystyle\sum_{j=1}^m H_j$$

Problem: Ground state energy

Complexity: StoqMA–complete

Ref: [BBT06]

Conditionals:

• Each Hamiltonian term $H_j$ is stoquastic
• Each $H_j$ acts on at most $2$ of the $n$ qubits
• $m = O(\mathsf{poly}(n))$

Reductions:

• From the $6$–local stoquastic Hamiltonian

---

Gadgets:

• Subdivision, 3–to–2 local

Hamiltonian: The weighted (xyz/.) Hamiltonian $$H_{QMC(EPR)}(G) = \frac{1}{2} \sum_{\{i,j\} \in E(G)} w_{ij} \left(\mathbb{I} + X_iX_j - Y_iY_j + Z_iZ_j\right)$$

Problem: Quantum Max–Cut(EPR)

Complexity: in StoqMA

Ref: [Kin23]

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\}$