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

Question

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.

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.