Researchers from the LINKS foundation have successfully implemented a novel algorithm on a PASQAL quantum computer to solve a complex problem in cellular communication networks. The problem involves the assignment of Physical Cell Identifiers (PCI) in dense networks, which can be represented using a graph coloring problem. The team used a hybrid quantum-classical algorithm to create a tree of graph-colored solutions. The algorithm was tested on four graphs and found an optimal coloring solution. This method could efficiently solve the PCI assignment problem and other applications such as job scheduling.
Quantum Computing and Cellular Communication Networks
Cellular communication networks are a crucial part of our daily lives, enabling our smartphones and other devices to connect and transfer data. As we move around, our devices constantly search for the nearest cell to connect to, and the signal must be transferred from one cell to another. This process, known as handover, is a complex task that requires careful planning and organization.
Physical Cell Identifiers (PCI) are used to organize the handover process. These identifiers are limited and constantly reused, and their misassignment can lead to issues such as call drops or loss of data connection. To avoid allocation conflicts, neighboring cells that use the same radio frequency should have different identifiers. This problem can be represented using the graph coloring problem, where 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.
Quantum Computing and Graph Coloring
Graph coloring is a complex task that can be computationally expensive. This has led scientists and engineers to explore the synergies between quantum and classical computers. Among the various quantum technologies developed so far, neutral atom quantum processors are particularly suitable for approaching graph combinatorial optimization problems, such as graph coloring.
Researchers from the LINKS foundation, supported by CINECA, have chosen PASQAL’s neutral atom quantum technology to solve a graph coloring problem that emerges in several industrial applications, such as the Physical Cell Identifier (PCI) assignment. Despite the noise in quantum processing units, the researchers were able to produce impressive results by exploiting the characteristics of the PASQAL machine in such a way that the algorithm is resistant to variations in the results.
A Novel Hybrid Classical Quantum Algorithm
The researchers developed a hybrid quantum-classical algorithm to address the cellular network assignment problem. The algorithm creates a tree of graph-colored solutions using both quantum and classical computations. The quantum device produces as many solutions as possible, and the classical computer uses the Branch and Bound algorithm to choose the best possible solution. The process is repeated until no node remains uncolored and a satisfactory solution is found.
Neutral Atom Quantum Technology and Graph Problems
Neutral atom quantum technology is ideal for tackling graph problems because it uses highly focused and intense lasers, called optical tweezers, to capture atoms individually and manipulate them to create 2D or 3D arbitrary shapes. Positioning the atoms in any desired configuration is key to tackling graph-based problems. In these architectures, the atomic energy levels encode the quantum information.
In collaboration with the PASQAL team, the research team from LINKS implemented their hybrid quantum-classical algorithm to solve the graph coloring problem for four graphs. In all four cases, the algorithm found an optimal coloring solution in excellent agreement with the corresponding numerical simulations.
Implications and Future Applications
The novel hybrid quantum-classical algorithm proposed by the LINKS team provides the foundations for efficiently solving the Physical Cell Identifier (PCI) assignment problem in cellular networks. It also has potential applications in other areas, such as job scheduling and public transportation scheduling.
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. As the technology continues to evolve, the time to solve for many nodes is expected to decrease exponentially, highlighting the advantage of using hybrid quantum-classical approaches for very large graphs.
