dorsal/arxiv
View SchemaExponential Separation of Quantum and Classical Online Space Complexity
| Authors | Francois Le Gall |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0606066 |
| URL | https://arxiv.org/abs/quant-ph/0606066 |
| DOI | 10.1007/s00224-007-9097-3 |
| Journal | Theory of Computing Systems 45(2): 188-202 (2009) |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
Although quantum algorithms realizing an exponential time speed-up over the best known classical algorithms exist, no quantum algorithm is known performing computation using less space resources than classical algorithms. In this paper, we study, for the first time explicitly, space-bounded quantum algorithms for computational problems where the input is given not as a whole, but bit by bit. We show that there exist such problems that a quantum computer can solve using exponentially less work space than a classical computer. More precisely, we introduce a very natural and simple model of a space-bounded quantum online machine and prove an exponential separation of classical and quantum online space complexity, in the bounded-error setting and for a total language. The language we consider is inspired by a communication problem (the set intersection function) that Buhrman, Cleve and Wigderson used to show an almost quadratic separation of quantum and classical bounded-error communication complexity. We prove that, in the framework of online space complexity, the separation becomes exponential.
{
"annotation_id": "b588eb67-cc68-4486-ad7c-ddd372dddb5d",
"date_created": "2026-03-02T18:02:27.116000Z",
"date_modified": "2026-03-02T18:02:27.116000Z",
"file_hash": "910b0fdbb7bfa9b6b6854a61931532a2271f6127eaee73f44499d44eef2a264e",
"private": false,
"record": {
"abstract": "Although quantum algorithms realizing an exponential time speed-up over the\nbest known classical algorithms exist, no quantum algorithm is known performing\ncomputation using less space resources than classical algorithms. In this\npaper, we study, for the first time explicitly, space-bounded quantum\nalgorithms for computational problems where the input is given not as a whole,\nbut bit by bit. We show that there exist such problems that a quantum computer\ncan solve using exponentially less work space than a classical computer. More\nprecisely, we introduce a very natural and simple model of a space-bounded\nquantum online machine and prove an exponential separation of classical and\nquantum online space complexity, in the bounded-error setting and for a total\nlanguage. The language we consider is inspired by a communication problem (the\nset intersection function) that Buhrman, Cleve and Wigderson used to show an\nalmost quadratic separation of quantum and classical bounded-error\ncommunication complexity. We prove that, in the framework of online space\ncomplexity, the separation becomes exponential.",
"arxiv_id": "quant-ph/0606066",
"authors": [
"Francois Le Gall"
],
"categories": [
"quant-ph",
"cs.CC"
],
"doi": "10.1007/s00224-007-9097-3",
"journal_ref": "Theory of Computing Systems 45(2): 188-202 (2009)",
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "Exponential Separation of Quantum and Classical Online Space Complexity",
"url": "https://arxiv.org/abs/quant-ph/0606066"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "a97bf6a0-99bf-4f96-a590-f49e44259475",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}