  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 $\epsilon$. The number of qubits communicated by the protocol is
polynomial in $\log{n}$ and $1/\epsilon$, while any classical protocol must
communicate $\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 $\ell_1$-graphs. This class includes
all trees, median graphs, Johnson graphs and Hamming graphs. Our protocol is
efficient for $\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 $\ell_1$-distances between
vectors efficiently.
