Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance

Details Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance

2004-11-20

arxiv.org/abs/cs/0411076v1

Computer Science

Computational Complexity

13 pages

Scientific paper

Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on \textit{at most} a bits? Let 0\leq a\leq n-1. We show that any deterministic protocol, as well as any error-free quantum protocol (C* version), for this problem requires at least n-2 bits of communication. We show the same bounds for the problem of determining if two strings differ in exactly a bits. We also prove a lower bound of n/2-1 for error-free Q* quantum protocols. Our results are obtained by lower-bounding the ranks of the appropriate matrices.

Affiliated with

Also associated with

No associations

Rating

Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance 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 Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-169856