Dear Reader,

this article is supplementary to the Quantum Traveling Salesman Demo we’ve recently created — so if you’ve not done it yet, please take a moment to explore it(Edit June 2020: Unfortunately the app stopped working some time ago. Perhaps this article still might have some value for the reader though. The source code is here if someone wants to play with that.).

I’d like to tell you the story of how and why our demo was created and how it works. And in the course of the story, I’ll also show you how contemporary quantum computers work and what they are capable of.

This post is intended for people who don’t know anything about quantum computers — if you have trouble understanding anything, please let me know so I can make it simpler!

One last thing: I use two abbreviations here: TSP for the Traveling Salesman Problem and QC for Quantum Computing.

The story

In spring 2018, Rigetti Computing released an awesome demo. It was a webpage where you could solve a MaxCut problem and check if you are doing it faster than a quantum computer. It was really fun!

Unfortunately, it’s no longer online and I’ve not seen any similar applications since then. I think it’s a great way of showing people how quantum computers work and therefore I’ve decided to build a similar demo, but for solving the Traveling Salesman Problem.

Since I had already written an algorithm for doing it, I decided to apply for a grant from the Unitary Fund and write a series of tutorials explaining how to solve this problem with a quantum computer and build this demo app (you can read my story here). Since part of the code I wanted to use had already been already written for some projects at Bohr Technology(my employer), I decided to do it as a joint project — funded and supported in part by both the Unitary Fund and Bohr Technology.

How does it work?

The results you see when you use the app are actually calculated by a quantum computer — specifically, D-Wave quantum annealer (see the picture above). For me, the fact that I can access a machine that was thought to be science fiction just a couple of years ago, is pretty mind-blowing. In this section I’d like to go into the details of how it works.

How the app works

When you open the application, you are presented with a set of cities on a map. You select a few cities, click on the “Find optimal route” button and the goal of the application is to find the best route when traveling from one city to another. Let us delve into the details.

1. Selecting cities

You are first asked to select a minimum of 4 cities. If the number of cities is too small, it’s not fun. We cannot also make it too large because the power of quantum computers is still limited (for now).

2. Clicking the “Find optimal route” button

After selecting the cities and clicking the button, the application takes the data about the coordinates of the cities and translates it into a so-called distance matrix. You can think about it as a table which stores all the distances between the cities.

3. Translation

In order to communicate with any type of computer, you need to speak its language. Fortunately, we usually don’t use plain 0s and 1s — rather, we use programming languages or applications. In the case of quantum computers, it’s similar. We can write programs for quantum computers using something akin to programming languages. But if we want to solve an optimization problem on a D-Wave computer, we don’t even need to know this “programming language” — we can write this program in the form of QUBO (Quadratic Unconstrained Binary Optimization). Explaining what QUBO is is beyond the scope of this article, though again, in our case it’s basically a table storing all the information about our problem in a specific format. So what we do is we take the data we got from the application (distances between cities), add the constraints (we can’t be in the same city more than once and we can’t visit more than one city at the same time) and create a QUBO. If you are curious about what this code looks like (either for D-Wave or other types of quantum computers), you can take a look at our repository with the quantum TSP solver.

4. Sending problem to the Quantum Computer

Now that we have our QUBO, we can send it to D-Wave. We do that with a simple HTTP request (though we need a special token to access it). Then it waits in a queue. This part is responsible for most of the waiting time in the application. The more people are trying to use the quantum computer at the same time, the longer the waiting time is.

5. Inside the QPU

Finally, our problem reaches the QPU (Quantum Processing Unit — i.e. the actual quantum chip). QUBO is encoded in the magnetic field interacting with the qubits (quantum bits) and after a short time (20 microseconds in our case) we can measure the state of the qubits and get the solution. This process is not perfect and we don’t always get the solution with the shortest possible distance. Sometimes we get another, suboptimal, solution. To have higher confidence that we got the optimal solution, we need to repeat this process multiple times and send back all the results. You can read more about this works in this article.

6. Grand finale

Once we calculate the solution, we can send it back to our application. Our application selects the solution with the shortest total distance of all the samples that it got, decodes it and displays it on the map in the application.

TSP — why it’s important?

In this section I’d like to elaborate on why TSP-like problems are important and hard to solve and why quantum computers might help with solving them.

