Scaling Qubit Mapping and Routing With Position Graph Abstraction and Memoization

Dit artikel introduceert een compilatiekader voor Trapped-Ion QCCD-architecturen dat gebruikmaakt van een positiegraaf-abstractie en memoïsatie-technieken om de SABRE-heuristische zoektocht naar qubit-mapping en -routing aanzienlijk te versnellen door redundante berekeningen te elimineren terwijl de besluitkwaliteit behouden blijft.

De kern

Stel je voor dat je probeert een enorme, hoog-risico danswedstrijd te organiseren in een drukke, smalle gang. De dansers zijn qubits (de basiseenheden van quantumcomputers), en het doel is om specifieke paren dansers te laten samenkomen in dezelfde kleine kamer (een "val") om een speciale duet (een quantumpoort) uit te voeren.

Er zijn echter strikte regels:

1. De gang is druk: Je kunt dansers niet zomaar teleporteren; ze moeten fysiek door de gang lopen.
2. Geen dubbel boeken: Slechts een bepaald aantal dansers past tegelijk in een kamer.
3. Verkeersopstoppingen: Als een danser langs een andere danser moet lopen die stilstaat, is het pad geblokkeerd. Je moet eerst uitzoeken hoe je de stilstaande danser uit de weg kunt krijgen.

Dit is de uitdaging van Quantum Compilation voor een specifiek type quantumcomputer genaamd een Trapped-Ion QCCD. Het artikel dat je hebt aangeleverd, beschrijft een nieuw "verkeerscontrolesysteem" dat het organiseren van deze dans veel sneller en efficiënter maakt.

Hier is een uiteenzetting van wat de auteurs hebben gedaan, met eenvoudige analogieën:

1. De oude kaart versus de nieuwe "Positiegrafiek"

Het probleem: Vroeger gebruikten computerprogramma's een simpele kaart genaamd een "Koppelingsgrafiek". Deze kaart was als een metrodigram dat alleen liet zien welke stations met elkaar verbonden waren. Het was geweldig voor computers waar je gewoon twee items verwisselt (zoals het ruilen van stoelen), maar het faalde voor deze ioncomputers waarbij je ionen fysiek door een complex doolhof van gangen en kamers moet verplaatsen.

De oplossing: De auteurs introduceerden de Positiegrafiek.

• Analogie: Denk aan de oude kaart als een lijntekening van een metro. De nieuwe Positiegrafiek is een volledig 3D-architectonisch blauwdruk van het gebouw. Het laat niet alleen zien welke kamers met elkaar verbonden zijn; het toont elke enkele tegel op de vloer, elke gang, elke deur en precies hoe lang het duurt om van de ene plek naar de andere te lopen.
• Waarom dit belangrijk is: Hierdoor kan de computer de echte fysieke beperkingen begrijpen, zoals "Je kunt niet door die muur lopen" of "Die kamer is te klein voor twee personen".

2. Het probleem van de "Verkeersagent" (Congestie)

Het probleem: Wanneer de computer probeert een danser (ion) naar een kamer te verplaatsen, komt het vaak een pad tegen dat geblokkeerd is door een andere danser. De oude software zou stoppen, naar de kaart kijken, een nieuw pad berekenen en het opnieuw proberen. Als het pad opnieuw geblokkeerd was, zou het opnieuw berekenen. Dit was als een GPS die elke keer dat je op een rood licht stuit, de hele route vanaf nul opnieuw berekent. Het was ontzettend traag.

De oplossing: De auteurs creëerden LightSHAW (een "Lichte" versie van hun vorige systeem).

• Analogie: Stel je een verkeersagent voor die een memo-blok (een cache) bijhoudt.
  • Memoïsatie: In plaats van elke keer de afstand van punt A naar punt B opnieuw te berekenen, schrijft de agent het één keer op. Als dezelfde situatie zich opnieuw voordoet, kijken ze gewoon naar de notitie.
  • Het "Blokkageprofiel": Het systeem onthoudt dat "Als je probeert van Gang 1 naar Kamer 5 te gaan, je altijd door Deur 3 moet". Het berekent vooraf de "boete" voor het geval die deur geblokkeerd is.
  • Het resultaat: Wanneer er een file ontstaat, raakt het systeem niet in paniek en berekent het niet alles opnieuw. Het controleert snel zijn notities: "Ah, ik ken deze file. Ik weet precies hoe ik deze kan oplossen." Dit maakt het proces veel sneller.

