Quantum computing per l’ottimizzazione delle reti mobili (4.5G e 5G)

Quantum computing per l’ottimizzazione delle reti mobili (4.5G e 5G)
 

Il quantum computing è tra le tecnologie innovative di mag­gior interesse, accompagnato da un “hype” sui mezzi di co­municazione per le potenzia­lità che sembrano promettere un impatto disruptive in diver­si campi.

La competizione per la leader­ship tecnologica nel quantum computing è partita da alcuni anni e l’interesse è cresciu­to negli ultimi tempi grazie ai progressi della ricerca e al recente annuncio sul raggiun­gimento della “quantum su­premacy” da parte di Google, cioè l'individuazione di un pri­mo esempio reale di algoritmo implementato sul Quantum Computer, che non può essere elaborato in tempi di calcolo accettabili sui computer clas­sici.

Questi risultati hanno creato grandi aspettative, ma, allo stato attuale di sviluppo del­la tecnologia, si prevede che la disponibilità “commercia­le” di quantum computers con potenze di calcolo elevate e la loro applicazione su larga sca­la, si verificherà su un orizzon­te temporale stimabile tra i 5 e i 10 anni.

Ciò non toglie che il quantum computing possa già essere applicato ad alcuni casi d’uso, sfruttandone opportunamente le capacità computazionali at­tualmente disponibili. È quan­to è avvenuto nel contesto TIM, in cui è stato applicato ad un problema di pianificazio­ne delle reti mobili 4.5G e 5G. I risultati sono incoraggianti avendo ottenuto una maggio­re rapidità di esecuzione (con un fattore 10x) e una qualità media superiore rispetto ai metodi tradizionali di ottimiz­zazione.

 

Introduzione al quantum

L’idea che ha dato origine allo svi­luppo del quantum computing na­sce dall’osservazione che i fenome­ni della natura e le aree scientifiche che dal loro studio sono state de­rivate (fisica, chimica, biologia…), sono governati dai fenomeni della meccanica quantistica. Pertanto, per progredire ulteriormente nella conoscenza di questi campi, è ne­cessario disporre di un computer che abbia una logica computazio­nale che riproduca gli stessi principi, cioè – in altri termini – un’analoga modalità di funzionamento. In que­sto modo, tutte le attività di ricer­ca e sviluppo (elaborazione di dati, definizione di modelli, simulazioni, analisi predittive, ecc.) potranno essere effettuate più facilmente e in maniera più accurata, perché più precisa potrà essere la rappresen­tazione dei fenomeni da analizzare. La caratteristica di questi problemi è quella di avere una complessità computazionale che cresce espo­nenzialmente all’aumentare delle dimensioni dei dati di input.

La complessità di questi problemi, dovuta alla numerosità delle varia­bili, impedisce ai computer classici di eseguire simulazioni o ricerche di ottimizzazione efficaci a causa del loro approccio "lineare e sequenzia­le". La crescita della capacità com­putazionale degli elaboratori classi­ci non è una soluzione praticabile in questo ambito, per cui si è guardato ai fenomeni della meccanica quan­tistica per realizzare degli elabora­tori che cambiassero l'approccio e la metodologia di lavoro. Sono stati così teorizzati e poi progettati i pri­mi computer quantistici che, grazie ad alcune caratteristiche peculiari della meccanica quantistica, per­mettono un’elaborazione parallela e probabilistica in grado di affrontare e risolvere questi casi complessi.[1]

Questo nuovo approccio “quantisti­co” è generalizzabile, perché questa tipologia di problemi si incontra in vari contesti come la chimica dei materiali, la meteorologia, la finan­za.

Pur disponendo di una potenza di calcolo elevata, i quantum compu­ters non sostituiranno i computer classici, ma lavoreranno in siner­gia con questi secondo un modello di computazione ibrida classica – quantistica. Le due tecnologie, in­fatti, sono adatte a classi distinte di problemi: alle famiglie di problemi elaborabili con computer classici, si aggiungono quindi le famiglie adat­te ai quantum computers.

