I am currently reading “Introduction to Topological Quantum Computation” by J.K. Pachos. In the book the author mentions that Shor’s factoring algorithm is polynomial (with regard to the complexity class) on a quantum computer. A similar algorithm on a classical computer is said to be exponential. After that complexity classes get introduced and the author says that we don’t have problems that are polynomial easy to solve with a quantum-computer and not polynomial easy on a classical computer. Doesn't Shor’s algorithm fulfil both criteria?

  • $\begingroup$ I don't think there is a proof that prime factorization is classically NP-hard. Regarding your question, maybe evaluation of Jones polynomial is an example (Pachos also discussed this algorithm). $\endgroup$
    – Meng Cheng
    Jun 16, 2015 at 5:50
  • 1
    $\begingroup$ I think this might be a little far from the physics of quantum computation. I'll defer to the QC experts, but if it's off topic here, we can send it to either Computer Science or Theoretical Computer Science depending on where it would fit. $\endgroup$
    – David Z
    Jun 16, 2015 at 6:09
  • 1
    $\begingroup$ We don't know a proof that factoring cannot be solved efficiently on a classical computer. (Indeed, solving this would imply that P$\ne$NP.) @MengCheng Factoring is likely not NP-hard but somewhere inbetween P and NP. $\endgroup$ Jun 16, 2015 at 6:44
  • $\begingroup$ From a physical perspective the algorithmic complexity question is fairly academic (as in: it does not apply). That does not mean that it isn't important to mathematicians and computer scientists, of course, but the vast majority of classical and quantum systems is is actually incomputable, i.e. we can not predict their future states. $\endgroup$
    – CuriousOne
    Jun 16, 2015 at 7:10

1 Answer 1


While we know that factoring can be solved in polynomial time on a quantum computer, we do not have a proof that factoring cannot be solved in polynomial time on a classical computer. (Indeed, this would be an extremely strong result as it would in particular show that P$\ne$NP.) See also https://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity

  • $\begingroup$ Ok. I study physics and don't know much about computer science. I thought you could always hope to someday find a nice algorithm but I did not know that you can proof that such a thing can or can not exist. Thank you for your answer. $\endgroup$ Jun 16, 2015 at 7:15
  • $\begingroup$ @ThomasElliot Why should it be impossible to prove that something is impossible? (It is, admittedly, often extremely difficult.) -- But in that case you should be even more convinced that we cannot find a problem which can provably be solved faster on a quantum than on a classical computer! $\endgroup$ Jun 16, 2015 at 7:17

Your Answer

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

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