dorsal/arxiv
View SchemaQuantum lower bounds for the collision and the element distinctness problems
| Authors | Yaoyun Shi |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0112086 |
| URL | https://arxiv.org/abs/quant-ph/0112086 |
| DOI | 10.1109/SFCS.2002.1181975 |
| Journal | Proceedings of The 43rd Annual IEEE Symposium on Foundations of Computer Science, 513 - 519, 2002 |
Abstract
Given a function f as an oracle, the collision problem is to find two distinct inputs i and j such that f(i)=f(j), under the promise that such inputs exist. Since the security of many fundamental cryptographic primitives depends on the hardness of finding collisions, quantum lower bounds for the collision problem would provide evidence for the existence of cryptographic primitives that are immune to quantum cryptanalysis. In this paper, we prove that any quantum algorithm for finding a collision in an r-to-one function must evaluate the function Omega((n/r)^{1/3}) times, where n is the size of the domain and r|n. This improves the previous best lower bound of Omega((n/r)^{1/5}) evaluations due to Aaronson [quant-ph/0111102], and is tight up to a constant factor. Our result also implies a quantum lower bound of Omega(n^{2/3}) queries to the inputs for the element distinctness problem, which is to determine whether or not the given n real numbers are distinct. The previous best lower bound is Omega(sqrt{n}} queries in the black-box model; and Omega(sqrt{n}log{n}) comparisons in the comparisons-only model, due to H{\o}yer, Neerbek, and Shi [ICALP'01, quant-ph/0102078].
{
"annotation_id": "a373141d-b4ee-4794-956e-6a804e48fbbb",
"date_created": "2026-03-02T18:01:48.339000Z",
"date_modified": "2026-03-02T18:01:48.339000Z",
"file_hash": "07733a28e89204779def4e7e50adf157f408b5de2ce76784b8a7a9e8a9506a23",
"private": false,
"record": {
"abstract": "Given a function f as an oracle, the collision problem is to find two\ndistinct inputs i and j such that f(i)=f(j), under the promise that such inputs\nexist. Since the security of many fundamental cryptographic primitives depends\non the hardness of finding collisions, quantum lower bounds for the collision\nproblem would provide evidence for the existence of cryptographic primitives\nthat are immune to quantum cryptanalysis.\n In this paper, we prove that any quantum algorithm for finding a collision in\nan r-to-one function must evaluate the function Omega((n/r)^{1/3}) times, where\nn is the size of the domain and r|n. This improves the previous best lower\nbound of Omega((n/r)^{1/5}) evaluations due to Aaronson [quant-ph/0111102], and\nis tight up to a constant factor.\n Our result also implies a quantum lower bound of Omega(n^{2/3}) queries to\nthe inputs for the element distinctness problem, which is to determine whether\nor not the given n real numbers are distinct. The previous best lower bound is\nOmega(sqrt{n}} queries in the black-box model; and Omega(sqrt{n}log{n})\ncomparisons in the comparisons-only model, due to H{\\o}yer, Neerbek, and Shi\n[ICALP\u002701, quant-ph/0102078].",
"arxiv_id": "quant-ph/0112086",
"authors": [
"Yaoyun Shi"
],
"categories": [
"quant-ph"
],
"doi": "10.1109/SFCS.2002.1181975",
"journal_ref": "Proceedings of The 43rd Annual IEEE Symposium on Foundations of\n Computer Science, 513 - 519, 2002",
"title": "Quantum lower bounds for the collision and the element distinctness problems",
"url": "https://arxiv.org/abs/quant-ph/0112086"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "363e7b10-509f-48eb-8526-db19cae9d0f0",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}