MIP*=RE References

Main Articles “MIP*=RE

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen

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
Quantum soundness of the classical low individual degree test

Commentary notes by the authors

Video List Interactive Proof (MIP*=RE)

On the eve of the proof

BIRS Workshop 2019/07

QIP 2017


[Introductory articles]

History of the theory

  • Tsirelson’s Problem
    V. B. Scholz, R. F. Werner

    [Submitted on 22 Dec 2008]

    The situation of two independent observers conducting measurements on a joint quantum system is usually modelled using a Hilbert space of tensor product form, each factor associated to one observer. Correspondingly, the operators describing the observables are then acting non-trivially only on one of the tensor factors. However, the same situation can also be modelled by just using one joint Hilbert space, and requiring that all operators associated to different observers commute, i.e. are jointly measurable without causing disturbance.
    The problem of Tsirelson is now to decide the question whether all quantum correlation functions between two independent observers derived from commuting observables can also be expressed using observables defined on a Hilbert space of tensor product form. Tsirelson showed already that the distinction is irrelevant in the case that the ambient Hilbert space is of finite dimension. We show here that the problem is equivalent to the question whether all quantum correlation functions can be approximated by correlation function derived from finite-dimensional systems. We also discuss some physical examples which fulfill this requirement.
  • Tsirelson’s problem and an embedding theorem for groups arising from non-local games
    Laszl Babai, Lance Fortnow and Carsten Lund

    We determine the exact power of two-prover interactive
    proof systems introduced by Ben-Or, Goldwasser, Kilian, and Wigderson (1988). In this system, two all-powerful noncommunicating provers
    convince a randomizing polynomial time veri er in polynomial time that the input x belongs to the language L. It was previously suspected (and proved in a relativized sense) that coN P-complete languages do not admit such proof systems. In sharp contrast, we show that the class of languages having two-prover interactive proof systems is nondeterministic exponential time.
    After the recent results that all languages in PSPACE have single prover interactive proofs (Lund, Fortnow, Karlo , Nisan, and Shamir),
    this represents a further step demonstrating the unexpectedly immense >power of randomization and interaction in effcient provability. Indeed, it follows that multiple provers with coins are strictly stronger than without, since NEXP 6= N P . In particular, for the first time, provably polynomial time intractable languages turn out to admit effcient proof systems” since NEXP = P
    We show that to prove membership in languages in EXP , the honest provers need the power of EXP only. A consequence, linking more standard concepts of structural complexity, states that if EXP has polynomial size circuits then EXP = MA, strengthening a result of A. Meyer that EXP = P under the same condition.
    The fi rst part of the proof of the main result extends recent techniques of polynomial extrapolation of truth values used in the single prover case. The second part is a veri fication scheme for multilinearity of function in several variables held by an oracle and can be viewed as an independent result on program veri cation. Its proof rests on combinatorial techniques employing a simple isoperimetric inequality for certain graphs.
  • Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions 

    Quite complex cryptographic machinery has been developed based on the assumption that one-way functions exist, yet we know of only a few possible such candidates. It is important at this time to find alternative foundations to the design of secure cryptography. We introduce a new model of generalized interactive proofs as a step in this direction. We prove that all NP languages have perfect zero-knowledge proof-systems in this model, without making any intractability assumptions.
    The generalized interactive-proof model consists of two computationally unbounded and untrusted provers , rather than one, who jointly agree on a strategy to convince the verifier of the truth of an assertion and then engage in a polynomial number of message exchanges with the verifier in their attempt to do so. To believe the validity of the assertion, the verifier must make sure that the two provers can not communicate with each other during the course of the proof process. Thus, the complexity assumptions made in previous work, have been traded for a physical separation between the two provers.
    We call this new model the multi-prover interactive-proof model, and examine its properties and applicability to cryptography.
  • Lecture 17: Arthur-Merlin games, Zero-knowledge proofs
  • Quantum Proofs
  • Quantum Information Processing 2017

Complexity Zoo



マルレク + MaruLabo