Hartmut Klauck, Ronald de Wolf
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, fool^1(f) its maximal fooling set size among 1-inputs, Q_1^*(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 entanglement). Our main results are the following, where logs are to base 2: * Q_1^*(f)>=(log fool^1(f)-1)/2. This result is tight via superdense coding, and gives optimal bounds for basic functions like equality and disjointness (for the former, no super-constant lower bound seems to follow from other known techniques). * NQ(f)>=log \fool^1(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 fool^1(f).
View original:
http://arxiv.org/abs/1204.4619
No comments:
Post a Comment