When you see me getting chased across the blogosphere by livid, paintbrush-wielding artistes, it can only mean one thing: that I’ve once again abandoned my “promise” to stick to the Serious Complexity Theory That I’m Actually Qualified To Discuss. So I’ll tell you what, whistling-pig-lovers: answer me the following; then come back for more.
Given a set of n-by-n real matrices, is there a nonzero linear combination of those matrices with rank 1? Equivalently, given a subspace S of a bipartite n-by-n Hilbert space, does S contain a separable state?
I’d like (1) a proof of NP-hardness for the exact version, and (2) more importantly, whether or not there’s a decent approximation algorithm. (For instance, an algorithm that finds a rank-1 matrix, with the sum of the squares of the entries equal to 1, whose L2-distance from the subspace of interest is at most a small additive constant more than optimal.)
So get cracking! If you do find a decent approximation algorithm, you’ll have shown, among other things, that QMA(2) (QMA with two unentangled yes-provers) is in EXP. Incredibly, right now we don’t have any upper bound better than NEXP.
Oh, yes: while my brain is closed, and while I can barely turn theorems into coffee, I will offer $20 for a solution to (2).