Efficient quantum protocols for XOR functions

We show that for any Boolean function f on {0,1}^n, the bounded-error quantum communication complexity of XOR functions $f\circ \oplus$ satisfies that $Q_\epsilon(f\circ \oplus) = O(2^d (\log|\hat f|{1,\epsilon} + \log \frac{n}{\epsilon}) \log(1/\epsilon))$,wheredistheF2-degreeoff,and$|\hat f|{1,\epsilon} = \min_{g:|f-g|\infty \leq \epsilon} |\hat f|1$. This implies that the previous lower bound $Q\epsilon(f\circ \oplus) = \Omega(\log|\hat f|{1,\epsilon})$ by Lee and Shraibman \cite{LS09} is tight for f with low F2-degree. The result also confirms the quantum version of the Log-rank Conjecture for low-degree XOR functions. In addition, we show that the exact quantum communication complexity satisfies $Q_E(f) = O(2^d \log |\hat f|_0)$,where$|\hat f|_0$ is the number of nonzero Fourier coefficients of f. This matches the previous lower bound $Q_E(f(x,y))=\mathrm{\Omega }(\log rank(M_f))$ by Buhrman and de Wolf \cite{BdW01} for low-degree XOR functions.