REVIEW 10 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
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 10 Pith papers
-
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...
-
Thermal operations from informational equilibrium
Thermal operations are uniquely the quantum channels that admit a dilation preserving the environment state at equilibrium, establishing an information-theoretic characterization.
-
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.
-
Representations of noncommutative cubes and prisms
The noncommutative triangular prism is exactly the maximal noncommutative convex set over the classical triangle prism, characterized by joint unitary dilations via Halmos and Mirman's theorems.
-
Quantum Nonlocality under Latency Constraints
Relaxing the light-speed-delay constraint so a subset of parties can communicate produces new Bell-type bounds, and quantum communication can beat classical bounds in games where the strict Bell scenario cannot.
-
Unitary induced channels and Tsirelson's problem
Generalized unitary induced channels are equal in the commuting and tensor models if and only if Tsirelson's conjecture holds, so the models differ.
-
Strong converse rate for asymptotic hypothesis testing in type III
In any von Neumann algebra, the strong converse rate B_r(ρ∥η) equals the Hoeffding anti-divergence H*_r(ρ∥η) when aρ ≤ η.
Discussion (0). Continue with ORCID to comment.