FWIW while existing graph algorithms can't solve it optimally, but they do approach it quite closely using heuristics. It's unclear how much benefit something like this would have for online (i.e. latency-sensitive) applications such as internet routing if the time-constant to setup the QC + execute + get the result is higher compared to a heuristic approach. My hunch is that it won't be useful there for a long time if ever.

That being said, for FPGA/ASIC layout & similar problems, it's possible that QC is worth it as an extra optimization level even if slower to get a result in absolute terms to eek out that last bit of optimality (e.g. LTO equivalent). It may also be useful as a way to evaluate how good existing heuristics perform against the true optimal route to see if there's any improvements that can be made to the heuristic algorithms or the heuristics being used themselves.