Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.02233 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917380825808896 |
|---|---|
| author | Caroppo, Susanna Vihrovs, Jevgēnijs Zajakina, Dārta Zajakins, Aleksejs |
| author_facet | Caroppo, Susanna Vihrovs, Jevgēnijs Zajakina, Dārta Zajakins, Aleksejs |
| contents | 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, which we obtain by adjusting the parameters of these algorithms and combining them with "quantized" classical strategies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_02233 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Quantum Time-Space Tradeoffs for Exponential Dynamic Programming Caroppo, Susanna Vihrovs, Jevgēnijs Zajakina, Dārta Zajakins, Aleksejs Quantum Physics 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, which we obtain by adjusting the parameters of these algorithms and combining them with "quantized" classical strategies. |
| title | Quantum Time-Space Tradeoffs for Exponential Dynamic Programming |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2604.02233 |