This article was inspired by the article by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen having a rather concise title "MIP*=RE". This article states that the problems solvable by using recursively enumerable languages (RE) is equal to the class of problems solved multiple-interrogator-prover allowing quantum entanglement between provers (MIP*). Quantum entanglement would play an essential role in quantum computation. Also the implications for physics are highly non-trivial. Connes imbedding problem asking whether all infinite-D matrices can always be approximated by finite-D matrices has a negative solution.Therefore MIP*= RE does not hold true for hyperfinite factors of type II1 (HFFs) central in quantum TGD. Also the Tirelson problem finds a solution. The measurements of commuting observers performed by two observers are equivalent to the measurements of tensor products of observables only in finite-D case and for HFFs. That quantum entanglement would not have any role in HFFs is in conflict with intuition.
This article was inspired by the article by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen having a rather concise title "MIP*=RE". This article states that the problems solvable by using recursively enumerable languages (RE) is equal to the class of problems solved multiple-interrogator-prover allowing quantum entanglement between provers (MIP*). Quantum entanglement would play an essential role in quantum computation. Also the implications for physics are highly non-trivial. Connes imbedding problem asking whether all infinite-D matrices can always be approximated by finite-D matrices has a negative solution.Therefore MIP*= RE does not hold true for hyperfinite factors of type II1 (HFFs) central in quantum TGD. Also the Tirelson problem finds a solution. The measurements of commuting observers performed by two observers are equivalent to the measurements of tensor products of observables only in finite-D case and for HFFs. That quantum entanglement would not have any role in HFFs is in conflict with intuition.
We show that the class MIP* of languages that can be decided by a classical verifier interacting with multiple all-powerful quantum provers sharing entanglement is equal to the class RE of recursively enumerable languages. Our proof builds upon the quantum low-degree test of (Natarajan and Vidick, FOCS 2018) and the classical low-individual degree test of (Ji, et al., 2020) by integrating recent developments from (Natarajan and Wright, FOCS 2019) and combining them with the recursive compression framework of (Fitzsimons et al., STOC 2019). An immediate byproduct of our result is that there is an efficient reduction from the Halting Problem to the problem of deciding whether a two-player nonlocal game has entangled value 1 or at most 1/2. Using a known connection, undecidability of the entangled value implies a negative answer to Tsirelson's problem: we show, by providing an explicit example, that the closure Cqa of the set of quantum tensor product correlations is strictly included in the set Cqc of quantum commuting correlations. Following work of (Fritz, Rev. Math. Phys. 2012) and (Junge et al., J. Math. Phys. 2011) our results provide a refutation of Connes' embedding conjecture from the theory of von Neumann algebras.
We show that the class MIP* of languages that can be decided by a classical verifier interacting with multiple all-powerful quantum provers sharing entanglement is equal to the class RE of recursively enumerable languages. Our proof builds upon the quantum low-degree test of (Natarajan and Vidick, FOCS 2018) and the classical low-individual degree test of (Ji, et al., 2020) by integrating recent developments from (Natarajan and Wright, FOCS 2019) and combining them with the recursive compression framework of (Fitzsimons et al., STOC 2019). An immediate byproduct of our result is that there is an efficient reduction from the Halting Problem to the problem of deciding whether a two-player nonlocal game has entangled value 1 or at most 1/2. Using a known connection, undecidability of the entangled value implies a negative answer to Tsirelson's problem: we show, by providing an explicit example, that the closure Cqa of the set of quantum tensor product correlations is strictly included in the set Cqc of quantum commuting correlations. Following work of (Fritz, Rev. Math. Phys. 2012) and (Junge et al., J. Math. Phys. 2011) our results provide a refutation of Connes' embedding conjecture from the theory of von Neumann algebras.
FINDING: MIP*=RE proves that the halting problem is equivalent to quantum entanglement verification, linking computation limits to Connes embedding problem via Tsirelson's problem. | MATH: MIP* = RE (multi-prover interactive proofs with quantum entanglement equal recursively enumerable languages); Connes embedding problem (every finite von Neumann algebra embeds into ultrapower of hyperfinite II₁ factor); Tsirelson's problem (equivalence of quantum correlation sets from finite-dimensional vs. infinite-dimensional Hilbert spaces). | CONNECTION: E8 lattice (root system of 240 vectors, Coxeter number 30, kissing number 240) is the largest exceptional Lie group lattice; its 8-dimensional structure relates to octonion algebra and 24-cell. The MIP*=RE result uses non-local games whose optimal strategies correspond to C*-algebraic relations that can be encoded in lattice symmetries—specifically, the synchronous correlation sets align with traces on the Cuntz algebra, which has a natural repre Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
FINDING: MIP*=RE proves quantum entanglement can verify undecidable problems, collapsing the quantum verification hierarchy into the classical recursively enumerable class. | MATH: MIP* = RE (where MIP* = multiprover interactive proofs with quantum entanglement, RE = recursively enumerable languages). The Halting Problem is in RE but not in R (decidable). This implies that the set of problems verifiable by entangled quantum provers is exactly the set of problems computable by a Turing machine that may not halt on non-members. | CONNECTION: No direct geometric ratios or constants (0.382, 0.618, etc.) appear. However, the result relies on the structure of the *commuting operator* model of quantum correlations, which is deeply tied to *operator algebras* and *C*-algebras — these have known connections to root systems and Lie algebras (e.g., the Weyl algebra, SU(2) representations). The proof uses a *self-testing* protocol based on the *linear constraint system* (LCS) games, which are buil Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
FINDING: The halting problem's undecidability is foundational to computation limits; recent MIP*=RE result links it to quantum entanglement and nonlocal games, while a 2024 paper nuances Turing's original attribution. | MATH: Undecidability proof via diagonalization: assume HALT exists, construct D(x) = loop if HALT(x,x) halts, else halt; contradiction. MIP*=RE: the class of languages decidable by multiprover interactive proofs with quantum entanglement equals recursively enumerable sets — equivalently, the commuting-operator and tensor-product models diverge (Connes embedding conjecture false). No classical constants; structure is ordinal/recursion-theoretic (ω₁^CK, Turing degrees). | CONNECTION: No direct geometric ratio (0.382, 0.618, etc.) appears. However, the MIP*=RE result relies on *lattice-like* constructions of nonlocal games (Tsirelson bounds, operator algebras) and the *root system* of quantum correlations — the set of quantum strategies forms a convex body with extreme poi Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
In 2020, a landmark result by Ji, Natarajan, Vidick, Wright, and Yuen shows that MIP*, the class of languages that can be decided by a classical verifier interacting with multiple computationally unbounded provers sharing entanglement in the tensor product model, is equal to RE. We show that the class MIPco, a complexity class defined similarly to MIP*, except with provers sharing the commuting operator model of entanglement, is equal to the class coRE. This shows that giving the provers two different models of entanglement leads to two completely different computational powers for interactive proof systems. Our proof builds upon the compression theorem used in the proof of MIP*=RE, and we use the tracially embeddable strategies framework to show that the same compression procedure in MIP* =RE also has the same desired property in the commuting operator setting. We also give a more streamlined proof of the compression theorem for non-local games by incorporating the synchronous framework used by Mousavi et al. [STOC 2022], as well as the improved Pauli basis test introduced by de la Salle [ArXiv:2204.07084].