What is the complexity of computing the ground state energy of the EPR Hamiltonian?
The EPR Hamiltonian is a quantum Hamiltonian defined on a graph where each edge contains a projector onto the symmetric Bell state $|\phi^+\rangle = \frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$. Given a graph $G = (V, E)$, the Hamiltonian is:
$$H = \sum_{(i,j) \in E} |\phi^+\rangle\langle\phi^+|_{ij}$$
Known results: - The problem is in StoqMA (the Hamiltonian is stoquastic / "sign-problem free") - Optimizing over product states is trivial: $|0\rangle^{\otimes n}$ achieves approximation ratio $1/2$ - The problem isolates the quantum task of optimizing over entangled states
Open question: Is the EPR Hamiltonian problem in P? Since StoqMA is believed to be strictly smaller than QMA, and the product state optimization is easy, this problem could potentially be efficiently solvable classically.
References: - King (2023) formally introduced the EPR Hamiltonian - See https://marwahaha.github.io/quantum-maxcut-reference/ for a comprehensive reference