2014/02/28 by Jozef Gruska, Gruska, Jozef, Daowen Qiu +3 · 20 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · Physics and Astronomy · #Combinatorics #Communication complexity #DNA and Biological Computing #Discrete mathematics #Exponential function #Lambda #Mathematics #Omega #Physics #Probabilistic logic #Quantum #Quantum Computing Algorithms and Architecture #Quantum algorithm #Quantum entanglement #Quantum information science #Quantum mechanics #cs.CC #cs.DC #cs.FL #quant-ph #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1402.7254
published in arXiv (Cornell University) (Cornell University) · we correct some errors of and improve the presentation the previous version. arXiv admin note: substantial text overlap with arXiv:1309.7739
openalex publication_date 2014/02/28 · arxiv created 2015/03/18 · arxiv updated 2015/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
In the \em distributed Deutsch-Jozsa promise problem, two parties are to determine whether their respective strings x,y∈\0,1\n are at the \em Hamming distance H(x,y)=0 or H(x,y)=(n)/(2). Buhrman et al. (STOC' 98) proved that the exact \em quantum communication complexity of this problem is \bf O(log n) while the \em deterministic communication complexity is \bf Ω(n). This was the first impressive (exponential) gap between quantum and classical communication complexity. In this paper, we generalize the above distributed Deutsch-Jozsa promise problem to determine, for any fixed (n)/(2)≤ k≤ n, whether H(x,y)=0 or H(x,y)= k, and show that an exponential gap between exact quantum and deterministic communication complexity still holds if k is an even such that (1)/(2)n≤ k