Quantum sketching protocols for Hamming distance and beyond
João Fernando Doriguello, Ashley Montanaro · Physical Review A · 2019
Comparing data is ubiquitous in communication, and quantum protocols like quantum fingerprinting provide an exponential advantage in the complexity of equality testing. In this work, a quantum protocol for approximately computing another comparison measure, the Hamming distance, up to low relative error, is developed.