@inproceedings{8c29cb7c1e444ea4b2d0b709e5620515,
title = "A lower bound on entanglement-assisted quantum communication complexity",
abstract = "We prove a general lower bound on the bounded-error entanglement-assisted quantum communication complexity of Boolean functions. The bound is based on the concept that any classical or quantum protocol to evaluate a function on distributed inputs can be turned into a quantum communication protocol. As an application of this bound, we give a very simple proof of the statement that almost all Boolean functions on n + n bits have communication complexity linear in n, even in the presence of unlimited entanglement.",
author = "Ashley Montanaro and Andreas Winter",
year = "2007",
doi = "10.1007/978-3-540-73420-8_13",
language = "English",
isbn = "3540734198",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "122--133",
booktitle = "Automata, Languages and Programming - 34th International Colloquium, ICALP 2007, Proceedings",
note = "34th International Colloquium on Automata, Languages and Programming, ICALP 2007 ; Conference date: 09-07-2007 Through 13-07-2007",
}