3. De "Slimme Filter" (Pruning)

Het probleem: Bij het beslissen naar welke kamer een groep dansers moet gaan, controleerde de computer vroeger elke mogelijke kamer in het gebouw en voerde het een volledige berekening uit voor elk ervan.

• Analogie: Het is alsof je probeert het beste restaurant in een stad te vinden door elk restaurant binnen te lopen, een maaltijd te bestellen, het te proeven en dan pas te beslissen.

De oplossing: Ze voegden een Pruning-stap toe.

• Analogie: Voordat je een restaurant binnenloopt, controleert het systeem een "menuvoorvertoning" (een ondergrensscore). Als de voorvertoning zegt: "Deze plek is beslist te duur", slaat het systeem deze direct over zonder er ooit binnen te stappen. Het voert alleen de volledige, dure controle uit op de paar restaurants die veelbelovend lijken. Dit bespaart een enorme hoeveelheid tijd.

4. De grote verrassing: Het werkt ook voor simpele systemen

De bewering: Meestal wordt een computer langzamer wanneer je een kaart gedetailleerder maakt (zoals het overstappen van een metrodigram naar een 3D-blauwdruk), omdat het meer gegevens moet verwerken.

• Het resultaat: De auteurs testten hun nieuwe "Positiegrafiek" op simpele systemen (Supergeleidende computers) die geen complexe 3D-blauwdruk nodig hebben. Ze ontdekten dat het nieuwe systeem even snel was als het oude, simpele systeem.
• Analogie: Het is als upgraden van een papieren kaart naar een GPS-app. Je zou denken dat de GPS langzamer is omdat het meer gegevens heeft, maar ze hebben het zo goed geoptimaliseerd dat het even snel loopt als de papieren kaart voor simpele tochten, terwijl het toch complexe omwegen kan hanteren wanneer dat nodig is.

Samenvatting van de resultaten

Het artikel beweert dat door gebruik te maken van deze nieuwe "Positiegrafiek" en de "LightSHAW"-geheugentrucs:

1. Snelheid: Ze quantumcircuits voor grote, complexe ioncomputers veel sneller kunnen compileren (organiseren) dan voorheen.
2. Schaalbaarheid: Naarmate het aantal dansers (qubits) groeit, groeit de tijd die nodig is om ze te organiseren veel langzamer dan voorheen.
3. Betrouwbaarheid: Het systeem kan "strakkere" gebouwen (overvolle kamers) aan, waar andere systemen volledig falen.
4. Veelzijdigheid: Dit ene systeem kan nu zowel de simpele "swap"-computers als de complexe "shuttling"-computers afhandelen zonder te vertragen.

Kortom, ze hebben een slimmer, sneller verkeerscontrolesysteem gebouwd dat eerdere files onthoudt en slechte routes overslaat, waardoor quantumcomputers complexe dansen kunnen uitvoeren zonder in de file te raken.

Technische samenvatting

Technische Samenvatting: Schalen van Qubit-toewijzing en Routing met Positiegraaf-abstractie en Memoïsatie

Probleemstelling

Schaalbare qubit-toewijzing en routing blijven kritieke knelpunten in kwantumcompilatie, met name voor TI-QCCD-architecturen (Trapped-Ion Quantum Charge-Coupled Device). In tegenstelling tot supergeleidende systemen, waarbij routing wordt gemodelleerd via SWAP-operaties op een statische koppelinggraaf, vereist TI-QCCD het fysiek verplaatsen van ionen door segmenten en kruispunten. Dit proces wordt beperkt door de legaliteit van bewegingen, de capaciteitslimieten van valkuilen en congestie (waarbij tussenliggende posities bezet zijn).

