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.
