2004/11/20 by Andris Ambainis, William Gasarch, Ambainis, Andris +5 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Alice and Bob #Bounding overwatch #Combinatorics #Communication complexity #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Computer science #Discrete mathematics #FOS: Computer and information sciences #FOS: Physical sciences #Hamming distance #Mathematics #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #Quantum entanglement #Quantum information science #Quantum mechanics #Upper and lower bounds #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.cs/0411076
published in arXiv (Cornell University) (Cornell University) · 12 pages, this version to appear in ACM Transactions on Computation Theory
openalex publication_date 2004/11/20 · arxiv created 2015/01/12 · arxiv updated 2015/01/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/08
Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on at most a bits? Let 0≤ a≤ 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.