# Do we have algorithms that are polynomial on a Q-Computer but not poly. on a classical Computer?

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?

• 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). Jun 16, 2015 at 5:50
• 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. Jun 16, 2015 at 6:09
• 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. Jun 16, 2015 at 6:44
• 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. Jun 16, 2015 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