REVIEW 20 cited by
MIP*=RE
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
MIP*=RE
read the original abstract
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.
Forward citations
Cited by 20 Pith papers
-
Multi-Prover Interactive Proof Systems with Leakage
Multi-prover interactive proof systems for NEXP and RE can be made robust against polynomial bits of leakage between provers via parallel repetition and PCP conversions.
-
Multi-Prover Interactive Proof Systems with Leakage
Two-prover one-round MIP protocols for NEXP and MIP* protocols for RE remain sound against any polynomial bits of leakage between provers.
-
Free information geometry and the model theory of noncommutative stochastic processes
A novel free entropy functional χ_chron^U is defined using chronological formulas that is concave along Wasserstein geodesics and whose heat evolution satisfies the evolution variational inequality as the metric gradi...
-
Nonlocal Games in the High-Noise Regime: Optimal Quantum Values and Rigidity
Explicit optimal quantum values for CHSH, Magic Square and 2-out-of-n games as functions of noise rate, plus noise-robust rigidity theorems certifying one, two or n pairs of anticommuting Pauli observables.
-
A mathematical foundation for self-testing: Lifting common assumptions
Proves a lifting theorem for self-testing assumptions with a counterexample correlation that requires them and cannot be realized by projective measurements on full Schmidt rank states.
-
Ubiquity of counterexamples to the Smith-Ward problem
Every finitely generated C*-algebra without LLP contains a hyperrigid three-dimensional operator subsystem without LP (and often without exactness), giving ubiquitous Smith-Ward counterexamples and a 3D nuclearity detector.
-
XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games
Approximating the quantum value of tilted XOR games to constant precision is RE-complete, implying binary nonlocal games are RE-hard to approximate.
-
Device-independent Quantum Key Distribution in the commuting operator framework
DIQKD key rates are rigorously computable via NPA hierarchies in the commuting-operator framework after a POVM-to-PVM dilation and a von Neumann-algebra Frenkel integral for relative entropy.
-
Bounding Classical and Quantum Correlations in Bayesian Networks with Quasiprobabilities
Quasiprobability models in Bayesian networks generalize to produce all non-signalling correlations for a broad class of networks and conjecturally recover the nested Markov model.
-
Linked Fates: How Small of an Ambiguity Increase Can Make the Difference Between Equaling and Separating from P?
New robust linkages between P and UP≤f(n) classes hold for certain function pairs via path-poisoning and padding, with oracle separations for essentially all other cases.
-
On ultraproduct approximations and property (T) factors
A framework is introduced to transfer deformation/rigidity methods into the continuous model theory of II1 factors, proving non-elementary equivalence of L(SL3(Z)) and LF2, non-pseudomatriciality of LF2, and existence...
-
Multi-Prover Interactive Proof Systems with Leakage
Two-prover MIP and MIP* protocols for NEXP and RE remain sound against any polynomial bits of leakage between provers, via parallel repetition and low-soundness PCPs.
-
Free information geometry and the model theory of noncommutative stochastic processes
A new free entropy χ_chron^U, built from chronological microstates, is geodesic-concave and makes free heat evolution the Wasserstein gradient flow of entropy.
-
Beyond real: Investigating the role of complex numbers in self-testing
Complex self-testing equals uniqueness of real parts of higher moments, reformulated in real C* algebras, with a quaternion strategy providing the first standard self-test for a genuinely complex non-local strategy.
-
On steering in the C*-algebraic framework
Provides necessary and sufficient conditions for equivalence of quantum commuting and tensor models in bipartite steering, demonstrates a model gap for m=2 and k>2 independent of Tsirelson's conjecture, and proves no-...
-
RFD property for groupoid C*-algebras of amenable groupoids and for crossed products by amenable actions
Characterizes the RFD property for crossed products by amenable actions and supplies conditions for amenable étale groupoid C*-algebras to be RFD.
-
Amenable traces and the joint numerical radius
The paper characterizes existence of amenable traces on C*-algebras via joint free numerical radius of unitaries/isometries/partial isometries and derives new obstructions to lifting properties.
-
No-signaling values of quantum games--an operator algebra perspective
Operator-space tensor norms characterize the no-signaling value of quantum games, yielding connections to operator algebra problems and new upper bounds on its separation from the quantum value.
-
Rethinking quantum information in gravity and fields
The paper organizes important open questions in quantum gravity and quantum information into four themes without presenting new results or derivations.
-
Nuclear C*-algebras: 99 problems
A compilation of 99 open problems in the structure and classification of nuclear C*-algebras.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.