Quantum speedup of the traveling-salesman problem for bounded-degree graphs
Dominic J. Moylett, Noah Linden, Ashley Montanaro · Physical Review A · 2017
The traveling-salesman problem is an iconic route-finding task, with applications from chip design to planning and logistics. Here the authors show that if the graph of cities to be visited is of low degree, a traveling salesman armed with a quantum satnav can find the best route quadratically faster than using any known classical method.