An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms

Understand

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.