Making decisions is commonly a challenge due to the uncertainty and overwhelming information needed to deal with a problem: from every engineering design, data analysis or most business decisions to even the choice of the queue at the supermarket, life is, in essence, a lot of optimization problems. These are ubiquitous in science and society, as wise decisions must be made constantly among several possibilities to achieve the best solution among all feasible ones.

For example, imagine a truck driver who must visit several European destinations. He needs to do it as fast as possible to save time and gas since both commodities are expensive, and our driver is environmentally conscious. In addition, depending on the day of the week, traffic suffers considerable fluctuations.

The problem of the street vendor

The above-described problem is an instance of the Traveling Salesman Problem (TSP), a well-known combinatorial optimization problem. The TSP main character -in our case, the truck driver– wants to visit some cities, but no more than once each. In his way, he also wants to take the shortest time/distance/expenditure possible. After racking his brain to find which path he should take tomorrow, by naïvely swapping the order of the destinations and calculating the corresponding total distance, he gives up. How many possible routes has he tried, and how many has he left to try?

In fact, the number of possible routes can be proved to be the factorial of the number  of cities, a concept mathematicians represent with an exclamation mark as . Although it is easy to pose, this is a vast number to handle. For example, in the following table, you can see the horrible scaling that this problem has as the number of cities grows:

To see how large this last number is, you can compare it, for example, with the estimated number of atoms in the observable universe . It is so big that it is impossible to find the shortest route by checking every possible path, even for the most powerful computers. No wonder our track driver gave up. However, how can one deal with such problems to reach the desired solution if that is the case?

Physics-inspired algorithms to solve optimization problems

The TSP belongs to the so-called combinatorial optimization problems. For these problems, we need to look for a given combination of items (in our case, the different paths) which performs best than all the others. Most of them are as hard as the TSP itself; fortunately, Physics comes to our help in this struggle.

Most of these combinatorial optimization problems can be written as instances of a well-known Physics problem called the spin-glass model. It consists of a network of spins, arrows pointing up and down, in layman’s terms. These spins are not isolated, but they interact between themselves: some want to point in the same direction as their neighbours, whereas others prefer the opposite. The amazing fact is that, by tailoring these interactions, these spins’ final order (the system’s ground state) can tell us which is the best route for our truck driver. Therefore, if we can solve the spin-glass model by finding that ground state, we can solve an apparently totally different problem, such as the TSP.

However, solving the spin-glass model is not an easy task either. This is due to its complex energy landscape. This means that many spin configurations look like the actual ground state but aren’t. When one navigates through the different spin orders, it is usual to get stuck at these fake ground states. This is especially true when we don’t use randomness to help our search. Most optimization methods that don’t rely on randomness are prone to get stuck on these fake ground states, having no way out of them.

In contrast, stochastic methods such as Simulated Annealing, Population Annealing or Parallel Tempering Monte Carlo leverage randomness to navigate this vast solution space. They can break from these fake ground states to reach the actual one. However, they need a lot of random numbers to get them free of these artificial ground states. In fact, they need so many of these that their generation becomes a bottleneck for faster simulations.

Quside’s technologies, such as the Quantum Random Number Generator (QRNG), provide the high-speed, high-quality randomness source required by these algorithms. With its help, these stochastic algorithms overcome their bottlenecks, improving their efficiency and effectiveness.