The travelling salesman problem

The search has been on to find quantum algorithms for other hard problems.

A very famous, and challenging, mathematical problem is called the travelling salesman problem. 

In this problem, a salesperson is tasked with delivering items to a variety of cities. There needs to be an order they visit the cities in to minimize the total length travelled, visiting each city only once and returning to the original city. 

The travelling salesman problem is of great practical importance, since it is possible to transform a wide variety of other optimisation tasks into a Travelling Salesman problem.  This means that if you could efficiently solve it you’d be able to solve many other problems companies have to make every day, from optimising the scheduling in a factory process, to asset pricing in finance. There has been a lot of interest in developing quantum algorithms to efficiently solve it.  

We do not yet know how well these algorithms will work for large-scale problems, as we don’t have sufficient theoretical understanding of them. As quantum computers of larger scale are developed we will be able to test them, and find out if they deliver quantum advantage for these very important problems.