Bare quantum simultaneity versus classical interactivity in communication complexity

A relational bipartite communication problem is presented that has an efficient quantum simultaneous-messages protocol, but no efficient classical two-way protocol.

Authors

• Dmitry Gavinsky

Keywords

• communication complexity models
• quantum communication complexity