Nei computer classici, l’unità di in­formazione attraverso cui sono co­dificati i dati da processare è rappre­sentata dal bit che può assumere due valori in maniera fra loro esclu­siva (0 oppure 1). Nei computer quantistici l’unità di informazione è, invece, il qubit (quantum bit) che, grazie ai principi della meccanica quantistica che ne sottendono l’im­plementazione, può assumere non solamente i valori 0 o 1, ma anche entrambi contemporaneamente (0 e 1), in uno stato di sovrapposizione intermedio tra i due stati fisici corri­spondenti ai valori 0 e 1. Per usare un’analogia, si può pensare ad una moneta che a seconda di come è po­sizionata può essere rivolta verso il lato “testa” o lato “croce”. Se la mo­neta viene fatta roteare, finché non si ferma entrambe le facce “testa” e “croce” sono contemporaneamen­te possibili; in questa condizione la moneta è come se si trovasse in uno stato di sovrapposizione. Que­sto stato, che nel mondo quantum si chiama superposition, conferisce ai quantum computer quelle carat­teristiche probabilistiche alla base delle loro potenze di calcolo espo­nenziali. Le capacità computazionali dei quantum computers si misurano sulla base del numero di qubit che sono in grado di gestire.

 

Figura 1 - Confronto tra Classical and Quantum Computing Il bit, unità di informazione classica, può assumere solo uno dei possibili valori alla volta (0 OR 1) mentre i qubit, unità di informazione quantistica, possono assumere entrambi i valori (0 AND 1) contemporaneamente (superposition)

Nella famiglia dei quantum compu­ter, si possono distinguere alcune tipologie di processori - anche de­nominati QPU (quantum processing unit) - in base alla tecnologia e alla finalità:

  • Quantum gate array: anche denominato universal quan­tum computer per intendere la macchina in grado di elaborare qualunque processo computa­zionale complesso (qualunque algoritmo quantistico) in forma massiva (senza limitazioni sulle dimensioni dei dati trattati) in tempi rapidi. Si tratta del quan­tum computer così come lo im­maginiamo per analogia con i computer classici, versatile con prestazioni massime, ma anche molto complesso da realizzare, a causa dell’elevato numero di qubit necessari. Per avere un’i­dea del grado di interesse attor­no al quantum gate array, i ven­dor che stanno investendo in questa tecnologia sono IBM, Go­ogle, Microsoft, Intel, Alibaba. I quantum computer attualmen­te più potenti supportano circa 50 qubit e per arrivare a disporre di macchine che ne equipaggi­no alcune centinaia, quantità necessaria per le dimensioni dei problemi che dovrebbero trat­tare, occorrerà, in base alle at­tuali previsioni, aspettare alcuni anni (5 – 10). Per coprire questo gap temporale e poter già ap­plicare il quantum computing a casi d’uso reali, la tecnologia si è orientata anche su soluzioni alternative, descritte nei punti seguenti. [2]
  • Quantum annealer: è un com­puter che utilizza una modalità di elaborazione che riproduce un fenomeno fisico specifico: la tendenza naturale che por­ta un sistema a raggiungere la condizione di equilibrio a mini­ma energia. Modellando quin­di un fenomeno ben definito, è un computer adatto a trattare una classe specifica di problemi, quelli di ottimizzazione di natu­ra combinatoria. Il fornitore più rappresentativo della categoria quantum annealer è canadese, D-Wave che fornisce un pro­cessore di 2000 qubit e ha in roadmap il rilascio commercia­le della sua evoluzione a 5000 qubit nel corso del 2020. La nu­merosità dei qubit così elevata rispetto al quantum gate array, è dovuta al fatto che i quantum annealer non sono macchine universali, ma ottimali per una specifica famiglia di problemi e nella loro modalità di proces­sing la gestione dei qubit è più semplice, semplificando di con­seguenza anche la tecnologia di base. Occorre anche considera­re che la potenza di calcolo del quantum annealer non è in rela­zione diretta col volume di qubit supportati, ma ridotta perché i qubit non sono tra loro connessi a maglia completa.

Attualmente entrambe le tipolo­gie funzionano come dei quantum computer solo se protette in un am­biente pressoché isolato e prossimo alla temperatura dello zero assolu­to. Qualunque minimo disturbo (vi­brazione, variazione di temperatu­ra, rumore, ecc.) provoca la perdita delle loro proprietà quantistiche e di conseguenza le loro capacità computazionali. Queste tipologie di quantum computer, quindi, devono essere installate in ambienti che ga­rantiscono quelle specifiche condi­zioni di isolamento tipiche dei labo­ratori. Per questa ragione l’accesso ai quantum computers attualmente è fornito in modalità cloud attraver­so un’interfaccia, tramite la quale si forniscono i dati di input e il codice dell’algoritmo da eseguire scritto in un linguaggio di alto livello e si ot­tengono i risultati dell’elaborazione.

Per la modalità on-premises, larga­mente diffusa con i computer classi­ci, occorrerà attendere l’evoluzione tecnologica.

