Quantum communication proves stronger than Merlin-Arthur protocols
BQP^cc is not contained in MA^cc
Computational Complexity
Summary
This work shows that there are some communication problems where quantum methods are more efficient than classical ones that rely on proofs checked in a traditional way. Specifically, the authors found a task that can be solved with very little quantum communication but requires much more communication if done with Merlin-Arthur style protocols. This suggests that quantum communication can solve some problems in ways classical approaches cannot match.
What this means in practice
- •For quantum communication engineers: Design communication systems that use quantum protocols to reduce communication costs beyond classical proof-based methods.
- •For cryptography system designers: Identify when quantum protocols can outperform classical interactive proofs to enhance secure communication schemes.
A theory result. No direct application yet.
Authors
Dmytro Gavinsky
Abstract
We exhibit a bipartite language with a poly-logarithmic quantum communication protocol and polynomial Merlin-Arthur communication complexity.