(58m) Quantum Algorithms for Optimization over Discrete Variables

Combinatorial optimization problems are found in many areas of science and engineering–in this talk we discuss the use of quantum computers to solve such problems. We begin by introducing a novel intermediate representation for quantum algorithms that streamlines the process of compiling, analyzing, and solving discrete optimization problems on quantum computers. Our approach leverages automated design and compilation of subroutines that are relevant to a variety of quantum approaches including QAOA, quantum annealing, and quantum imaginary time evolution, particularly for problems with integer domains. Using our framework, we compare several distinct qubit encodings in five problem areas: routing, scheduling, graph coloring, portfolio rebalancing, and integer linear programming. We examine resource requirements for various quantum subroutines, drawing practical conclusions regarding which quantum data types are most efficient for which problem classes in different parameter regimes.