MIP*=RE 関連資料集

マルレク + MaruLabo

論文 “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 12. 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 Cqa of the set of quantum tensor product correlations is strictly included in the set Cqc 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.


論文 “NEEXP ⊆ MIP*”

Anand Natarajan, John Wright
[v1] Thu, 11 Apr 2019 17:56:45 UTC (120 KB)
[v2] Fri, 24 May 2019 01:54:21 UTC (121 KB)
[v3] Mon, 2 Sep 2019 20:39:46 UTC (119 KB)

We study multiprover interactive proof systems. The power of classical multiprover interactive proof systems, in which the provers do not share entanglement, was characterized in a famous work by Babai, Fortnow, and Lund (Computational Complexity 1991), whose main result was the equality MIP = NEXP. The power of quantum multiprover interactive proof systems, in which the provers are allowed to share entanglement, has proven to be much more difficult to characterize. The best known lower-bound on MIP* is NEXP, due to Ito and Vidick (FOCS 2012). As for upper bounds, MIP* could be as large as RE, the class of recursively enumerable languages.

The main result of this work is the inclusion of NEEXP (nondeterministic doubly exponential time) in MIP*. This is an exponential improvement over the prior lower bound and shows that proof systems with entangled provers are at least exponentially more powerful than classical provers. In our protocol the verifier delegates a classical, exponentially large MIP protocol for NEEXP to two entangled provers: the provers obtain their exponentially large questions by measuring their shared state, and use a classical PCP to certify the correctness of their exponentially-long answers. For the soundness of our protocol, it is crucial that each player should not only sample its own question correctly but also avoid performing measurements that would reveal the other player’s sampled question. We ensure this by commanding the players to perform a complementary measurement, relying on the Heisenberg uncertainty principle to prevent the forbidden measurements from being performed.


論文 “Quantum proof systems for iterated exponential time and beyond

Joseph F Fitzsimons, Zhengfeng  Ji,  Thomas  Vidick, Henry  Yuen

We show that any language solvable in nondeterministic time exp(exp(· · · exp(n))), where the number of iterated exponentials is an arbitrary function R(n), can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness 1 and soundness 1 − exp(−C exp(· · · exp(n))), where the number of iterated exponentials is R(n) − 1 and C > 0 is a universal constant.
The result was previously known for R = 1 and R = 2; we obtain it for any time-constructible function R. The result is based on a compression technique for interactive proof systems with entangled provers that significantly simplifies and strengthens a protocol compression result of Ji (STOC’17).
As a separate consequence of this technique we obtain a different proof of Slofstra’s recent result on the uncomputability of the entangled value of multiprover games (Forum of Mathematics, Pi 2019).
Finally, we show that even minor improvements to our compression result would yield remarkable consequences in computational complexity theory and the foundations of quantum mechanics: first, it would imply that the class MIP∗ contains all computable languages; second, it would provide a negative resolution to a multipartite version of Tsirelson’s problem on the relation between the commuting operator and tensor product models for quantum correlations.


  • 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.
    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

Complexity Zoo