Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function
Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function
复制标题
DOI：
--
复制
发表时间：
2006-07
期刊：
影响因子：
--
通讯作者：
Dmitry Gavinsky;J. Kempe;R. D. Wolf
中科院分区：
文献类型：
--
作者：
Dmitry Gavinsky;J. Kempe;R. D. Wolf
对于布尔函数，我们给出了单向量子通信复杂性和经典通信复杂性之间的指数分离。早些时候，这样的分离只为一种关系所知。Kerenidis和Raz早些时候独立地得到了非常相似的结果[KR06]。我们的结果给出了密码学有限存储模型中的一个例子，在该模型中，如果对手拥有一定量的经典存储，则密钥是安全的，但如果他具有类似数量的量子存储，则密钥是完全不安全的。
We 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.