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 '15 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 '15 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$ – Norbert Schuch Jun 16 '15 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 '15 at 7:10

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

| cite | improve this answer | |
  • $\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$ – Thomas Elliot Jun 16 '15 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$ – Norbert Schuch Jun 16 '15 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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