Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs
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.