a domain that can be defined as a permutation of integers, though its cost
function is substantially different from TSP.

Here we consider a simple single machine scheduling (SMS) problem. We are
given a set of $M$ jobs with three properties: processing times $\\{p_{k}\\}$,
deadlines $\\{d_{k}\\}$, and weights $\\{w_{k}\\}$. For job $k$, the start
time is $s_{k}$. Our goal is to determine start times that minimize total
weighted lateness $\sum_{k}w_{k}T_{k}$, where the lateness of each job is
$T_{k}=(s_{k}+p_{k}-d_{k})$. Note that one may also express the scheduling
configurations as a list of start times (instead of a permutation of job IDs)
[7], or otherwise, though we do not consider such representations here.
Importantly, a number of more sophisticated but closely related scheduling
problem variants are studied in the literature, including ones with additional
hard problem constraints and multiple machines [119].

We choose to use lateness [120, 119, 121, 122] in our problem definition here
in order to consider as simple a cost function as possible. However, many
other cost functions may be of interest in real-world scheduling problems, for
instance tardiness or earliness, defined respectively as
$\max\\{0,s_{k}+p_{k}-d_{k}\\}$ and $\max\\{0,d_{k}-s_{k}-p_{k}\\}$ [119].
Note that because lateness is simply tardiness minus earliness, it may be
viewed a special case of the latter quantities. Though we do not explicitly
consider tardiness and earliness in this work, we note here that the quantum
phase operator may be extended to the $\max\\{0,f(x)\\}$ operation using
ancilla qubits. First one would compute $f(x)$ into the ancilla register using
subroutines of Section 2.2, which may include standard arithmetic operations,
before performing operators controlled on the ancilla register value being
positive to implement phase kickback, and finally uncomputing the first step
to disentangle the ancilla register. Alternatively, one may consider distinct
representations of the problem domain [7].

For SMS problem it is useful to introduce value primitives for the processing
times

$\mathcal{A}_{\alpha}^{proc}=\sum_{k=0}^{M-1}p_{k}\mathcal{P}^{(k)}_{\alpha}$
(65)

and the deadlines

$\mathcal{A}_{\alpha}^{dead}=\sum_{k=0}^{M-1}d_{k}\mathcal{P}^{(k)}_{\alpha}.$
(66)

In DQIR, a precursor for the start time operator can be written as an
expression of value primitives and an indicator primitive,

$s_{k,\alpha}=\mathcal{P}^{(k)}_{\alpha}\sum_{\beta<\alpha}\mathcal{A}_{\beta}^{proc}$
(67)

where this operator’s support on a classical state is non-zero only when the
$k$th job is in the $\alpha$th position. This is a prototypical example of a
value primitive being useful in mapping classical problems to the quantum
representation of DQIR.

A full start time operator for job $k$ may be expressed as

$s_{k}=\sum_{\alpha}^{M}s_{k,\alpha}=\sum_{\alpha}^{M}\mathcal{P}^{(k)}_{\alpha}\sum_{\beta<\alpha}\mathcal{A}_{\beta}^{proc}$
(68)

Combining the above formulas, one way to compactly describe the cost function
of total weighted tardiness is

$\begin{split}H_{C}&=\sum_{k}s_{k}+\sum_{\alpha}^{M}\left(\mathcal{A}_{\alpha}^{proc}-\mathcal{A}_{\alpha}^{dead}\right)\\\
&=\sum_{k}\left(\sum_{\alpha}^{M}\mathcal{P}^{(k)}_{\alpha}\sum_{\beta<\alpha}\mathcal{A}_{\beta}^{proc}\right)\\\
&+\sum_{\alpha}^{M}\left(\mathcal{A}_{\alpha}^{proc}-\mathcal{A}_{\alpha}^{dead}\right).\end{split}$
(69)

We highlight again the compactness of this expression, that it is encoding-
independent, and that it written entirely in terms of the primitives of DQIR.
Because SMS is a permutation problem, mixers, penalties, and/or initial states
need to be introduced as appropriate, analogously to the case of TSP.

Note that when Gray or SB is used, $\sum_{k}\mathcal{P}^{(k)}_{\alpha}$ in
equation (69) is equal to the identity in qubit space if
$\lceil\log_{2}{d}\rceil=\log_{2}{d}$. Hence when a compact code is $d$ is a
power of 2, this will lead to very favorable cancellations only in these
compact encodings, as we will see in the numerical results.

###  5.4 Financial portfolio rebalancing

In computational finance, the task of portfolio rebalancing is an optimization
problem. Here we use a simple model previously proposed in the context of QAOA
[47]. For a set of financial stocks separated into “lots” of discrete
quantities, and given the previous portfolio position and a set of parameters,
the goal is to determine whether to have a long, short, or no-hold position
for each lot. The relevant parameters are the solution vector
$\mathbf{z}\in\\{-1,0,+1\\}^{M}$, the normalized risk-return function
$C_{RR}(\mathbf{z})$, the normalized trading cost function
$C_{RC}(\mathbf{z})$, the number of lots $M$, the number of lots one may
invest in $D$, a risk parameter $0\leq\lambda\leq 1$, the normalized asset
returns covariance matrix $\sigma$, the normalized average asset returns
vector $\mu$, the previous portfolio position
$\mathbf{y}\in\\{-1,0,+1\\}^{M}$, and the normalized cost $T$ of trading.

The optimization function is

$H_{C}=C_{RR}(\vec{z})+C_{TC}(\vec{z})$ (70)

where

$C_{RR}(\textbf{z})=\lambda\sum_{\alpha}^{M}\sum_{\beta}^{M}\sigma_{\alpha\beta}z_{\alpha}z_{\beta}-(1-\lambda)\sum_{\alpha}^{M}\mu_{\alpha}z_{\alpha}$
(71)

and

$C_{TC}(\textbf{z})=\sum_{\alpha}(1-\delta(z_{\alpha}-y_{\alpha}))T,$ (72)

where $\delta()$ is the Dirac delta function. We now write down DQIR
expressions for the classical $C_{RR}$ and $C_{TC}$. An arbitrary choice for
labeling the three possible states is to use {long, no-hold, short}
$\mapsto\\{|0\rangle,|1\rangle,|2\rangle\\}$, which can be expressed via the
value primitive

$\begin{split}\mathcal{A}_{\alpha}^{z}&=\sum_{i}z_{i}|i\rangle\langle
i|_{\alpha}\\\ &=(-1)|0\rangle\langle 0|+(0)|1\rangle\langle
1|+(+1)|2\rangle\langle 2|\\\ &=|2\rangle\langle 2|-|0\rangle\langle
0|\end{split}$ (73)

In DQIR the neat expressions are

$C_{RR}=\lambda\sum_{\alpha}\sum_{\beta}\sigma_{\alpha\beta}\mathcal{A}_{\alpha}\mathcal{A}_{\beta}-(1-\lambda)\sum_{\alpha}\mu_{\alpha}\mathcal{A}_{\alpha}$
(74)

and

$\begin{split}C_{TC}=\sum_{\alpha}^{M}\left(1-\mathcal{P}^{(y)}_{\alpha}\right)T\end{split}$
(75)

where we note that any delta function between a constant and a variable may be
replaced by $\delta(j_{0}-z)_{\alpha}\mapsto\mathcal{P}^{(j_{0})}_{\alpha}$.
Finally, we have the constraint

$\sum_{\alpha}z_{\alpha}=D$ (76)

which may be treated as a hard constraint by choosing appropriate initial
state and mixers, or as a soft constraint by introducing a $F_{sum}$ penalty
(equation (44)).

###  5.5 Integer programming

Because many industrially relevant problems tend to be cast as integer
programming and related problems [123, 124], here we outline the canonical
form of ILP and briefly summarize its implementation in DQIR. Given a
rectangular matrix $A$ and constant vectors $\mathbf{b}$ and $\mathbf{c}$, the
problem is to maximize $\mathbf{c}\cdot\mathbf{x}$ under the two constraints

$A\mathbf{x}\leq\mathbf{b}$ (77)

and $\mathbf{x}\geq\mathbf{0}$. The cost function for canonical ILP is simply
represented as

$H_{C}=\sum_{\alpha}c_{\alpha}\mathcal{A}_{\alpha}^{\rm{ILP}}$ (78)

where the value primitive is the previously defined number operator
$\mathcal{N}=\sum_{k}^{d}k\mathcal{P}^{(k)}$. Considering that this cost
function is “one-local” in DQIR space, most of the algorithmic complexity
appears via the problem’s constraints, e.g. via introduction of constructs
such as $F_{\text{lin}}$ in equation (45).

