Phase-context decomposition of diagonal unitaries for higher-dimensional systems

We generalize the efficient decomposition method for phase-sparse diagonal operators of J. Welch et al. [Quantum Info. Comput. 16, 87 (2016)] to qudit systems. The phase-context-aware method focuses on cascaded entanglers, whose decomposition into multicontrolled inc gates can be optimized by the choice of a proper signed base-$d$ representation for the natural numbers. While the gate count of the best-known decomposition method for general diagonal operators on qubit systems scales with $O\left(2^n\right)$, the circuits synthesized by the Welch algorithm for diagonal operators with $k$ distinct phases are upper-bounded by $O\left(n^{2}k\right)$, which is generalized to $O\left(d{n}^{2}k\right)$ for the qudit case in this paper.