An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms
This work addresses the fundamental problem of approximating quantum Hamiltonians for researchers in quantum computing and complexity theory, providing an optimal result that is not incremental.
The paper resolves the approximability of the maximum energy for the Quantum Max Cut problem using product states, achieving an optimal classical 1/2-approximation that is unconditionally optimal, as shown by a gap of 1/2 between product and general quantum states.
We resolve the approximability of the maximum energy of the Quantum Max Cut (QMC) problem using product states. A classical 0.498-approximation, using a basic semidefinite programming relaxation, is known for QMC, paralleling the celebrated 0.878-approximation for classical Max Cut. For Max Cut, improving the 0.878-approximation is Unique-Games-hard (UG-hard), and one might expect that improving the 0.498-approximation is UG-hard for QMC. In contrast, we give a classical 1/2-approximation for QMC that is unconditionally optimal, since simple examples exhibit a gap of 1/2 between the energies of an optimal product state and general quantum state. Our result relies on a new nonlinear monogamy of entanglement inequality on a triangle that is derived from the second level of the quantum Lasserre hierarchy. This inequality also applies to the quantum Heisenberg model, and our results generalize to instances of Max 2-Local Hamiltonian where each term is positive and has no 1-local parts. Finally, we give further evidence that product states are essential for approximations of 2-Local Hamiltonian.