Exponential separation of quantum and classical communication complexity 论文

摘要

Communication complexity has become a central completity model. In that model, we count the amount of communication bits needed between two parties in order to solve certain computational problems. We show that for certain communication complezity problems quantum communication protocols are exponentially faster than classical ores. More explicitly, we give an example for a communication complexity relation (0~ promise problem) P such that: 1) The quantum communication