Tobias Osborne (University of Hannover) - Assessing quantum advantage for integer linear programs

Title: Assessing quantum advantage for integer linear programs
Abstract:
There has been a lot of optimism that quantum computers could deliver better/faster/cheaper/greener solutions for combinatorial optimization problems. Concrete evidence for this hope is ... challenging to collect as general polytime quantum algorithms for their solution are extremely unlikely, and we don't yet have a true fault-tolerant quantum computer to test out ideas on. We focus on integer linear programs as a representative class of such problems and argue that progress can nevertheless be made by employing hybrid benchmarking - a framework pioneered at QuSoft - to assess runtimes beyond asymptotic analysis. In particular, we identify classes of problems which are very unlikely to ever enjoy quantum speedup. However, also identify instances where runtime analysis suggests that quantum computers may provide competitive results, as compared to best-in-class classical branch and bound solvers such as Gurobi and cplex and dynamic programming.
Date of talk: 2024-06-14