dorsal/arxiv
View SchemaQuantum Algorithm for the Collision Problem
| Authors | Gilles Brassard, Peter Hoyer, Alain Tapp |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9705002 |
| URL | https://arxiv.org/abs/quant-ph/9705002 |
| DOI | 10.1007/BFb0054319 |
| Journal | Third Latin American Symp. on Theoretical Informatics (LATIN'98), pp. 163-169, 1998. LNCS 1380 |
Abstract
In this note, we give a quantum algorithm that finds collisions in arbitrary r-to-one functions after only O((N/r)^(1/3)) expected evaluations of the function. Assuming the function is given by a black box, this is more efficient than the best possible classical algorithm, even allowing probabilism. We also give a similar algorithm for finding claws in pairs of functions. Furthermore, we exhibit a space-time tradeoff for our technique. Our approach uses Grover's quantum searching algorithm in a novel way.
{
"annotation_id": "0e1f78e5-ddbd-496a-b4a6-222af7ea85b8",
"date_created": "2026-03-02T18:02:40.785000Z",
"date_modified": "2026-03-02T18:02:40.785000Z",
"file_hash": "28a827cd5016d65ec907877ccfd10ef60b0e11e562164819cfde84066b64afbc",
"private": false,
"record": {
"abstract": "In this note, we give a quantum algorithm that finds collisions in arbitrary\nr-to-one functions after only O((N/r)^(1/3)) expected evaluations of the\nfunction. Assuming the function is given by a black box, this is more efficient\nthan the best possible classical algorithm, even allowing probabilism. We also\ngive a similar algorithm for finding claws in pairs of functions. Furthermore,\nwe exhibit a space-time tradeoff for our technique. Our approach uses Grover\u0027s\nquantum searching algorithm in a novel way.",
"arxiv_id": "quant-ph/9705002",
"authors": [
"Gilles Brassard",
"Peter Hoyer",
"Alain Tapp"
],
"categories": [
"quant-ph"
],
"doi": "10.1007/BFb0054319",
"journal_ref": "Third Latin American Symp. on Theoretical Informatics (LATIN\u002798),\n pp. 163-169, 1998. LNCS 1380",
"title": "Quantum Algorithm for the Collision Problem",
"url": "https://arxiv.org/abs/quant-ph/9705002"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "f2e457cb-d54a-4c76-98da-94db9d4cd502",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}