dorsal/arxiv
View SchemaA Polynomial-Time Quantum Algorithm for Collision Problem
| Authors | Dong Pyo Chi, Jinsoo Kim |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9707011 |
| URL | https://arxiv.org/abs/quant-ph/9707011 |
Abstract
In this paper, we give a quantum algorithm which solves collision problem in an expected polynomial time. Especially, when the function is two-to-one, we present a quantum algorithm which can find a collision with certainty in a worst-case polynomial time. We also give a quantum algorithm which solves claw problem with certainty in a worst-case polynomial time.
{
"annotation_id": "2464040f-7e0b-46c4-bb2b-d972cde65a7b",
"date_created": "2026-03-02T18:02:41.347000Z",
"date_modified": "2026-03-02T18:02:41.347000Z",
"file_hash": "85e6561e86c8df4456db74f59201bbc407bacad5a0509d0ecdcf72eeb108917a",
"private": false,
"record": {
"abstract": "In this paper, we give a quantum algorithm which solves collision problem in\nan expected polynomial time. Especially, when the function is two-to-one, we\npresent a quantum algorithm which can find a collision with certainty in a\nworst-case polynomial time. We also give a quantum algorithm which solves claw\nproblem with certainty in a worst-case polynomial time.",
"arxiv_id": "quant-ph/9707011",
"authors": [
"Dong Pyo Chi",
"Jinsoo Kim"
],
"categories": [
"quant-ph"
],
"title": "A Polynomial-Time Quantum Algorithm for Collision Problem",
"url": "https://arxiv.org/abs/quant-ph/9707011"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "688fedd1-a825-4a55-89c5-fce560772e43",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}