A complexity phase transition at the EPR Hamiltonian

The Local Hamiltonian Problem (LHP) is the canonical complete problem for the complexity class QMA (the quantum analogue of NP). When the set of allowed local terms is restricted in some way, however, the problem may become easy. We study the restriction to a single positively-weighted 2-local term that is symmetric under the interchange of qubits. This restriction was introduced by Piddock and Montanaro and captures the Quantum MaxCut (Heisenberg), XY, and EPR Hamiltonians. We demonstrate an elegant physical picture: the complexity of the LHP only depends on the energy-level ordering of the local term in the Bell basis. We show the EPR problem, introduced by King in 2209.02589, is at a phase transition between hard problems and potentially easy problems. Furthermore, the potentially easy problems are all reducible to an augmented version of the EPR problem. Showing that EPR is easy (BPP, BQP, P) would thus complete the classification.

*We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*