  GCD computations and variants of the Euclidean algorithm enjoy broad uses in
both classical and quantum algorithms. In this paper, we propose quantum
circuits for GCD computation with $O(n \log n)$ depth with O(n) ancillae. Prior
circuit construction needs $O(n^2)$ running time with O(n) ancillae. The
proposed construction is based on the binary GCD algorithm and it benefits from
log-depth circuits for 1-bit shift, comparison/subtraction, and managing
ancillae. The worst-case gate count remains $O(n^2)$, as in traditional
circuits.
