15

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)

Community
  • 1
Turbo
  • 12,812
  • 1
  • 19
  • 68

1 Answers1

15

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

Alessandro Cosentino
  • 4,000
  • 35
  • 43
  • 6
    It would be nice if you can explain the relation between quantum Fourier transform and GCD. – Kaveh Mar 07 '13 at 17:16
  • I agree with Kaveh. It would be nice to provide the relation. – Turbo Mar 08 '13 at 02:56
  • 2
    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 Mar 08 '13 at 13:16
  • Hi Alessandro: Do you know if Polynomial GCD is in NC? – Turbo Mar 28 '13 at 13:22
  • 1
    @Arul: yes, it is. See von zur Gathen, Parallel algorithms for algebraic problems. http://dx.doi.org/10.1145/800061.808728 – Alessandro Cosentino Mar 28 '13 at 13:57