Quantum Time-Space Tradeoffs for Exponential Dynamic Programming

Abstract

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 classical approaches with quantum techniques. For instance, we show that the Travelling Salesman Problem can be solved quantumly in $\tilde{O}(1.859^n)$ time and $\tilde{O}(1.315^n)$ QRAM space.

Updated with the project reference