Design toolkit for quantum discrete optimization*

We present a new representation for quantum algorithms that facilitates compilation, analysis, and solving of discrete optimization problems. Our methods and representations allow for automated design and compilation of subroutines relevant to a variety of quantum approaches including QAOA, quantum annealing, and quantum imaginary time evolution, in particular 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 study resource counts for subroutines involving cost functions and constraint-preserving mixers, drawing practical conclusions regarding which encodings are most efficient for which problem classes in different parameter regimes.