In questa fase transitoria, in attesa della piena maturità del quantum computing, si stanno affacciando sul mercato soluzioni che possia­mo definire “QUANTUM INSPIRED”. Si tratta di emulatori Hardware e/o Software che permettono di svi­luppare codice Quantum Ready, eseguendolo inizialmente su pro­cessori lineari come CPU e GPU. Le potenzialità equivalenti di queste soluzioni sono nell’ordine di alcune decine di qubit e quindi compara­bili con le potenze di calcolo degli attuali quantum computer di tipo gate array. Rispetto a questi hanno il vantaggio che i loro qubit sono più stabili, visto che utilizzano hardware classico. Ricordando che la potenza di calcolo dei quantum annealer è inferiore rispetto al dato di targa, i quantum inspired sono comparabi­li - in termini di prestazioni – anche con questa tipologia di quantum computer.

Oltre ai fattori prestazionali, le so­luzioni quantum inspired sono in­teressanti per una serie di ulteriori motivi:

  • il software sviluppato per que­ste piattaforme sarà riutilizza­bile sui computer quantistici di potenza elevata, quando si ren­deranno disponibili
  • offrono un ambiente di sviluppo sul quale acquisire esperienza nella modellizzazione e pro­grammazione quantistica
  • la programmazione quantistica degli algoritmi porta già dei pri­mi vantaggi negli scenari di otti­mizzazione, poiché la corrispon­dente modellizzazione è diversa e abilita la ricerca non lineare di soluzioni al problema
  • utilizzando processori classici (CPU e GPU), ammettono anche la modalità di installazione on-premises o in Edge (sempre che le loro potenze di calcolo siano sufficienti per le applicazioni su cui si intende impiegarli)

La disponibilità di computer quantici di capacità di calcolo elevate, potrà sicuramente ridurre i tempi di ela­borazione di queste stesse procedu­re sviluppate su quantum inspired e contemporaneamente aiutare a trovare le soluzioni ottime, cioè di maggiore qualità.

 

Applicazioni del quantum computing

I computer quantistici sono adat­ti per trattare problemi complessi, che sono rappresentabili con mo­delli multidimensionali nei quali intervengono un numero elevato di variabili e che richiedono, di conse­guenza, tempi di elaborazione mol­to lunghi, talvolta non compatibili con le tecnologie tradizionali.

I casi d’uso che presentano queste caratteristiche sono tipicamente:

  • problemi di ottimizzazione 
    • ottimizzazione nell’asse­gnazione/riuso di risorse soddisfacendo certi vincoli, come per esempio nei casi assimilabili al problema di colorazione delle mappe
    • ottimizzazione di percorsi (esempio tipico è il travel salesman problem) per ge­stione di veicoli, robot, dro­ni, aerei, flusso di traffico ecc.
  • ricerche esaustive su spazi di ri­cerca di grosse dimensioni 
    • applicazioni legate alla crittografia, per sviluppare nuovi protocolli di cifratura resistenti ai quantum com­puter
  • classificazione di dati di grosse dimensioni o per identificazione di pattern ricorrenti 
    • applicazioni per il Machine Learning di image proces­sing, analisi predittive, dia­gnosi
    • set ottimale dei pesi di una rete neurale.

Le applicazioni descritte sono non solo complesse a livello computa­zionale, ma anche – nella maggior parte dei casi – time-critical.

La gestione real-time di questi casi d’uso, che tipicamente viene soddi­sfatta collocando la logica di con­trollo in prossimità del punto di at­tuazione, al momento non è ancora possibile con i quantum computers ma lo diventerà col miglioramento della tecnologia.

Nella prospettiva che il quantum computing diventi una tecnolo­gia adatta per un’installazione on-premises, si può pensare ad un suo utilizzo a livello di edge, proprio per la gestione delle applicazioni time-critical.

Un’alternativa, per disporre di ca­pacità computazionali quantistiche all’edge, è rappresentata dalle solu­zioni quantum inspired, presumibil­mente realizzabili in tempi più brevi e compatibilmente con le prestazio­ni che sono in grado di garantire [3].

 

Un esempio di ottimizzazione della rete mobile: la pianificazione degli identificativi di cella (PCI)

Nell’ambito delle telecomunicazio­ni, problemi di ottimizzazione sono presenti in differenti contesti in cui le risorse sono limitate e condivi­se. Un primo esempio che è stato affrontato e sperimentato con le tecniche di quantum computing è la pianificazione degli identificativi di cella (PCI: Physical Cell Identifier) nelle reti mobili 4.5G e 5G. I

