<p>A search for "Quantum GCD" yields a 2013 paper by Saeedi and Markov titled <a href="http://arxiv.org/abs/1304.7516" rel="nofollow">"Quantum Circuits for GCD Computation with O(n \log n) Depth and O(n) Ancillae"</a>. It's not mentioned in the title, but the size of the circuit used in their algorithm $O(n^2)$.</p>

CC BY-SA 3.0
2014-05-26T16:49:14.470Z
I was wondering if there was an approach using Gaussian sums(like van dam seroussi), wherein we get an Eulers coefficient(tells us number of relative primes relative to N), and then start from there to get the gcd!
Tom
CC BY-SA 3.0
2014-05-26T18:41:06.640Z
You should probably revise your question to make that more clear. I read your question as, "Is there a Quantum Algorithm for GCD?"
Logan Mayfield
CC BY-SA 3.0
2014-05-26T12:51:33.163Z
2014-05-26T12:51:33.163Z
Logan Mayfield
<p>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, </p>

CC BY-SA 3.0
2014-05-26T12:43:34.907Z
related? http://cstheory.stackexchange.com/questions/16773/is-there-a-quantum-nc-algorithm-for-computing-gcd
Logan Mayfield
CC BY-SA 3.0
2014-05-27T01:07:22.220Z
@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
<approximation-algorithms><quantum-computing>
A quantum algorithm for GCD
Tom
# A quantum algorithm for GCD

(Asked by: username_0 on 2014-05-26)

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,

**Tags:** approximation-algorithms, quantum-computing

> **Comments:**
> **username_1**: related? http://cstheory.stackexchange.com/questions/16773/is-there-a-quantum-nc-algorithm-for-computing-gcd  
> **username_2**: @username_0 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.  

---

## 1 answers

### Answer by username_1 on 2014-05-26. Score: 1

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"](http://arxiv.org/abs/1304.7516). It's not mentioned in the title, but the size of the circuit used in their algorithm $O(n^2)$.

> **Comments:**
> **username_0**: I was wondering if there was an approach using Gaussian sums(like van dam seroussi), wherein we get an Eulers coefficient(tells us number of relative primes relative to N), and then start from there to get the gcd!  
> **username_1**: You should probably revise your question to make that more clear. I read your question as, "Is there a Quantum Algorithm for GCD?"  

---

