  Instruction scheduling is a key transformation in backend compilers that take
an untimed description of an algorithm and assigns time slots to the
algorithm's instructions so that they can be executed as efficiently as
possible while taking into account the target processor limitations, such as
the amount of computational units available. For example, for a superconducting
quantum processor these restrictions include the amount of analogue instruments
available to play the waveforms to drive the qubit rotations or on-chip
connectivity between qubits. Current small-scale quantum processors contain
only a few qubits; therefore, it is feasible to drive qubits individually
albeit not scalable. Consequently, for NISQ and beyond NISQ devices, it is
expected that classical instrument sharing to be designed in the future quantum
control architectures where several qubits are connected to an instrument and
multiplexing is used to activate only the qubits performing the same quantum
operation at a time. Existing quantum scheduling algorithms either rely on ILP
formulations, which do not scale well, or use heuristic based algorithms such
as list scheduling which are not versatile enough to deal with quantum
requirements such as scheduling with exact relative timing constraints between
instructions, situation that might occur when decomposing complex instructions
into native ones and requiring to keep a fixed timing between the primitive
ones to guarantee correctness. In this paper, we propose a novel resource
constrained scheduling algorithm that is based on the SDC formulation, which is
the state-of-the-art algorithm used in the reconfigurable computing. We
evaluate it against a list scheduler and describe the benefits of the proposed
approach. We find that the SDC-based scheduling is not only able to find better
schedules but also model flexible relative timing constraints.
