updated 2026-05-19
Here we consider a general class of 2-Local Hamiltonian problems first introduced by [CM16]. These Hamiltonians are 2-Local, so they can be specified by a graph
\[H = \sum_{(i,j) \in E} w_{ij} K_{ij}\]where \(E\) is the set of edges in the graph, \(w_{ij}\) are edge weights, and \(K\) is a two local term (when specified with indices \(i\) and \(j\), this means that \(K\) acts nontrivially on qubits \(i\) and \(j\) and as the identity on the rest).
[CM16] considers the case where \(w_{ij}\) can be positive or negative, and classifies the problem as either in \(P\), \(StoqMA\)-complete, or \(QMA\)-complete depending on the choice of \(K\). Allowing for arbirary signs on the weights is often unhelpful, as we cannot distinguish between ferromagnetic and antiferromagnetic interactions (i.e. MinCut vs MaxCut). We define the local Hamiltonian problems restricted to the single interaction term \(K\) with positive weights as the \(\{K\}^+\)-Hamiltonian problem.
We may also restrict the problem further: [PM15] considers the case where the local term \(K\) is symmetric upon the interchange of its qubits. This means that \(K_{ij}=K_{ji}\). This restriction is common in statistical mechanics (Heisenberg, Ising, XYZ models) and in computer science (MaxCut). [PM15] then shows that in this case, the local term can always be diagonalized in the Bell basis, i.e. it can be written as
\[K = \alpha' |\psi^+\rangle \langle\psi^+| + \beta' |\phi^+\rangle \langle\phi^+| + \gamma' |\phi^-\rangle \langle\phi^-| + \delta' |\psi^-\rangle \langle\psi^-|\]where
\[|\psi^{\pm}\rangle = |01\rangle \pm |01\rangle, \quad |\phi^{\pm}\rangle = |00\rangle \pm |11\rangle,\]are the canonical Bell states. We can always choose an identity shift by \(-\delta' I\) to convert the local term to the form
\[K = \alpha |\psi^+\rangle \langle\psi^+| + \beta |\phi^+\rangle \langle\phi^+| + \gamma |\phi^-\rangle \langle\phi^-|.\]Shifting by the identity does not change the complexity of the Local Hamiltonian problem. Then, [PM15] and [MS26] further classifies the \(\{K\}^+\)-Hamiltonian problem for any \(\alpha, \, \beta, \, \gamma\). The green region denotes that the problem is reducible to an augmented version of the EPR problem, which we call EPR*.