dorsal/arxiv
View SchemaStrengths and Weaknesses of Quantum Fingerprinting
| Authors | Dmytro Gavinsky, Julia Kempe, Ronald de Wolf |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0603173 |
| URL | https://arxiv.org/abs/quant-ph/0603173 |
| Journal | Proc. 21st CCC (Complexity), p. 288-295 (2006) |
Abstract
We study the power of quantum fingerprints in the simultaneous message passing (SMP) setting of communication complexity. Yao recently showed how to simulate, with exponential overhead, classical shared-randomness SMP protocols by means of quantum SMP protocols without shared randomness ($Q^\parallel$-protocols). Our first result is to extend Yao's simulation to the strongest possible model: every many-round quantum protocol with unlimited shared entanglement can be simulated, with exponential overhead, by $Q^\parallel$-protocols. We apply our technique to obtain an efficient $Q^\parallel$-protocol for a function which cannot be efficiently solved through more restricted simulations. Second, we tightly characterize the power of the quantum fingerprinting technique by making a connection to arrangements of homogeneous halfspaces with maximal margin. These arrangements have been well studied in computational learning theory, and we use some strong results obtained in this area to exhibit weaknesses of quantum fingerprinting. In particular, this implies that for almost all functions, quantum fingerprinting protocols are exponentially worse than classical deterministic SMP protocols.
{
"annotation_id": "b4c6378c-b078-4275-8a00-55c3c84f1ae4",
"date_created": "2026-03-02T18:02:23.907000Z",
"date_modified": "2026-03-02T18:02:23.907000Z",
"file_hash": "f57bbfecca14d4186cc5e47db30c3da16fa7076111b60f1d758db9d13752f0d6",
"private": false,
"record": {
"abstract": "We study the power of quantum fingerprints in the simultaneous message\npassing (SMP) setting of communication complexity. Yao recently showed how to\nsimulate, with exponential overhead, classical shared-randomness SMP protocols\nby means of quantum SMP protocols without shared randomness\n($Q^\\parallel$-protocols). Our first result is to extend Yao\u0027s simulation to\nthe strongest possible model: every many-round quantum protocol with unlimited\nshared entanglement can be simulated, with exponential overhead, by\n$Q^\\parallel$-protocols. We apply our technique to obtain an efficient\n$Q^\\parallel$-protocol for a function which cannot be efficiently solved\nthrough more restricted simulations. Second, we tightly characterize the power\nof the quantum fingerprinting technique by making a connection to arrangements\nof homogeneous halfspaces with maximal margin. These arrangements have been\nwell studied in computational learning theory, and we use some strong results\nobtained in this area to exhibit weaknesses of quantum fingerprinting. In\nparticular, this implies that for almost all functions, quantum fingerprinting\nprotocols are exponentially worse than classical deterministic SMP protocols.",
"arxiv_id": "quant-ph/0603173",
"authors": [
"Dmytro Gavinsky",
"Julia Kempe",
"Ronald de Wolf"
],
"categories": [
"quant-ph",
"cs.CC"
],
"journal_ref": "Proc. 21st CCC (Complexity), p. 288-295 (2006)",
"title": "Strengths and Weaknesses of Quantum Fingerprinting",
"url": "https://arxiv.org/abs/quant-ph/0603173"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "fe6ac193-a262-494b-aea7-02d87a22e320",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}