Quantum Time-Space Tradeoffs for Exponential Dynamic Programming
Susanna Caroppo, Jevgēnijs Vihrovs, Dārta Zajakina, Aleksejs Zajakins · 2026
Read Quantum Time-Space Tradeoffs for Exponential Dynamic Programming by Susanna Caroppo, Jevgēnijs Vihrovs, Dārta Zajakina, Aleksejs Zajakins (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-02233.txt.
Description
Caroppo and colleagues trade quantum memory for time in dynamic programming. The earlier quantum algorithms speed up NP hard problems but demand large quantum random access memory, hard to build. By mixing classical methods with quantum techniques, the authors derive new time space tradeoffs that keep a speedup over classical methods while cutting memory needs. The traveling salesperson problem, for instance, gains a quantum solution with far less QRAM than before.
Catalog record
| CREATOR | Susanna Caroppo, Jevgēnijs Vihrovs, Dārta Zajakina, Aleksejs Zajakins |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61644 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.02233