Abstract
We prove the existence of (one-way) communication tasks with a subconstant versus superconstant asymptotic gap, which we call “doubly infinite,” between their quantum information and communication complexities. We do so by studying the exclusion game [C. Perry et al., Phys. Rev. Lett. 115, 030504 (2015)] for which there exist instances where the quantum information complexity tends to zero as the size of the input increases. By showing that the quantum communication complexity of these games scales at least logarithmically in , 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 -qubit quantum message of the zero-error strategy can be compressed polynomially.
- Received 22 July 2015
- Revised 30 November 2015
DOI:https://doi.org/10.1103/PhysRevA.93.012347
©2016 American Physical Society