Asymptotically optimal circuits for arbitrary n-qubit diagonal computations

A unitary operator U=₉, ₊ u₉, ₊ k j is called diagonal when u₉, ₊=0 unless j=k. The definition extends to quantum computations, where j and k vary over the 2ⁿ binary expressions for integers 0, 1, 2ⁿ-1, given n qubits. Such operators do not affect outcomes of the projective measurement \ jj \; ; \; 0 j 2ⁿ-1\ but rather create arbitrary relative phases among the computational basis states \ j \; ; \; 0 j 2ⁿ-1\.