7
collaborators
2026–2026
years active
Contributions
QIP QCrypt TQC talk poster presenter award · △program ◇steering ○organizing · filled = chair
3 Posters
| Title | Conference | Co-authors |
|---|---|---|
| Quantum Speedups for Polynomial-Time Dynamic Programming | QIP 2026 | Giordano Da Lozzo, Giuseppe Di Battista, Michael T. Goodrich, Martin Nöllenburg |
| Quantum Time-Space Tradeoffs for Exponential Dynamic Programming | QIP 2026 | Jevgēnijs Vihrovs, Dārta Zajakina, Aleksejs Zajakins |
| Quantum Time-Space Tradeoffs for Exponential Dynamic Programming | TQC 2026 | Jevgēnijs Vihrovs, Dārta Zajakina, Aleksejs Zajakins |
We investigate the quantum algorithms for dynamic programming by Ambainis et al. (SODA'19). While they give provable complexity speedups and they can be apply 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. |
||
Collaborators
| Co-author | Joint talks |
|---|---|
| Aleksejs Zajakins | 2 |
| Dārta Zajakina | 2 |
| Jevgēnijs Vihrovs | 2 |
| Giordano Da Lozzo | 1 |
| Giuseppe Di Battista | 1 |
| Martin Nöllenburg | 1 |
| Michael T. Goodrich | 1 |