Physics – Quantum Physics
Scientific paper
2012-04-20
Physics
Quantum Physics
9 pages LaTeX
Scientific paper
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).
Klauck Hartmut
Wolf Ronald de
No associations
LandOfFree
Fooling One-Sided Quantum Protocols does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Fooling One-Sided Quantum Protocols, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fooling One-Sided Quantum Protocols will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-5728