Quantum Time-Space Tradeoffs for Exponential Dynamic Programming

Susanna Caroppo, Jevgēnijs Vihrovs, Jevgēnijs Vihrovs +3

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 problem…