Paper 2026/403
On the Need for (Quantum) Memory with Short Outputs
, University of California, San Diego, University of Cambridge, University of California, San DiegoAbstract
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.
Note: Updates 1, Add a example for our Fourier Tail-Bound Composition Conjecture, showing that the bound 4\eps (as many may expect) is false. 2, Add a related work ECCC 2026-171 which uses our result and solves one of the open question in the previous revision. 3, Correct some typos.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Minor revision. 58th Annual ACM Symposium on Theory of Computing (STOC2026)
- DOI
- 10.1145/3798129.3800896
- Keywords
- random oraclecollision-resistancespace-time tradeoff
- Contact author(s)
-
z1hao @ ucsd edu
zh446 @ cam ac uk
qipengliu0 @ gmail com - History
- 2026-09-26: last of 3 revisions
- 2026-02-27: received
- See all versions
- Short URL
- https://ia.cr/2026/403
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/403,
author = {Zihan Hao and Zikuan Huang and Qipeng Liu},
title = {On the Need for (Quantum) Memory with Short Outputs},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/403},
year = {2026},
doi = {10.1145/3798129.3800896},
url = {https://eprint.iacr.org/2026/403}
}
