# A quantum algorithm for GCD

Does anyone know of a direct quantum algorithm for computing GCD, - There could be quantum gates for addition subtraction constructed explicitly, using CNOT, etc. - the construction can be done in some poly(n) of input, (this is just a guess), but is there any algorithm, scheme for computing GCD, using quantum algorithms, gauss sums, QFT, quantum approximation, anything(!!) thanks,

• – Logan Mayfield May 26 '14 at 12:43
• @Tom The way you phrased the question, it doesn't make much sense to me. What is the goal, improving the complexity? I agree with Logan that you should revise it and maybe ask for a specific approach, once you have fixed the goal you want to obtain. – Alessandro Cosentino May 27 '14 at 1:07

A search for "Quantum GCD" yields a 2013 paper by Saeedi and Markov titled "Quantum Circuits for GCD Computation with O(n \log n) Depth and O(n) Ancillae". It's not mentioned in the title, but the size of the circuit used in their algorithm $O(n^2)$.