Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.23763 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913006536884224 |
|---|---|
| author | Hao, Zihan Huang, Zikuan Liu, Qipeng |
| author_facet | Hao, Zihan Huang, Zikuan Liu, Qipeng |
| contents | In this work, we establish the first separation between computation with bounded and unbounded space, for problems with short outputs (i.e., working memory can be exponentially larger than output size), both in the classical and the quantum setting. Towards that, we introduce a problem called nested collision finding, and show that optimal query complexity can not be achieved without exponential memory. Our result is based on a novel ``two-oracle recording'' technique, where one oracle ``records'' the computation's long outputs under the other oracle, effectively reducing the time-space trade-off for short-output problems to that of long-output problems. We believe this technique will be of independent interest for establishing time-space tradeoffs in other short-output settings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_23763 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Need for (Quantum) Memory with Short Outputs Hao, Zihan Huang, Zikuan Liu, Qipeng Computational Complexity In this work, we establish the first separation between computation with bounded and unbounded space, for problems with short outputs (i.e., working memory can be exponentially larger than output size), both in the classical and the quantum setting. Towards that, we introduce a problem called nested collision finding, and show that optimal query complexity can not be achieved without exponential memory. Our result is based on a novel ``two-oracle recording'' technique, where one oracle ``records'' the computation's long outputs under the other oracle, effectively reducing the time-space trade-off for short-output problems to that of long-output problems. We believe this technique will be of independent interest for establishing time-space tradeoffs in other short-output settings. |
| title | On the Need for (Quantum) Memory with Short Outputs |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2602.23763 |