Quantum sketching protocols for Hamming distance and beyond
arXiv:1810.12808 · doi:10.1103/PhysRevA.99.062331
Abstract
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 -bit strings up to relative error . The number of qubits communicated by the protocol is polynomial in and , while any classical protocol must communicate 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 -graphs. This class includes all trees, median graphs, Johnson graphs and Hamming graphs. Our protocol is efficient for -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 -distances between vectors efficiently.
arXiv comment11 pages; v3: epsilon dependence was improved and typos corrected; v4: appendix on -graphs characterisation deleted due to a mistake and references added
References in corpus (13)
- Quantum fingerprinting
- Non-locality and Communication Complexity
- Exponential Communication Complexity Advantage from Quantum Superposition of the Direction of Communication
- Experimental Quantum Switching for Exponentially Superior Quantum Communication Complexity
- Experimental Quantum Fingerprinting
- Quantum Fingerprinting with Coherent States and a Constant Mean Number of Photons
- The Communication Complexity of the Hamming Distance Problem
- Single-qubit optical quantum fingerprinting
- Observation of quantum fingerprinting beating the classical limit
- Efficient quantum communications with multiplexed coherent state fingerprints
- One-qubit fingerprinting schemes
- Quantum Communication Cannot Simulate a Public Coin
- Two-dimensional partial cubes