  We present a framework for the synthesis of phase polynomials that addresses
both cases of full connectivity and partial connectivity for NISQ
architectures. In most cases, our algorithms generate circuits with lower CNOT
count and CNOT depth than the state of the art or have a significantly smaller
running time for similar performances. We also provide methods that can be
applied to our algorithms in order to trade an increase in the CNOT count for a
decrease in execution time, thereby filling the gap between our algorithms and
faster ones.
