From the comments on one of my questions on MathOverflow 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)
-
5$\begingroup$ when you cross-post it's better to write the question again. $\endgroup$Alessandro Cosentino– Alessandro Cosentino2013年03月07日 09:49:29 +00:00Commented Mar 7, 2013 at 9:49
1 Answer 1
First of all, there is a formal definition of "quantum-NC", see 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
-
6$\begingroup$ It would be nice if you can explain the relation between quantum Fourier transform and GCD. $\endgroup$Kaveh– Kaveh2013年03月07日 17:16:41 +00:00Commented Mar 7, 2013 at 17:16
-
$\begingroup$ I agree with Kaveh. It would be nice to provide the relation. $\endgroup$Turbo– Turbo2013年03月08日 02:56:34 +00:00Commented Mar 8, 2013 at 2:56
-
2$\begingroup$ 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. $\endgroup$Alessandro Cosentino– Alessandro Cosentino2013年03月08日 13:16:59 +00:00Commented Mar 8, 2013 at 13:16
-
$\begingroup$ Hi Alessandro: Do you know if Polynomial GCD is in NC? $\endgroup$Turbo– Turbo2013年03月28日 13:22:43 +00:00Commented Mar 28, 2013 at 13:22
-
1$\begingroup$ @Arul: yes, it is. See von zur Gathen, Parallel algorithms for algebraic problems. dx.doi.org/10.1145/800061.808728 $\endgroup$Alessandro Cosentino– Alessandro Cosentino2013年03月28日 13:57:07 +00:00Commented Mar 28, 2013 at 13:57
Explore related questions
See similar questions with these tags.