Noise Resilient Quantom Computing method for Cellular Networks

Researchers successfully implemented a novel algorithm on a PASQAL quantum computer providing the foundations for solving a complex problem in cellular communication networks

While you walk down the street, your smartphone is constantly looking for the nearest cell to connect and transfer data to function. As you continue moving, the signal must be handed over from one cell to another. But you are not alone, almost everyone around you carries devices playing the same game. Cellular communication networks are usually highly dense and for every device to have access to a fair share of the network capacity their structure needs to be very well-planned.

To organize the handover process of mobile signals from one cell to another, networks use identifiers, technically called Physical Cell Identifiers(PCI). These identifiers are limited and constantly reused and their misassignment may lead to multiple impairments, such as call drops or loss of data connection. For example, if both cells in the handover process share the same identifier, a smartphone can interpret the command as if it should stay connected to the same cell and the service will be interrupted. To avoid allocation conflicts, two neighboring cells that use the same radio frequency should have different identifiers.

The physical cell identifier assignment problem can be represented using the so-called graph coloring problem. A graph has dots, called nodes, and lines connecting the dots, called edges. When addressing the cellular network case, each node represents a cell, and if two cells are close enough to each other for the handover process to take place, this proximity can be represented by an edge.

Graph coloring consists in assigning to each node a color such that nodes that share the same edge have different colors. In other words, the rule is that no two nodes sharing an edge can have the same color, as shown in the figure below.

Thus, for the physical cell identifier assignment problem, each different color would represent an identifier. As you already probably guessed, in a dense and intricate cellular network the combinations satisfying this condition may be large and optimizing the number of colors used on its associated graph can be a very complex task.

Neutral atom devices, the best choice to solve the graph coloring problem

Finding the optimal solution for a real-world cellular network by coloring graphs could be computationally overly expensive, motivating scientists and engineers to explore the rapidly emerging synergies between quantum and classical computers. However, many quantum architectures are fundamentally different, and companies and research institutions need to choose which of them suits their needs.

From the variety of quantum technologies, so far developed, neutral atom quantum processors are extremely suitable for approaching graph combinatorial optimization problems, such as graph coloring. For this reason, researchers from the LINKS foundation—specialized in applied research, frontier research, innovation, and technology transfer with strong competencies in High-Performance Computing (HPC) and Quantum Computing—supported by CINECA, have chosen PASQAL’s neutral atom quantum technology to solve a graph coloring problem that emerge in several industrial applications, such as the Physical Cell Identifier (PCI) assignment.

Quantum processing units are still noisy; however, the clever use of these technologies has been able to produce impressive results, and this is pretty much the case. LINKS Quantum Computing team –part of the Advanced Computing, Photonics and Electromagnetics (CPE) research domain- created and successfully implemented a hybrid quantum-classical algorithm on Fresnel, the first PASQAL commercial device and one of the first quantum devices available in the market, showing that their novel method is noise resilient.

“The strongest point of this experiment is that it exploits the characteristics of the PASQAL current machine in such a way that the algorithm is resistant to variations in the results,” said Chiara Vercellino, researcher of the CPE LINKS Quantum Computing team.

“The most impressive part of this implementation is that the results LINKS’ team has obtained are very reliable, even if a QPU (Quantum Process Unit) is still noisy,” said Mauro D’Arcangelo, senior quantum software developer at PASQAL. “Provided that you can embed the graph in our QPU, the algorithm just works. You can use it right now. You only need to have enough atoms in the register to represent the graph that you want.”

But how does this novel algorithm work? Let us take a quick peek.

A novel hybrid classical quantum algorithm to address a crucial cellular network assignment problem

The algorithm’s key idea is to create a tree of graph-colored solutions through a hybrid workflow using both quantum and classical computations. This is how it works: Given a graph, representing a problem that we want to tackle, the quantum device produces as many solutions as possible. Each solution corresponds to one color that has been assigned to the nodes in such a way that, if a node has the color, then its neighbors sharing an edge with it cannot be colored. See some simple examples below.

The classical computer uses the Branch and Bound algorithm to choose the best possible solution produced by the quantum device. At the beginning of the optimization procedure, i.e., at the root of the tree, the graph is uncolored. By calling the QPU, we obtain a set of viable color assignments, each of those generate a branch. Moving along the branches, the colored nodes are removed from the original graph and the quantum device repeats the process for the new graph producing more solutions that will add colors to the graph. The classical algorithm continues choosing the best solutions, and therefore pruning the tree until no node remains uncolored and a satisfactory solution is found.

From coloring dots to coloring atoms

So, why is neutral atom quantum technology ideal to tackle graph problems? The reason is that this hardware uses highly focused and intense lasers, called optical tweezers, to capture atoms individually and manipulate them to create 2D or 3D arbitrary shapes. The ability to position the atoms in any desired configuration is key to tackle graph-based problems. In these architectures, the quantum information is encoded in the atomic energy levels, usually a ground and a very high Rydberg states.

An atom in a Rydberg state physically grows influencing adjacent atoms preventing them from reaching the Rydberg state when they are closer than a certain distance, called blockade distance. The machine uses these properties of atoms in the Rydberg state to naturally represent graphs, where the atoms represent the nodes and, when two atoms are closer than their blockade distance, they are considered connected by an edge.

The research team from LINKS, in collaboration with PASQAL team, implemented their hybrid quantum-classical algorithm to solve the graph coloring problem for four graphs with 7, 7, 10, and 19 nodes. In all four graphs, the algorithm found an optimal coloring solution in excellent agreement with the corresponding numerical simulations.

“During its implementation on a PASQAL quantum device the workflow showed a natural interplay between the classical computer and the quantum processing unit,” said Mauro D’Arcangelo.

“The code ran smoothly on the machine, and we knew from the beginning that we could expect good results,” explained Chiara Vercellino. “The time to solve for many nodes grows exponentially if you consider methods using classical computers only, so for very large graphs we will see the real advantage of using hybrid quantum-classical approaches.”

The novel hybrid quantum-classical algorithm proposed by LINKS team provides the foundations for efficiently solving the Physical Cell Identifier(PCI) assignment problem in cellular networks and for many other applications, such as scheduling jobs (where time slots to work should be efficiently assigned to personnel), scheduling taxis or other forms of public transportation.

Embracing quantum devices as part of computational workflows, and more precisely, neutral atom technologies, may be vital to tackling these and other pressing industrial and scientific problems.

‍