In this work we consider the interplay between multiprover interactive proofs, quantum entanglement, and zero knowledge proofs - notions that are central pillars of complexity theory, quantum information and cryptography. In particular, we study the relationship between the complexity class MIP @math , the set of languages decidable by multiprover interactive proofs with quantumly entangled provers, and the class PZKMIP @math , which is the set of languages decidable by MIP @math protocols that furthermore possess the perfect zero knowledge property. Our main result is that the two classes are equal, i.e., MIP @math PZKMIP @math . This result provides a quantum analogue of the celebrated result of Ben-Or, Goldwasser, Kilian, and Wigderson (STOC 1988) who show that MIP @math PZKMIP (in other words, all classical multiprover interactive protocols can be made zero knowledge). We prove our result by showing that every MIP @math protocol can be efficiently transformed into an equivalent zero knowledge MIP @math protocol in a manner that preserves the completeness-soundness gap. Combining our transformation with previous results by Slofstra (Forum of Mathematics, Pi 2019) and Fitzsimons, Ji, Vidick and Yuen (STOC 2019), we obtain the corollary that all co-recursively enumerable languages (which include undecidable problems as well as all decidable problems) have zero knowledge MIP @math protocols with vanishing promise gap.
Recently, Kinoshita @cite_20 showed that a model of honest-verifier'' zero knowledge QMIP can be lifted to general zero knowledge QMIP protocols. He also shows that @math have interactive proofs with zero knowledge proofs under a computational assumption.
@cite_20
2915900549
Zero-knowledge and multi-prover systems are both central notions in classical and quantum complexity theory. There is, however, little research in quantum multi-prover zero-knowledge systems. This paper studies complexity-theoretical aspects of the quantum multi-prover zero-knowledge systems. This paper has two results: 1.QMIP* systems with honest zero-knowledge can be converted into general zero-knowledge systems without any assumptions. 2.QMIP* has computational quantum zero-knowledge systems if a natural computational conjecture holds. One of the main tools is a test (called the GHZ test) that uses GHZ states shared by the provers, which prevents the verifier's attack in the above two results. Another main tool is what we call the Local Hamiltonian based Interactive protocol (LHI protocol). The LHI protocol makes previous research for Local Hamiltonians applicable to check the history state of interactive proofs, and we then apply 's zero-knowledge protocol for QMA BJSW to quantum multi-prover systems in order to obtain the second result.