REVIEW 19 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
Signed reviews
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 19 Pith papers
-
A Sharp Local-Question Threshold for GHZ-Equatorial Completeness in Four-Player XOR Games
For four-player XOR games, commuting-operator value one forces a perfect GHZ-equatorial strategy exactly when each player has at most three active questions; the Klein four-group game shows the threshold is sharp.
-
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.
-
An operator system approach to self-testing
Self-testing in the commuting operator model is defined operationally via local isometries between operator-system models, unifying POVM, QNS, contextuality, colouring and Schur-channel self-tests.
-
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.
-
The ineffectiveness of the regularity lemma for bounded degree graphs
For every maximum degree Δ ≥ 3, no computable function of the error ε and radius r bounds the size of a graph that reproduces r-neighborhood statistics up to ε.
-
Lifting the maximally-entangledness assumption in robust self-testing for synchronous games
A synchronous game that robustly certifies a strategy under maximally entangled projective assumptions robustly certifies the same strategy for all finite-dimensional strategies, with polynomially related robustness.
-
Gap-preserving reductions and RE-completeness of independent set games
Independent set games with a constant number of questions are RE-complete for entangled provers, so their gapped quantum value is undecidable while the classical problem is polynomial-time solvable.
-
Information geometry for types in the large-$n$ limit of random matrices
Free entropy and related quantities are controlled along Wasserstein geodesics for full types, and an explicit counterexample shows non-commutative laws cannot simultaneously realize entropy and Wasserstein distance i...
-
Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem
This paper proves quantitative preservation of approximate winning strategies between arbitrary synchronous games and graph 3-coloring games, but its undecidability applications rely on an instance-dependent threshold...
-
Absolutely dilatable bimodule maps
Every absolutely dilatable completely positive map that is bimodular over a von Neumann algebra has the form of a unitary rotation followed by a trace slice, and a hierarchy of such maps is equivalent to the Connes Em...
-
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ρ ≤ η.
-
Bisynchronous Games and Factorizable Maps
Bisynchronous nonlocal correlations with n inputs and n outputs are exactly traces on the quantum permutation group, and their associated completely positive maps are factorizable via quantum permutations.
Discussion (0). Continue with ORCID to comment.