n ambito radiomobile, si definisce “cella” l’unità elementare di terri­torio corrispondente ad una anten­na trasmittente e ad una specifica banda frequenziale. L’identificazio­ne della cella, proprio attraverso il PCI, consente ai terminali mobili di gestire le procedure di mobilità nel passaggio tra celle geograficamen­te adiacenti.

L’identificativo PCI è assegnato a ciascuna cella della rete mobile all’interno di un set predefinito di valori, variabile da sistema a si­stema in base alle specifiche ca­ratteristiche della rete. In termini generali, il PCI è composto da due differenti campi, denominati – ri­spettivamente – Group_ID e Cell_ID; il valore risultante dell’identifi­cativo è espresso, in funzione delle due componenti, mediante la rela­zione:

[Eq1] PCI=3.Group_ID+Cell_ID

La coppia Group_ID e Cell_ID è usa­ta sia per la generazione dei cana­li di sincronizzazione utilizzati dal terminale mobile per agganciarsi correttamente alla cella sulla qua­le intende operare, sia per generare il segnale di riferimento della cella medesima (un vero e proprio “faro”) la cui individuazione è necessaria affinché il terminale possa decodifi­care le informazioni di servizio tra­smesse dal sistema.

L’obiettivo finale della pianificazione dei PCI è la definizione di un “piano” che minimizzi i problemi correlati ai cosiddetti casi di “collision” (PCI uguali assegnati a celle adiacenti) e “confusion” (PCI uguali assegnati a celle aventi un’adiacenza in co­mune) illustrati sinteticamente in Figura 2.

 

Figura 2 - Condizioni di “ collision” e “ confusion” fra celle delle reti 4.5G o 5G

In presenza di tali situazioni, infatti, il terminale mobile può fallire le pro­cedure di mobilità nel passaggio da una cella all’altra e – di conseguenza – subire una caduta di chiamata. Un ulteriore obiettivo, meno priorita­rio rispetto al precedente, è evitare l’assegnazione di PCI con lo stesso Group_ID a nodi geograficamente vicini (“adiacenti”) e operanti sulla stessa banda frequenziale, condi­zione utile – insieme all’uso obbli­gatorio di un medesimo Group_ID all’interno di ciascun nodo – al fine di facilitare le funzionalità di deco­difica.

I problemi di “collision” e “confusion” corrispondono, a tutti gli effetti, a veri e propri vincoli di assegnazio­ne (comunemente detti di “riuso”), che discendono dall’esistenza delle adiacenze di rete e/o elettromagne­tiche specifiche del sistema 5G o LTE e delle adiacenze di rete dovute alla presenza, nel medesimo territo­rio, di celle delle reti 2G e/o 3G.

In tale contesto è importante evi­denziare come la gestione del pas­saggio di una connessione in essere dalle reti di precedente generazione alla rete LTE, sia spesso garantita semplicemente definendo “in adia­cenza” la cella 2G o 3G di interesse e la banda frequenziale LTE verso la quale si intende far migrare la gene­rica chiamata, senza indicazione di specifiche celle della rete 4.5G.

In termini generali, la definizione di un piano dei PCI che soddisfa il maggior numero possibile di vincoli di “riuso” permette di migliorare le prestazioni della rete di accesso e, quindi, la qualità del servizio speri­mentata dagli utenti.

In particolare, una buona pianifica­zione consente di ridurre significati­vamente i tassi di caduta delle con­nessioni in corso, il tutto grazie alla diminuzione dei fallimenti nell’ese­cuzione delle procedure di Hand-Over (cioè il passaggio della connes­sione da una cella ad un’altra). Ciò implica notevoli benefici – in parti­colare – per le connessioni “voce” (chiamate VoLTE, nel contesto LTE) per le quali la velocità di esecuzione e il corretto completamento della procedura sono di fondamentale importanza per ottenere prestazioni adeguate.

Il numero di differenti PCI disponibili ai fini della pianificazione degli iden­tificativi di cella dipende dalla rete considerata ed è pari a 1008 (con numerazione 0÷1007) nel caso 5G e 504 (con numerazione 0÷503) nel caso LTE. Tali valori sono generati mediante la relazione [Eq 1] in base al Group_ID e al Cell_ID, i cui campi di esistenza sono i seguenti:

per 5G

Group_ID ∈ [0; 355] Cell_ID ∈ [0; 2]

per LTE

Group_ID ∈ [0; 167] Cell_ID ∈ [0; 2]

