Title: Two-step approach to scheduling quantum circuits,
Abstract: As the effort to scale up existing quantum hardware proceeds, it becomes
necessary to schedule quantum gates in a way that minimizes the number of
operations. There are three constraints that have to be satisfied: the order or
dependency of the quantum gates in the specific algorithm, the fact that any
qubit may be involved in at most one gate at a time, and the restriction that
two-qubit gates are implementable only between connected qubits. The last
aspect implies that the compilation depends not only on the algorithm, but also
on hardware properties like connectivity. Here we suggest a two-step approach
in which logical gates are initially scheduled neglecting connectivity
considerations, while routing operations are added at a later step in a way
that minimizes their overhead. We rephrase the subtasks of gate scheduling in
terms of graph problems like edge-coloring and maximum subgraph isomorphism.
While this approach is general, we specialize to a one dimensional array of
qubits to propose a routing scheme that is minimal in the number of exchange
operations. As a practical application, we schedule the Quantum Approximate
Optimization Algorithm in a linear geometry and quantify the reduction in the
number of gates and circuit depth that results from increasing the efficacy of
the scheduling strategies.