MIP*=RE References
Main Articles "MIP*=RE"
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
2020/01
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) 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.
"MIP*=RE re-derived"
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
MIP*=RE
2020/09/30
Quantum soundness of the classical low individual degree test
2020/09/27
Commentary notes by the authors
- MIP* = RE Part 1: The Quantum Low-Degree Test (video)
By Anand Natarajan
- MIP* = RE Part 2: PCPs and Introspection (video)
By John Wright
- MIP* = RE: Putting Everything Together (video)
By Zhengfeng Ji
- ITC2020: Invited Talk: MIP* = RE
By Anand Natarajan
- An overview of MIP* = RE and some of its ingredients
By Henry Yuen
- TCS+ Talk: MIP* = RE
By Henry Yuen
- MIP* Wiki
By Henry Yuen
- The shape of MIP* = RE
By Henry Yuen
-
By Thomas Vidick
Video List Interactive Proof (MIP*=RE)
On the eve of the proof
- NEEXP ⊆ MIP*
[v1] Thu, 11 Apr 2019 17:56:45 UTC (120 KB)
By Anand Natarajan, John Wright - Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
FOCS 2018
by Anand Natarajan, Thomas Vidick - Quantum proof systems for iterated exponential time and beyond
https://arxiv.org/abs/1805.12166
2018年5月By Joseph F Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen - Tsirelson’s problem and linear system games （video）
2017/01/20
By William Slofstra
BIRS Workshop 2019/07
- Slofstra’s Contributions to the Connes Embedding Problem
By Vern Paulsen - A complexity-theoretic approach to disproving Connes' Embedding Problem
By Thomas Vidick - Compression of non-local games via self-testing
By Henry Yuen - You must have n qubits or more to win: efficient self-tests for high-dimensional entanglement
By Anand Natarajan - Nonlocal games are harder to approximate than we thought
By John Wright
QIP 2017
- Zero-knowledge proof systems for QMA
Anne Broadbent, Zhengfeng Ji, Fang Song, and John Watrous
Presentation slides | Abstract and video - Compression of quantum multi-prover interactive proofs
Zhengfeng Ji
Presentation slides | Abstract and video - A parallel repetition theorem for all entangled games
Henry Yuen
Presentation slides | Abstract and video - Limitations of semidefinite programs for separable states and entangled games
Aram Harrow, Anand Natarajan, and Xiaodi Wu
Presentation slides | Abstract and video - Sculpting quantum speedups
Scott Aaronson and Shalev Ben-David
Presentation slides | Abstract and video - Robust self-testing of many qubit states
Anand Natarajan and Thomas Vidick
Presentation slides | Abstract and video - Overlapping qubits
Rui Chao, Ben Reichardt, Chris Sutherland and Thomas Vidick,
Presentation slides | Abstract and video - Parallel self-testing of (tilted) EPR pairs via copies of (tilted) CHSH
Andrea W. Coladangelo,
Presentation slides | Abstract and video - The parallel-repeated magic square game is rigid
Matthew Coudron and Anand Natarajan
Presentation slides | Abstract and video - Tsirelson’s problem and an embedding theorem for groups arising from non-local games
William Slofstra
Presentation slides | Abstract and video
[References]
- Non-Local Binary Games With Noisy Epr States Are Decidable
- Self-Testing as an Approach to Certifying Quantum Systems
- The Algebraic Side of MIP* = RE
- Quantum PCPs Meet Derandomization
- Quantum Protocols: Testing & Quantum PCPs
- From Operator Algebras to Complexity Theory and Back
Thomas Vidick
- Robust self-testing of many qubit states
- The parallel-repeated magic square game is rigid
[Introductory articles]
- MIP*=RE
By Scott Aaronson
- MIP*=RE, disproving Connes embedding conjecture.
- Halting Is Poly-Time Quantum Provable
- Graced With Knowledge, Mathematicians Seek to Understand
- Landmark Computer Science Proof Cascades Through Physics and Math
- Computer Scientists Expand the Frontier of Verifiable Knowledge
In Quantum Games, There’s No Way to Play the Odds - The Universe’s Ultimate Complexity Revealed by Simple Quantum Games
History of the theory
Interactive Proof / PCP Theorem
- Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class Babai, László; Moran, Shlomo (1988)
- The knowledge complexity of interactive proof systems Goldwasser, S.; Micali, S.; Rackoff, C. (1989)
- Interactive proofs and the hardness of approximating cliques
Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996)" - Probabilistic checking of proofs: a new characterization of NP
Arora, Sanjeev; Safra, Shmuel (1998) - Proof verification and the hardness of approximation problems
Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998)" - The PCP theorem by gap amplification" Dinur, Irit (2007)
- NON-DETERMINISTIC EXPONENTIAL TIME HAS TWO-PROVER INTERACTIVE PROTOCOLS
Laszl Babai, Lance Fortnow and Carsten Lund - Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions
Tsirelson's problem / Connes' embedding conjecture
\( C_{q} \subseteq C_{qs} \subseteq C_{qa} \subseteq C_{qc} \)
- \( C_{qa} \neq C_{qc} \)
Can you compute the operator norm?
Tobias Fritz, Tim Netzer, and Andreas Thom (2014) - \( C_{qs} \neq C_{qc} \)
Tsirelsons problem and an embedding theorem for groups arising from nonlocal games
Slofstra (2016) - \( C_{qs} \neq C_{qa} \)
The set of quantum correlations is not closed
2017 Slofstra (2017) - \( C_{q} \neq C_{qs} \)
Unconditional separation of finite and infinitedimensional quantum correlations
Andrea Coladangelo and Jalex Stark (2018)
- Tsirelson's Problem
V. B. Scholz, R. F. Werner
- Lecture 17: Arthur-Merlin games, Zero-knowledge proofs
- Quantum Proofs
- Quantum Information Processing 2017
Complexity Zoo
- MIP*
- MA: Merlin-Arthur , MA', MAEXP, MAE
- AM: Arthur-Merlin, AMEXP, AM intersect co-AM, AM[polylog], coAM, BP•NP
- QMA: Quantum AM, QMA+, QMA(2), QMAlog, QMAM
- IP: Interactive Proof Systems, MIP, IPP, QIP, QIP(2), compIP, frIP
- PCP(r(n),q(n))
Wiki
- Interactive proof system
- MIP
- RE (complexity)
- List of complexity classes
- Arthur–Merlin protocol
- Connes embedding problem
- Tsirelson's bound
- Alain Connes
- Scott Aaronson
[その他の関連記事]
- Milestone Experiment Proves Quantum Communication Really Is Faster
https://www.quantamagazine.org/milestone-experiment-proves-quantum-communication-really-is-faster-20181219/ - ‘Outsiders’ Crack 50-Year-Old Math Problem
https://www.wired.com/2015/12/outsiders-crack-a-50-year-old-math-problem/
マルレク + MaruLabo
- 2020/11/27 コンピュータ・サイエンスの現在 — MIP*=RE定理とは何か？–
- 2020/11/01 Interactive Proof 入門 第二部 nonlocal game とInteractive Proof
- 2020/10/29 Interactive Proof 入門 第一部 機械と人間のインタラクション
- 2020/10/17 量子コンピュータ入門 — 量子コンピュータと人工知能 —
- 2020/09/18 人工知能と計算科学
- 2020/08/** 数学的認識について/数学の基礎と計算科学
- 2020/06/30 2のn乗の話
- 2018/11/19 人工知能と量子コンピュータ -- NP-完全問題とその含意
- 2018/10/15 計算理論入門 — 「やさしい計算」と「むずかしい計算」
- 2018/09/27 人工知能と複雑性理論
- 2018/01/31 ポスト・ディープラーニングの人工知能技術を展望する
Part IV 数学的認識能力への数学的アプローチ - 2017/09/28 エントロピーと情報理論 — 量子情報理論入門
