  A variety of quantum algorithms employ Pauli operators as a convenient basis
for studying the spectrum or evolution of Hamiltonians or measuring multi-body
observables. One strategy to reduce circuit depth in such algorithms involves
simultaneous diagonalization of Pauli operators generating unitary evolution
operators or observables of interest. We propose an algorithm yielding quantum
circuits with depths $O(n \log r)$ diagonalizing $n$-qubit operators generated
by $r$ Pauli operators. Moreover, as our algorithm iteratively diagonalizes all
operators on at least one qubit per step, it is well suited to maintain low
circuit depth even on hardware with limited qubit connectivity. We observe that
our algorithm performs favorably in producing quantum circuits diagonalizing
randomly generated Hamiltonians as well as molecular Hamiltonians with short
depths and low two-qubit gate counts.
