A non-linear advance probably wouldn't involve Shor's algorithm. As what happened with AI algorithms. What we call post quantum cryptography is really post Shor's cryptography.

The difference is that we know Shor's algorithm will work once you solve certain engineering problems. As I understand it even the theoretical side of AI was always shooting in the dark.

I don't think it's really fair to call these engineering problems. Creating a working quantum computer is at the bleeding edge of experimental physics. Sure, the theoretical physics behind a working QC is somewhat understood, but there are no successful experiments in the area.

Even the theory is somewhat debatable, as creating a working QC pushes close to the boundaries of the measurement problem.