  Various quantum algorithms require usage of arbitrary diagonal operators as
subroutines. For their execution on a physical hardware, those operators must
be first decomposed into target device's native gateset and its qubit
connectivity for entangling gates. Here, we assume that the allowed gates are
exactly the CX gate and the parameterized phase gate. We introduce a framework
for the analysis of CX-only circuits and through its lens provide solution
constructions for several different device topologies (fully-connected, linear
and circular). We also introduce two additional variants of the problem. Those
variants can be used in place of exact decomposition of the diagonal operator
when the circuit following it satisfies a set of prerequisites, enabling
further reduction in the CX cost of implementation. Finally, we discuss how to
exploit the framework for the decomposition of a particular, rather than
general, diagonal operator.
