Tutte Colloquium - Stephen Jordan

Title: Quantum information science for combinatorial optimization

Abstract:

Due to input-output bottlenecks, quantum computers are expected to be most applicable to problems for which the quantity of data specifying the instance is small but the computational cost of finding a solution is large. Aside from cryptanalysis and quantum simulation, combinatorial optimization provides some of the best candidates for problems of real-world impact fitting these criteria. Many of these problems are NP-hard and thus unlikely to be solvable on quantum computers with polynomial worst-case time complexity. Nevertheless, quantum heuristics for optimization have been a vibrant area of research. In this talk I will survey quantum algorithms for optimization as well as classical stochastic optimization heuristics that have arisen as a spinoff technology from quantum computing research. These classical algorithms are now finding real-world application under the name of quantum-inspired optimization (QIO) in diverse areas ranging from trucking to medical imaging.