Al fine di meglio quantificare il po­tenziale peggioramento delle pre­stazioni della rete, è associato – al mancato rispetto dei vincoli di “riu­so” – un “costo” dipendente sia dal­la tipologia del vincolo coinvolto, sia dalla numerosità delle violazioni introdotte (una generica coppia di celle, infatti, può violare contempo­raneamente più vincoli di “riuso”, anche della stessa tipologia).

Il costo relativo a ciascun tipo di violazione dipende, quindi, sia dalla conformazione geografica del ter­ritorio – attraverso la copertura del segnale radio garantita da ciascuna cella che incide direttamente sul­la definizione delle adiacenze – sia dall’importanza che si attribuisce a ciascun vincolo non rispettato, che è propria di ogni Telco Operator poiché derivante dalla lunga espe­rienza accumulata nel corso dello sviluppo delle reti.

In conseguenza di quanto descritto e data una generica coppia di celle (i,j), i due fattori di costo sono i se­guenti:

Ci,j costo (“degrado”) dovuto all’as­segnazione dello stesso PCI alle cel­le i e j

Si,j costo (“degrado”) dovuto all’as­segnazione dello stesso gruppo alle celle i e j.

Il costo complessivo (cioè il “degra­do” totale) di un piano di assegna­zione, è dato da una funzione di co­sto contenente i contributi (alcuni di valore nullo) dovuti alla potenziale violazione dei vincoli di “riuso” rela­tivi ai PCI e ai Group_ID di ciascuna possibile coppia di celle oggetto del­la pianificazione.


La funzione assume, quindi, la se­guente forma:

Totcost=ΣiΣjCi,j ⋅ vi,j+ΣiΣjSi,j ⋅ wi,j [Eq 2]

dove:

vi,j = 1 se lo stesso PCI è assegnato alle celle i e j

vi,j = 0 altrimenti

wi,j = 1 se lo stesso Group_ID è asse­gnato alle celle i e j

wi,j = 0 altrimenti.

La pianificazione degli identificati­vi PCI effettuata in coordinamento con l’algoritmo automatico di indi­viduazione delle adiacenze di rete (operante in closed looop sulla base delle misure raccolte dai terminali) è gestita in TIM attraverso la piat­taforma Software Open SON (Self Organizing Network) descritta in [4].

In [5] sono illustrati, inoltre, i risul­tati ottenuti – in termini di miglio­ramento delle cadute VoLTE – at­traverso la pianificazione dei PCI in “closed loop” integrando, all’interno del framework, gli algoritmi di ri­cerca operativa sviluppati da TIM e impiegati anche nelle fasi di proget­tazione della rete.

Nel caso della pianificazione dei PCI, in particolare, è utilizzato un algorit­mo di tipo “Fast Greedy” [6].

L’approccio alla pianificazione dei PCI basato sul Quantum Computing si inserisce nel contesto Open SON, come descritto in Figura 3.

In particolare, il modulo RAN Orche­strator (corrispondente all’applicati­vo TIMqual sviluppato “in house” da TIM) si occupa di gestire lo scambio di informazioni con gli elementi di rete, attraverso le API (Application Programming Interfaces) rese di­sponibili dai sistemi di ACM (Auto­matic Configuration Management) forniti dai RAN vendors nell’ambito dei sistemi di gestione della rete (Element Managers).

L’applicazione del Quantum Com­puting è stata pensata con un ulte­riore scambio di informazioni verso sistemi esterni (nel caso specifico “hosted” presso D-Wave). Un mag­giore livello di integrazione sarà va­lutato nell’ipotesi di disponibilità di quantum computer gestiti “on pre­mises” all’interno della rete TIM.

 

Modellizzazione dell’algoritmo di pianificazione PCI in ottica quantum Computing

Modello QUBO

L’attività di pianificazione degli identificativi di cella (PCI), ha l’obiet­tivo, come descritto, di ottimizzare l’assegnazione rispettando i vincoli di “riuso”.

È quindi un problema di natura com­binatoria analogo, in linea di princi­pio, al problema di colorazione delle mappe geografiche, nelle quali due paesi confinanti devono assumere colori diversi.

Nella classe dei problemi di ottimiz­zazione combinatoria, un framework che trova ampia applicazione è il QUBO (Quadratic Unconstrained Bi­nary Optimization)[7].

In questi problemi, generalmente, intervengono una serie di variabili bi­narie, che possono quindi assumere due soli valori corrispondenti a due stati “netti” (0/1, si/no, on/off...). Ogni combinazione del set di variabili de­termina un risultato che, a seconda del problema, rappresenta un costo o un guadagno.

