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

Problem: Local Hamiltonian

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: Local Hamiltonian

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:

• To the $2$–local stoquastic Hamiltonian

Techniques:

• Subdivision gadget
• 3–to–2 local gadget

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)

Ref: [Kin23]

Conditionals:

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

Hamiltonian: Pinned Stoquastic $3$-Local Hamiltonian $$H = \sum_{j=1}^m H_j$$

Problem: Pinned Stoquastic Local Hamiltonian

Complexity: QMA–complete

Ref: [NHES20]

Conditionals:

• $3$–local interactions
• stoquastic interactions
• $|\phi\rangle$ is a fixed state over $p < n$ qubits

Hamiltonian: $5$-Local Stoquastic Hamiltonian $$H = \sum_{j=1}^m H_j$$

Problem: Ground state connectivity

Complexity: QCMA–complete

Ref: [NHES20]

Conditionals:

• $5$–local interactions
• stoquastic interactions
• $2$–local unitaries
• $\Delta$ is polynomially–small