On the Power of Quantum Distributed Proofs

Explore a conference talk from TQC 2024 that delves into quantum nondeterministic distributed computing and dQMA (distributed quantum Merlin-Arthur) protocols. Learn about groundbreaking research demonstrating exponential separation between classical and quantum verification protocols in network-based equality problems. Discover how researchers developed more efficient dQMA protocols through symmetrization and permutation testing, while maintaining quantum advantages even in large path networks. Examine the implementation of efficient dQMA protocols for ranking verification, Hamming distance problems, and applications derived from quantum one-way communication complexity protocols. Understand the first established lower bounds on proof and communication costs in dQMA protocols, including the simulation of entangled proofs using separable proofs through QMA communication-complete problems. Presented at the 19th Conference on the Theory of Quantum Computation, Communication and Cryptography at OIST, Japan, this 23-minute presentation advances theoretical quantum information science through rigorous mathematical analysis and innovative protocol design.