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?
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