Weizmann Logo
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

RSS-Feed




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


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: 3427
Keywords: 


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