ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > QUANTUM COMMUNICATION:
Reports tagged with Quantum Communication:
TR07-058 | 9th June 2007
Dmitry Gavinsky

Classical Interaction Cannot Replace a Quantum Message

Revisions: 1

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.

more >>>

TR07-074 | 7th August 2007
Dmitry Gavinsky, Pavel Pudlak

Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity

We give the first exponential separation between quantum and
classical multi-party
communication complexity in the (non-interactive) one-way and
simultaneous message
passing settings.
For every k, we demonstrate a relational communication problem
between k parties
that can be solved exactly by a quantum simultaneous message passing
protocol of
cost O(log ... more >>>


TR08-109 | 10th November 2008
Marc Kaplan, Sophie Laplante

Kolmogorov complexity and combinatorial methods in communication complexity

A very important problem in quantum communication complexity is to show that there is, or isn?t, an exponential gap between randomized and quantum complexity for a total function. There are currently no clear candidate functions for such a separation; and there are fewer and fewer randomized lower bound techniques that ... more >>>




ISSN 1433-8092 | Imprint