Minor Embedding for Quantum Annealing with Reinforcement Learning

Dit artikel presenteert een Reinforcement Learning-benadering met Proximal Policy Optimization voor het efficiënt oplossen van het minor embedding-probleem bij kwantum-annealing, waarbij het model succesvol schaalbare en aanpasbare oplossingen toont voor diverse probleemgrafieken op moderne hardware-topologieën zoals Zephyr.

De kern

🧩 De Grote Puzzel: Hoe we een computer helpen om te dromen

Stel je voor dat je een enorme, ingewikkelde puzzel hebt. Je wilt deze oplossen met een heel speciale soort computer: een Quantum Annealer. Deze computer is als een genie dat kan "dromen" om het beste antwoord te vinden voor moeilijke problemen, zoals het plannen van een logistieke route of het ontwerpen van een nieuw medicijn.

Maar er is een probleem: deze quantum-computer is een beetje als een ouderwetse, starre speelgoeddoos. Hij heeft vaste vakjes (qubits) die op een heel specifiek patroon liggen. Sommige vakjes kunnen met elkaar praten, maar andere niet.

De problemen die we willen oplossen (zoals die logistieke route) zijn echter als een losse hoop blokken die overal met elkaar verbonden moeten kunnen zijn. Ze passen niet in de starre doos van de computer.

De Oplossing: "Minor Embedding" (De Kunst van het Inprikken)

Om het probleem in de computer te krijgen, moeten we het "inpassen". Dit heet Minor Embedding.

• De uitdaging: Als twee blokken in je probleem met elkaar moeten praten, maar in de computer zitten ze niet naast elkaar, dan moet je een "brug" bouwen. Je gebruikt meerdere blokken in de computer om één blok in je probleem te vertegenwoordigen. Je koppelt ze aan elkaar met een sterke lijm (koppeling), zodat ze als één geheel gedragen.
• Het probleem: Dit inpassen is een nachtmerrie voor de computer. Het kost meer tijd om de puzzel in de doos te krijgen dan om de puzzel daadwerkelijk op te lossen! De oude methodes zijn als een trage, stijve robot die probeert de blokken erin te duwen. Soms lukt het, soms niet, en vaak gebruikt hij veel te veel blokken (wat de computer verwarrend maakt).

De Nieuwe Helden: Een Leerling met Reinforcement Learning

De auteurs van dit paper hebben een nieuwe aanpak bedacht. In plaats van een stijve robot, hebben ze een Leerling gemaakt die leert door te proberen. Dit noemen ze Reinforcement Learning (Versterkend Leren).

• Hoe werkt het? Stel je voor dat je een kind leert een kamer in te richten.
  • De Leerling (de AI-agent) kijkt naar de kamer (de quantum-computer) en de meubels (het probleem).
  • Hij probeert een meubel ergens neer te zetten.
  • Beloning: Als hij slim kiest en de kamer blijft overzichtelijk, krijgt hij een puntje. Als hij de kamer volstopt met meubels die niet nodig zijn, krijgt hij een klein strafje.
  • Straf: Elke stap die hij zet kost tijd. Dus hij leert snel om de kamer zo efficiënt mogelijk in te richten.
• De methode: Ze gebruikten een slimme versie van deze leerling genaamd PPO (Proximal Policy Optimization). Deze leerling probeert, faalt, leert van zijn fouten en probeert het opnieuw, tot hij een perfecte indeling heeft gevonden.

Het Experiment: Oude vs. Nieuwe Speelgoeddozen

De onderzoekers testten hun leerling op twee soorten quantum-computers:

1. Chimera: De "oude" speelgoeddoos. De blokken hierin hebben maar een paar buren (maximaal 6). Het is hier lastig om alles met elkaar te verbinden zonder een enorm wirwar van bruggen te bouwen.
2. Zephyr: De "nieuwe", moderne speelgoeddoos. Hier hebben de blokken veel meer buren (tot wel 20). Het is hier makkelijker om bruggen te bouwen.

Wat ontdekten ze?

• Op de oude doos (Chimera): De leerling deed het redelijk bij kleine puzzels, maar bij grote, ingewikkelde puzzels raakte hij in de war. Hij maakte veel fouten en gebruikte soms veel te veel blokken. Het was alsof hij probeerde een kasteel te bouwen in een krappe slaapkamer.
• Op de nieuwe doos (Zephyr): Hier was de leerling een ster! Omdat de blokken meer buren hebben, kon hij de puzzel veel makkelijker en efficiënter inpassen. Hij slaagde bijna altijd en gebruikte weinig blokken.

De Magische Truc: "Data Augmentation" (De Spiegels)

Er was nog een slimme truc. De leerling had moeite om te begrijpen dat een kamer die gedraaid of gespiegeld is, eigenlijk nog steeds dezelfde kamer is.

