ECCC-Report TR07-074https://eccc.weizmann.ac.il/report/2007/074Comments and Revisions published for TR07-074en-usWed, 08 Aug 2007 13:33:34 +0300
Paper TR07-074
| Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity |
Dmytro Gavinsky,
Pavel Pudlak
https://eccc.weizmann.ac.il/report/2007/074 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 n) and requires protocols of cost n^{c/k^2}, where c>0 is a
constant, in the
classical non-interactive one-way message passing model with shared randomn=
ess
and bounded error. Thus our separation of corresponding communication
classes is
superpolynomial as long as k=3Do(\sqrt{\log n / \log\log n}) and
exponential for k=3DO(1).
Wed, 08 Aug 2007 13:33:34 +0300https://eccc.weizmann.ac.il/report/2007/074