Is there such a thing as quantum reduction ( like there is a special reduction for every type of Turing machine: polynomial reduction, probabilistic polynomial reduction etc )

I guess best candidates for example to have reduction between them is factoring and DLOG ( there is no polynomial reduction between them as far as i know ) ]]>

As for the conjecture, you’re right, the paper does not provide evidence against that. It’s just a general feeling that the easiest way for the conjecture to be right would be if you could always get the optimal strategy with an amount of entanglement that would be a function of the size of the input, and this is not true. Certainly you might be able to get within ε for some nice function, but nobody knows any bound on how ε goes with the dimension of the state and the size of the input.

]]>Also, the paper you linked to is interesting and not something I’d seen, so thanks! However, from a quick scan, I couldn’t tell whether the paper *actually* provides any evidence against the conjecture that I made. Remember, I’m not saying there aren’t games (even purely-classical games) where you can win with higher and higher probability the more entanglement you have—in fact, I think it’s quite likely that such games exist (and the Pal-Vertesi paper strengthens that belief). My conjecture says only that:

(1) As you increase the amount of entanglement, the success probability *converges to a limit*, which *equals* the success probability that you can attain using a countably-infinite amount of entanglement.

(2) A computable upper bound can be given on the rate of convergence.

So, again, do Pal and Vertesi give any evidence against *that*?

(1) and (2) above would clearly suffice for placing a computable upper bound on the QMIP*(2,1) class.

]]>So, the converse seems clear to me, but I still don’t see how being able to approximate ω*(G) (how well? up to a costant?) would give a computable upper bound on MIP*. Does computable upper bound in this context mean including it in a computable complexity class?

About the conjecture, I don’t expect to get within ε for a reasonable amount of entanglement. After all, there is strong numerical evidence that even for a particular instance of a game you need infinite-dimensional states: arXiv:1006.3032.

]]>FWIW, my guess is that it might well be undecidable whether ω*(G)=1—I’m not sure—but that, in any case, there ought to be an algorithm to *approximate* ω*(G), since you ought to be able to get within ε of the optimal value ω*(G) using an amount of entanglement that scales reasonably with the size of G.

So why the computability of ω*(G) implies that one can reduce the number of provers to 2? And are good upper bounds known for MIP*(2,1)?

I’d be glad if you could explain or point me to a reference.

In addition, do you wish to risk a guess on the computability of ω*(G)? At least from my side (and I believe most physicists agree with me) it’s clear that it’s not computable.

]]>Figure out a good way to express what it means for a set of gates to be not universal. ]]>