• De truc: Tijdens het leren lieten ze de leerling de kamer in verschillende hoeken zien (gedraaid, gespiegeld, etc.).
• Het resultaat: Bij willekeurige, chaotische puzzels hielp dit enorm. De leerling werd flexibeler en leerde de "essentie" van het probleem, in plaats van alleen de specifieke positie van de blokken. Bij de zeer strakke, volgepropte puzzels (waar alles met alles verbonden is) hielp deze truc minder, maar bij de losse puzzels was het een game-changer.

Conclusie: Wat betekent dit voor de toekomst?

Dit onderzoek laat zien dat we niet hoeven te wachten tot quantum-computers perfect zijn. We kunnen slimme AI-agenten gebruiken om de brug te slaan tussen onze complexe problemen en de beperkte hardware.

• De les: De nieuwe quantum-computers (Zephyr) zijn veel beter geschikt voor deze slimme leerling.
• De toekomst: Hoewel de huidige leerling (die een simpele hersenstructuur heeft) al goed werkt, denken de onderzoekers dat de volgende generatie leerlingen, die specifiek zijn gebouwd om patronen te zien (zoals "Graph Neural Networks"), nog veel slimmer zullen worden.

Kortom: We hebben een slimme, lerende assistent gevonden die helpt om de quantum-computers van morgen veel sneller en efficiënter te gebruiken.

Technische samenvatting

1. Probleemstelling: Minor Embedding in Quantum Annealing

Quantum Annealing (QA) is een paradigma voor het oplossen van combinatorische optimalisatieproblemen, vaak geformuleerd als Quadratic Unconstrained Binary Optimization (QUBO). Een cruciale stap in dit proces is Minor Embedding (ME). Omdat de fysieke qubits van een Quantum Processing Unit (QPU) slechts beperkt verbonden zijn (via specifieke topologieën zoals Chimera of Zephyr), moet het probleemgraf (waarbij variabelen verbonden zijn) worden gemapt op deze schaarse hardwaretopologie.

• De uitdaging: Als een probleemvariabele meer verbindingen nodig heeft dan de hardware toelaat, moet deze worden vertegenwoordigd door een keten (chain) van meerdere fysieke qubits.
• Huidige beperkingen: Bestaande methoden, zoals de heuristiek minorminer (ontwikkeld door D-Wave), zijn vaak specifiek ontworpen voor bepaalde grafen of hardware. Ze zijn computatief duur, schalen slecht bij toenemende probleemgrootte, en bieden weinig flexibiliteit om de optimalisatiedoelstellingen aan te passen. Langere ketens verhogen de kans op fouten (ketenbreuken) tijdens het annealing-proces, wat de kwaliteit van de oplossing beïnvloedt.

2. Methodologie: Reinforcement Learning (RL)

De auteurs stellen een nieuwe aanpak voor waarbij Minor Embedding wordt behandeld als een sequentiële besluitvormingsopgave binnen het kader van Reinforcement Learning.

• Agent en Algorithm: Er wordt een agent getraind met Proximal Policy Optimization (PPO), een actor-critic algoritme dat bekend staat om zijn stabiliteit en efficiëntie.
• Architectuur: De agent gebruikt een Multi-Layer Perceptron (MLP). Hoewel Graph Neural Networks (GNNs) theoretisch beter zouden passen voor grafstructuren, kiezen de auteurs voor een MLP vanwege de eenvoud en trainbaarheid, en compenseren ze het gebrek aan ingebouwde graf-invariantie via data-augmentatie.
• State Observatie (Toestand): De agent ontvangt een observatievector die bestaat uit vier componenten:
  1. Beschikbare qubits op de hardware (binair masker).
  2. Ontbrekende links in het probleemgraf (hoeveel verbindingen nog nodig zijn).
  3. Huidige knoop (welke probleemvariabele moet nu worden toegewezen, bepaald door een Round-Robin strategie).
  4. Huidige keten (welke qubits horen bij de huidige variabele).
• Actie: De agent kiest een fysieke qubit om aan de keten van de huidige variabele toe te voegen.
• Invalid Action Masking (IAM): Om de zoekruimte te beperken en de agent te dwingen geldige stappen te zetten, worden ongeldige acties (bijv. niet-beschikbare qubits of niet-aangrenzende qubits) gemaskeerd (kans = 0) in de policy-output.
• Beloningsfunctie (Reward): De agent ontvangt een vaste negatieve beloning (-0,1) voor elke stap. Dit motiveert de agent om een geldige embedding te vinden met zo min mogelijk stappen (dus zo kort mogelijke ketens).
• Data Augmentatie: Om de beperkingen van de MLP-architectuur (geen inherente symmetrie-invariantie) te overwinnen, worden tijdens het trainen symmetrische transformaties toegepast op de hardwaregraf (rotaties, spiegelingen, permutaties). Dit helpt de agent om robuustere patronen te leren die onafhankelijk zijn van de specifieke labelering van de qubits.

