Tight Hardness of the Non-commutative Grothendieck Problem

Jop Briët, Oded Regev, Rishi Saket

We prove that for any $\eps > 0$ it is $\text{NP}$-hard to approximate the non-commutative Grothendieck problem to within a factor $1/2 + \eps$,…