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?

EDIT: Henry Yuen has created an MIP* Wiki for those interested in better understanding this complexity class or the $MIP^\ast = RE$ result.

  • 4
    $\begingroup$ 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. $\endgroup$ Commented Aug 16, 2020 at 16:42
  • $\begingroup$ @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. $\endgroup$ Commented Aug 16, 2020 at 16:48
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Aug 16, 2020 at 17:29
  • 3
    $\begingroup$ 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. $\endgroup$
    – Condo
    Commented Aug 17, 2020 at 13:45

1 Answer 1


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.

The MIP* = RE result is about what computational problems can be verified using nonlocal games, as opposed to what can be solved by nonlocal games (I'm not sure what that would mean, anyhow!). The distinction between verifying and solving is because of the following: in a nonlocal game, we assume that Alice and Bob magically know the answer to the problem (so we assume they can solve any computational problem instantly). Their challenge is not to solve it, but to prove to a polynomial-time classical verifier they know the answer. Just knowing the answer to something doesn't mean that you're able to convince someone else of the answer. Whether Alice and Bob can use correlations from the tensor product framework or the commuting operator framework affects what they're able to prove to the verifier. MIP* = RE shows that, with tensor product correlations, Alice and Bob can prove that they know a Turing Machine eventually halts. This is something that cannot be done if Alice and Bob share commuting operator correlations; therefore commuting operator model differs from the tensor product model.

The second thing I wanted to mention is, separately, it is an interesting question whether one can define a model of quantum computation that talks about commuting operators and infinite dimensional systems. It appears that Cleve, et al has tried to come up with a model for this, something they call the C*-circuit model: https://arxiv.org/pdf/1811.12575.pdf. You might find this interesting.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.