Quantum sketching protocols for Hamming distance and beyond

In this work we use the concept of quantum fingerprinting to develop a quantum communication protocol in the simultaneous message passing model that calculates the Hamming distance between two $n$-bit strings up to relative error $ϵ$. The number of qubits communicated by the protocol is polynomial in $\log n$ and $1\mathrm{/}ϵ$, while any classical protocol must communicate $\mathrm{\Omega }(\sqrt{n})$ bits. Motivated by the relationship between Hamming distance and vertex distance in hypercubes, we apply the protocol to approximately calculate distances between vertices in graphs that can be embedded into a hypercube such that all distances are preserved up to a constant factor. Such graphs are known as ${\mathrm{\ell }}_1$-graphs. This class includes all trees, median graphs, Johnson graphs and Hamming graphs. Our protocol is efficient for ${\mathrm{\ell }}_1$-graphs with low diameter, and we show that its dependence on the diameter is essentially optimal. Finally, we show that our protocol can be used to approximately compute ${\mathrm{\ell }}_1$-distances between vectors efficiently.