Quantum Circuits for GCD Computation with $O(n\log n)$ Depth and O(n) Ancillae

Mehdi Saeedi, Igor L. Markov

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 w…