Technische Samenvatting: Constraint-Preserving QAOA voor Personeelsplanning

Probleemstelling

Personeelsplanning is een combinatorisch optimalisatieprobleem dat wordt gekenmerkt door harde operationele beperkingen, zoals dagelijkse bezettingsvereisten en restricties op opeenvolgende werkdagen. Hoewel klassieke methoden (integer programmeren, metaheuristieken) succes hebben geboekt, motiveert de exponentiële groei van de zoekruimte met de systeemgrootte het gebruik van quantumalgoritmen, specifiek het Quantum Approximate Optimization Algorithm (QAOA).

Standaard QAOA-formuleringen voor beperkte problemen vertrouwen doorgaans op penalty-gebaseerde benaderingen. In dit kader worden harde beperkingen afgedwongen door energetische penalty-termen toe te voegen aan de fase-Hamiltoniaan. Deze aanpak heeft significante nadelen:

1. Kalibratiesensitiviteit: De prestaties zijn sterk afhankelijk van de keuze van de penalty-coëfficiënten.
2. Landschapverstoring: Grote penalties kunnen het optimalisatielandschap verstoren.
3. Onbereikbaarheid van onhaalbare configuraties: Onhaalbare configuraties blijven dynamisch toegankelijk tijdens de variationele evolutie, waardoor quantumamplitude kan accumuleren in regio's die verboden zouden moeten zijn, zelfs als deze energetisch worden bestraft.

Het artikel adresseert de behoefte aan een constraint-preserving QAOA-framework waarbij harde beperkingen direct in de mixer-Hamiltoniaan worden ingebed, waardoor de quantumevolutie strikt binnen de haalbare subspace wordt gehouden.

Methodologie

1. Wiskundige Formulering

De auteurs formuleren een binair personeelsplanningsprobleem met $N$ werknemers over $D$ dagen. De staat wordt gerepresenteerd door een binaire matrix $q \in \{0,1\}^{N \times D}$, waarbij $q_{n,d}=1$ aangeeft dat werknemer $n$ op dag $d$ is toegewezen.
Het probleem behelst het minimaliseren van een toewijzingskostenfunctie $C(q)$ onder twee harde beperkingen:

• Dagelijkse Bezetting: $\sum_{n} q_{n,d} = W_d$ (vaste personeelssterkte per dag).
• Geen Opeenvolgende Diensten: $q_{n,d} q_{n,d+1} = 0$ (geen werknemer werkt twee dagen achter elkaar).

De configuratieruimte is hiërarchisch gestructureerd:

• $\mathcal{H}$: De volledige binaire Hilbertruimte.
• $\mathcal{F}_{cov}$: De subspace die alleen de bezettingsbeperking voldoet.
• $\mathcal{F}_{full}$: De subspace die beide beperkingen voldoet (het volledig haalbare manifold).

2. Mixer Constructies

Het artikel stelt een hiërarchie van mixer-Hamiltoniaanse voor die overeenkomen met de haalbare sectoren:

• Penalty-X (Baseline): Gebruikt een standaard transverse-field mixer ($\sum X_{n,d}$) en dwingt beide beperkingen af via energetische penalties in de fase-Hamiltoniaan.
• Coverage-XY: Gebruikt een XY-mixer die het aantal excitaties (werknemersaantal) voor elke dag conserveert. Dit behoudt $\mathcal{F}_{cov}$ dynamisch, maar vereist nog steeds een penalty-term voor de beperking van geen opeenvolgende diensten.
• Guarded-XY (Voorgesteld): Introduceert een guarded transition operator die beide beperkingen direct in de mixer inbedt.
  • Guard-mechanisme: Voor een voorgestelde uitwisseling tussen werknemers $u$ en $v$ op dag $d$, bevat de operator een "guard projector" $\hat{G}$. Deze projector evalueert de status van naburige dagen ($d-1, d+1$) en wordt nul als de uitwisseling een schending van de opeenvolgende dienst zou creëren.
  • Resultaat: De mixer $\hat{H}_{M}^{guard}$ genereert transities alleen binnen $\mathcal{F}_{full}$. Bij consequentie bevat de fase-Hamiltoniaan alleen de objectieve functie ($\hat{H}_C = \hat{H}_{obj}$), waardoor de noodzaak voor kalibratie van hard-constraint penalties vervalt.

3. Bereikbaarheid en Tight-Pattern Extensie

De auteurs identificeren dat exacte haalbaarheid-preservatie geen bereikbaarheid (connectiviteit van de haalbare graaf) garandeert. In "verzadigde" workload-segmenten waar $W_d + W_{d+1} = N$, dwingt de beperking van geen opeenvolgende diensten complementaire toewijzingen af, wat potentieel de haalbare graaf fragmenteert in niet-verbonden componenten.

