  Challenging combinatorial optimization problems are ubiquitous in science and
engineering. Several quantum methods for optimization have recently been
developed, in different settings including both exact and approximate solvers.
Addressing this field of research, this manuscript has three distinct purposes.
First, we present an intuitive method for synthesizing and analyzing discrete
(i.e., integer-based) optimization problems, wherein the problem and
corresponding algorithmic primitives are expressed using a discrete quantum
intermediate representation (DQIR) that is encoding-independent. This compact
representation often allows for more efficient problem compilation, automated
analyses of different encoding choices, easier interpretability, more complex
runtime procedures, and richer programmability, as compared to previous
approaches, which we demonstrate with a number of examples. Second, we perform
numerical studies comparing several qubit encodings; the results exhibit a
number of preliminary trends that help guide the choice of encoding for a
particular set of hardware and a particular problem and algorithm. Our study
includes problems related to graph coloring, the traveling salesperson problem,
factory/machine scheduling, financial portfolio rebalancing, and integer linear
programming. Third, we design low-depth graph-derived partial mixers (GDPMs) up
to 16-level quantum variables, demonstrating that compact (binary) encodings
are more amenable to QAOA than previously understood. We expect this toolkit of
programming abstractions and low-level building blocks to aid in designing
quantum algorithms for discrete combinatorial problems.