In termini generali, il QUBO è un mo­dello matematico per ottimizzare un problema che può essere rappresen­tato nella seguente forma:

minimizzare y = xT Qx [Eq 3]

Analizzando la formulazione mate­matica si può notare che:

il problema viene descritto ma­tematicamente in una forma quadratica, nella quale il vettore x rappresenta il set delle variabili di cui occorre trovare la combi­nazione di 0 e 1 ottimale

la matrice Q è composta da ele­menti di valore costante che, oltre a modellare matemati­camente il problema, tengono conto anche dei vincoli a cui le variabili devono sottostare. L’ar­tificio matematico per includere questi vincoli porta ad avere ad una formulazione “compatta”, autoconsistente e quindi “un­constrained”

l’ottimizzazione consiste nell’in­dividuare il minimo della funzio­ne di costo quadratica.

Mettendo assieme gli elementi de­scritti, si ottiene il “Quadratic Uncon­strained Binary Optimization” model, cioè il QUBO.

La generalizzazione del modello ai casi in cui anziché il minimo occorra individuare il massimo, si deriva ri­formulando la funzione obiettivo del problema nel suo opposto negativo; in questo modo il metodo di risolu­zione continua ad essere lo stesso, perché il valore minimo che si ottiene corrisponde al valore massimo del problema originario.

L’attività di sviluppo di un algoritmo di ottimizzazione si può così ricon­durre alla riformulazione del pro­blema secondo il modello QUBO e all’utilizzo delle librerie che risolvono questi casi in maniera efficiente.

Questa metodologia di lavoro con­sente di standardizzare e rendere ef­ficiente l’intero processo.

La grande varietà di problemi a cui il modello è applicabile, unitamen­te all’ampia gamma di piattaforme (CPU e GPU) che supportano le libre­rie software di risoluzione, danno al framework QUBO un ruolo distintivo nell’ambito dei problemi di ottimiz­zazione combinatoria.

A rafforzare ulteriormente l’impor­tanza del modello, contribuisce il fat­to che anche nelle librerie software delle piattaforme di quantum com­puting sono stati integrati solver di risoluzione per il QUBO.

Per quanto visto nell’introduzione, i quantum annealer sono particolar­mente adatti per i problemi di otti­mizzazione di natura combinatoria; per questo motivo l’algoritmo di pia­nificazione PCI, sviluppato secondo il modello QUBO, è stato eseguito sul quantum computer di D-Wave 2000QTM.

Lo stesso algoritmo QUBO è stato elaborato anche su CPU e GPU.

 

Figura 3 - Framework Open SON di TIM e interazione con la piattaforma di Quantum Computing

Modellizzazione pianificazione identificativi di celle

Riprendendo la formulazione mate­matica degli identificativi di cella [Eq 1] unitamente ai vincoli di “riuso”, la modellizzazione del problema – se­condo il framework QUBO – si tradu­ce nella seguente forma:

QUBO=λ1HPCIHC+ λ2HGROUPHC+ λ3HPCISC+ λ4HGROUPSC+ λ5HGROUP_yHC

[Eq 4]

Nella quale intervengono 5 contribu­ti:

HPCIHC esprime il vincolo di utilizzare PCI diversi per celle adiacenti

HGROUPHC esprime il vincolo di uti­lizzare Group_ID differenti per nodi diversi

HPCISC esprime il costo che deriva dall’utilizzo dello stesso PCI su celle adiacenti

HGROUPSC esprime il costo che deriva dall’utilizzo dello stesso Group_ID su nodi adiacenti

HGROUP_yHC esprime il vincolo di uti­lizzare Cell_ID diversi per celle dello stesso nodo.

I pesi di ognuno (le λ) devono essere calibrati per individuare l’area otti­male di lavoro.

L’elaborazione di questo algoritmo “completo”, comprensivo di tutte le componenti, ha però presentato al­cuni problemi:

la calibrazione dei pesi (le λ) è risultata complessa per la quan­tità di parametri (5)

il modello è poco scalabile

la qualità della soluzione non è migliore rispetto al metodo tra­dizionale.

Queste criticità hanno portato così allo sviluppo di un nuovo modello se­guendo una strategia alternativa:

il modello è stato scomposto in fasi computazionali, definite in modo che la complessità com­putazionale di ognuna fosse ge­stibile con i computer classici e quantistici attuali, utilizzandoli anche entrambi con flussi di ela­borazione ibrida