3. Experimentele Opzet

De auteurs testen hun model op twee hardwaretopologieën:

1. Chimera: De oudere, minder verbonden topologie (max. 6 verbindingen per qubit).
2. Zephyr: De nieuwere, meer verbonden topologie (max. 20 verbindingen per qubit).

Twee scenario's worden onderzocht:

• Volledig verbonden grafen: Een specifieke, moeilijke klasse van problemen.
• Willekeurig gegenereerde grafen: Grafen met variërende grootte (3-10 knopen) en dichtheid om generalisatie te testen.

De prestaties worden vergeleken met de standaard minorminer tool.

4. Belangrijkste Resultaten

A. Succesratio en Schaalbaarheid:

• Chimera: De succesratio van de RL-agent daalt sterk naarmate de probleemgraf groter wordt, vooral bij grotere hardware-omvang. De agent heeft moeite met het modelleren van complexe ketens in de minder verbonden Chimera-topologie.
• Zephyr: De RL-agent presteert uitzonderlijk goed op Zephyr, met een 100% succesratio voor alle geteste grafen, zelfs bij grotere maten. De hogere connectiviteit van Zephyr maakt het voor de agent makkelijker om geldige ketens te vinden.

B. Kwantum-efficiëntie (Qubit Efficiency Ratio - QER):

• De QER meet hoeveel qubits de RL-agent gebruikt ten opzichte van minorminer (waarbij 1 ideaal is).
• Bij kleine grafen en kleine hardware-omvang presteert de agent vergelijkbaar met minorminer.
• Bij grotere hardware-omvang (grote $H_{size}$) bij kleine probleemgraf ($|G|$) neemt het aantal gebruikte qubits door de RL-agent onnodig toe. Dit suggereert dat de agent moeite heeft om de grote zoekruimte efficiënt te navigeren en "verdwijnt" in de grote hardwaregraf, terwijl minorminer compacte oplossingen vindt.
• Data Augmentatie Effect:
  • Bij volledig verbonden grafen had data augmentatie een wisselend effect; soms verbeterde het de succesratio, soms verslechterde het de efficiëntie.
  • Bij willekeurige grafen was data augmentatie (zowel tijdens training als testing) cruciaal. Het leidde tot een aanzienlijke reductie in het aantal benodigde qubits. Zonder augmentatie explodeerde het aantal qubits bij grotere grafen; met augmentatie bleef het laag en stabiel.

C. Training en Convergentie:

• De training toont stabiele convergentie, vooral op de Zephyr-topologie. De episode-lengte (aantal stappen) neemt af en stabiliseert, wat aangeeft dat de agent efficiëntere strategieën leert.
• Bij zeer grote hardware-omvang (grote $H_{size}$) vertoont de training soms stagnatie of suboptimale lokale minima, wat wijst op de beperkingen van de MLP-architectuur in hoge-dimensionale actie-ruimtes.

5. Bijdragen en Betekenis

Kernbijdragen:

1. RL-gebaseerde aanpak: Het introduceren van Minor Embedding als een sequentiële beslissingsopgave opgelost met PPO.
2. Data Augmentatie Strategie: Het ontwikkelen van specifieke augmentatietechnieken (rotaties, spiegelingen, permutaties) om de symmetrie-invariantie van de hardware te benutten binnen een MLP-architectuur.
3. Uitgebreide Vergelijking: Een gedetailleerde analyse van prestaties op zowel Chimera als Zephyr, en op zowel volledig verbonden als willekeurige grafen.

Significantie en Toekomstperspectief:

• Flexibiliteit: De RL-aanpak biedt meer flexibiliteit dan traditionele heuristieken, omdat de beloningsfunctie en doelstellingen eenvoudig kunnen worden aangepast.
• Hardware-afhankelijkheid: De resultaten tonen aan dat de prestaties van ML-modellen sterk afhankelijk zijn van de hardware-topologie. De verbeterde connectiviteit van moderne hardware (Zephyr) compenseert gedeeltelijk de beperkingen van het huidige model.
• Beperkingen en Toekomst: De huidige MLP-architectuur heeft moeite met het modelleren van complexe grafstructuren en schaalt niet optimaal naar zeer grote problemen. De auteurs suggereren dat Graph Neural Networks (GNNs) een veelbelovende volgende stap zijn, omdat deze architecturen de grafstructuur en symmetrieën inherent kunnen modelleren, wat de trainings-efficiëntie en robuustheid zou kunnen verbeteren.

Kortom, dit werk toont aan dat Reinforcement Learning een haalbaar en flexibel alternatief is voor Minor Embedding, met name op moderne hardware, maar dat de keuze van de modelarchitectuur en trainingsstrategie (zoals data augmentatie) kritiek is voor succes.