Comparison of heuristic approaches to PCI planning for Quantum Computers

Quantum Computing (QC) provides the possibility to develop new approaches to tackle complex problems. Real-world applications, however, cannot yet be managed directly due to the limitation of present and near-future noisy intermediate-scale quantum (NISQ) computers. Decomposition into smaller and manageable subproblems is often needed to take advantage of QC even when using hybrid (classical-quantum) solvers or solvers that already apply decomposition techniques. In this paper, heuristic decomposition algorithms to solve the Physical Cell Identifier (PCI) problem in 4G cellular networks in a way suitable for QC are presented. The PCI problem can be viewed as a map coloring problem with additional constraints and has been represented in a Quadratic Unconstrained Binary Optimization (QUBO) model, a form that, for instance, a quantum annealing machine could crunch. We propose two strategies, with variable decomposition granularity. The first one solves the problem recursively through bisection (max-cut problem), to use only one qubit to represent the status of the objects, avoiding one-hot encoding and thus minimizing the qubit requirement. The second is a multi-step approach, finally solving sets of randomized modified max-k-cut problems of customizable qubit size. We executed the algorithms on real cellular networks of one of the main Italian national telecom operators (TIM). The results show that all proposed QUBO approaches can be effectively applied to very large problems with similar or better performance of the reference classical algorithm, paving the way for the use on NISQ computers.