> The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer.

That's only a problem if you need the exact solution. If you're OK with 99.9% quality, approximate solutions are much cheaper. So the question is, is it necessary to invest into that 1%?