We note that it may be computationally hard in general to even produce an
initial state that contains the full feasibly subspace while excluding the
infeasible subspace. Therefore, it appears likely that penalties (Section 3.2)
will be necessary in NISQ implementations of ILP that use the approach of this
subsection, else other approaches may be applicable only in limited cases.
While we do not expect quantum computers to efficiently solve NP-hard problems
such as ILP it may prove worthwhile to explore problem variants or restricted
settings where quantum approaches may become viable.

##  6 Numerical Study of Encoding Choice

The purpose of this section is to perform a preliminary but extensive
numerical investigation of the differences in behavior between the different
encodings in terms of quantum resources (specifically circuit depths), with a
focus on the subroutines in Sections 3 and 4, and applied instances of
problems considered in Section 5. The observations and results of this section
may help guide practitioners in deciding which encoding to use when designing
suitable algorithm implementations for particular quantum devices. We
emphasize that, as illustrated in Figure 1, different encodings require
significantly different quantities of qubits—hence the shortest-depth encoding
may not always be the encoding of choice for a given set of hardware. Note
that we assume all-to-all connectivity in the results presented here.

With the exception of the strict GDPM mixers, this preliminary resource
analysis involves compiling the matrix exponential $\exp(-i\beta H)$ for a
Hermitian operator $H$ and real constant $\beta$. The general connection to
quantum algorithms is that the standard formulations of AQO and QAOA are
directly implemented in terms of such operator exponentials; hence these
numerical results may aid in making preliminary encodings choices when
implementing AQO or QAOA. For QAOA, as discussed a variety of different mixers
are possible with different resource tradeoffs beyond those we consider here.
The connections to QITE and non-QAOA ansatzes are less obvious and thus our
results are less applicable to those two classes of algorithm.

The operators for which we calculate circuit depths should be placed into
three distinct categories: (a) exact exponentials of diagonal functions, (b)
approximate mixers as implemented in equation 52, and (c) strict mixers. The
former two operator categories use the same compilation procedure, which is
described in Section 6.1: after a Hermitian operator is converted to the Pauli
representation generated by a given encoding, each Pauli term is exponentiated
as the simple first-order product formula of equation 52 with an ordering
choice described below. This product formula leads to exact exponentials only
in category (a) because all the terms are diagonal and thus commute. On the
other hand, the calculated depths for the strict mixers of category (c) are
determined as described in Section 4.4. Results in Sections 6.2 and 6.3 belong
to category (a), while those in Section 6.4 belong to categories (b) and (c).
We consider DQIR variable sizes $2<d\leq 16$, from which some preliminary
trends emerge. We plot the resulting circuit depths for the different
encodings and discuss the observed relative advantages.

We note that there are many Hamiltonian simulation algorithms for implementing
the exponential of a Hermitian operator, each with various resource and
accuracy trade-offs [125, 126, 127, 128, 129, 130, 131, 132, 133]. In this
work, in an attempt to provide some preliminary guidance specifically for
nearer-term quantum optimization, we chose a recently proposed Hamiltonian
simulation technique [134] that is designed to produce short-depth circuits
for early generations of quantum hardware. The trends observed in our
numerical results may differ when using other Hamiltonian simulation
algorithms, including methods that require advanced fault-tolerant quantum
hardware.

###  6.1 Compiling product formulas from DQIR

We implemented a prototype of DQIR in Python, which we used to produce our
numerical results. The code is built on three object classes: one to represent
a discrete variable, one for defining the multivariate space, and one for
describing and manipulating an arbitrary operator as a sum of products of
local primitives. The latter class is based on the use of a Python dictionary,
where keys are operator strings and values are coefficients which may be
numeric or symbolic. High-level functions return a DQIR object for each
combinatorial problem type and auxiliary operators such as mixer generators.
Algebra routines are built into the classes, allowing for multiplication and
addition of any operators as well as replacing symbolic coefficients with
numerical values. We use subroutines from mat2qubit [135], Scipy [136],
OpenFermion [137], and SymPy [138]. The examples included in the mat2qubit
package give explicit code for producing these Hamiltonians, and we also
include the qubit-encoded Hamiltonians and raw quantum circuits in the
Supplemental Materials. Terms are cancelled and combined inside DQIR, which
reduces the amount of computational algebra that need be performed in the
final Pauli representation; this is especially important when one’s goal is to
compare many encodings. We implemented functionality for returning a complex
operator’s full matrix representation, allowing for the study of matrix
properties.

For qubits, converting to the Pauli representation is automated with the help
of the Intel Quantum SDK [139]. After each discrete variable is assigned an
encoding, the DQIR-to-qubit encoding procedure of Section 2.4 is used. This
yields a weighted sum of terms $\sum_{v}G_{M,v}$ as in equation (51), where
each $G_{M,v}$ is a Pauli string with a real coefficient. Our task is to
compile a circuit that performs either an exact (for cost functions) or
approximate (for mixers) simulation of the exponential $\exp({\sum_{v}-i\beta
G_{M,v}})$. The circuit depths that we report are for the simple product
formula $\prod_{v}e^{-i\beta G_{M,v}}$ for arbitrary real $\beta$, where the
ordering of terms is determined using an algorithm that attempts to minimize
circuit depth (discussed below). For all diagonal operators (cost functions,
penalties, and diagonal primitives), this procedure provides exact
exponentials, because all $G_{M,v}$ commute with each other. For non-diagonal
mixer Hamiltonians this procedure leads to an approximate mixer that may
produce leakage as described in Section 3.3.1. We do not necessarily recommend
the use of these instances of approximate mixer, but perform this analysis in
order to have a point of comparison against our novel GDPMs). The circuit
depths we present are independent of the scalar $\beta$ in the exponential.
Note that circuit depths for the strict mixers are based on Section 4.4, not
based on the compilation procedure of this section.

From the Pauli representation we produce first-order product formulas using an
algorithm [134]based on Pauli Frame Graphs (PFG). In this approach, one does
not “uncompute” the change of basis for each Pauli term, but instead moves
directly to another Pauli frame in order to exponentiate the next term.
Optimizing the circuit depth can then be recast in terms of a graph search
problem. This PFG-based approach has been shown to produce significantly
shorter circuits for a variety of physics and chemistry Hamiltonian classes,
as compared to more standard circuit construction methods.

It is worth noting that the use of a gate set that natively performs the
continuous two-gate operation $\exp(-i\theta ZZ)$ [140] may lead to shorter
depths as well as circuit times that are more directly dependent on the
magnitude of the coefficients. However, in our view such a gate set is
unlikely to be the one that is used in most commercialized quantum hardware
[141, 142]. While some platforms are capable of arbitrary-angle multi-qubit
entangling gates, and such operations can vary in time of operation,
“continuous” control is antagonistic to arbitrary operation time due to the
difficulties of system-wide clock synchronization. Thus, in practice,
operations ought to be fixed to integer multiples of the system clock, where
idle time is typically inserted to make up the difference. Thus at best, small
angles will still likely be limited to the time of a single clock cycle.

When reporting results below, our calculated circuit depths result from the
PFG decompositions, where our code uses a gate set of arbitrary one-qubit
rotations and the 9 entangling gates defined in reference [134], which
includes the CNOT gate. (Converting these entangling gates to CNOT can be done
using only one-qubit gates; because such one-qubit gates may be fused with
existing adjacent one-qubit gates, the reported circuit depths are similar to
using the gate set of CNOT and arbitrary one-qubit rotations.) Single-variable
strict mixers were designed by Algorithm 1, and the resulting unitaries were
decomposed based either on the PFG algorithm or on the circuit decompositions
summarized in Section 4.4, whichever yielded shorter depth.

###  6.2 Primitives and penalties

Figure 9: Circuit depths for exponentiating various diagonal primitives and
penalties with varying $d$. As all terms commute in the diagonal cost
functions, these depths correspond to exact exponentials.

Here we present numerical results for diagonal operators that are used as
building blocks in the construction of cost functions, i.e. we study
primitives from Section 2.2 and penalties from Section 3.2. Figure 9 shows
circuit depth plotted against variable size, for diagonal operator building
blocks $EQ$, $\mathcal{A}_{n}$, $\mathcal{A}_{n}^{2}$, $F_{perm}$, $F_{sum}$,
and $F_{SS}$ of Section 2. We remind the reader that unary requires $d$
qubits, compact codes require $\lceil\log_{2}d\rceil$ qubits, and block unary
interpolates between them (see Figure 1). Thus the shortest-depth circuit is
not necessarily the most appropriate choice if a given quantum device is
space-limited. Results here assume all-to-all connectivity; circuit depths
will be different when considering a different hardware topology [18], an
important aspect beyond the scope of this work.

