Skip main navigation

The travelling salesman problem

You've seen how challenging the travelling salesman problem is to solve. Prof Dan Browne goes into more detail.

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. 

This article is from the free online

Introduction to Quantum Computing

Created by
FutureLearn - Learning For Life

Reach your personal and professional goals

Unlock access to hundreds of expert online courses and degrees from top universities and educators to gain accredited qualifications and professional CV-building certificates.

Join over 18 million learners to launch, switch or build upon your career, all at your own pace, across a wide range of topic areas.

Start Learning now