  Current noisy intermediate-scale quantum (NISQ) devices can only execute
small circuits with shallow depth, as they are still constrained by the
presence of noise: quantum gates have error rates and quantum states are
fragile due to decoherence. Hence, it is of great importance to optimize the
depth/gate-count when designing quantum circuits for specific tasks. Diagonal
unitary matrices are well-known to be key building blocks of many quantum
algorithms or quantum computing procedures. Prior work has discussed the
synthesis of diagonal unitary matrices over the primitive gate set
$\{\text{CNOT}, R_Z\}$. However, the problem has not yet been fully understood,
since the existing synthesis methods have not optimized the circuit depth.
  In this paper, we propose a depth-optimized synthesis algorithm that
automatically produces a quantum circuit for any given diagonal unitary matrix.
Specially, it not only ensures the asymptotically optimal gate-count, but also
nearly halves the total circuit depth compared with the previous method.
Technically, we discover a uniform circuit rewriting rule well-suited for
reducing the circuit depth. The performance of our synthesis algorithm is both
theoretically analyzed and experimentally validated by evaluations on two
examples. First, we achieve a nearly 50\% depth reduction over Welch's method
for synthesizing random diagonal unitary matrices with up to 16 qubits. Second,
we achieve an average of 22.05\% depth reduction for resynthesizing the
diagonal part of specific quantum approximate optimization algorithm (QAOA)
circuits with up to 14 qubits.