• Oplossing: Een tight-pattern extensie wordt geïntroduceerd. Deze voegt collectieve uitwisselingsoperatoren toe die volledige alternerende toewijzingspatronen over verzadigde segmenten wisselen, waardoor de connectiviteit binnen $\mathcal{F}_{full}$ wordt hersteld zonder de beperkingen te schenden.

4. Simulatieprotocol

De studie gebruikt exacte statevector-simulaties op een benchmark-instantie ($N=4, D=4$, workload $W=[2,1,2,1]$).

• Vergelijkingen: Penalty-X, Coverage-XY, en Guarded-XY (met en zonder tight-pattern extensie).
• Optimalisatie: Geëvalueerd onder zowel Expectation-Value als Conditional Value-at-Risk (CVaR, $\alpha=0.2$) doelstellingen.
• Kalibratie: Penalty-coëfficiënten voor baseline-methoden werden rigoureus gekalibreerd om een eerlijke vergelijking te garanderen, terwijl Guarded-XY geen dergelijke kalibratie vereiste.
• Initialisatie: Tests omvatten uniforme superposities over haalbare sectoren en gelokaliseerde haalbare starttoestanden.

Belangrijkste Resultaten

1. Eliminatie van Penalty Kalibratie

De Guarded-XY aanpak elimineert succesvol de noodzaak om hard-constraint penalty-coëfficiënten af te stemmen. De fase-Hamiltoniaan bevat alleen de toewijzingskosten, wat de variationele landscape vereenvoudigt.

2. Superieure Kwaliteit van de Outputdistributie

• Haalbaarheid: Guarded-XY handhaaft $P_{full} = 1$ (100% waarschijnlijkheid van haalbare toestanden) door constructie. In contrast vertonen Coverage-XY en Penalty-X lekkage naar onhaalbare regio's ($P_{full} < 1$), zelfs met geoptimaliseerde penalties.
• Optimale Concentratie: Onder CVaR-optimalisatie levert Guarded-XY consistent de hoogste waarschijnlijkheid van het samplen van de exacte optimale planning ($P_{opt}$) vergeleken met de andere methoden.
• Oplossingskwaliteit: Guarded-XY bereikt de hoogste gemiddelde benaderingsratio ($\langle r \rangle$). Het artikel merkt op dat gedeeltelijk constraint-preserverende methoden (Coverage-XY) vaak een significante waarschijnlijkheid toekennen aan onhaalbare schema's die kunstmatig lage ruwe kosten hebben, wat de optimalisatie wegstuurt van ware haalbare optima.

3. Structurele Sensitiviteit en Initialisatie

• Verzadigde Workloads: De tight-pattern extensie is aangetoond noodzakelijk te zijn voor het behoud van connectiviteit in zeer verzadigde workload-scenario's, om te voorkomen dat de haalbare graaf fragmenteert.
• Initialisatie: Het framework blijft effectief wanneer het wordt geïnitialiseerd vanuit één enkele gelokaliseerde haalbare planning (in plaats van een uniforme superpositie), mits er enkele "spreading" mixer-lagen worden toegepast. Dit suggereert een hardware-vriendelijke initialisatiestrategie.
• Schaalbaarheid: Tests op instanties met variërende qubit-aantallen (12, 16, 20) laten zien dat hoewel de ruwe optimale waarschijnlijkheid afneemt met de grootte (door de grotere zoekruimte), de optimale-toestand verrijking ($\eta_{opt}$) hoog blijft, wat aangeeft dat het algoritme de optimale oplossing consistent versterkt ten opzichte van uniforme sampling.

Betekenis en Claims

Het artikel claimt het eerste systematische constraint-preserving QAOA-formulering voor personeelsplanning te presenteren waarbij beide harde planningsbeperkingen direct in de mixer-Hamiltoniaan zijn ingebed.

Belangrijke bijdragen zijn onder meer:

1. Verschuiving in Constraint Handling: Het verplaatsen van de handhaving van beperkingen van de energetische fase-Hamiltoniaan naar de dynamische mixer, waardoor de evolutie door constructie binnen het haalbare manifold wordt gehouden.
2. Scheiding van Ontwerpprincipes: Het onderscheid maken tussen feasibility preservation (waarborgen dat de mixer in de haalbare set blijft) en reachability design (waarborgen dat de haalbare set verbonden is). De Guarded-XY mixer behandelt de eerste, terwijl de tight-pattern extensie de tweede afhandelt.
3. Generaliseerbaarheid: De auteurs stellen dat het transitie-graaf framework en het principe van de guarded transitie toepasbaar zijn op een brede klasse van beperkte quantumoptimalisatieproblemen (planning, routing, resource allocatie) waarbij haalbaarheid kan worden gekarakteriseerd door lokale transitie-regels.

Het werk demonstreert dat constraint-preserving mixers een hogere kwaliteit van outputdistributies en een sterkere concentratie op optimale oplossingen kunnen opleveren dan penalty-gebaseerde methoden, zonder de sensitiviteit voor penalty-coëfficiënt kalibratie.