Sintesi Tecnica: QAOA con Preservazione dei Vincoli per la Pianificazione del Personale

Definizione del Problema

La pianificazione del personale (personnel rostering) è un problema di ottimizzazione combinatoria caratterizzato da vincoli operativi rigidi, come i requisiti di copertura giornaliera e le restrizioni sui giorni di lavoro consecutivi. Sebbene i metodi classici (programmazione intera, metaeuristiche) abbiano ottenuto successi, la crescita esponenziale dello spazio di ricerca con la dimensione del sistema motiva l'uso di algoritmi quantistici, specificamente il Quantum Approximate Optimization Algorithm (QAOA).

Le formulazioni standard QAOA per problemi vincolati si affidano tipicamente ad approcci basati su penalità. In questo framework, i vincoli rigidi vengono imposti aggiungendo termini di penalità energetica al hamiltoniano di fase. Questo approccio presenta svantaggi significativi:

1. Sensibilità alla Calibrazione: Le prestazioni dipendono fortemente dalla scelta dei coefficienti di penalità.
2. Distorsione del Paesaggio: Penalità elevate possono distorcere il paesaggio di ottimizzazione.
3. Accessibilità di Configurazioni Inammissibili: Le configurazioni inammissibili rimangono dinamicamente accessibili durante l'evoluzione variazionale, permettendo all'ampiezza quantistica di accumularsi in regioni che dovrebbero essere proibite, anche se energeticamente penalizzate.

Il documento affronta la necessità di un framework QAOA che preservi i vincoli, in cui i vincoli rigidi siano incorporati direttamente nell'hamiltoniano del mixer, confinando l'evoluzione quantistica strettamente nello spazio sottostante ammissibile.

Metodologia

1. Formulazione Matematica

Gli autori formulano un problema di pianificazione del personale binario con $N$ lavoratori su $D$ giorni. Lo stato è rappresentato da una matrice binaria $q \in \{0,1\}^{N \times D}$, dove $q_{n,d}=1$ indica che il lavoratore $n$ è assegnato nel giorno $d$.
Il problema consiste nel minimizzare un costo di assegnazione $C(q)$ soggetto a due vincoli rigidi:

• Copertura Giornaliera: $\sum_{n} q_{n,d} = W_d$ (forza lavoro fissa per giorno).
• Nessun Turno Consecutivo: $q_{n,d} q_{n,d+1} = 0$ (nessun lavoratore lavora due giorni di fila).

Lo spazio delle configurazioni è strutturato gerarchicamente:

• $\mathcal{H}$: Il pieno spazio di Hilbert binario.
• $\mathcal{F}_{cov}$: Il sottospazio che soddisfa solo il vincolo di copertura.
• $\mathcal{F}_{full}$: Il sottospazio che soddisfa entrambi i vincoli (il manifold completamente ammissibile).

2. Costruzioni del Mixer

Il documento propone una gerarchia di hamiltoniani del mixer corrispondenti ai settori ammissibili:

• Penalty-X (Baseline): Utilizza un mixer a campo trasversale standard ($\sum X_{n,d}$) e impone entrambi i vincoli tramite penalità energetiche nell'hamiltoniano di fase.
• Coverage-XY: Utilizza un mixer XY che conserva il numero di eccitazioni (conteggio dei lavoratori) per ogni giorno. Questo preserva $\mathcal{F}_{cov}$ dinamicamente, ma richiede ancora un termine di penalità per il vincolo del turno non consecutivo.
• Guarded-XY (Proposto): Introduce un operatore di transizione protetto (guarded transition operator) che incorpora entrambi i vincoli direttamente nel mixer.
  • Meccanismo di Protezione (Guard): Per uno scambio proposto tra i lavoratori $u$ e $v$ nel giorno $d$, l'operatore include un "proiettore di protezione" $\hat{G}$. Questo proiettore valuta lo stato dei giorni adiacenti ($d-1, d+1$) e si annulla se lo scambio creerebbe una violazione del turno consecutivo.
  • Risultato: Il mixer $\hat{H}_{M}^{guard}$ genera transizioni solo all'interno di $\mathcal{F}_{full}$. Di conseguenza, l'hamiltoniano di fase si riduce al solo costo dell'obiettivo ($\hat{H}_C = \hat{H}_{obj}$), eliminando la necessità di calibrare le penalità dei vincoli rigidi.

3. Raggiungibilità ed Estensione del Modello Stretto (Tight-Pattern Extension)

Gli autori identificano che la preservazione esatta della fattibilità non garantisce la raggiungibilità (connettività del grafo ammissibile). Nei segmenti di carico di lavoro "saturati" dove $W_d + W_{d+1} = N$, il vincolo del turno non consecutivo forza assegnazioni complementari, potenzialmente frammentando il grafo ammissibile in componenti disconnesse.

