Quantum and Classical Communication Complexity of Permutation-Invariant Functions

Ziyi Guan, Yunqi Huang, Penghui Yao +1

This paper gives a nearly tight characterization of the quantum communication complexity of the permutation-invariant Boolean functions. With such a characterization, we show that…