A Block-Sensitivity Lower Bound for Quantum Testing Hamming Distance

Autor:	Villagra, Marcos
Rok vydání:	2017
Předmět:	Computer Science - Computational Complexity F.1.2 F.2.0
Druh dokumentu:	Working Paper
Popis:	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|\geq 1$ and $a$ and $b$ could depend on $n$. In this short note, we give a lower bound of $\Omega( \sqrt{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. Comment: Short note, 3 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1705.09710 Zobrazit plný text záznamu View this record from Arxiv