Bestaande heuristische methoden, zoals SABRE, vertrouwen op abstracties zoals Koppelingsgrafen die ontoereikend zijn voor TI-QCCD omdat ze de complexe beperkingen van fysiek transport, tussenliggende bezetting en padblokkering niet kunnen uitdrukken. Hoewel een eerdere studie de abstractie van de Positiegraaf introduceerde om uitvoerbare locaties, bewegingspaden en routingbeperkingen te verenigen, leed de initiële implementatie aan ernstige schaalbaarheidsproblemen. Bijvoorbeeld, het compileren van een 128-qubit circuit op een apparaat met 180 ionen kon een dag duren vanwege redundante berekeningen tijdens heuristisch zoeken en congestieoplossing.

Methodologie

Het artikel stelt een compilatiekader voor dat de Positiegraaf-abstractie verbetert met caching- en memoïsatiestrategieën om redundante berekeningen te elimineren zonder routingbeslissingen te veranderen.

1. Positiegraaf-abstractie

Het kader maakt gebruik van de Positiegraaf ($G_p$), een gelabelde graaf waarbij:

• Hoekpunten bezetbare fysieke locaties vertegenwoordigen (valkuilen, tussenliggende transportgebieden).
• Randen geldige overgangen vertegenwoordigen (swaps binnen een valkuil, samenvoegen/splitsen tussen valkuil en transport, of beweging binnen transport).
• Labels onderscheid maken tussen operationele typen (swap, samenvoegen/splitsen, bewegen).
  Deze abstractie generaliseert de Koppelingsgraaf (gebruikt voor supergeleidende systemen) om de rijkere topologie van TI-QCCD te ondersteunen.

2. Caching op Architectuurniveau

Om overhead te verminderen, berekenen en cache de auteurs architectuurgeafhankelijke grootheden die statisch blijven tijdens een compilatierun:

• Kortste paden en afstandsmatrices voor alle paren.
• Uitvoerbare subgrafen afgeleid van randlabels.
• Profielen van padblokkering: Voor elke bron-doelbeweging een gecachete lijst van tussenliggende posities die blokkering kunnen veroorzaken, samen met vaste straffen voor het oplossen daarvan.

3. LightSHAW: Gememoïseerde Congestieoplossing

De kernbijdrage is LightSHAW, een gecachete variant van de SHAW-heuristiek (SHuttling-AWare). SHAW lost congestie recursief op wanneer een bewegend ion wordt geblokkeerd door een bezette positie. LightSHAW optimaliseert dit via een tweeledige cache:

• Lokale Score-Set Cache: Cache de set nabijgelegen posities om te inspecteren voor een gegeven kandidaat-opruimingsbeweging, waardoor herhaalde graafdoorloop om het zoekgebied te definiëren wordt vermeden.
• Configuratie-gekeyde Congestie Memoïsatie: Memoïseert de congestiescore op basis van een "lokale bezettingssignatuur" ($\sigma$). De sleutel is $(p, t, b, d, \sigma)$, waarbij $p$ de kandidaatpositie is, $t$ het doel, $b$ de blokkering, $d$ de zoekdiepte en $\sigma$ de bezetting van de lokale score-set voorstelt. Dit stelt het systeem in staat scores voor herhaalde lokale congestiepatronen opnieuw te gebruiken zonder het volledige apparaat opnieuw te scannen.

4. Pruning van Valkuilselectie

Om de selectie van doelvalkuilen voor multi-qubit poorten te optimaliseren, implementeren de auteurs een pruningstrategie op basis van een ondergrens. Ze berekenen een optimistische ondergrens voor de routingkosten voor elke valkuil (met inachtneming van congestie en verschillende slotvereisten). Valkuilen worden beoordeeld in oplopende volgorde van deze ondergrens; exacte scoring stopt zodra de ondergrens van de volgende kandidaat de beste tot nu toe gevonden exacte score overschrijdt.

5. Validatie op Supergeleidende Architecturen

