2012/04/20 by Hartmut Klauck, Klauck, Hartmut, Ronald de Wolf +1
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.1204.4619
10 pages LaTeX. Version: corrected an error in Section 2, slightly weakening the result
arxiv created 2012/09/25 · arxiv updated 2012/09/26
We use the venerable "fooling set" method to prove new lower bounds on the quantum communication complexity of various functions. Let f:X x Y-->0,1 be a Boolean function, fool1(f) its maximal fooling set size among 1-inputs, Q1^*(f) its one-sided error quantum communication complexity with prior entanglement, and NQ(f) its nondeterministic quantum communication complexity (without prior entanglement; this model is trivial with shared randomness or entanglement). Our main results are the following, where logs are to base 2: * If the maximal fooling set is "upper triangular" (which is for instance the case for the equality, disjointness, and greater-than functions), then we have Q1^*(f)>=(1/2)log fool1(f) - 1/2, which is essentially optimal by superdense coding. No super-constant lower bound for equality seems to follow from earlier techniques. * For all f we have Q1^*(f)>=(1/4)log fool1(f) - 1/2, which is optimal up to a factor of 2. * NQ(f)>=log \fool1(f)/2 + 1. We do not know if the factor 1/2 is needed in this result, but it cannot be replaced by 1: we give an example where NQ(f)~0.613 log fool1(f).