le λ sono state suddivise nelle varie fasi, semplificandone il tu­ning.

Così facendo l’algoritmo QUBO è stato strutturato in due fasi:

  1. primo layer: assegnazione degli identificativi di gruppo (Group_ID) con la definizione di un modello QUBO che coinvol­ge i soli due termini: HGROUPHC, HGROUPSC
  2. secondo layer: assegnazione dei Cell_ID di ogni cella all’interno dei gruppi, utilizzando l’assegna­zione dei gruppi del primo layer, ottenendo così la distribuzione dei PCI di ogni cella. Il corrispon­dente modello QUBO contie­ne quindi i tre termini: HPCIHC, HGROUP_yHC, HPCISC.

I due layer così costituiti, hanno sin­golarmente una complessità com­putazione inferiore rispetto all'algo­ritmo “completo”.

Con questo nuovo modello è sta­to possibile elaborare set di celle di dimensioni significative, ottenendo una qualità migliore rispetto alla procedura di pianificazione dei PCI basata su tecniche combinatorie tra­dizionali.

Una sintesi dei risultati ottenuti è riportata nella sezione sui risultati dell'elaborazione.

 

Segmentazione dei dati di input

Lo sviluppo dell’algoritmo non si è limitato alla sola modellizzazione QUBO, ma è stato necessario tarare i set di celle affinché le loro dimensio­ni fossero gestibili con le potenze di calcolo dei computer a disposizione (CPU, GPU, QPU).

Questo perché la complessità com­putazionale del problema cresce esponenzialmente all’aumentare del numero delle celle.

In funzione dei vincoli sulla potenza di calcolo, sono stati creati dei set di dimensioni massime di alcune cen­tinaia di celle, sulla base delle loro adiacenze.

 

Risultati dell’elaborazione dell’algoritmo QUBO di pianificazione PCI

L’applicazione dell’algoritmo QUBO al contesto della pianificazione dei PCI delle reti 5G e LTE ha fornito ri­sultati incoraggianti dal confronto con quelli garantiti dal Fast Greedy Algorithm già utilizzato nell’ambito del framework Open SON di TIM.

Dal punto di vista dei tempi di calco­lo necessari per definire un piano dei PCI, non è facile effettuare un con­fronto “omogeneo” poiché i criteri di stop dei due algoritmi sono profon­damente diversi. Ciononostante, da misure indicative e tenendo conto del processo complessivo emerge la chiara indicazione di una riduzione del tempo di un fattore 10x, con la prospettiva di ulteriori margini di mi­glioramento.

La riduzione dei tempi di calcolo è di particolare interesse nell’ottica dell’evoluzione della pianificazione dei PCI verso modalità “real-time” (ad esempio attraverso l’integrazio­ne in sistemi di tipo RIC – Radio In­telligent Controller nell’ambito delle architetture definite dalla O-RAN Alliance).

Oltre ai tempi di calcolo, al fine di analizzare le potenzialità dell’algorit­mo su piani di complessità variabile, sono state effettuate una serie di prove diminuendo il numero di grup­pi disponibili (rispetto al massimo consentito dallo standard).

 

Figura 4 - Grafico di confronto su insieme campione

Al diminuire del numero di gruppi, in­fatti, aumenta la probabilità di viola­zione dei vincoli. In tal modo, è stato individuato il minimo numero di PCI necessario per definire un piano ot­timale, cioè tale da soddisfare tutti i vincoli di importanza “prioritaria” (relativi al PCI completo) e sono stati ottenuti i costi complessivi del piano (sia “primari”, sui PCI, sia “seconda­ri”, sul GROUP_ID, valutati mediante la [Eq 2]) quando questo viola uno o più vincoli di “riuso” sull’identificativo di cella completo.

A titolo di esempio, si presentano i risultati ottenuti nel caso di un insie­me campione di 450 celle della rete TIM, riportati in Figura 4:

Come si può osservare, in tutti i casi si ha un miglior comportamento dell’algoritmo QUBO.

Nella zona A, quest’ultimo ottiene soluzioni con un numero di vincoli inferiore rispetto al precedente al­goritmo Fast Greedy (che conferma comunque la propria efficacia), men­tre nella zona B – cioè in assenza di vincoli violati – esso garantisce fun­zioni costo inferiori grazie al minor numero di Group_ID utilizzati (46 contro 50) e ad una più efficace ge­stione del vincolo di “riuso” relativo al GROUP_ID.

 

Verso un applicazione sistematica del Quan­tum Computing

