マルレク + MaruLabo
- 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 エントロピーと情報理論 — 量子情報理論入門
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
- MIP* = RE Part 1: The Quantum Low-Degree Test
By Anand Natarajan
- MIP* = RE Part 2: PCPs and Introspection
By John Wright
- MIP* = RE: Putting Everything Together
By Zhengfeng Ji
- A Masters project
- There is a protocol by which two entangled provers can convince a polynomial-time verifier of the answer to any computable problem whatsoever (!!), or indeed that a given Turing machine halts.
- There is a two-prover game, analogous to the Bell/CHSH game, for which Alice and Bob can do markedly better with a literally infinite amount of entanglement than they can with any finite amount of entanglement.
- There is no algorithm even to approximate the entangled value of a two-prover game (i.e., the probability that Alice and Bob win the game, if they use the best possible strategy and as much entanglement as they like). Instead, this problem is equivalent to the halting problem.
- There are types of correlations between Alice and Bob that can be produced using infinite entanglement, but that can’t even be approximated using any finite amount of entanglement.
- The Connes embedding conjecture, a central conjecture from the theory of operator algebras dating back to the 1970s, is false.
- 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
- MIP*=RE, disproving Connes embedding conjecture.
- Halting Is Poly-Time Quantum Provable
- From Operator Algebras to Complexity Theory and Back
- Graced With Knowledge, Mathematicians Seek to Understand
- Landmark Computer Science Proof Cascades Through Physics and Math
論文 “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.
- 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
論文 “Quantum proof systems for iterated exponential time and beyond“
Joseph F Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen
- 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.
- NON-DETERMINISTIC EXPONENTIAL TIME HAS TWO-PROVER INTERACTIVE PROTOCOLS
Laszl Babai, Lance Fortnow and Carsten Lund
https://lance.fortnow.com/papers/files/mip2.pdfWe determine the exact power of two-prover interactiveproof systems introduced by Ben-Or, Goldwasser, Kilian, and Wigderson (1988). In this system, two all-powerful noncommunicating proversconvince a randomizing polynomial time verier 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 = PWe 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 first 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 verification scheme for multilinearity of function in several variables held by an oracle and can be viewed as an independent result on program verication. Its proof rests on combinatorial techniques employing a simple isoperimetric inequality for certain graphs.
- Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions
https://dl.acm.org/doi/pdf/10.1145/62212.62223Quite 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
- 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
- Interactive proof system
- 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
- ‘Outsiders’ Crack 50-Year-Old Math Problem