Om ervoor te zorgen dat de Positiegraaf geen onnodige overhead oplegt aan eenvoudigere architecturen, hebben de auteurs LightSABRE (een SABRE-variant) geïnstancieerd met zowel een traditionele Koppelingsgraaf-backend als een Positiegraaf-backend. Beide implementaties waren geconfigureerd om identieke routingbeslissingen te nemen, waardoor de kosten van de abstractie zelf geïsoleerd werden.

Belangrijkste Bijdragen

1. Verwijdering van Redundante Berekeningen: Identificatie en caching van kortste MOVE-paden, reistijd-afstanden en padinformatie gerelateerd aan blokkering in SHAW.
2. LightSHAW-algoritme: Introductie van een gememoïseerde procedure voor congestieoplossing die architectuurgeafhankelijke informatie (bewegingspaden, lokale opruimingsgebieden) en lokale bezettingsscores hergebruikt, wat herhaald werk tijdens recursieve blokkeringoplossing aanzienlijk reduceert.
3. Analyse van Abstractie-Overhead: Demonstratie dat de Positiegraaf de Koppelingsgraaf kan vervangen voor LightSABRE-routing met verwaarloosbare runtime-overhead, wat bewijst dat rijkere architectuurmodellen de compilatiesnelheid niet inherent compromitteren.
4. Open-Source Kader: Levering van een implementatie die zowel supergeleidende als TI-QCCD-workflows ondersteunt, wat experimenten over heterogene kwantumarchitecturen faciliteert.

Experimentele Resultaten

De auteurs evalueerden het kader met benchmarks, waaronder QAOA-, QFT- en Hamiltonian-simulatiecircuiten (TFIM, TFXY) variërend van 16 tot 512 qubits.

• Schaling van Compilatietijd: LightSHAW presteert significant beter dan de originele SHAW en de state-of-the-art QCCDSim-simulator wat betreft schaling.
  • SHAW: Schaalt als $O(x^{3.91})$.
  • QCCDSim: Schaalt als $O(x^{3.04})$.
  • LightSHAW: Schaalt als $O(x^{1.72})$.
  • Hoewel LightSHAW voor zeer kleine circuits meer overhead heeft dan QCCDSim, komt het overeen met of overtreft het de prestaties van QCCDSim op grotere circuits (bijvoorbeeld 180-ionen architecturen) en schalt het veel gunstiger.
• Operationstijd (Kwaliteit): LightSHAW produceert schema's met aanzienlijk lagere totale operationstijd (poortuitvoering + transport) in vergelijking met QCCDSim. Bijvoorbeeld, op een 512-qubit QAOA-circuit bereikte LightSHAW een operationstijdverhouding van 0,171 ten opzichte van QCCDSim, wat een ~6-voudige reductie in uitvoeringstijd aangeeft.
• Robuustheid: In strikte scenario's met beperkte middelen (hoge ionbenutting per valkuil) faalde QCCDSim frequent om geldige compilaties te produceren (aangeduid als 'X' in resultaten), terwijl LightSHAW alle instanties succesvol voltooide.
• Compatibiliteit met Supergeleiders: Wanneer toegepast op supergeleidende routing (LightSABRE), kwam de Positiegraaf-backend overeen met de runtime van de traditionele Koppelingsgraaf-backend, wat bevestigt dat de abstractie geen significante straf introduceert voor eenvoudigere architecturen.

Betekenis

Het artikel betoogt dat de Positiegraaf-abstractie een praktische en effectieve weg biedt naar schaalbare qubit-toewijzing en routing over heterogene kwantumarchitecturen. Door architectuurbewuste representatie te combineren met gememoïseerde heuristische evaluatie, lost het kader het schaalbaarheidsknelpunt van TI-QCCD-compilatie op zonder prestaties op supergeleidende systemen te offeren. De resultaten suggereren dat compilerinfrastructuur voorbij minimale nabijheidsmodellen kan gaan om complexe fysieke beperkingen (zoals transport) te ondersteunen, terwijl de efficiëntie die nodig is voor grootschalige kwantumcompilatie behouden blijft. Het werk stelt vast dat een verenigde representatie zowel SWAP-gebaseerde als transport-gebaseerde architecturen kan dienen, waardoor een enkel kader diverse hardwarebeperkingen kan afhandelen.