ECCC-Report TR06-086https://eccc.weizmann.ac.il/report/2006/086Comments and Revisions published for TR06-086en-usTue, 25 Jul 2006 22:00:22 +0300
Paper TR06-086
| Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function |
Dmytro Gavinsky,
Julia Kempe,
Ronald de Wolf
https://eccc.weizmann.ac.il/report/2006/086We give an exponential separation between one-way quantum and classical communication complexity for a Boolean function. Earlier such a separation was known only for a relation. A very similar result was obtained earlier but independently by Kerenidis and Raz [KR06]. Our version of the result gives an example in the bounded storage model of cryptography, where the key is secure if the adversary has a certain amount of classical storage, but is completely insecure if he has a similar amount of quantum storage.
Tue, 25 Jul 2006 22:00:22 +0300https://eccc.weizmann.ac.il/report/2006/086