Why it’s hard

TSP is one of the problems from the family of combinatorial optimization problems. The issue with these problems is that the number of possible solutions grows extremely fast. To get some intuition on how fast, take a look at the table below. Of course, checking all the solutions one by one is not a reasonable approach in such cases and we have algorithms that solve them in much more clever ways. We can divide these algorithms into two classes — exact and approximate methods.

Cities Possible routes
5 12
10 181000
20 6.1 x 1016
25 3.1 x 1023

When it comes to the exact methods, they allow us to get the exact solution to our problem; so they do indeed find the shortest path between the cities. Unfortunately, it comes with a price: while these methods scale much better than a brute-force approach (i.e. simply checking all the possible options), the size of the problem you can work on is limited. To get some perspective, solving for 33000 cities would take an average computer 15 years and for 85000 cities — 136 years (source).

That’s why we often use approximate methods — here we don’t have any guarantee of finding an optimal solution. It’s even worse — we sometimes don’t even have any mathematical explanation for why a given method should work. But these methods can give us a solution that’s close enough to the optimal one (e.g. 2-3% worse). They’re also much quicker and can handle much bigger problem sizes, like millions of cities.

Why it’s important

Solving TSP might seem unrelated to real problems. I mean — how often in your life have you heard about problems like this at a scale that’s actually hard to solve , e.g. tens of thousands of cities?

But as it often happens with algorithms (and in much of scientific work) — we first focus on a simpler version of the problem and then adjust our method to work well with the more advanced variations.

So imagine that you have a delivery company and every day you need to deliver 1000 packages. You have 20 couriers and your clients have preferences on when they want to get the package. It’s definitely not TSP in the traditional sense, but it’s a TSP-related problem and some methods that we use for solving TSP can help us solve this problem. Oh, and remember that you actually can’t spend 130 years calculating the solution, since every day is different.

Everyone likes to get their packages on time, and there are similar problems in other industries such as airlines, manufacturing and transportation, to name a few.

Furthermore, there is a whole family of other problems that are equally hard to tackle and could be solved with somewhat similar methods.

Solving them better and faster could save a lot of money across multiple industries, but also make your life much easier.

Putting quantum computers in the picture

Ok, we know that TSP and other similar problems are important. But what do quantum computers have to do with them? Well, we want to solve bigger problems and do it faster and/or better. And classical computer architectures are hitting their limits.

Limits of classical computing

You’ve probably heard about Moore’s Law. It states (more or less) that the power of computers doubles every two years. The problem is that today the pace of improvement is significantly slower. There are a couple of reasons for that:

  • transistors are so small that quantum effects start affecting them, which is not necessarily desirable — further miniaturization is no longer possible.
  • it’s hard to dissipate heat from such small devices efficiently.
  • there are limits of how big speedup we can get from using devices in parallel, thus adding more and more cores does not improve the overall performance (see Amdahl’s law),
  • in general, it’s getting harder and harder for companies to justify the huge effort that has to be put on developing new processor generations.

That’s why more and more specialized computers (ASICs) are built, which can solve a limited number of tasks, but much faster than regular CPUs. In the last couple of years there has been plenty of new interesting announcements, like TPU (Tensor Processing Units), neuromorphic chips, memristors or quantum computing.

The potential of quantum computing

I think there are two main reasons why people get excited about QC.

What entices a lot of people is the novelty of this field, the blend of physics, engineering and computer science, the unexplored possibilities. Also, for physicists, the fact that QC will make it possible to simulate some quantum systems and hence understand many quantum phenomena is very important. This, in turn, may allow us to design better materials, drugs or batteries.

Additionally, there is a promise of a bright future where adding a single qubit to the quantum computer doubles its computational power. It’s very different compared to a regular computer, where you need to double the size of the computer to double its power.

A future where we will be able to solve optimization problems in a couple of seconds instead of several hours or days. A future where we will be able to simulate complex molecules and their interactions with incredible precision and at an incredible pace. Think about room temperature superconductors, materials capturing CO2 from the atmosphere or catalysts that will make some industrial processes 100 times more energy efficient.

To put it simply: doing QC allows you to work on incredibly interesting problems and the potential payoff is enormous.

Current state of quantum computing

Well, the future might seem bright, but when we look at what we have at hand, it’s dim at best.