Allo stato attuale, sono in corso svi­luppi dell’algoritmo di pianificazione dei PCI mirati a far evolvere l’algorit­mo QUBO in modo da gestire insie­mi sempre maggiori di celle.
Con questo obiettivo è stata definita una pipeline di lavoro, articolata su tre fasi:

  • una di clustering da realizzare attraverso una procedura di de­composizione dei set di celle in base alle loro adiacenze
  • due fasi successive che corri­spondono ai due livelli di elabo­razione presentati nella sezione descrittiva del modello

prevedendo anche il tipo di hardwa­re (CPU, GPU, QPU) più appropriato per ogni fase, rispetto alla comples­sità computazione che dovranno gestire.

Nel secondo layer di elaborazione è prevista, in particolare, l’invocazione al quantum computer di D-Wave.

L’architettura della pipeline è sche­matizzata nella figura 5.

 

Figura 5 - Pipeline obiettivo di evoluzione dell’algoritmo QUBO di pianificazione PCI

La pianificazione dei PCI della rete mobile è stato il primo caso d’uso affrontato in TIM con un approccio quantistico, utile per verificare l’ap­plicabilità, le implicazioni e i vantag­gi di questa nuova metodologia di programmazione.

È importante evidenziare come in ambito “Telco” sia possibile indi­viduare ulteriori problemi adatti a tale tipologia di approccio e come altri use case siano stati identifica­ti come potenziali candidati per la modellizzazione secondo la meto­dologia quantum.

Se gli studi di fattibilità daranno esi­to positivo – un possibile esempio sono gli algoritmi di Coverage and Capacity Optimization, anche ove basati sull’impiego dell’AI – questi casi d’uso verranno trasportati nel mondo della computazione quanti­stica.

Tra gli use case candidati si stanno considerando alcune applicazioni non real-time e near real-time pro­prie dei RAN Intelligent Controller (RIC) che, secondo il paradigma della open RAN, potrebbero inte­grarsi con le funzionalità real-time proprietarie dei vendor, con le qua­li opererebbero in sinergia a fini di ottimizzazione della gestione delle risorse radio.

Un fattore che favorirà l’utilizzo del quantum è legato al possibile impiego on-premises, per gestire la complessità delle applicazioni time-critical e tra queste, come già accennato, il suo utilizzo a livello di edge.

L’obiettivo di un’azienda come TIM, è – in conclusione – quello di esten­dere ulteriormente l’utilizzo del quantum computing alle applicazio­ni in ambito Telco, per gestire e ri­solvere problemi reali, trarne benefi­cio e migliorare la qualità dei servizi offerti alla clientela grazie a questa tecnologia innovativa.

 

Bibliografia

1. State of Quantum Computing in 2020 for Business Leaders. (s.d.). Tratto da Blog Aimultiple: https://blog.aimultiple.com/quantum-computing/

2. KATWALA, A. (s.d.). Quantum computers will change the world (if they work). Tratto da Wired: https://www.wired.co.uk/article/quantum-computing-explained

3. Quantum Computing Applications in 2020. (s.d.). Tratto da Blog AIMultiple: https://blog.aimultiple.com/quantum-computing-applications/

4. Bertotto, P., Epifani, F., Ludovico, M., & Zarba, G. (s.d.). Open Self-Organizing Network: a continuous development for Radio Access Network performance optimization. Tratto da Telecom Italia: https://www.telecomitalia.com/tit/it/notiziariotecnico/edizioni-2019/n-3-2019/N3-Open-Self-Organizing-Network-continuous-development-for-Radio-Access-Network-performance-optimization.html

5. Bertotto, P., & Zarba, G. (s.d.). Applicazioni “Open SON” nella rete TIM. Tratto da https://www.telecomitalia.com/content/tiportal/it/notiziariotecnico/edizioni-2018/n-1-2018/N6-DigiRAN-valore-automazione-accesso-radio/approfondimenti-2.html

6. B., C. (s.d.). The Greedy Algorithms Class: Formalization, Synthesis and Generalization. Tratto da Université catholique de Louvain: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34.5676&rep=rep1&type=pdf

7. Glover, F. K. (2019, May). A Tutorial on Formulatingand Using QUBO Models. Tratto da Leeds Faculty of Colorado: : http://leeds-faculty.colorado.edu/glover/511%20-%20QUBO%20Tutorial%20-%20updated%20version%20-%20May%204,%202019.pdf

8. Asproni, et al., Accuracy and minor embedding in subqubo decomposition with fully connected large problems: a case study about the number partitioning problem, arXiv:1907.01892v2