dorsal/arxiv
View SchemaQuantum Time-Space Tradeoffs for Sorting
| Authors | Hartmut Klauck |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0211174 |
| URL | https://arxiv.org/abs/quant-ph/0211174 |
Abstract
We investigate the complexity of sorting in the model of sequential quantum circuits. While it is known that in general a quantum algorithm based on comparisons alone cannot outperform classical sorting algorithms by more than a constant factor in time complexity, this is wrong in a space bounded setting. We observe that for all storage bounds n/\log n\ge S\ge \log^3 n, one can devise a quantum algorithm that sorts n numbers (using comparisons only) in time T=O(n^{3/2}\log^{3/2} n/\sqrt S). We then show the following lower bound on the time-space tradeoff for sorting $n$ numbers from a polynomial size range in a general sorting algorithm (not necessarily based on comparisons): TS=\Omega(n^{3/2}). Hence for small values of S the upper bound is almost tight. Classically the time-space tradeoff for sorting is TS=\Theta(n^2).
{
"annotation_id": "ce1d4479-e74d-443b-a0d2-e55c03e83e6b",
"date_created": "2026-03-02T18:01:56.558000Z",
"date_modified": "2026-03-02T18:01:56.558000Z",
"file_hash": "01ed2bbf5e09670f9670ecc079753563250d4b5a81fe6d606c90d693af3ca7b6",
"private": false,
"record": {
"abstract": "We investigate the complexity of sorting in the model of sequential quantum\ncircuits. While it is known that in general a quantum algorithm based on\ncomparisons alone cannot outperform classical sorting algorithms by more than a\nconstant factor in time complexity, this is wrong in a space bounded setting.\nWe observe that for all storage bounds n/\\log n\\ge S\\ge \\log^3 n, one can\ndevise a quantum algorithm that sorts n numbers (using comparisons only) in\ntime T=O(n^{3/2}\\log^{3/2} n/\\sqrt S). We then show the following lower bound\non the time-space tradeoff for sorting $n$ numbers from a polynomial size range\nin a general sorting algorithm (not necessarily based on comparisons):\nTS=\\Omega(n^{3/2}). Hence for small values of S the upper bound is almost\ntight. Classically the time-space tradeoff for sorting is TS=\\Theta(n^2).",
"arxiv_id": "quant-ph/0211174",
"authors": [
"Hartmut Klauck"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "Quantum Time-Space Tradeoffs for Sorting",
"url": "https://arxiv.org/abs/quant-ph/0211174"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "f0454508-1abd-4974-bc01-b787b812a4b1",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}