I'd argue that we haven't encountered an "impossible" problem in the past 20+ years -- expensive, yes, time-consuming, yes, but impossible?

And I don't see quantum computing changing this.

Faster, yes. Even more expensive, yes. Magic, no.