For most diagonal operators considered here, unary provides the shortest-depth
circuits. However, there are many important exceptions apparent for
$\mathcal{A}_{n}$ and $F_{\text{sum}}$ These exceptions are notable for the
following reason. When the circuit depths for the compact codes are equal to
or less than the depths for unary, this means a compact code is likely to be
superior on most hardware, as it would require both shorter depth and fewer
qubits. However, the circuit depth of the full quantum algorithm (not just one
of its subroutines) must be analyzed to determine whether this is the case—we
do not perform such an analysis of full quantum algorithms in this work, but
we note that in the context of Hamiltonian simulation there are some problem
instances for which compact codes out-performed unary in terms of both depth
and space [12].

Because of favorable term cancellation in qubit space, compact codes tend to
be most useful when $d$ is a power of 2, as discussed in previous work [12].
This trend is exhibited in the examples of Figure 9, where compact codes are
more likely to be competitive with other encodings when $\log_{2}d$ is an
integer.

Though the Gray and SB encodings often yield the same circuit depth, in some
cases they have different depths, for example in $\mathcal{N}$ and
$F_{\text{sum}}$. This highlights the fact that in some instances it may be
worth considering multiple compact encodings. A practitioner may choose to
explore more of the (exponentially many) compact encodings before choosing the
shortest-depth one.

The reason for BU’s intermediate depth is that the locality of the diagonal
operators is smaller than the compact code but larger than unary. For a given
quantum device, block unary is an optimal choice only when two necessary
conditions are met. First, the depth for BU must be less than that of the
compact codes. This is true for most $d$ values in the simple diagonal
functions considered here. Second, the hypothetical device must be qubit-
limited, such that there are not enough qubits available to use a unary code.
Because our results show that (often) BU is intermediate in both depth and in
qubit count as compared with the other encodings, there is a strong chance
that BU will be the optimal choice for some near-term hardware parameters
(those with moderate depth and moderate qubit counts).

The three types of penalties considered show similar behavior; namely, unary
is usually shortest-depth and it is common for BU to have shorter depth than
compact codes. Note that the single-variable validity penalty $F_{\text{SS}}$
is the null operator in the following cases: in compact codes when $d$ is a
power of 2, in block unary when $d$ is divisible by $g$, and always for the
unary encoding because we are assuming that validity-preserving operators are
used for unary algorithms. Both the permutation and summation penalties
involve a quadratic number of two-variable terms, which is the reason for
their larger circuit depths. Note that the depth of the permutation penalty is
strongly dependent on the number of discrete variables $M$ (e.g. number of
cities). This suggests that problems for which $M$ is not a power of 2 ought
to be reformulated—this could be accomplished in the TSP by adding cities with
very small distance to an existing city, and in scheduling this could be
accomplished by adding extra tasks with very small $p_{k}$.

Finally, we highlight one clear example where penalty exchanging (Section
3.3.4) would reduce overall circuit depth. When $d=7$ with compact codes, the
$EQ$ operator yields a depth of 70 while single-variable validity penalty
$F_{SS}$ yields depth 12. Hence one can reduce depth by implementing the $d=8$
version of $EQ$ (depth 15) while introducing a validity penalty for $d=7$,
which results in a net overall depth reduction. As mentioned, shorter depth
does not always lead to improved algorithms—any modification of a subroutine
ought to be tested for performance in a real algorithm.

###  6.3 Full cost functions

Figure 10: Circuit depths for implementing the exponential of four cost
Hamiltonians. As all terms commute in the cost functions, these depths
correspond to exact exponentials. The graph coloring Hamiltonians use complete
graphs with $d$ nodes. All portfolio rebalancing problem instances have $d=3$.

Here we consider circuit depths for implementing the exponential of a cost
function, a subroutine that is necessary for executing AQO and QAOA
(summarized in Section 3.1). Figure 10 shows circuit depths for exponentiating
four classes of cost functions defined in Section 5: graph coloring,
scheduling, routing, and portfolio rebalancing. The problem parameters used
are defined in the text below. Though these problem instances should be
considered as toy models, the numerical results are useful for understanding
trends in $d$ and in encoding choice that may also be applicable to more
realistic real-world problems.

Our graph coloring problem instances use complete (i.e. fully connected)
graphs for which the number of nodes equals the number of colors $d$, i.e. $d$
scales linearly with the number of variables $M$. We use this class of graphs
as a worst-case example of scaling behavior. Resource requirements will be
substantially different for example when $d$ is constant and independent of
$M$. In real-world problems, the circuit depth would be heavily dependent on
both the class of graph (e.g. complete, regular, multipartite, etc.) and how
the number of colors $d$ scales with $M$. Graph coloring is “two-local” in the
sense that all terms are products of at most two DQIR variables, and in the
case of complete graphs the number of terms scales quadratically. The results,
which follow the trends of the $EQ$ operator, show that while unary and BU
encodings follow clean monotoic trends, in compact codes the depth shows a
much less consistent trend. For example, for SB and Gray there is a large drop
in depth from $d=7$ to $d=8$. Expanding the domain and using penalty
exchanging may be appropriate in such cases.

Machine scheduling (or factory scheduling) is one of two problems we present
where the solution must be a permutation of integers. The substantial depths
observed here result from the quadratic number of two-variable terms in the
cost Hamiltonian. At $d=4,8,16$, the depths for compact (SB and Gray)
encodings are over an order of magnitude lower than the unary depths. This is
because, when $d$ is a power of 2 and a compact encoding is used, the
$\sum_{k}\mathcal{P}^{(k)}_{\alpha}$ term of equation (69) in qubit space is
equal to the identity, which leads to massive simplifications and term
cancellations in the Hamiltonian. We hasten to note that this does not
necessarily imply that the compact codes are superior to unary for machine
scheduling. An algorithm implementation requires not just the cost function
but also either a $F_{perm}$ penalty or PPMs, the versions of which have
presented are much higher depth for compact than for unary (see Figures 8 and
9).

However, we have not extensively explored the design of PPMs in this work. We
are hopeful that a future design of PPMs that operate on fewer qubits (see the
hypothetical case on the left of Figure 7) may lead to PPMs that are much
shorter-depth when decomposed. Though their existence is only speculated, if
such shorter-depth PPMs are possible, it may result in the compact code being
both the lowest-space and lowest-depth choice in QAOA for machine scheduling.

TSP (routing) is also a permutation problem composed of two-variable terms and
all-to-all connectivity. As in the case of machine scheduling, higher-depth
penalties and/or mixers are unavoidable when solving the problem, because one
must stay in the permutation space. The numerical trend matches what was
expected, with circuit depths highest for compact and lowest for unary. This
is another case where the results appear to suggest that BU has a strong
chance of being viable, in cases where there are not enough qubits available
for the unary encoding.

In the financial portfolio rebalancing problem, $d=3$ regardless of the number
of variables. Therefore BU${}^{\rm{Gray}}_{g=3}$ gives identical results to
the Gray code, as they both use 2 qubits per variable. The circuit depths for
all encodings are very similar, which leads us to conclude that the more
space-efficient compact codes are preferred for this Hamiltonian class,
especially considering the short-depth $d=3$ compact mixers that we present.
Note that the Gray code is similar to the encoding used in the original study
of QAOA for portfolio rebalancing [47].

Notably, as observed in the last section, these full cost functions (excluding
portfolio rebalancing) show that that there is a potential role for block
unary—certainly more so than previous studies of physics Hamiltonians would
have suggested [12]. This is because when the depth of BU lies in between
compact and unary, there exists some set of hardware parameters for which
block unary is the optimal choice. As previously stated, BU is the optimal
choice when there are not enough qubits to use unary, but there are enough
qubits to implement BU or compact codes.

###  6.4 Mixers

Figure 11:  Left: Circuit depths for approximate single-variable mixers (which
cause some leakage) defined as the exponential of equation (53). Right: Strict
GDPM single-variable mixers designed using Algorithm 1, decomposed into one-
and two-qubit gates.

Figure 11 shows circuit depths for implementing approximate (i.e. leaky) shift
mixers (left) and strict (leakage-free) single-variable GDPMs (right) designed
by Algorithm 1. The approximate shift mixers are simply the first-order
product formula that implements decomposition of the exponential of equation
(53), with the term ordering and depths determined using the previously
mentioned PFG approach [134]. In the exact mixers, depths are determined by
whichever decompositions outlined in Section 4.4 produce the lowest depths.

In nearly all cases, the naive approach of approximating the exponential of a
mixer Hamiltonian yields larger depths than our designed exact mixers. This
means that the single-variable GDPM designs are superior both in terms of
depth and in terms of not producing leakage. This suggests that our
algorithmically designed single-variable mixers will find utility in real
algorithms, though we leave numerical analysis of these mixers’ performance in
a QAOA simulation to future work.

