Quantum Max-Cut is NP hard to approximate

Abstract

We unconditionally prove that it is NP-hard to compute a constant multiplicative approximation to the QUANTUM MAX-CUT problem on an unweighted graph of constant bounded degree. The proof works in two stages: first we demonstrate a generic reduction to computing the optimal value of a quantum problem, from the optimal value over product states. Then we prove an approximation preserving reduction from MAX-CUT to PRODUCT-QMC the product state version of QUANTUM MAX-CUT. More precisely, in the second part, we construct a PTAS reduction from MAX-CUT${}_k$ (the rank-k constrained version of MAX-CUT) to MAX-CUT${}_{k+1}$, where MAX-CUT and PRODUCT-QMC coincide with MAX-CUT${}_1$ and MAX-CUT${}_3$ respectively. We thus prove that Max-Cut${}_k$ is APX-complete for all constant $k$.

19 pages, 2 figures