Classical interaction cannot replace a quantum message

We demonstrate a two-player communication problem that can be solved in the one-way quantum model by a 0-error protocol of cost O(log n) but requires exponentially more communication in the classical interactive (bounded error) model.

Authors

• Dmitry Gavinsky

Keywords

• quantum
• communication complexity