Perfect Zero Knowledge for Quantum Multiprover Interactive Proofs

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*, the set of languages decidable by multiprover interactive proofs with quantumly entangled provers, and the class PZK-MIP*, which is the set of languages decidable by MIP* protocols that furthermore possess the perfect zero knowledge property. Our main result is that the two classes are equal, i. e. , MIP* = PZK-MIP*. This result provides a quantum analogue of the celebrated result of Ben-Or, Goldwasser, Kilian, and Wigderson (STOC 1988) who show that MIP = PZK-MIP (in other words, all classical multiprover interactive protocols can be made zero knowledge). We prove our result by showing that every MIP* protocol can be efficiently transformed into an equivalent zero knowledge MIP* protocol in a manner that preserves the completeness-soundness gap. Combining our transformation with previous results, we obtain the corollaries that i) all languages that can be solved in non-deterministic double exponential time have zero knowledge MIP* protocols and ii) all co-recursively enumerable languages (which include undecidable problems as well as all decidable problems) have zero knowledge MIP* protocols with vanishing promise gap.

Authors

• Alex Bredariol Grilo
• William Slofstra
• Henry Yuen

Keywords

• Computer science
• Quantum computing
• Quantum entanglement
• Mathematics
• Complexity theory
• Zero knowledge proof
• Interactive
• Perfect Knowledge
• Zero Knowledge
• Complex Class
• Entangled State
• Computational Efficiency
• Fault-tolerant
• Hilbert Space
• Boolean Logic
• Original Protocol
• Density Matrix
• Matrix Representation
• Probability 1
• Number Of Time Steps
• Universal Set
• Efficient Representation
• Quantum Circuit
• Turing Machine
• Quantum Error Correction
• Set Of Languages
• Zero-knowledge Proof
• Probabilistic Polynomial Time
• Partial Trace
• Protocol States
• Single Qubit
• Local Measurements
• Time Step
• Cross Terms
• Efficient Simulation
• Quantum Complexity
• Non local games