{"id":"arxiv/2604.02233","url":"https://arxiv.org/abs/2604.02233","tags":["quant-ph"],"score":0,"title":"Quantum Time-Space Tradeoffs for Exponential Dynamic Programming","domain":"quant-ph","source":"arxiv","authors":["Susanna Caroppo","Jevgēnijs Vihrovs","Dārta Zajakina","Aleksejs Zajakins"],"reviews":0,"subject":"quant-ph","summary":"We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While giving provable complexity speedups and applicable to a variety of NP-hard problems, these algorithms have a notable drawback: they require a large amount of Quantum Random Access Memory (QRAM), which potentially could be very challenging to implement in a physical quantum computer. In this work, we study how we can improve the space complexity by trading it for time, while still retaining a speedup over the classical algorithms. We show novel quantum time-space tradeoffs by combining different…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-04-02","reactions":{}}