[Beldin]

This is a very good reminder that we don't know for various problems whether there is an efficient algorithm. For problems studied for decades (eg travelling salesman) we feel fairly confident that there is no polynomial-time algorithm - but even then, we don't know for sure.

As far as I know, the problems underpinning post-quantum cryptography have not yet enjoyed such extensive scrutiny / search for efficient (regular or quantum) algorithms.

In other words: stuff that is hoped to be post-quantum might turn out to be quantum -- or even in a feasible non-quantum class. The latter seems unlikely barring p=np-alike breakthroughs, but even these cannot fully be ruled out.