What can quantum computers do for us? In this blog, I will explain from a technical point of view how a quantum computer performs an optimization using a classic routing challenge as an example.

Solving optimization problems faster

Consider a company that needs to deliver thousands of packages to addresses in the Netherlands. They have a fleet of trucks and they want to optimize the route that each truck takes. This is a huge problem that is difficult to solve for classical computers given the massive number of possible routes. Quantum computers however, take a completely different approach to this problem. To illustrate the power of quantum, let’s look at a scaled down version of this problem.

Using a quantum algorithm to find the fastest

route

Suppose we have 1 truck that is tasked with driving to Amsterdam, Rotterdam and Den Haag, starting in and returning to Utrecht. What is the best order of visiting the cities? The table below contains all travel times between the cities in minutes. We will represent each of these segments with a qubit. Recall that a qubit is in a superposition of 1 and 0. Only upon measuring will the qubit take on one of these two values. If we measure a 1, we will travel over the corresponding segment, if the outcome is zero, we do not. The quantum algorithm is therefore responsible for manipulating the qubits in such a way that if we measure each qubit, it will give 1 for segments that are part of the optimal route, and 0 for segments that are not part of the optimal route.

Table 1: Travel times between cities in minutes.

Figure 1: A schematic view of all possible segments connecting the cities Amsterdam, Utrecht, Den Haag and Rotterdam. The segments are labelled S₀ to S₅.

Step 1: formulate the problem

The first step now is to formulate the problem as a mathematical equation. I will skip the mathematics here, but I will sketch the idea behind it. If you are interested, the Traveling Santa blog explains very well how to get this equation.

Each segment of the route that we will take has a cost associated to it. In our case it is the number of minutes it will take to travel between two cities. Let’s assume the measurements on our qubits yields 101011. That would mean we travel over segments S₀, S₂, S₄, and S₅, which corresponds to a route from Utrecht to Den Haag, then to Amsterdam, Rotterdam and finally back to Utrecht (see Figure 1). This will take us 219 minutes of driving time. The goal is to minimize the number of minutes, however because these are qubits, we could also measure 000000. This route will take 0 minutes, so that’s better right? To ensure that the quantum algorithm that minimizes the driving time optimizes for a valid route, we add constraints in the form of penalties. For example, we can add a penalty of 100 minutes for each city that is not on the route. After you have identified all constraints, you end up with a lengthy equation as input for the algorithm.

Step 2: manipulate qubits

The next step is to find a way to manipulate our qubits such that upon measuring, the qubits that belong to segments that are part of the optimal route have a high probability to yield a value of 1. This will be done using a hybrid algorithm; it consists of a quantum part and a classical part. The quantum part manipulates the qubits based on the lengthy equation and a set of parameters passed to the algorithm. The purpose of these parameters will become evident in a little. The quantum part returns an estimate of the driving time for the current quantum state, including the penalties for invalid routes, to the classical part. Note the word ‘estimate’ in the previous sentence. The stochastic nature of quantum mechanics causes measurements on the exact same state to return different routes, with different duration.

As a simple example, consider a two-qubit quantum state that has a probability of 25% to be measured as 01, and 75% to be measured as 10 (and 0% for 00 and 11). Let’s say route 01 takes 9 minutes, and route 10 takes 5 minutes, then we will measure the 5-minute route 3 times more often than the 9-minute route. On average, we can say that measurements on this state yields a route that takes 6 minutes. It is impossible however, to know the probabilities of the individual routes. All we know is that the way this state is currently prepared will yield a driving time of 6 minutes on average, if we were to perform many measurements on it. The important realization here is that the lower average driving time, the higher the probability of measuring a short route.

Figure 2: The rescaled driving time as a function of the number of steps of the optimizer.

Information of the average driving time is then passed to the classical part. The classical part is an optimizer that tweaks the set of parameters passed to the quantum algorithm as to minimize the average driving time. In Figure 2 you can see the optimizer lowering the estimated driving time. Since we are running on a simulator, we can also inspect the quantum state during the optimization. So, to better understand what is happening, we plot in Figure 3 the probability of measuring each state during the optimization. On an actual quantum computer, we would not have access to this information.

Figure 3: Probability of measuring each state for 6 qubits after 0 optimization steps (top-left), 500 optimization steps (top-right), 3400 optimization steps (bottom-left), and 5000 optimization steps (bottom-right). The peaks in the bottom-right picture occur at 010111, 101011, and 111100.

In the top left picture, no optimization has been done, and each combination of routes to take and not to take have equal probability. The average driving time is relatively high (Figure 2 at 0 optimization steps). After approximately 3400 optimization steps, three states start to stand out. And in the final picture, we can see that 010111, 101011 and 111100 have a significantly higher probability to be measured than any other state. These 3 states are the only states that correspond to valid routes that visit each city exactly once. Among each other, 111100 has the highest probability to be measured. This state corresponds to driving along segments S₀, S₁, S₂ and S₃, or in words: starting in Utrecht, go to Rotterdam, then Den Haag, Amsterdam, and finally back to Utrecht (or in the exact opposite order). Indeed, we can calculate that of these three routes, this is the fastest with a total travel time of 182 minutes.

Step 3: measure the optimized route

In step 2 we found a way to manipulate the qubits such that, upon measuring, there is relatively high probability to find the shortest route, but that is still a probability. So the final step is to repeat the optimal manipulation found by the optimizer multiple times. With enough measurements, the result that pops up the most corresponds to the optimal route.

Using better optimization and preparation algorithms than the ones currently implemented, it is possible to prepare a quantum state that has a larger than 80% probability to give an optimized solution to the problem.

In these series on quantum computing I tried to give a practical introduction to quantum computing as concise as possible. If you want to learn more, don’t hesitate to contact me. I am more than happy to talk in more depth about quantum computing and programming.