BU mixers were designed by using two-qubit mixers within each block, and
connecting each two-qubit block with doubly-controlled $A_{\phi}$ gates. The
latter four-qubit gates connect two blocks by mixing adjacent cross-block
integers. For example, states $|2\rangle\mapsto|0010\rangle$ and
$|3\rangle\mapsto|0100\rangle$ are mixed using such a four-qubit gate. The
depths for this four-qubit gate were calculated using the PFG method. The
resulting depths are largest for BU in all cases $d>3$, but the discrepancy is
not large enough to overwhelm the differences in cost function depths shown in
the previous two sections. These are not necessarily the optimal mixer designs
for BU.

In compact codes, the figure shows the mixer depth is equal to one when $d$ is
a power of 2 ($d=4,8,16$). This is because the simple mixer of equation (55)
is used. This short depth, along with the fact that circuits for cost function
exponentials also tend to be shorter depth at these same $d$ values (Figure
10), shows that SB and Gray may sometimes be more competitive with unary than
expected, while requiring far fewer qubits. Finally, we highlight that the
GDPM compact (Gray and SB) mixers are even shorter depth than unary mixers for
the majority of $d$ values.

##  7 Conclusions

In this work we have constructed and analyzed a large set of quantum
subroutines relevant to solving optimization problems defined on domains of
discrete (e.g. integer) variables. We introduced an intermediate
representation (DQIR) which facilitates the synthesis of a variety of
algorithm components into qubit-based hardware, though these procedures may be
used for qudit-based hardware as well. Previous work had analytically derived
operators for each encoding, whereas our method automates the implementation
of any arbitrary integer-to-bit mapping by building on previous techniques [7,
12].

The first advantage of our approach is that it provides a compact, flexible
and readily interpretable representation of discrete optimization problems;
one may fully define discrete problems and algorithmic components before
considering any hardware implementation. Second, one may automate the process
of “screening” any number of potential hardware mappings, comparing circuit
depths or other measures of resource efficiency for different encodings. In
addition, we have provided numerical and conceptual guidance for which
operator components are most useful for which algorithmic approaches to a
given problem class. We suggested several best practices regarding the
interplay between initial states, preservation of feasibility and validity,
and encoding choice.

Our numerical results yielded several rules of thumb regarding encoding
choice. First, though the unary (one-hot) encoding is often the lowest-depth
and highest-space choice, there are some subroutines for which the compact
codes (e.g. Gray and standard binary) are advantageous both in terms of qubit
counts and circuit depth. Second, the block unary code, because its depth
usually lies between the depths of compact and unary encodings, indeed often
sits on the space-depth Pareto front (Figure 1). This means that BU would in
fact be the optimal choice for combinatorial problems for some hypothetical
hardware parameters; this was somewhat surprising, as BU appears less likely
to be useful in physics simulation [12]. Third, the choice of bitstring for
labeling each discrete value in compact codes can affect circuit depths—this
is shown by the differences in depth sometimes observed between Gray and
standard binary. Fourth, compact codes are much shorter depth when the
variable domain $d$ is a power of 2. Finally, our numeric results highlighted
that penalty exchanging, in which the the variable domain size is modified in
exchange for introducing a penalty, may be an important strategy in algorithm
design.

Separately, we have introduced criteria and approaches for designing a new
class of QAOA mixers, which we call graph-derived partial mixers (GDPMs). Our
computationally designed single-variable GDPM mixers provide systematic low-
depth construction of exact mixers that preserve a desired feasible subspace.
The very short depths of GDPMs for compact codes, even when $d$ is not a power
of 2, lead us to be optimistic about the use of compact codes for quantum
optimization.

There are several important open directions for future study. While we have
implicitly assumed all-to-all connectivity throughout, the constructions of
this work may be further tailored to a given hardware topology. Similarly, the
generalization to quantum error correcting codes may be straightforward in
some cases. In either case, the specific details may affect which encoding is
preferable. In particular, the type of basic quantum gate which is considered
"expensive" may be quite different between the near-term and fault-tolerant
settings. Using DQIR, automated compilation of many encodings, and the low-
level quantum subroutines introduced in this work, some of these questions can
begin to be addressed systematically.

In terms of algorithms, performance is ultimately the most tantalizing
question, which has so far proven challenging to analyze. As improved quantum
hardware becomes available better, empirical evidence should help further
guide algorithm design and choice. For QAOA, many questions remain as to how
to select the best mixer for a given problem with fixed quantum resources. For
example, while alternative mixers requiring deeper circuits than the ones
considered in Sec. 4 may in some sense provide more efficient mixing, their
cost may limit the number of implementable QAOA layers; for comparable circuit
depths it is not clear which approach will ultimately result in better
performance.

## Acknowledgements

This research used the resources of the National Energy Research Scientific
Computing Center (NERSC), a U.S. Department of Energy Office of Science User
Facility located at Lawrence Berkeley National Laboratory, operated under
Contract No. DE-AC02-05CH11231 using NERSC award DDR-ERCAP0018781. SH is
grateful for support from the NASA Ames Research Center, under NASA Academic
Mission Services (NAMS) Contract no. NNA16BD14C, from the DARPA ONISQ program
under interagency agreement IAA 8839 Annex 114, and from the DARPA RQMLS
program under interagency agreement IAA 8839 Annex 128.

