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
It's possible there is a Markov chain that works on this model. It could sample from closed walks to estimate Tr[H^k] (or similar) as a proxy for the ground state energy. See some papers relating approximate counting and sampling [here](https://www.sciencedirect.com/science/article/pii/0890540189900679), [here](https://web.archive.org/web/20170922034813id_/https://people.eecs.berkeley.edu/~sinclair/perm.pdf), [here](https://people.eecs.berkeley.edu/~sinclair/ising.pdf) . Jerrum also has a [book](https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/JerrumBook.pdf). There are some related papers to estimate ground state energy of similar Hamiltonians [here](https://arxiv.org/pdf/2509.21683), [here](https://arxiv.org/pdf/2411.01452). Farther away are these papers [here](https://arxiv.org/pdf/1910.09071), [here](https://arxiv.org/pdf/2602.03605). Markov chains are used in other contexts like [here](https://arxiv.org/pdf/2510.08446), [here for a summary](https://personal.math.ubc.ca/~holmescerfon/teaching/asa22/handout-Lecture3_2022.pdf), [here for another summary](https://math.dartmouth.edu/~pw/M100W11/nathan.pdf), [here for the Loop algorithm](https://arxiv.org/pdf/cond-mat/9707221) . Also for a short tutorial [here](https://www.issp.u-tokyo.ac.jp/public/CQCP/Sandvik_Workshop(sse).pdf).