Quantum Traveling Salesman

There was a travelling salesman who wanted to visit several capitals in Europe. He wondered "What order should I do that in, if I want to travel the smallest possible distance?"

This is the same question mathematicians and computer scientists ponder over for more than half a century. Why do we say it is a hard problem?

Because the number of possible solutions explodes exponentially — take a look at the table below.

Cities Combinations Time for full search
5 12 12 microseconds
10 181000 0.18 seconds
20 6.1×1016 2000 years
25 3.1×1023 983 million years

A growing problem

Even for a relatively small number of cities, there are too many possible solutions to search through all of them.

It’s not that we're not able to solve this problem with contemporary computers — we can find “good enough” solutions for millions of cities. But it takes a lot of time and we know our solutions could be better.

Why do we even bother?

Let’s be honest — TSP itself doesn’t have that many crucial applications. But if you slightly modify the problem, for example by adding many salesmen and limiting how many items a given salesman can take, it turns out this is exactly the problem companies like Fedex or DHL are struggling with. Now imagine how hard it must to be to optimize this kind of problems on the national scale.

But solving TSP is just the tip of an iceberg. There are many more problems across all industries that require a similar approach and are equally hard to solve. We call them combinatorial optimization problems. We solve them not only to deliver packages but also to coordinate airplanes, create schedules, improve manufacturing, among other jobs.

How can quantum computers help?

There are plenty of things you can't do with a quantum computer. You can't browse internet, shop online or watch videos. There aren't many conventional usages.

But there are a couple of things they are particularly good at. One of them is solving optimization problems. By leveraging some intrinsic properties of quantum systems, they will be able to make calculations faster and produce better results than classical computers.

Quantum computers are not beating classical computers yet. But this might change even in the next 5 years due to their rapid development. That's why more and more people are excited about this field.

Sounds interesting?

Solve a Travelling Salesman Problem using an actual quantum computer!