Marcos Villagra

A Block-Sensitivity Lower Bound for Quantum Testing Hamming Distance

2017 · arXiv (Cornell University)

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 …