%0 Journal Article
%T Doubly infinite separation of quantum information and communication
%A Zi-Wen Liu
%A Christopher Perry
%A Yechao Zhu
%A Dax Enshan Koh
%A Scott Aaronson
%J Computer Science
%D 2015
%I arXiv
%X We prove the existence of (one-way) communication tasks with a subconstant vs. superconstant asymptotic gap, which we call "doubly infinite", between the quantum information and communication complexities. We do so by studying the exclusion game for which there exist instances where the quantum information complexity tends to zero. By showing that as the size of the input $n$ increases, the quantum communication complexity of these games scales at least logarithmically in $n$, we obtain our result. We further show that the established lower bounds and gaps still hold even if we allow a small probability of error. However in this case, the $n$-qubit quantum message of the zero-error strategy can be compressed polynomially.
%U http://arxiv.org/abs/1507.03546v3