Reducing the costs of deploying a 5G network with a hybrid classical-quantum approach
In an era of increasing demand for data traffic and rapid expansion of the internet of things, the fifth generation of cellular communications, 5G, was set to enhance the internet connectivity already accomplished by the 4G networks. Innovations behind 5G have allowed its networks to achieve reliability, higher data transfer speed, and improve the response delay between devices compared to the former generation of cellular networks.
This advanced communications technology already proved its remarkable capabilities to save lives in 2019, when surgeons performed long-distance robotic interventions, remote controlled—some of them over thousands of kilometers—using 5G in China, Spain, Italy, and Germany.
In wireless communications, the information travels on electromagnetic waves, typically in the radio spectrum, and communication companies use specific frequencies of these electromagnetic waves to transmit information. To avoid interference between services, the government regulates the rights to emit radio frequencies, and companies have to pay for the rights to transmit signals in specific frequency bands using the auction method.
Acquiring the rights to use frequencies for communications is costly; therefore, companies need to calculate with high accuracy how many and which frequencies they need. To perform these calculations, companies consider many options, such as the number of antennas, the distances between them, and which frequencies they need to avoid interference while ensuring good coverage. These kinds of problems often come with a variety of options to combine, for this reason they are called combinatorial optimization problems.
Finding the best option, a big headache in classical computing
Combinatorial optimization consists of finding the “best option”, according to some criteria, out of a–often a very large—collection of options. In real-life problems, like the 5G frequencies assignment problem, the number of all options companies need to consider before purchasing the rights to use frequencies can be prohibitively large for traditional computers to handle, even for the most powerful classical computers.
A popular approach to tackling such industrial combinatorial optimization problems consists of restricting the number of options to a subgroup and solving the sub-problem associated to that subgroup. This sub-problem is called the Restricted Master Problem.
But hold on, solving the Restricted Master Problem is not solving the real original problem. So, more work needs to be done. The following step is to create several iterations generating new options to be added to the Restricted Master Problem at each iteration and check if the result improves. The new sub-problem created and solved on each iteration is called the Pricing Sub-problem. The process stops when the result does not improve by adding new options. This approach is called the Column Generation method.
Although column generation is a powerful algorithm because it simplifies complex problems, the step involving generating new options is, in many cases, still extremely challenging and costly in classical computing.
A hybrid classical-quantum method to find the best option
At PASQAL, we have recently proposed a complete hybrid classical-quantum column generation method in which we solve the Restricted Master Problem using classical computing and generate the new options using quantum computing.
Our scientific article shows that incorporating our quantum approach into state-of-the-art classical algorithms improves their performance by dramatically reducing the number of iterations needed to find accurate results.
Compared with several state-of-the-art classical approaches, our hybrid classical-quantum pricing reduces the number of iterations needed to find accurate solutions using the Column Generation approach by up to 83%.
“I have extensive experience using classical computing approaches to solve telecommunications network problems, and I know that in the column generation approach the bottleneck is exactly on how to generate new options to tackle the Restricted Master Problem. Now, with our quantum methods we can hope to solve the full problem with fewer iterations, enhancing the quality of the final solution”, says Wesley Coelho, quantum computing applications engineer at PASQAL.
How does this method work? Let’s explore the details.
Finding the best option by coloring dots
Combinatorial problems can naturally be represented with graphs, where data are composed of elements represented by dots called vertices or nodes, and the lines drawn between them, or edges, represent the connection between those elements.
The edges may encode different information, such as the importance of the connections (generically called weights). We can also assign labels to differentiate the vertices, and is there anything more practical than using colors as labels?
For several optimization problems that can be translated into graphs, we use colors as labels to find what are called independent sets. An independent set in a graph is a group of vertices such that no pair of elements in the group are connected by an edge. The idea is to use as few hues as possible by coloring vertices that are not connected by an edge with exactly the same color, but using different colors if they are connected by an edge. In this way, each group of nodes with the same color represents an Independent Set.
In vertex coloring problems, the original problem that we want to solve translates into finding the minimum number of Independent Sets that can cover all graph nodes exactly once. By doing so, you can minimize the number of colors you need to cover your graph while respecting the constraints imposed by the problem.
Now, let’s go back to our main example and see how we can represent the 5G network deployment problem using this method.
Solving the 5G frequencies problem by coloring graphs
Suppose a company wants to deploy 5G antennas in a city and get the rights to use the needed frequencies from the government. For the company to buy the rights to use as few frequencies as possible and save money, it must consider deploying enough antennas to achieve good communicational covering. But, at the same time, these antennas cannot use the same frequencies if they are too close to each other because the signals will interfere.
This is a perfect example of a problem that can be solved using graphs. What we do is represent each antenna with a vertex on a graph. If two antennas are closer than a threshold for their signals to interfere, the related nodes are connected by an edge. Then we proceed to “paint” the graph letting a different color represent each frequency. In this way, we have each independent set colored with the same color, which means that the antennas in each independent set can use the same frequency.
So, in this problem, finding the minimum number of independent sets, minimizing the number of colors we use, will minimize the number of frequencies the company will need to buy in the auction, optimizing the costs.
A promising outlook
Until now, we have been emulating our hybrid classical-quantum approach to column generation algorithm using Pulser, our open-source Python library. We have emulated different PASQAL quantum processors, including perfect noiseless and noisy ones. Even with noise, our methods performed better than other methods that we have tested using only classical computing. The next step is to implement our method in our actual quantum processors.
“In almost all hybrid approaches, classical computing is used to help quantum computing. In our approach, we are using quantum computing to help classical computers to solve combinatorial optimization problems.” Wesley Coelho remarks.
Combinatorial optimization is at the heart of a variety of industry applications, such as the logistics of delivering goods from a warehouse to clients, finding efficient ways to distribute electricity, or deploying a new communication technology, such as the 5G technology. With our approach, we are definitely on the way to helping solve these problems reliably and efficiently, —moving closer to near-term quantum advantage.
References
- Da Silva Coelho, W., Henriet, L., Henry, L-P. (2023). A quantum pricing-based column generation framework for hard combinatorial problems. Phys. Rev. A 107(3). https://link.aps.org/doi/10.1103/PhysRevA.107.032426. Preprint available: 2301.02637.pdf (arxiv.org).
- Henriet, L., Beguin, L., Signoles, A., Lahaye, T., Browaeys, A., Reymond, G. O., & Jurczak, C. (2020b). Quantum computing with neutral atoms. Quantum, 4, 327. https://doi.org/10.22331/q-2020-09-21-327.
Photo by Scott Elkins.