Matching upper bounds on symmetric predicates in quantum communication complexity

Daiki Suruga

In this paper, we focus on the quantum communication complexity of functions of the form $f\circ G=f(G(X_1,Y_1),\dots ,G(X_n,Y_n))$ where $f:\{0,1{\}}^n\to \{0,1\}$ is a s…