• Soluzione: Viene introdotta un'estensione del modello stretto (tight-pattern extension). Questa aggiunge operatori di scambio collettivi che scambiano interi pattern di assegnazione alternati attraverso i segmenti saturati, ripristinando la connettività all'interno di $\mathcal{F}_{full}$ senza violare i vincoli.

4. Protocollo di Simulazione

Lo studio utilizza simulazioni esatte di stato vettoriale su un caso di benchmark ($N=4, D=4$, carico di lavoro $W=[2,1,2,1]$).

• Confronti: Penalty-X, Coverage-XY e Guarded-XY (con e senza estensione del modello stretto).
• Ottimizzazione: Valutata sia sotto obiettivi di Valore Atteso che di Conditional Value-at-Risk (CVaR, $\alpha=0.2$).
• Calibrazione: I coefficienti di penalità per i metodi baseline sono stati rigorosamente calibrati per garantire un confronto equo, mentre il Guarded-XY non ha richiesto tale calibrazione.
• Inizializzazione: I test hanno incluso sovrapposizioni uniformi sui settori ammissibili e stati iniziali ammissibili localizzati.

Risultati Chiave

1. Eliminazione della Calibrazione delle Penalità

L'approccio Guarded-XY elimina con successo la necessità di sintonizzare i coefficienti di penalità dei vincoli rigidi. L'hamiliano di fase contiene solo il costo di assegnazione, semplificando il paesaggio variazionale.

2. Qualità Superiore della Distribuzione di Uscita

• Fattibilità: Il metodo Guarded-XY mantiene $P_{full} = 1$ (probabilità del 100% di stati ammissibili) per costruzione. Al contrario, Coverage-XY e Penalty-X mostrano perdite (leakage) in regioni inammissibili ($P_{full} < 1$), anche con penalità ottimizzate.
• Concentrazione dell'Ottimo: Sotto l'ottimizzazione CVaR, il metodo Guarded-XY produce costantemente la più alta probabilità di campionare lo schema esattamente ottimale ($P_{opt}$) rispetto agli altri metodi.
• Qualità della Soluzione: Il Guarded-XY raggiunge il più alto rapporto di approssimazione medio ($\langle r \rangle$). Il documento nota che i metodi parzialmente preservanti dei vincoli (Coverage-XY) spesso assegnano una probabilità significativa a programmi inammissibili che hanno costi grezzi artificialmente bassi, il che devia l'ottimizzazione lontano dai veri ottimi ammissibili.

3. Sensibilità Strutturale e Inizializzazione

• Carichi di Lavoro Saturati: L'estensione del modello stretto si dimostra necessaria per mantenere la connettività in scenari di carico di lavoro altamente saturati, impedendo la frammentazione del grafo ammissibile.
• Inizializzazione: Il framework rimane efficace quando inizializzato da un singolo schema ammissibile localizzato (anziché da una sovrapposizione uniforme), a patto di applicare alcuni strati di mixer di "diffusione" (spreading). Ciò suggerisce una strategia di inizializzazione favorevole all'hardware.
• Scalabilità: I test su istanze con diversi conteggi di qubit (12, 16, 20) mostrano che, sebbene la probabilità dell'ottimo grezza diminuisca con la dimensione (a causa del maggiore spazio di ricerca), l'arricchimento dello stato ottimale ($\eta_{opt}$) rimane elevato, indicando che l'algoritmo amplifica costantemente la soluzione ottimale rispetto al campionamento uniforme.

Significato e Rivendicazioni

Il documento sostiene di presentare la prima formulazione sistematica QAOA che preserva i vincoli per la pianificazione del personale, in cui entrambi i vincoli di pianificazione rigidi sono incorporati direttamente nell'hamiltoniano del mixer.

I contributi chiave includono:

1. Spostamento della Gestione dei Vincoli: Spostare l'applicazione dei vincoli dall'hamiltoniano di fase energetico all'hamiltoniano dinamico del mixer, garantendo che l'evoluzione sia confinata nel manifold ammissibile per costruzione.
2. Separazione dei Principi di Design: Distinguere tra preservazione della fattibilità (assicurare che il mixer rimanga nell'insieme ammissibile) e design della raggiungibilità (assicurare che l'insieme ammissibile sia connesso). Il mixer Guarded-XY gestisce il primo, mentre l'estensione del modello stretto gestisce il secondo.
3. Generalizzabilità: Gli autori affermano che il framework dei grafi di transizione e il principio della transizione protetta sono applicabili a una vasta classe di problemi di ottimizzazione quantistica vincolata (pianificazione, routing, allocazione risorse) in cui la fattibilità può essere caratterizzata da regole di transizione locali.

Il lavoro dimostra che i mixer che preservano i vincoli possono produrre distribuzioni di uscita di qualità superiore e una maggiore concentrazione sulle soluzioni ottime rispetto ai metodi basati su penalità, senza la sensibilità alla calibrazione dei coefficienti di penalità.