Fetching the paper…
Reading the bibliography…
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.
On computable numbers, with an application to the Entscheidungsproblem
Alan M. Turing · 1937
Earlier work this paper cites.
Introduction to Metamathematics
Stephen C. Kleene · 1954
Earlier work this paper cites.
On the computational complexity of algorithms
Juris Hartmanis and Richard E Stearns · 1965
Earlier work this paper cites.
Proposed experiment to test local hidden-variable theories
John F Clauser, Michael A Horne, Abner Shimony, and Richard A Holt · 1969
Earlier work this paper cites.
Probabilistic algorithms for sparse polynomials
Richard Zippel · 1979
Earlier work this paper cites.
Fast probabilistic algorithms for verification of polynomial identities
Jacob Schwartz · 1980
Earlier work this paper cites.
Theory of Recursive Functions and Effective Computability
Hartley Rogers, Jr · 1987
Earlier work this paper cites.
An algorithm to design finite field multipliers using a self-dual normal basis
Charles C. Wang · 1989
Earlier work this paper cites.
Algebraic methods for interactive proof systems
Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan · 1990
Earlier work this paper cites.
Simple unified form for the major no-hidden-variables theorems
David Mermin · 1990
Earlier work this paper cites.
Incompatible results of quantum measurements
Asher Peres · 1990
Earlier work this paper cites.
𝖨𝖯 = 𝖯𝖲𝖯𝖠𝖢𝖤 \mathsf{IP}=\mathsf{PSPACE}
Adi Shamir · 1990
Earlier work this paper cites.
New algorithms for finding irreducible polynomials over finite fields
Victor Shoup · 1990
Earlier work this paper cites.
Non-deterministic exponential time has two-prover interactive protocols
László Babai, Lance Fortnow, and Carsten Lund · 1991
Earlier work this paper cites.
Quantum cryptography based on bell’s theorem
Artur K Ekert · 1991
Earlier work this paper cites.
Finding isomorphisms between finite fields
H.W. Lenstra Jr · 1991
Earlier work this paper cites.
Two-prover one-round proof systems: Their power and their problems
Uriel Feige and László Lovász · 1992
Earlier work this paper cites.
Some results and problems on quantum bell-type inequalities
Boris S Tsirelson · 1993
Earlier work this paper cites.
Computational complexity
Christos Papadimitriou · 1994
Earlier work this paper cites.
Robust characterizations of polynomials with applications to program testing
Ronitt Rubinfeld and Madhu Sudan · 1996
Earlier work this paper cites.
A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP
Ran Raz and Shmuel Safra · 1997
Earlier work this paper cites.
Probabilistic checking of proofs: A new characterization of NP
Sanjeev Arora and Shmuel Safra · 1998
Earlier work this paper cites.
A simple demonstration of Bell’s theorem involving two observers and no probabilities or inequalities
PK Aravind · 2002
Earlier work this paper cites.
Consequences and limits of nonlocal strategies
Richard Cleve, Peter Hoyer, Benjamin Toner, and John Watrous · 2004
Earlier work this paper cites.
Robust PCPs of proximity and shorter PCPs
Prahladh Harsha · 2004
Cited alongside, same era.
Simple PCPs with poly-log rate and query complexity
Eli Ben-Sasson and Madhu Sudan · 2005
Cited alongside, same era.
Robust PCPs of proximity, shorter PCPs, and applications to coding
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan · 2006
Cited alongside, same era.
Bell inequalities and operator algebras, 2006
Boris S Tsirelson · 2006
Cited alongside, same era.
Short PCPs with polylog query complexity
Eli Ben-Sasson and Madhu Sudan · 2008
Cited alongside, same era.
The quantum moment problem and bounds on entangled multi-prover games
Andrew C Doherty, Yeong-Cherng Liang, Ben Toner, and Stephanie Wehner · 2008
Cited alongside, same era.
Survey on nonlocal games and operator space theory
Carlos Palazuelos and Thomas Vidick · 2016
Later among the works it cites.
Three-player entangled xor games are np-hard to approximate
Thomas Vidick · 2016
Later among the works it cites.
Quantum proofs
Thomas Vidick and John Watrous · 2016
Later among the works it cites.
A parallel repetition theorem for all entangled games
Henry Yuen · 2016
Later among the works it cites.
Hardness amplification for entangled games via anchoring
Mohammad Bavarian, Thomas Vidick, and Henry Yuen · 2017
Later among the works it cites.
Robust self-testing for linear constraint system games
Andrea Coladangelo and Jalex Stark · 2017
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
Miguel Navascués, Stefano Pironio, and Antonio Acín · 2008
Cited alongside, same era.
Oracularization and two-prover one-round interactive proofs against nonlocal strategies
Tsuyoshi Ito, Hirotada Kobayashi, and Keiji Matsumoto · 2009
Cited alongside, same era.
Connes’ embedding problem and Tsirelson’s problem
Marius Junge, Miguel Navascues, Carlos Palazuelos, David Perez-Garcia, Volkher B Scholz, and Reinhard F Werner · 2011
Cited alongside, same era.
Entangled games are hard to approximate
Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick · 2011
Cited alongside, same era.
Parallel repetition of entangled games
Julia Kempe and Thomas Vidick · 2011
Cited alongside, same era.
Tsirelson’s problem and Kirchberg’s conjecture
Tobias Fritz · 2012
Cited alongside, same era.
Compression of quantum multi-prover interactive proofs
Zhengfeng Ji · 2017
Later among the works it cites.
A quantum linearity test for robustly verifying entanglement
Anand Natarajan and Thomas Vidick · 2017
Later among the works it cites.
Unconditional separation of finite and infinite-dimensional quantum correlations
Andrea Coladangelo and Jalex Stark · 2018
Later among the works it cites.
A synchronous game for binary constraint systems
Se-Jin Kim, Vern Paulsen, and Christopher Schafhauser · 2018
Later among the works it cites.
Magdalena Musat and Mikael Rørdam · 2018
Later among the works it cites.
Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
Anand Natarajan and Thomas Vidick · 2018
Later among the works it cites.
Two-player entangled games are NP-hard
Anand Natarajan and Thomas Vidick · 2018
Later among the works it cites.
Andrea Coladangelo · 2019
Later among the works it cites.
Non-closure of the set of quantum correlations via graphs
Ken Dykema, Vern I Paulsen, and Jitendra Prakash · 2019
Later among the works it cites.
Quantum proof systems for iterated exponential time, and beyond
Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, and Henry Yuen · 2019
Later among the works it cites.
𝖭𝖤𝖤𝖷𝖯 ⊆ 𝖬𝖨𝖯 ∗ \mathsf{NEEXP}\subseteq\mathsf{MIP}^{*}
Anand Natarajan and John Wright · 2019
Later among the works it cites.
The set of quantum correlations is not closed
William Slofstra · 2019
Later among the works it cites.
Tsirelson’s problem and an embedding theorem for groups arising from non-local games
William Slofstra · 2019
Later among the works it cites.
The universal theory of the hyperfinite II 1 factor is not computable
Isaac Goldbring and Bradd Hart · 2020
Closest in time.
Quantum soundness of the classical low individual degree test
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen · 2020
Closest in time.
On the complexity of zero gap 𝖬𝖨𝖯 ∗ \mathsf{MIP}^{*}
Hamoon Mousavi, Seyed Sajjad Nezhadi, and Henry Yuen · 2020
Closest in time.
Quantum soundness of testing tensor codes
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen · 2021
Closest in time.