Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Prespacetime journal

MIP*= RE: What could this mean physically?

Matti Pitkänen

Published Jan 1, 2020• 0 citations
Publisher

Abstract

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.

DOI
10.13140/rg.2.2.34403.58405

Related papers

MIP*=RE

Zhengfeng Ji, Anand Natarajan, Thomas Vidick +2 more

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 $C_{qa}$ of the set of quantum tensor product correlations is strictly included in the set $C_{qc}$ 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.

•Jan 13, 2020•9 citations

MIP*=RE

Zhengfeng Ji, Anand Natarajan, Thomas Vidick +2 more

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 $C_{qa}$ of the set of quantum tensor product correlations is strictly included in the set $C_{qc}$ 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.

arXiv:2001.04383•Jan 13, 2020•326 citations

MIP*=RE Links Halting Problem, Quantum Entanglement, and Connes Embedding — E8 Intelligence Research

Andrew Stewart Caldin

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

•Jul 31, 2026•0 citations

Quantum Entanglement Collapses Quantum Verification Hierarchy to Recursively Enumerable Class — E8 Intelligence Research

Andrew Stewart Caldin

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

•Aug 2, 2026•0 citations

Quantum Entanglement Redefines Undecidability: MIP*=RE and Turing's Legacy — E8 Intelligence Research

Andrew Stewart Caldin

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

•Oct 15, 2026•0 citations

MIPᶜᵒ=coRE

Junqiao (Randy) Lin

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].

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•0 citations
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 111 or at most 1/21/21/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 CqaC_{qa}Cqa​ of the set of quantum tensor product correlations is strictly included in the set CqcC_{qc}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 111 or at most 1/21/21/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 CqaC_{qa}Cqa​ of the set of quantum tensor product correlations is strictly included in the set CqcC_{qc}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].