User Tools

Site Tools


Open Problems

A list of open problems related to MIP*, nonlocal games, correlation sets, and their connections to mathematics.

Complexity theory

  1. What is the complexity of MIPco, the class of problems decidable by multiprover interactive proofs in the commuting operator model? It is known that MIPco is contained in coRE, so it is different from MIP*. Could it be equal to coRE? See for a discussion of the complexity landscape of variants of MIP*.

Quantum information theory/non-local games

  1. What is the simplest game $G$ (in terms of description length, ease of analysis, etc) for which one can show that $\omega^{co}(G) \neq \omega^*(G)$ (i.e. the commuting operator and tensor product values are different)?
  2. The MIP* = RE paper shows that there exists a game $G$ for which the commuting operator value $\omega^{co}(G)$ is strictly larger than its tensor product value $\omega^*(G)$. On the other hand, the main result of the paper is a computable reduction from Turing machines $M$ to non-local games $G_M$ such that if $M$ halts, then $\omega^*(G_M) = 1$, and if $M$ does not halt, then $\omega^*(G_M) \leq 1/2$. It ought to be the case that for all $M$ that don't halt, $\omega^*(G_M) \leq 1/2$ but $\omega^{co}(G_M) = 1$. Is this true?
  3. Can the game in the Turing machine-to-nonlocal game reduction be formulated as a Linear Constraint System (LCS) game? If not, can it be made to be?
  4. Does a parallel repetition theorem hold for the commuting operator value of nonlocal games? (This would be useful for trying to prove a result like MIPco = coRE).


  1. Is there a non-hyperlinear group? One approach to this is related to the question above about whether the games in the MIP* = RE paper can be made LCS games.
  2. Give an explicit description of a separation between $C^*(\mathbb{F}) \otimes_{max} C^*(\mathbb{F})$ and $C^*(\mathbb{F}) \otimes_{min} C^*(\mathbb{F})$ (i.e. an explicit counter-example to Kirchberg's QWEP Conjecture). The MIP* = RE result implies a negative answer to Tsirelson's problem (that the commuting operator correlations cannot all be approximated by finite dimensional correlations), which by the work of Fritz and Junge, et al. implies that Kirchberg's QWEP Conjecture (and hence Connes' embedding conjecture) is false. However the proof of MIP* = RE is not entirely constructive; it gives an explicit description of a non-local game with differing commuting operator and tensor product values, which is a separating linear functional between the correlation sets $C_{qc}$ and $C_{qa}$. But what about an explicit description of a point in $C_{qc} \setminus C_{qa}$?
  3. Similarly, give an explicit description of a type $II_1$ factor that does not have the Connes embedding property.
open-problems.txt · Last modified: 2020/03/19 21:01 by hyuen