dorsal/arxiv
View SchemaQuantum lower bound for sorting
| Authors | Yaoyun Shi |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0009091 |
| URL | https://arxiv.org/abs/quant-ph/0009091 |
Abstract
We prove that \Omega(n log(n)) comparisons are necessary for any quantum algorithm that sorts n numbers with high success probability and uses only comparisons. If no error is allowed, at least 0.110nlog_2(n) - 0.067n + O(1) comparisons must be made. The previous known lower bound is \Omega(n).
{
"annotation_id": "8316cd84-a708-482b-9e20-ffed83296b89",
"date_created": "2026-03-02T18:01:38.869000Z",
"date_modified": "2026-03-02T18:01:38.869000Z",
"file_hash": "d3960c4545edebfc199ed0a1a10f994ce36d873f91ebb51509c3f533dd6e1b7e",
"private": false,
"record": {
"abstract": "We prove that \\Omega(n log(n)) comparisons are necessary for any quantum\nalgorithm that sorts n numbers with high success probability and uses only\ncomparisons. If no error is allowed, at least 0.110nlog_2(n) - 0.067n + O(1)\ncomparisons must be made. The previous known lower bound is \\Omega(n).",
"arxiv_id": "quant-ph/0009091",
"authors": [
"Yaoyun Shi"
],
"categories": [
"quant-ph"
],
"title": "Quantum lower bound for sorting",
"url": "https://arxiv.org/abs/quant-ph/0009091"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "d2fe8e1b-e908-41b9-9be3-1c59ca26085c",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}