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,

  • 2
    $\begingroup$ related? cstheory.stackexchange.com/questions/16773/… $\endgroup$ – Logan Mayfield May 26 '14 at 12:43
  • $\begingroup$ @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. $\endgroup$ – 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)$.

  • $\begingroup$ 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! $\endgroup$ – Tom May 26 '14 at 16:49
  • $\begingroup$ You should probably revise your question to make that more clear. I read your question as, "Is there a Quantum Algorithm for GCD?" $\endgroup$ – Logan Mayfield May 26 '14 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.