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 logn and 1/ϵ, while any classical protocol must communicate ω(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 ?1-graphs. This class includes all trees, median graphs, Johnson graphs, and Hamming graphs. Our protocol is efficient for ?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 ?1 distances between vectors efficiently.