Skip main navigation
Home / IT & Computer Science / Introduction to Quantum Computing / The travelling salesman problem

The travelling salesman problem

You've seen how challenging the travelling salesman problem is to solve. Prof Dan Browne goes into more detail.
View transcript
9
Shor’s algorithm was a huge breakthrough for quantum computing but unless you’re trying to crack codes, being able to factor very large numbers isn’t particularly useful. So the search is on for other heart problems to apply quantum computers too. Now it’s important to recognise that quantum computers don’t automatically give you a speedup for the problem you’re looking at. You need to find an algorithm which is able to take advantage of the special properties of the interference between quantum superpositions. Now there are a number of optimisation problems which are extremely hard and very important in industry and one of the most famous is called the Travelling Salesman Problem. The Travelling Salesman Problem is very easy to describe.
52.2
Imagine we have a salesman here in his car and this salesman needs to visit five cities, the five cities marked on this map. So he needs to go to Dallas, stop off at Detroit, go to Denver, and also visit Salt Lake City and Phoenix. And he wants to pick a route to do this which visits each of these cities only once but which covers the minimum distance, and that way he’ll save on petrol. So there are a number of different possibilities he could choose. Starting at Dallas, he could choose to first go up to Detroit. Then after that he needs to visit Salt Lake City and Denver but he has a choice.
93.8
He could go to Denver on his way to Salt Lake City, or maybe it would be better for him to go all the way to Phoenix and then come via Salt Lake City and Denver on his return to Dallas. Now when we only have five cities this problem doesn’t look too difficult, you could just work out all the different routes, work out the distances, and just see which is shortest. And the reason that doesn’t look difficult is because there aren’t very many routes. There are only actually 12 different possible routes if we have five cities. But if we increase the number of cities, if we increase the number of pins on this map, the problem gets significantly harder.
131
In fact if we just go up to ten cities there are already over a million different possible routes. If we go larger, imagine you’re a courier and you have 100 parcels to deliver, this problem with 100 cities actually has more than 10 to the 155 possible solutions, so that’s a one with 155 zeroes after it, a huge number. So this problem is very challenging for conventional computers, yhere isn’t an efficient algorithm to solve this problem in general. And while we have some approximate algorithms that give reasonably good solutions, we’d prefer it if we could find the optimal solution.
174.1
So this is an exciting opportunity for quantum computers: can we find a quantum algorithm for the Travelling Salesman Problem? Well, the progress on this has been very interesting. We’ve found a number of algorithms which directly target the Travelling Salesman Problem and those have been shown to work well with small instances of the problem. But we don’t have the same kind of general theoretical understanding of these algorithms that we have for Shor’s algorithm. And so we don’t know for sure how well they’re going to work for large problem sizes and perhaps the only way to find out will be to test them on a large enough quantum computer.
211.1
Now this would be extremely important because not only could it solve this very practical Travelling Salesman Problem, but there are many other optimisation problems important in the industry which can be translated into the Travelling Salesman Problem. So if you can solve the Travelling Salesman Problem efficiently you can solve all these other problems as well. So if we could find the quantum algorithm which solves the Travelling Salesman Problem for large instances, and does it significantly faster than our best classical algorithms, this would be a wonderful example of real world quantum advantage and it would have huge impact around the world.

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. 

Want to keep learning?

This content is taken from UCL (University College London) online course
Introduction to Quantum Computing
View Course
See other articles from this course
This article is from the online course:

Introduction to Quantum Computing

Created by
Join Now
This article is from the free online

Introduction to Quantum Computing

Created by
Join Now
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

Register to receive updates

  • Create an account to receive our newsletter, course recommendations and promotions.

    Register for free