dorsal/arxiv
View SchemaOptimal fingerprinting strategies with one-sided error
| Authors | A. J. Scott, Jonathan Walgate, Barry C. Sanders |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0507048 |
| URL | https://arxiv.org/abs/quant-ph/0507048 |
| Journal | Quantum Inf. Comput. 7, 243 (2007) |
Abstract
Fingerprinting enables two parties to infer whether the messages they hold are the same or different when the cost of communication is high: each message is associated with a smaller fingerprint and comparisons between messages are made in terms of their fingerprints alone. In the simultaneous message passing model, it is known that fingerprints composed of quantum information can be made exponentially smaller than those composed of classical information. For small message lengths, we present constructions of optimal classical fingerprinting strategies with one-sided error, in both the one-way and simultaneous message passing models, and provide bounds on the worst-case error probability with the help of extremal set theory. The performance of these protocols is then compared to that for quantum fingerprinting strategies constructed from spherical codes, equiangular tight frames and mutually unbiased bases.
{
"annotation_id": "7712b547-0e93-4275-b27f-e180bf063820",
"date_created": "2026-03-02T18:02:17.213000Z",
"date_modified": "2026-03-02T18:02:17.213000Z",
"file_hash": "e9b2260b5d2fd767d0bc2fa3578aee925c5a4d6fa3712d0a1557277be0bf35cb",
"private": false,
"record": {
"abstract": "Fingerprinting enables two parties to infer whether the messages they hold\nare the same or different when the cost of communication is high: each message\nis associated with a smaller fingerprint and comparisons between messages are\nmade in terms of their fingerprints alone. In the simultaneous message passing\nmodel, it is known that fingerprints composed of quantum information can be\nmade exponentially smaller than those composed of classical information. For\nsmall message lengths, we present constructions of optimal classical\nfingerprinting strategies with one-sided error, in both the one-way and\nsimultaneous message passing models, and provide bounds on the worst-case error\nprobability with the help of extremal set theory. The performance of these\nprotocols is then compared to that for quantum fingerprinting strategies\nconstructed from spherical codes, equiangular tight frames and mutually\nunbiased bases.",
"arxiv_id": "quant-ph/0507048",
"authors": [
"A. J. Scott",
"Jonathan Walgate",
"Barry C. Sanders"
],
"categories": [
"quant-ph"
],
"journal_ref": "Quantum Inf. Comput. 7, 243 (2007)",
"title": "Optimal fingerprinting strategies with one-sided error",
"url": "https://arxiv.org/abs/quant-ph/0507048"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "9578fbef-7a82-40ab-a3a9-43d88235b4ad",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}