ECCC - TR07-058

ECCC

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login

Register

Classic Style

REPORTS > DETAIL:

Revision(s):

Revision #1 to TR07-058 | 21st February 2008 00:00

Classical Interaction Cannot Replace a Quantum Message

Contact

Add Comment

Revision #1 Authors: Dmitry Gavinsky
Accepted on: 21st February 2008 00:00
Downloads: 3012

Keywords:

Communication complexity, Quantum Communication, separation

Abstract:

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 (two-way) model.

Paper:

TR07-058 | 9th June 2007 00:00

Classical Interaction Cannot Replace a Quantum Message

TR07-058 Authors: Dmytro Gavinsky
Publication: 11th July 2007 11:46
Downloads: 3407

Keywords:

communication models, exponential separation, Quantum Communication

Abstract:

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 (two-way) model.

ISSN 1433-8092 | Imprint