Quantum Max-Cut is NP hard to approximate

Stephen Piddock

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…