## References

  * [1] Christos H Papadimitriou and Kenneth Steiglitz.  Combinatorial optimization: algorithms and complexity.  Courier Corporation, 1998.
  * [2] Lov K Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996.  https://doi.org/10.1145/237814.237866.
  * [3] Tad Hogg and Dmitriy Portnov.  Quantum optimization.  Information Sciences, 128(3-4):181–197, 2000.  https://doi.org/10.1016/s0020-0255(00)00052-9.
  * [4] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.  A quantum approximate optimization algorithm.  arXiv preprint arXiv:1411.4028, 2014.  https://doi.org/10.48550/arXiv.1411.4028.
  * [5] Matthew B Hastings.  A short path quantum algorithm for exact optimization.  Quantum, 2:78, 2018.  https://doi.org/10.22331/q-2018-07-26-78.
  * [6] Tameem Albash and Daniel A Lidar.  Adiabatic quantum computation.  Reviews of Modern Physics, 90(1):015002, 2018.  https://doi.org/10.1103/revmodphys.90.015002.
  * [7] Stuart Hadfield, Zhihui Wang, Bryan O’Gorman, Eleanor Rieffel, Davide Venturelli, and Rupak Biswas.  From the quantum approximate optimization algorithm to a quantum alternating operator ansatz.  Algorithms, 12(2):34, 2019.  https://doi.org/10.3390/a12020034.
  * [8] Philipp Hauke, Helmut G Katzgraber, Wolfgang Lechner, Hidetoshi Nishimori, and William D Oliver.  Perspectives of quantum annealing: Methods and implementations.  Reports on Progress in Physics, 83(5):054401, 2020.  https://doi.org/10.1088/1361-6633/ab85b8.
  * [9] K.M. Svore, A.V. Aho, A.W. Cross, I. Chuang, and I.L. Markov.  A layered software architecture for quantum computing design tools.  Computer, 39(1):74–83, jan 2006.  https://doi.org/10.1109/MC.2006.4.
  * [10] David Ittah, Thomas Häner, Vadym Kliuchnikov, and Torsten Hoefler.  Enabling dataflow optimization for quantum programs.  arXiv preprint arXiv:2101.11030, 2021.  https://doi.org/10.48550/arXiv.2101.11030.
  * [11] Ruslan Shaydulin, Kunal Marwaha, Jonathan Wurtz, and Phillip C Lotshaw.  Qaoakit: A toolkit for reproducible study, application, and verification of the qaoa.  In 2021 IEEE/ACM Second International Workshop on Quantum Computing Software (QCS), pages 64–71. IEEE, 2021.  https://doi.org/10.1109/qcs54837.2021.00011.
  * [12] Nicolas P. D. Sawaya, Tim Menke, Thi Ha Kyaw, Sonika Johri, Alán Aspuru-Guzik, and Gian Giacomo Guerreschi.  Resource-efficient digital quantum simulation of d-level systems for photonic, vibrational, and spin-s hamiltonians.  npj Quantum Information, 6(1), jun 2020.  https://doi.org/10.1038/s41534-020-0278-0.
  * [13] Stuart Hadfield.  On the representation of Boolean and real functions as Hamiltonians for quantum computing.  ACM Transactions on Quantum Computing, 2(4):1–21, 2021.  https://doi.org/10.1145/3478519.
  * [14] Kesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu, and Michael Hicks.  Verified optimization in a quantum intermediate representation.  CoRR, abs/1904.06319, 2019.  https://doi.org/10.48550/arXiv.1904.06319.
  * [15] Thien Nguyen and Alexander McCaskey.  Retargetable optimizing compilers for quantum accelerators via a multilevel intermediate representation.  IEEE Micro, 42(5):17–33, 2022.  https://doi.org/10.1109/mm.2022.3179654.
  * [16] Alexander McCaskey and Thien Nguyen.  A MLIR dialect for quantum assembly languages.  In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 255–264. IEEE, 2021.  https://doi.org/10.1109/qce52317.2021.00043.
  * [17] Andrew W Cross, Lev S Bishop, John A Smolin, and Jay M Gambetta.  Open quantum assembly language.  arXiv preprint arXiv:1707.03429, 2017.  https://doi.org/10.48550/arXiv.1707.03429.
  * [18] Nicolas P. D. Sawaya, Gian Giacomo Guerreschi, and Adam Holmes.  On connectivity-dependent resource requirements for digital quantum simulation of d-level particles.  In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, 2020.  https://doi.org/10.1109/qce49297.2020.00031.
  * [19] Alexandru Macridin, Panagiotis Spentzouris, James Amundson, and Roni Harnik.  Electron-phonon systems on a universal quantum computer.  Phys. Rev. Lett., 121:110504, 2018.  https://doi.org/10.1103/PhysRevLett.121.110504.
  * [20] Sam McArdle, Alexander Mayorov, Xiao Shan, Simon Benjamin, and Xiao Yuan.  Digital quantum simulation of molecular vibrations.  Chem. Sci., 10(22):5725–5735, 2019.  https://doi.org/10.1039/c9sc01313j.
  * [21] Pauline J. Ollitrault, Alberto Baiardi, Markus Reiher, and Ivano Tavernelli.  Hardware efficient quantum algorithms for vibrational structure calculations.  Chem. Sci., 11(26):6842–6855, 2020.  https://doi.org/10.1039/d0sc01908a.
  * [22] Nicolas PD Sawaya, Francesco Paesani, and Daniel P Tabor.  Near-and long-term quantum algorithmic approaches for vibrational spectroscopy.  Physical Review A, 104(6):062419, 2021.  https://doi.org/10.1103/physreva.104.062419.
  * [23] Jakob S Kottmann, Mario Krenn, Thi Ha Kyaw, Sumner Alperin-Lea, and Alán Aspuru-Guzik.  Quantum computer-aided design of quantum optics hardware.  Quantum Science and Technology, 6(3):035010, 2021.  https://doi.org/10.1088/2058-9565/abfc94.
  * [24] R Lora-Serrano, Daniel Julio Garcia, D Betancourth, RP Amaral, NS Camilo, E Estévez-Rams, LA Ortellado GZ, and PG Pagliuso.  Dilution effects in spin 7/2 systems. the case of the antiferromagnet GdRhIn5.  Journal of Magnetism and Magnetic Materials, 405:304–310, 2016\.  https://doi.org/10.1016/j.jmmm.2015.12.093.
  * [25] Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik.  The theory of variational hybrid quantum-classical algorithms.  New Journal of Physics, 18(2):023023, 2016.  https://doi.org/10.1088/1367-2630/18/2/023023.
  * [26] Vladyslav Verteletskyi, Tzu-Ching Yen, and Artur F Izmaylov.  Measurement optimization in the variational quantum eigensolver using a minimum clique cover.  The Journal of chemical physics, 152(12):124114, 2020.  https://doi.org/10.1063/1.5141458.
  * [27] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, et al.  Variational quantum algorithms.  Nature Reviews Physics, 3(9):625–644, 2021.  https://doi.org/10.1038/s42254-021-00348-9.
  * [28] Dmitry A Fedorov, Bo Peng, Niranjan Govind, and Yuri Alexeev.  VQE method: A short survey and recent developments.  Materials Theory, 6(1):1–21, 2022.  https://doi.org/10.1186/s41313-021-00032-6.
  * [29] Andrew Lucas.  Ising formulations of many NP problems.  Frontiers in physics, 2:5, 2014.  https://doi.org/10.3389/fphy.2014.00005.
  * [30] Young-Hyun Oh, Hamed Mohammadbagherpoor, Patrick Dreher, Anand Singh, Xianqing Yu, and Andy J. Rindos.  Solving multi-coloring combinatorial optimization problems using hybrid quantum algorithms.  arXiv preprint arXiv:1911.00595, 2019.  https://doi.org/10.48550/arXiv.1911.00595.
  * [31] Zhihui Wang, Nicholas C. Rubin, Jason M. Dominy, and Eleanor G. Rieffel.  XY mixers: Analytical and numerical results for the quantum alternating operator ansatz.  Phys. Rev. A, 101:012320, Jan 2020.  https://doi.org/10.1103/PhysRevA.101.012320.
  * [32] Zsolt Tabi, Kareem H. El-Safty, Zsofia Kallus, Peter Haga, Tamas Kozsik, Adam Glos, and Zoltan Zimboras.  Quantum optimization for the graph coloring problem with space-efficient embedding.  In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, oct 2020.  https://doi.org/10.1109/qce49297.2020.00018.
  * [33] Franz G Fuchs, Herman Oie Kolden, Niels Henrik Aase, and Giorgio Sartor.  Efficient encoding of the weighted MAX k-CUT on a quantum computer using qaoa.  SN Computer Science, 2(2):89, 2021.  https://doi.org/10.1007/s42979-020-00437-z.
  * [34] Bryan O’Gorman, Eleanor Gilbert Rieffel, Minh Do, Davide Venturelli, and Jeremy Frank.  Comparing planning problem compilation approaches for quantum annealing.  The Knowledge Engineering Review, 31(5):465–474, 2016.  https://doi.org/10.1017/S0269888916000278.
  * [35] Tobias Stollenwerk, Stuart Hadfield, and Zhihui Wang.  Toward quantum gate-model heuristics for real-world planning problems.  IEEE Transactions on Quantum Engineering, 1:1–16, 2020.  https://doi.org/10.1109/TQE.2020.3030609.
  * [36] Tobias Stollenwerk, Bryan OGorman, Davide Venturelli, Salvatore Mandra, Olga Rodionova, Hokkwan Ng, Banavar Sridhar, Eleanor Gilbert Rieffel, and Rupak Biswas.  Quantum annealing applied to de-conflicting optimal trajectories for air traffic management.  IEEE Transactions on Intelligent Transportation Systems, 21(1):285–297, jan 2020.  https://doi.org/10.1109/tits.2019.2891235.
  * [37] Alan Crispin and Alex Syrichas.  Quantum annealing algorithm for vehicle scheduling.  In 2013 IEEE International Conference on Systems, Man, and Cybernetics. IEEE, 2013.  https://doi.org/10.1109/smc.2013.601.
  * [38] Davide Venturelli, Dominic J. J. Marchand, and Galo Rojo.  Quantum annealing implementation of job-shop scheduling.  arXiv preprint arXiv:1506.08479, 2015.  https://doi.org/10.48550/arXiv.1506.08479.
  * [39] Tony T. Tran, Minh Do, Eleanor G. Rieffel, Jeremy Frank, Zhihui Wang, Bryan O’Gorman, Davide Venturelli, and J. Christopher Beck.  A hybrid quantum-classical approach to solving scheduling problems.  In Ninth Annual Symposium on Combinatorial Search. AAAI, 2016.  https://doi.org/10.1609/socs.v7i1.18390.
  * [40] Krzysztof Domino, Mátyás Koniorczyk, Krzysztof Krawiec, Konrad Jałowiecki, and Bartłomiej Gardas.  Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines.  arXiv preprint arXiv:2010.08227, 2020.  https://doi.org/10.48550/arXiv.2010.08227.
  * [41] Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel, Wolfgang Lechner, Simon Perdrix, Marc Porcheron, and Margarita Veshchezerova.  Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles.  EPJ Quantum Technology, 8(1), 2021.  https://doi.org/10.1140/epjqt/s40507-021-00100-3.
  * [42] David Amaro, Matthias Rosenkranz, Nathan Fitzpatrick, Koji Hirano, and Mattia Fiorentini.  A case study of variational quantum algorithms for a job shop scheduling problem.  EPJ Quantum Technology, 9(1):5, 2022.  https://doi.org/10.1140/epjqt/s40507-022-00123-4.
  * [43] Julia Plewa, Joanna Sieńko, and Katarzyna Rycerz.  Variational algorithms for workflow scheduling problem in gate-based quantum devices.  Computing & Informatics, 40(4), 2021.  https://doi.org/10.31577/cai_2021_4_897.
  * [44] Adam Glos, Aleksandra Krawiec, and Zoltán Zimborás.  Space-efficient binary optimization for variational quantum computing.  npj Quantum Information, 8(1):39, 2022.  https://doi.org/10.1038/s41534-022-00546-y.
  * [45] Özlem Salehi, Adam Glos, and Jarosław Adam Miszczak.  Unconstrained binary models of the travelling salesman problem variants for quantum optimization.  Quantum Information Processing, 21(2):67, 2022.  https://doi.org/10.1007/s11128-021-03405-5.
  * [46] David E. Bernal, Sridhar Tayur, and Davide Venturelli.  Quantum integer programming (QuIP) 47-779: Lecture notes.  arXiv preprint arXiv:2012.11382, 2020.  https://doi.org/10.48550/arXiv.2012.11382.
  * [47] Mark Hodson, Brendan Ruck, Hugh Ong, David Garvin, and Stefan Dulman.  Portfolio rebalancing experiments using the quantum alternating operator ansatz.  arXiv preprint arXiv:1911.05296, 2019.  https://doi.org/10.48550/arXiv.1911.05296.
  * [48] Sergi Ramos-Calderer, Adrián Pérez-Salinas, Diego García-Martín, Carlos Bravo-Prieto, Jorge Cortada, Jordi Planagumà, and José I. Latorre.  Quantum unary approach to option pricing.  Phys. Rev. A, 103:032414, 2021.  https://doi.org/10.1103/PhysRevA.103.032414.
  * [49] Kensuke Tamura, Tatsuhiko Shirai, Hosho Katsura, Shu Tanaka, and Nozomu Togawa.  Performance comparison of typical binary-integer encodings in an ising machine.  IEEE Access, 9:81032–81039, 2021.  https://doi.org/10.1109/ACCESS.2021.3081685.
  * [50] Ludmila Botelho, Adam Glos, Akash Kundu, Jarosław Adam Miszczak, Özlem Salehi, and Zoltán Zimborás.  Error mitigation for variational quantum algorithms through mid-circuit measurements.  Physical Review A, 105(2):022441, 2022.  https://doi.org/10.1103/physreva.105.022441.
  * [51] Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G Rieffel.  Quantum approximate optimization algorithm for maxcut: A fermionic view.  Physical Review A, 97(2):022304, 2018.  https://doi.org/10.1103/physreva.97.022304.
  * [52] Stuart Andrew Hadfield.  Quantum algorithms for scientific computing and approximate optimization.  Columbia University, 2018.  https://doi.org/10.48550/arXiv.1805.03265.
  * [53] Matthew B. Hastings.  Classical and quantum bounded depth approximation algorithms.  quantum Information and Computation, 19(13&14):1116–1140, 2019\.  https://doi.org/10.26421/QIC19.13-14-3.
  * [54] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang.  Obstacles to variational quantum optimization from symmetry protection.  Physical Review Letters, 125(26):260505, 2020.  https://doi.org/10.1103/physrevlett.125.260505.
  * [55] Alexander M Dalzell, Aram W Harrow, Dax Enshan Koh, and Rolando L La Placa.  How many qubits are needed for quantum computational supremacy?  Quantum, 4:264, 2020.  https://doi.org/10.22331/q-2020-05-11-264.
  * [56] Daniel Stilck França and Raul Garcia-Patron.  Limitations of optimization algorithms on noisy quantum devices.  Nature Physics, 17(11):1221–1227, 2021.  https://doi.org/10.1038/s41567-021-01356-3.
  * [57] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin.  Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices.  Physical Review X, 10(2):021067, 2020.  https://doi.org/10.1103/physrevx.10.021067.
  * [58] Boaz Barak and Kunal Marwaha.  Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs.  In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1–14:21, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  https://doi.org/10.4230/LIPIcs.ITCS.2022.14.
  * [59] Lennart Bittel and Martin Kliesch.  Training variational quantum algorithms is NP-hard.  Physical Review Letters, 127(12):120502, 2021.  https://doi.org/10.1103/PhysRevLett.127.120502.
  * [60] Kunal Marwaha and Stuart Hadfield.  Bounds on approximating Max $k$ XOR with quantum and classical local algorithms.  Quantum, 6:757, 2022.  https://doi.org/10.22331/q-2022-07-07-757.
  * [61] A Barış Özgüler and Davide Venturelli.  Numerical gate synthesis for quantum heuristics on bosonic quantum processors.  Frontiers in Physics, page 724, 2022.  https://doi.org/10.3389/fphy.2022.900612.
  * [62] Yannick Deller, Sebastian Schmitt, Maciej Lewenstein, Steve Lenk, Marika Federer, Fred Jendrzejewski, Philipp Hauke, and Valentin Kasper.  Quantum approximate optimization algorithm for qudit systems with long-range interactions.  arXiv preprint arXiv:2204.00340, 2022.  https://doi.org/10.1103/physreva.107.062410.
  * [63] Stuart Hadfield, Zhihui Wang, Eleanor G Rieffel, Bryan O’Gorman, Davide Venturelli, and Rupak Biswas.  Quantum approximate optimization with hard and soft constraints.  In Proceedings of the Second International Workshop on Post Moores Era Supercomputing, pages 15–21, 2017.  https://doi.org/10.1145/3149526.3149530.
  * [64] Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, et al.  Quantum optimization using variational algorithms on near-term quantum devices.  Quantum Science and Technology, 3(3):030503, 2018.  https://doi.org/10.1088/2058-9565/aab822.
  * [65] Sam McArdle, Tyson Jones, Suguru Endo, Ying Li, Simon C Benjamin, and Xiao Yuan.  Variational ansatz-based quantum simulation of imaginary time evolution.  npj Quantum Information, 5(1):1–6, 2019.  https://doi.org/10.1038/s41534-019-0187-2.
  * [66] Mario Motta, Chong Sun, Adrian T. K. Tan, Matthew J. O’Rourke, Erika Ye, Austin J. Minnich, Fernando G. S. L. Brandão, and Garnet Kin-Lic Chan.  Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution.  Nature Physics, 16(2):205–210, 2019.  https://doi.org/10.1038/s41567-019-0704-4.
  * [67] Ryan O’Donnell.  Analysis of Boolean functions.  Cambridge University Press, 2014.
  * [68] Kyle E. C. Booth, Bryan O’Gorman, Jeffrey Marshall, Stuart Hadfield, and Eleanor Rieffel.  Quantum-accelerated constraint programming.  Quantum, 5:550, September 2021.  https://doi.org/10.22331/q-2021-09-28-550.
  * [69] Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A Smolin, and Harald Weinfurter.  Elementary gates for quantum computation.  Physical review A, 52(5):3457, 1995.  https://doi.org/10.1103/PhysRevA.52.3457.
  * [70] V.V. Shende and I.L. Markov.  On the CNOT cost of TOFFOLI gates.  Quantum Information and Computation, 9(5&6):461–486, 2009.  https://doi.org/10.26421/qic8.5-6-8.
  * [71] Mehdi Saeedi and Igor L Markov.  Synthesis and optimization of reversible circuits—a survey.  ACM Computing Surveys (CSUR), 45(2):1–34, 2013.  https://doi.org/10.1145/2431211.2431220.
  * [72] Gian Giacomo Guerreschi.  Solving quadratic unconstrained binary optimization with divide-and-conquer and quantum algorithms.  arXiv preprint arXiv:2101.07813, 2021.  https://doi.org/10.48550/arXiv.2101.07813.
  * [73] Zain H. Saleem, Teague Tomesh, Michael A. Perlin, Pranav Gokhale, and Martin Suchara.  Quantum divide and conquer for combinatorial optimization and distributed computing.  arXiv preprint arXiv:2107.07532, 2021.  https://doi.org/10.48550/arXiv.2107.07532.
  * [74] Daniel A Lidar and Todd A Brun.  Quantum error correction.  Cambridge university press, 2013.
  * [75] Nicholas Chancellor.  Domain wall encoding of discrete variables for quantum annealing and qaoa.  Quantum Science and Technology, 4(4):045004, 2019.  https://doi.org/10.1088/2058-9565/ab33c2.
  * [76] Jesse Berwald, Nicholas Chancellor, and Raouf Dridi.  Understanding domain-wall encoding theoretically and experimentally.  Philosophical Transactions of the Royal Society A, 381(2241):20210410, 2023.  https://doi.org/10.1098/rsta.2021.0410.
  * [77] Jie Chen, Tobias Stollenwerk, and Nicholas Chancellor.  Performance of domain-wall encoding for quantum annealing.  IEEE Transactions on Quantum Engineering, 2:1–14, 2021.  https://doi.org/10.1109/tqe.2021.3094280.
  * [78] Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, Richard Harris, Andrew J Berkley, Jan Johansson, Paul Bunyk, et al.  Quantum annealing with manufactured spins.  Nature, 473(7346):194–198, 2011.  https://doi.org/10.1038/nature10012.
  * [79] Zoe Gonzalez Izquierdo, Shon Grabbe, Stuart Hadfield, Jeffrey Marshall, Zhihui Wang, and Eleanor Rieffel.  Ferromagnetically shifting the power of pausing.  Physical Review Applied, 15(4):044013, 2021.  https://doi.org/10.1103/physrevapplied.15.044013.
  * [80] Davide Venturelli and Alexei Kondratyev.  Reverse quantum annealing approach to portfolio optimization problems.  Quantum Machine Intelligence, 1(1):17–30, 2019.  https://doi.org/10.1007/s42484-019-00001-w.
  * [81] Nike Dattani, Szilard Szalay, and Nick Chancellor.  Pegasus: The second connectivity graph for large-scale quantum annealing hardware.  arXiv preprint arXiv:1901.07636, 2019.  https://doi.org/10.48550/arXiv.1901.07636.
  * [82] Wolfgang Lechner, Philipp Hauke, and Peter Zoller.  A quantum annealing architecture with all-to-all connectivity from local interactions.  Science advances, 1(9):e1500838, 2015.  https://doi.org/10.1126/sciadv.1500838.
  * [83] MS Sarandy and DA Lidar.  Adiabatic quantum computation in open systems.  Physical review letters, 95(25):250503, 2005.  https://doi.org/10.1103/physrevlett.95.250503.
  * [84] MHS Amin, Peter J Love, and CJS Truncik.  Thermally assisted adiabatic quantum computation.  Physical review letters, 100(6):060503, 2008.  https://doi.org/10.1103/physrevlett.100.060503.
  * [85] Sergio Boixo, Tameem Albash, Federico M Spedalieri, Nicholas Chancellor, and Daniel A Lidar.  Experimental signature of programmable quantum annealing.  Nature communications, 4(1):2067, 2013.  https://doi.org/10.1038/ncomms3067.
  * [86] Kostyantyn Kechedzhi and Vadim N Smelyanskiy.  Open-system quantum annealing in mean-field models with exponential degeneracy.  Physical Review X, 6(2):021028, 2016.  https://doi.org/10.1103/physrevx.6.021028.
  * [87] Gianluca Passarelli, Ka-Wa Yip, Daniel A Lidar, and Procolo Lucignano.  Standard quantum annealing outperforms adiabatic reverse annealing with decoherence.  Physical Review A, 105(3):032431, 2022.  https://doi.org/10.1103/physreva.105.032431.
  * [88] Stefanie Zbinden, Andreas Bärtschi, Hristo Djidjev, and Stephan Eidenbenz.  Embedding algorithms for quantum annealers with chimera and pegasus connection topologies.  In International Conference on High Performance Computing, pages 187–206. Springer, 2020.  https://doi.org/10.1007/978-3-030-50743-5_10.
  * [89] Mario S Könz, Wolfgang Lechner, Helmut G Katzgraber, and Matthias Troyer.  Embedding overhead scaling of optimization problems in quantum annealing.  PRX Quantum, 2(4):040322, 2021.  https://doi.org/10.1103/prxquantum.2.040322.
  * [90] Aniruddha Bapat and Stephen Jordan.  Bang-bang control as a design principle for classical and quantum optimization algorithms.  arXiv preprint arXiv:1812.02746, 2018.  https://doi.org/10.26421/qic19.5-6-4.
  * [91] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg, and Ilya Safro.  Classical symmetries and the quantum approximate optimization algorithm.  Quantum Information Processing, 20(11):1–28, 2021.  https://doi.org/10.48550/arXiv.2012.04713.
  * [92] Vishwanathan Akshay, Daniil Rabinovich, Ernesto Campos, and Jacob Biamonte.  Parameter concentrations in quantum approximate optimization.  Physical Review A, 104(1):L010401, 2021.  https://doi.org/10.1103/physreva.104.l010401.
  * [93] Michael Streif and Martin Leib.  Training the quantum approximate optimization algorithm without access to a quantum processing unit.  Quantum Science and Technology, 5(3):034008, 2020.  https://doi.org/10.1088/2058-9565/ab8c2b.
  * [94] Guillaume Verdon, Michael Broughton, Jarrod R McClean, Kevin J Sung, Ryan Babbush, Zhang Jiang, Hartmut Neven, and Masoud Mohseni.  Learning to learn with quantum neural networks via classical neural networks.  arXiv preprint arXiv:1907.05415, 2019.  https://doi.org/10.48550/arXiv.1907.05415.
  * [95] Max Wilson, Rachel Stromswold, Filip Wudarski, Stuart Hadfield, Norm M Tubman, and Eleanor G Rieffel.  Optimizing quantum heuristics with meta-learning.  Quantum Machine Intelligence, 3(1):1–14, 2021.  https://doi.org/10.1007/s42484-020-00022-w.
  * [96] Alicia B Magann, Kenneth M Rudinger, Matthew D Grace, and Mohan Sarovar.  Feedback-based quantum optimization.  Physical Review Letters, 129(25):250502, 2022.  https://doi.org/10.1103/physrevlett.129.250502.
  * [97] Lucas T Brady, Christopher L Baldwin, Aniruddha Bapat, Yaroslav Kharkov, and Alexey V Gorshkov.  Optimal protocols in quantum annealing and quantum approximate optimization algorithm problems.  Physical Review Letters, 126(7):070505, 2021.  https://doi.org/10.1103/physrevlett.126.070505.
  * [98] Jonathan Wurtz and Peter J Love.  Counterdiabaticity and the quantum approximate optimization algorithm.  Quantum, 6:635, 2022.  https://doi.org/10.22331/q-2022-01-27-635.
  * [99] Andreas Bärtschi and Stephan Eidenbenz.  Grover mixers for QAOA: Shifting complexity from mixer design to state preparation.  In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 72–82. IEEE, 2020.  https://doi.org/10.1109/qce49297.2020.00020.
  * [100] Daniel J Egger, Jakub Mareček, and Stefan Woerner.  Warm-starting quantum optimization.  Quantum, 5:479, 2021.  https://doi.org/10.22331/q-2021-06-17-479.
  * [101] Jonathan Wurtz and Peter J Love.  Classically optimal variational quantum algorithms.  IEEE Transactions on Quantum Engineering, 2:1–7, 2021.  https://doi.org/10.1109/tqe.2021.3122568.
  * [102] Xiaoyuan Liu, Anthony Angone, Ruslan Shaydulin, Ilya Safro, Yuri Alexeev, and Lukasz Cincio.  Layer VQE: A variational approach for combinatorial optimization on noisy quantum computers.  IEEE Transactions on Quantum Engineering, 3:1–20, 2022.  https://doi.org/10.1109/tqe.2021.3140190.
  * [103] Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven.  Barren plateaus in quantum neural network training landscapes.  Nature communications, 9(1):1–6, 2018.  https://doi.org/10.1038/s41467-018-07090-4.
  * [104] Linghua Zhu, Ho Lun Tang, George S Barron, FA Calderon-Vargas, Nicholas J Mayhall, Edwin Barnes, and Sophia E Economou.  Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer.  Physical Review Research, 4(3):033029, 2022.  https://doi.org/10.1103/physrevresearch.4.033029.
  * [105] Bence Bakó, Adam Glos, Özlem Salehi, and Zoltán Zimborás.  Near-optimal circuit design for variational quantum optimization.  arXiv preprint arXiv:2209.03386, 2022.  https://doi.org/10.48550/arXiv.2209.03386.
  * [106] Itay Hen and Marcelo S Sarandy.  Driver hamiltonians for constrained optimization in quantum annealing.  Physical Review A, 93(6):062312, 2016.  https://doi.org/10.1103/physreva.93.062312.
  * [107] Itay Hen and Federico M Spedalieri.  Quantum annealing for constrained optimization.  Physical Review Applied, 5(3):034007, 2016.  https://doi.org/10.1103/PhysRevApplied.5.034007.
  * [108] Yue Ruan, Samuel Marsh, Xilin Xue, Xi Li, Zhihao Liu, and Jingbo Wang.  Quantum approximate algorithm for NP optimization problems with constraints.  arXiv preprint arXiv:2002.00943, 2020.  https://doi.org/10.48550/arXiv.2002.00943.
  * [109] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, New York, NY, USA, 10th edition, 2011.
  * [110] Masuo Suzuki.  Decomposition formulas of exponential operators and Lie exponentials with some applications to quantum mechanics and statistical physics.  Journal of mathematical physics, 26(4):601–612, 1985.  https://doi.org/10.1063/1.526596.
  * [111] Michael Streif, Martin Leib, Filip Wudarski, Eleanor Rieffel, and Zhihui Wang.  Quantum algorithms with local particle-number conservation: Noise effects and error correction.  Physical Review A, 103(4):042412, 2021.  https://doi.org/10.1103/physreva.103.042412.
  * [112] Vishwanathan Akshay, Hariphan Philathong, Mauro ES Morales, and Jacob D Biamonte.  Reachability deficits in quantum approximate optimization.  Physical review letters, 124(9):090504, 2020.  https://doi.org/10.22331/q-2021-08-30-532.
  * [113] Franz Georg Fuchs, Kjetil Olsen Lye, Halvor Møll Nilsen, Alexander Johannes Stasik, and Giorgio Sartor.  Constraint preserving mixers for the quantum approximate optimization algorithm.  Algorithms, 15(6):202, 2022.  https://doi.org/10.3390/a15060202.
  * [114] Vandana Shukla, O. P. Singh, G. R. Mishra, and R. K. Tiwari.  Application of CSMT gate for efficient reversible realization of binary to gray code converter circuit.  In 2015 IEEE UP Section Conference on Electrical Computer and Electronics (UPCON). IEEE, dec 2015.  https://doi.org/10.1109/UPCON.2015.7456731.
  * [115] Alexander Slepoy.  Quantum gate decomposition algorithms.  Technical report, Sandia National Laboratories, 2006.  https://doi.org/10.2172/889415.
  * [116] Bryan T. Gard, Linghua Zhu, George S. Barron, Nicholas J. Mayhall, Sophia E. Economou, and Edwin Barnes.  Efficient symmetry-preserving state preparation circuits for the variational quantum eigensolver algorithm.  npj Quantum Information, 6(1), 2020.  https://doi.org/10.1038/s41534-019-0240-1.
  * [117] D.P. DiVincenzo and J. Smolin.  Results on two-bit gate design for quantum computers.  In Proceedings Workshop on Physics and Computation. PhysComp 94. IEEE Comput. Soc. Press, 1994.  https://doi.org/10.48550/arXiv.cond-mat/9409111.
  * [118] David Joseph, Adam Callison, Cong Ling, and Florian Mintert.  Two quantum ising algorithms for the shortest-vector problem.  Physical Review A, 103(3):032433, 2021.  https://doi.org/10.1103/PhysRevA.103.032433.
  * [119] Peter Brucker.  Scheduling Algorithms.  Springer-Verlag Berlin Heidelberg, 2004.
  * [120] AMA Hariri and Chris N Potts.  Single machine scheduling with batch set-up times to minimize maximum lateness.  Annals of Operations Research, 70:75–92, 1997.  https://doi.org/10.1023/A:1018903027868.
  * [121] Xiaoqiang Cai, Liming Wang, and Xian Zhou.  Single-machine scheduling to stochastically minimize maximum lateness.  Journal of Scheduling, 10(4):293–301, 2007.  https://doi.org/10.1007/s10951-007-0026-8.
  * [122] Derya Eren Akyol and G Mirac Bayhan.  Multi-machine earliness and tardiness scheduling problem: an interconnected neural network approach.  The International Journal of Advanced Manufacturing Technology, 37(5):576–588, 2008.  https://doi.org/10.1007/s00170-007-0993-0.
  * [123] Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli, et al.  Integer programming, volume 271.  Springer, 2014.
  * [124] Hannes Leipold and Federico M Spedalieri.  Constructing driver hamiltonians for optimization problems with linear constraints.  Quantum Science and Technology, 7(1):015013, 2021.  https://doi.org/10.1088/2058-9565/ac16b8.
  * [125] Masuo Suzuki.  Generalized Trotter’s formula and systematic approximants of exponential operators and inner derivations with applications to many-body problems.  Communications in Mathematical Physics, 51(2):183–190, 1976.  https://doi.org/10.1007/BF01609348.
  * [126] Dominic W. Berry and Andrew M. Childs.  Black-box hamiltonian simulation and unitary implementation.  Quantum Info. Comput., 12(1–2):29–62, 2012.  https://doi.org/10.26421/qic12.1-2-4.
  * [127] D. W. Berry, A. M. Childs, and R. Kothari.  Hamiltonian simulation with nearly optimal dependence on all parameters.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 792–809, 2015.  https://doi.org/10.1109/FOCS.2015.54.
  * [128] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma.  Simulating Hamiltonian dynamics with a truncated Taylor series.  Physical Review Letters, 114(9):090502, 2015.  https://doi.org/10.1103/PhysRevLett.114.090502.
  * [129] Guang Hao Low and Isaac L. Chuang.  Optimal hamiltonian simulation by quantum signal processing.  Phys. Rev. Lett., 118:010501, 2017.  https://doi.org/10.1103/PhysRevLett.118.010501.
  * [130] Guang Hao Low and Isaac L. Chuang.  Hamiltonian simulation by qubitization.  Quantum, 3:163, 2019.  https://doi.org/10.22331/q-2019-07-12-163.
  * [131] Andrew M. Childs, Aaron Ostrander, and Yuan Su.  Faster quantum simulation by randomization.  Quantum, 3:182, 2019.  https://doi.org/10.22331/q-2019-09-02-182.
  * [132] Earl Campbell.  Random Compiler for Fast Hamiltonian Simulation.  Physical Review Letters, 123(7):070503, 2019.  https://doi.org/10.1103/PhysRevLett.123.070503.
  * [133] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu.  Theory of trotter error with commutator scaling.  Phys. Rev. X, 11:011020, 2021.  https://doi.org/10.1103/PhysRevX.11.011020.
  * [134] Albert T Schmitz, Nicolas PD Sawaya, Sonika Johri, and AY Matsuura.  Graph optimization perspective for low-depth trotter-suzuki decomposition.  arXiv preprint arXiv:2103.08602, 2021.  https://doi.org/10.48550/arXiv.2103.08602.
  * [135] Nicolas PD Sawaya.  mat2qubit: A lightweight pythonic package for qubit encodings of vibrational, bosonic, graph coloring, routing, scheduling, and general matrix problems.  arXiv preprint arXiv:2205.09776, 2022.  https://doi.org/10.48550/arXiv.2205.09776.
  * [136] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, İlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors.  SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python.  Nature Methods, 17:261–272, 2020.  https://doi.org/10.1038/s41592-019-0686-2.
  * [137] Jarrod R McClean, Nicholas C Rubin, Kevin J Sung, Ian D Kivlichan, Xavier Bonet-Monroig, Yudong Cao, Chengyu Dai, E Schuyler Fried, Craig Gidney, Brendan Gimby, et al.  Openfermion: the electronic structure package for quantum computers.  Quantum Science and Technology, 5(3):034014, 2020.  https://doi.org/10.1088/2058-9565/ab8ebc.
  * [138] Aaron Meurer, Christopher P Smith, Mateusz Paprocki, Ondřej Čertík, Sergey B Kirpichev, Matthew Rocklin, AMiT Kumar, Sergiu Ivanov, Jason K Moore, Sartaj Singh, et al.  Sympy: symbolic computing in Python.  PeerJ Computer Science, 3:e103, 2017.  https://doi.org/10.7717/peerj-cs.103.
  * [139] Pradnya Khalate, Xin-Chuan Wu, Shavindra Premaratne, Justin Hogaboam, Adam Holmes, Albert Schmitz, Gian Giacomo Guerreschi, Xiang Zou, and AY Matsuura.  An LLVM-based C++ compiler toolchain for variational hybrid quantum-classical algorithms and quantum accelerators.  arXiv preprint arXiv:2202.11142, 2022.  https://doi.org/10.48550/arXiv.2202.11142.
  * [140] C. A. Ryan, C. Negrevergne, M. Laforest, E. Knill, and R. Laflamme.  Liquid-state nuclear magnetic resonance as a testbed for developing quantum control methods.  Phys. Rev. A, 78:012328, Jul 2008.  https://doi.org/10.1103/PhysRevA.78.012328.
  * [141] Richard Versluis, Stefano Poletto, Nader Khammassi, Brian Tarasinski, Nadia Haider, David J Michalak, Alessandro Bruno, Koen Bertels, and Leonardo DiCarlo.  Scalable quantum circuit and control for a superconducting surface code.  Physical Review Applied, 8(3):034021, 2017.  https://doi.org/10.1103/physrevapplied.8.034021.
  * [142] Bjoern Lekitsch, Sebastian Weidt, Austin G Fowler, Klaus Mølmer, Simon J Devitt, Christof Wunderlich, and Winfried K Hensinger.  Blueprint for a microwave trapped ion quantum computer.  Science Advances, 3(2):e1601540, 2017.  https://doi.org/10.1126/sciadv.1601540.