To do some of the grandiose things described earlier, we would need around 500 perfect fully connected qubits. For less grandiose, but still impressive tasks, a 100 should be enough. So how many of those qubits do we have today?

Zero.

So what do we have?

We are in the era of NISQ — Noisy Intermediate Scale Quantum devices. This means, that even though we are talking about 20-70 qubits, they are so crappy, that you can’t do anything useful with them. The first reason for that is that they are extremely sensitive to all types of noise — that’s one of the reasons why they need to operate in the temperature of 15 mK. And every interaction with the outside world might end up with the destruction of the quantum state. The second reason is that you usually can’t make two arbitrary qubits interact with each other — and this limits their computational power significantly. The third reason is that in order to be useful, these machines have to outcompete regular computers which have at least a 50 years head start.

And keep in mind, that the “crappy” machines we are talking about here are marvels of contemporary engineering, with dedicated teams of people working on refining this technology.

There is one caveat here — D-Wave quantum annealer, that we were talking about earlier, has actually 2000 qubits. But this is a totally different type of qubits and this number has nothing to do with the numbers provided in this paragraph, it’s like comparing apples to oranges. Yes, I know it’s confusing :(

Discouraged? I know how you feel. But keep reading — there is hope :)

Hybrid quantum computing

The most prevalent way of doing QC today, arguably, is called hybrid classical-quantum computing. The idea is simple — there are some things that classical computers can do extremely well and there are certain things that quantum computers can do extremely well. Both of them also have their own limitations. So why not leverage the best in those two types of hardware?

Example: we know that it will be hard to solve TSP for huge numbers of cities on a quantum computer — our hardware still has a long way to go before it gets there. But at some point, a quantum computer will be able to solve TSP for, let’s say, 50 cities much faster than a regular computer. So it might turn out that the following hybrid algorithm will work better than the classical one:

  • Divide 1 million cities into groups of 50 cities.
  • Solve each group using a quantum computer.
  • Combine smaller solutions together.

(For a more technical description of how this kind of problems might be tackled, take a look here).

Can we prove mathematically that if we’re able to solve TSP for 50 cities on a quantum machine, the hybrid algorithm will beat the classical one?

No.

And that’s the trick! Because in practice, it means that we have no idea when quantum computers will become truly useful. We don’t even know what will be the first problem that they will help to solve. And this is actually natural for new technologies — scientist 50 years ago didn’t realize that computers will be so ubiquitous and important in our everyday life. The true applications only revealed themselves when people could get their hands on the real machines.

Many of the people in this industry will tell you that it will probably happen in the next 2-5 years, so somewhere between 2021-2024. This is only an educated guess, but it’s actually pretty hopeful considering how many problems current hardware needs to deal with.

So…

DIY

If you simply want to learn more about QC and its applications:

  1. Wired guide
  2. BCG report on QC
  3. Great talk by John Preskill and interview with him as well

If you would like to experiment with QC yourself:

  1. Leap — a platform which gives you access to the actual D-Wave machine. Right now it’s accessible only in North America, but access for people in Europe should be available in Spring 2019. It has plenty of tutorials and other resources that will help you start.
  2. Forest and IBM Q — also good platforms with access to real quantum computers and helpful communities.
  3. At Bohr.Technology we are interested in solving optimization problems with quantum computers. Here you can find algorithm very similar to the one we used for this demo. If you would like to help us develop these algorithms, feel free to apply to our bqResearch program
  4. If you are interested in how to solve TSP problem with a universal quantum computer, please take a look at the tutorials I’ve created.
  5. Quantum Open Source Foundation is also a place with plenty of great resources for beginners.

Team & closing notes

If I had to work on this project alone, it would never see the light of day. So here are the people that made it possible:

Doing stuff:

Letting things happen:

Reviewers: Thanks to all of you, especially Ntwali Bashige and Rafał Ociepa!

If playing with the web app or reading this article prompted you to explore the realm of quantum computing — please let me know. Among the few pleasures of an author, knowing that their work influenced other people in positive ways is appreciated. Send me an email if that’s the case for you :)

And, as always, if you have any other feedback, regarding the app or this article, no matter how small, don’t hesitate to write! My e-mail: michal@mustythoughts.com.

Have a nice day!

Michał