15
$\begingroup$

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)

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ when you cross-post it's better to write the question again. $\endgroup$
    – Alessandro Cosentino
    Mar 7, 2013 at 9:49

1 Answer 1

Reset to default
15
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • 6
    $\begingroup$ It would be nice if you can explain the relation between quantum Fourier transform and GCD. $\endgroup$
    – Kaveh
    Mar 7, 2013 at 17:16
  • $\begingroup$ I agree with Kaveh. It would be nice to provide the relation. $\endgroup$
    – Turbo
    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
    Mar 8, 2013 at 13:16
  • $\begingroup$ Hi Alessandro: Do you know if Polynomial GCD is in NC? $\endgroup$
    – Turbo
    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
    Mar 28, 2013 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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