dorsal/arxiv
View SchemaA quantum lower bound for the collision problem
| Authors | Samuel Kutin |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0304162 |
| URL | https://arxiv.org/abs/quant-ph/0304162 |
Abstract
We extend Shi's 2002 quantum lower bound for collision in $r$-to-one functions with $n$ inputs. Shi's bound of $\Omega((n/r)^{1/3})$ is tight, but his proof applies only in the case where the range has size at least $3n/2$. We give a modified version of Shi's argument which removes this restriction.
{
"annotation_id": "2dfa140d-4299-4226-986a-20e74a65eee3",
"date_created": "2026-03-02T18:01:58.927000Z",
"date_modified": "2026-03-02T18:01:58.927000Z",
"file_hash": "fa992cf814d87f86deab1cd2fb2b62f2380e0d8c7693a95b56560b52359b34f9",
"private": false,
"record": {
"abstract": "We extend Shi\u0027s 2002 quantum lower bound for collision in $r$-to-one\nfunctions with $n$ inputs. Shi\u0027s bound of $\\Omega((n/r)^{1/3})$ is tight, but\nhis proof applies only in the case where the range has size at least $3n/2$. We\ngive a modified version of Shi\u0027s argument which removes this restriction.",
"arxiv_id": "quant-ph/0304162",
"authors": [
"Samuel Kutin"
],
"categories": [
"quant-ph"
],
"title": "A quantum lower bound for the collision problem",
"url": "https://arxiv.org/abs/quant-ph/0304162"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "24cd2391-e4fc-4403-b744-0240a9e455d8",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}