Speaker
Dr
Pooya Ronagh
(1QBit, IQC, UW)
Description
We introduce quantum algorithms for solving finite-horizon and infinite-horizon dynamic programming problems. We visit the query complexity lower bounds for classical randomized algorithms for the same tasks and consequently demonstrate a polynomial separation between the query complexity of our quantum algorithms and best-case query complexity of classical randomized algorithms. Up to polylogarithmic factors, our quantum algorithms provide quadratic advantage in terms of the numbers of states and actions in the dynamic programming problem. Nevertheless, the speed-up achieved is at the expense of appearance of other polynomial factors in the scaling of the algorithm which contribute to the precision of the solution. Our framework pertains to discrete and combinatorial optimization problems solved classically using dynamic programming techniques. As an example, we show how quantum computers can solve the travelling salesperson problem quadratically faster than the Bellman–Held–Karp algorithm does.
Primary author
Dr
Pooya Ronagh
(1QBit, IQC, UW)
