12/10/2026 - Camille GRANGE (LIPN , Sorbonne Paris Nord)

Abstract

Quantum computation is a new paradigm that is increasingly being exploited today for designing methods to solve optimization problems. Although its application to numerical instances is limited, among other reasons due to the lack of quantum RAM, theoretical advantages are emerging compared to classical approaches for several classes of problems. In this talk, we propose a bounded-error quantum-classical algorithm that tackles a large class of NP-hard single-machine scheduling problems, which satisfy a specific dynamic programming property (Dynamic Programming Across the Subsets). Our algorithm, based on the seminal idea of Ambainis et al. (2019), combines classical dynamic programming and quantum search of the minimum in a table (generalization of Grover Search). It reduces the worst-case time complexity, sometimes at the cost of an additional pseudo-polynomial factor.