2017/05/26 by Marcos Villagra, Villagra, Marcos
Computer Science · Mathematics · #Algorithm #Block (permutation group theory) #Block code #Combinatorics #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Discrete mathematics #F.1.2 #F.2.0 #FOS: Computer and information sciences #Geometry #Hamming bound #Hamming code #Hamming distance #Mathematics #Minimum distance #Quantum Computing Algorithms and Architecture #Reduction (mathematics) #Sensitivity (control systems) #Upper and lower bounds #cs.CC
paper · pdf · doi:10.48550/arxiv.1705.09710
published in arXiv (Cornell University) (Cornell University) · Short note, 3 pages
arxiv created 2017/05/26 · openalex publication_date 2017/05/26 · arxiv updated 2017/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The Gap-Hamming distance problem is the promise problem of deciding if the Hamming distance h between two strings of length n is greater than a or less than b, where the gap g=|a-b|≥ 1 and a and b could depend on n. In this short note, we give a lower bound of Ω( √(n/g)) on the quantum query complexity of computing the Gap-Hamming distance between two given strings of lenght n. The proof is a combinatorial argument based on block sensitivity and a reduction from a threshold function.