# Consequences of $MIP^\ast=RE$ Regarding Quantum Algorithms

The (pending-peer review) proof of $$MIP^\ast=RE$$ in this pre-print has been hailed as a significant breakthrough. The significance of this result is addressed by Henry Yuen (one of the authors) in this blog post. Scott Aaronson also lists some of the major implications in this blog post.

For a non-local game ($$G$$), define the supremum of success probabilities for non-relativistic tensor product strategies as $$\omega^\ast(G)$$, and the supremum of success probabilities for a relativistic commuting operator (QFT) strategy as $$\omega^{co}(G)$$. Since non-relativistic QM is a special case of QFT, it's clear that an optimal commuting operator-based strategy is at least as good as an optimal tensor product-based strategy, $$\omega^\ast(G) \le \omega^{co}(G)$$.

My understanding of Yuen's post is that one consequence of $$MIP^\ast=RE$$ is that non-local games exist for which $$\omega^\ast(G) < \omega^{co}(G)$$. Specifically, he says

There must be a game $$G$$, then, for which the quantum value is different from the commuting operator value. But this implies Tsirelson’s problem has a negative answer, and therefore Connes’ embedding conjecture is false.

I understand this to mean that there is a class of problems for which algorithms using techniques from QFT (commuting operators) have higher success probabilities than algorithms using techniques from non-relativistic QM (tensor products, quantum circuit formalism).

The first part of my question is, assuming this proof stands:

• Does $$MIP^\ast=RE$$ imply that there is a set of problems that can be solved more efficiently by employing the mathematical formalism of QFT (commuting operators) rather than non-relativistic QM formalism (conventional quantum circuits)?

Unless I am misinterpreting, this seems to follow directly from Yuen's statements. If that's so, is it possible that there exists a set of non-local games for which $$\omega^\ast(G) < 0.5$$ and $$\omega^{co}(G) > 0.5$$? Specifically, the second part of my question is:

• Does $$MIP^\ast=RE$$ imply that there is (or might be) a set of problems that can be solved using commuting operators that cannot be solved using quantum circuits, or is this possibility forclosed by the universality of the quantum circuit model?
• Are you asking if there's a practical, down-to-earth way to leverage $MIP^*=RE$ to get something stronger than what is afforded by the quantum circuit model? The "universality" of the quantum circuit model implies that the model can't invalidate the Church-Turing thesis. But by $MIP^*=RE$, two god-like entities sharing a potentially infinite amount of entanglement can invalidate the Church-Turing thesis. – Mark S Aug 16 at 16:42
• @MarkS I'm trying understand the upshot from reconciling your last two sentences, and whether that implies that commuting operator-based algorithms will (or might) offer improved performance over quantum circuit-based algorithms for some set of problems. – Jonathan Trousdale Aug 16 at 16:48
• Do you want a QFT solution to a problem in-between the universality afforded by the quantum-circuit model and, for example, the Halting problem, which is complete for $RE$? Is the Wiki article on Turing degrees of any help? – Mark S Aug 16 at 16:58
• I see, the first question asks about using QFT to get a computational speedup over-and-above the quantum circuit model. Note that Kuperberg is fond of saying something to the effect of "it's rare to have more than one major revolution", e.g., I believe he posits that the quantum circuit model is the end-of-the-line for computational efficiency. – Mark S Aug 16 at 17:29
• I think its important to remember that if your Hilbert spaces are finite dimensional then then the set of correlations achieved by the commuting operator framework and the tensor product framework are the same. The separation happens in infinite dimensions and so the application to any real algorithm with a quantum circuit seems implausible. – Condo Aug 17 at 13:45

I don't know if the MIP* = RE result, and in particular the claim that there exists a nonlocal game $$G$$ where $$\omega^*(G) \neq \omega^{co}(G)$$, has any algorithmic implications for quantum computers. There's a couple things to say here.