<p>First of all, there is a formal definition of "quantum-NC", see <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aQ#qnc">QNC</a> on the zoo.</p>

<p>GCD is indeed a good candidate for a problem that could be shown to be in QNC, but it's not known to be in NC. However, finding a QNC algorithm for GCD is still an open problem. </p>

<p>The feeling for which this is believed to be true comes from the fact that the Quantum Fourier Transform can be done in QNC.</p>

<p>Reference: Conclusion section of "R. Cleve and J. Watrous, Fast parallel circuits for the quantum Fourier transform", <a href="http://arxiv.org/abs/quant-ph/0006004">arXiv:quant-ph/0006004</a></p>

CC BY-SA 3.0
2013-03-07T17:16:41.630Z
It would be nice if you can explain the relation between quantum Fourier transform and GCD.
Kaveh
CC BY-SA 3.0
2013-03-08T02:56:34.887Z
I agree with Kaveh. It would be nice to provide the relation.
Turbo
CC BY-SA 3.0
2013-03-08T13:16:59.190Z
I don't think there is a direct relation. What I meant to say is that we suspect QNC to be more powerful than NC, because we can do QFT in QNC. So we ask if there is some more natural problem that is in QNC too, and one of the simplest natural problem that we don't know how to do in NC is GCD. At some point I had suspected that there is a relation between the two problems coming from the fact that QFT and GCD are both used as sub-routines in the period-finding algorithm, but I wasn't able to make this formal. Maybe other users can enlighten us more.
Alessandro Cosentino
CC BY-SA 3.0
2013-03-28T13:22:43.933Z
Hi Alessandro: Do you know if Polynomial GCD is in NC?
Turbo
CC BY-SA 3.0
2013-03-28T13:57:07.110Z
@Arul: yes, it is. See von zur Gathen, Parallel algorithms for algebraic problems. http://dx.doi.org/10.1145/800061.808728
Alessandro Cosentino
CC BY-SA 3.0
2013-03-07T09:55:50.317Z
2013-03-08T13:19:25.263Z
2013-03-08T13:19:25.263Z
Alessandro Cosentino
<p>From the comments on <a href="https://mathoverflow.net/questions/122616/is-integer-gcd-in-nc">one of my questions on MathOverflow</a> 
I get the feeling that the question regarding GCD being in $\mathsf{NC}$ vs. $\mathsf{P}$ is akin to the question regarding Integer Factorization being in $\mathsf{P}$ vs. $\mathsf{NP}$. </p>

<p>Is there something like a "quantum $\mathsf{NC}$" algorithm for GCD as there is a quantum polynomial time ($\mathsf{BQP}$) algorithm for Integer Factorization?</p>

<p>Related question: <a href="https://cstheory.stackexchange.com/questions/2708/complexity-of-greatest-common-divisor-gcd">complexity of greatest common divisor (gcd)</a></p>

CC BY-SA 3.0
2013-03-07T09:49:29.343Z
when you cross-post it's better to write the question again.
Alessandro Cosentino
<cc.complexity-theory><quantum-computing><dc.parallel-comp><nt.number-theory><comp-number-theory>
Is there a quantum NC algorithm for computing GCD?
Turbo
# Is there a quantum NC algorithm for computing GCD?

(Asked by: username_0 on 2013-03-07)

From the comments on [one of my questions on MathOverflow](https://mathoverflow.net/questions/122616/is-integer-gcd-in-nc)
I get the feeling that the question regarding GCD being in $\mathsf{NC}$ vs. $\mathsf{P}$ is akin to the question regarding Integer Factorization being in $\mathsf{P}$ vs. $\mathsf{NP}$.

Is there something like a "quantum $\mathsf{NC}$" algorithm for GCD as there is a quantum polynomial time ($\mathsf{BQP}$) algorithm for Integer Factorization?

Related question: [complexity of greatest common divisor (gcd)](https://cstheory.stackexchange.com/questions/2708/complexity-of-greatest-common-divisor-gcd)

**Tags:** cc.complexity-theory, quantum-computing, dc.parallel-comp, nt.number-theory, comp-number-theory

> **Comments:**
> **username_1**: when you cross-post it's better to write the question again.  

---

## 1 answers

### Answer by username_1 on 2013-03-07. Score: 15 | Accepted answer

First of all, there is a formal definition of "quantum-NC", see [QNC](https://complexityzoo.uwaterloo.ca/Complexity_Zoo%3aQ#qnc) on the zoo.

GCD is indeed a good candidate for a problem that could be shown to be in QNC, but it's not known to be in NC. However, finding a QNC algorithm for GCD is still an open problem.

The feeling for which this is believed to be true comes from the fact that the Quantum Fourier Transform can be done in QNC.

Reference: Conclusion section of "R. Cleve and J. Watrous, Fast parallel circuits for the quantum Fourier transform", [arXiv:quant-ph/0006004](http://arxiv.org/abs/quant-ph/0006004)

> **Comments:**
> **username_2**: It would be nice if you can explain the relation between quantum Fourier transform and GCD.  
> **username_0**: I agree with username_2. It would be nice to provide the relation.  
> **username_1**: I don't think there is a direct relation. What I meant to say is that we suspect QNC to be more powerful than NC, because we can do QFT in QNC. So we ask if there is some more natural problem that is in QNC too, and one of the simplest natural problem that we don't know how to do in NC is GCD. At some point I had suspected that there is a relation between the two problems coming from the fact that QFT and GCD are both used as sub-routines in the period-finding algorithm, but I wasn't able to make this formal. Maybe other users can enlighten us more.  
> **username_0**: Hi Alessandro: Do you know if Polynomial GCD is in NC?  
> **username_1**: @Arul: yes, it is. See von zur Gathen, Parallel algorithms for algebraic problems. http://dx.doi.org/10.1145/800061.808728  

---

