2013/07/25 by Zhang, Shengyu · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1307.6738
We show that for any Boolean function f on 0,1n, the bounded-error quantum communication complexity of XOR functions f∘ ⊕ satisfies that Qε(f∘ ⊕) = O(2d (log‖ f‖1,ε + log \fracnε) log(1/ε)), where d is the F2-degree of f, and ‖ f‖1,ε = ming:‖f-g‖_∞ ≤ ε ‖ f‖1. This implies that the previous lower bound Qε(f∘ ⊕) = Ω(log‖ f‖1,ε) by Lee and Shraibman \citeLS09 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 QE(f) = O(2d log ‖ f‖0), where ‖ f‖0 is the number of nonzero Fourier coefficients of f. This matches the previous lower bound QE(f(x,y)) = Ω(log rank(Mf)) by Buhrman and de Wolf \citeBdW01 for low-degree XOR functions.