General circuit mapping algorithm for neutral atom quantum computers

Technische Samenvatting: Algoritme voor algemene circuitmapping voor neutrale atoomkwantumcomputers

Probleemstelling
Neutrale atoomkwantumcomputers (NAQC) bieden een schaalbaar platform dat wordt gekenmerkt door lange coherentietijden, flexibele qubit-configuraties en native multi-qubit gate-mogelijkheden (bijv. CCZ, Ck-fase). Het uitvoeren van kwantumcircuits op NAQC-hardware vereist echter het fysiek verplaatsen van atomen via optische tweezers om qubits in de nabijheid te brengen voor verstrengelingsgates (Rydberg-blokkade). Dit "remapping"-proces introduceert aanzienlijke overhead:

1. Fidelityverlies: Elke transfer brengt een risico op atoomverlies of een verandering van de toestand met zich mee. Hoewel de succespercentages van enkelvoudige transfers hoog zijn (>0,99), worden cumulatieve fouten prohibitief voor circuits met veel qubits of transfers.
2. Tijdsoverhead: Transfers verbruiken tijd, wat het totale berekeningsvenster verkort.
3. Optimalisatieuitdaging: Bestaande compilers (bijv. ZAC, MQT) vertrouwen vaak op heuristieken zoals simulated annealing of greed-algoritmen. Hoewel ze verbeteringen bieden ten opzichte van eerdere methoden, ontbreken ze een expliciete theoretische ondergrens voor het aantal vereiste transfers en bieden ze geen algemene formulering die tegelijkertijd optimaliseert voor de totale afgelegde afstand en parallelle transferoperaties (PTO's) over zowel monolithische (M-arch) als gezoneerde (Z-arch) architecturen.

Methodologie
De auteurs stellen een verenigd, circuit-onafhankelijk wiskundig kader voor op basis van grafentheoretische combinatorische optimalisatie. De methodologie verloopt in vier afzonderlijke stadia:

1. Grafische Representatie (Theoretisch Fundament):

   • Het kwantumcircuit wordt gedecomposeerd in een gerichte acyclische graaf (DAG) waarbij knopen "instructies" vertegenwoordigen (groepen gates die op specifieke qubits werken binnen een stadium) en zijden overgangen tussen stadia vertegenwoordigen.
   • Het probleem van het minimaliseren van transfers tussen stadia wordt gemodelleerd als het vinden van een maximale gewogen matching in bipartiete subgrafen die opeenvolgende stadia verbinden.
   • Stelling 3.1 & 3.2: De auteurs bewijzen dat het minimale aantal transfers voor zowel M-arch als Z-arch kan worden afgeleid door de lokale minima van deze matchings op te tellen. Voor Z-arch wordt de graaf gedecomposeerd in zone-specifieke subgrafen, waarbij verplichte transfers tussen zones plaatsvinden.

2. Stick Encoding (Probleemreductie):

   • Om de fysieke plaatsing van atomen te optimaliseren, introduceren de auteurs een "stick encoding". Deze representatie abstraheert het mapping-probleem door qubits die statisch blijven tussen stadia te groeperen in "sticks".
   • Binnen een stick vormen qubits "substicks". De encoding legt de intrinsieke vrijheidsgraden (DoFs) vast: de 2D ruimtelijke coördinaat van de stick op het atomaire rooster en een Booleaanse variabele die aangeeft of de substicks binnen een multi-qubit stick zijn verwisseld.
   • Deze encoding ontkoppelt de beslissing over welke qubits te bewegen (bepaald door de graafmatching) van de plaatsing van die qubits, wat een efficiënte optimalisatie van de afgelegde afstand mogelijk maakt.

3. Genetisch Algoritme (Optimalisatie):

   • Een Genetisch Algoritme (GA) wordt ingezet om het resulterende niet-lineaire gehele getal programma op te lossen.
   • De GA werkt zonder crossover, maar vertrouwt in plaats daarvan op lokale willekeurige modificaties (het verplaatsen van sticks of het husselen van substicks) om de configuratieruimte te verkennen.
   • De objectieffunctie is flexibel, waardoor de gebruiker kan prioriteren tussen het minimaliseren van de totale afgelegde afstand, het maximaliseren van het aantal parallelle transfers, of een gewogen combinatie van beide.

4. Constructie van Parallelle Transferoperaties (PTO):

   • Een post-processing stap construeert de sequentie van parallelle transfers.
   • Het algoritme analyseert de transfer-digraaf om cycli te detecteren. Als een cyclus bestaat (atomen die elkaars pad blokkeren), wordt een "parkeerplaats" (een lege atomaire slot) gebruikt om de cyclus te doorbreken, wat één extra transfer vereist.
   • Een greed-algoritme plant vervolgens de transfers, waarbij wordt gewaarborgd dat ze compatibel zijn met hardwarebeperkingen (bijv. beperkingen van de Acousto-Optische Deflector) om parallellisme te maximaliseren terwijl botsingen worden vermeden.

Belangrijkste Bijdragen

• Algemeen Wiskundig Kader: Het artikel biedt de eerste grafentheoretische formulering die de theoretische ondergrens bepaalt voor het aantal benodigde atoomtransfers voor elk kwantumcircuit op NAQC-platforms, toepasbaar op zowel monolithische als gezoneerde architecturen.
• Nieuwe Encoding: De introductie van "stick encoding" reduceert effectief de complexiteit van het mapping-probleem door de vrijheidsgraden gerelateerd aan ruimtelijke plaatsing en interne qubit-volgorde te isoleren.
• Controle over Trade-offs: Het kader maakt expliciet een afweging mogelijk tussen het minimaliseren van de totale afstand die door atomen wordt afgelegd (tijd verminderen) en het maximaliseren van parallelle transferoperaties (latentie verminderen).
• Theoretische Garanties: In tegen tegenover eerdere heuristische benaderingen, biedt dit werk bewijsbare ondergrenzen voor transferaantallen (Stelling 3.1/3.2) en demonstreert het dat de voorgestelde methode consequent deze grenzen bereikt.

Resultaten
De auteurs hebben hun algoritme getest tegen state-of-the-art mappers, specifiek ZAC (een reuse-aware zoned architecture mapper) en MQT (Munich Quantum Toolkit).

• Transferaantal: De voorgestelde methode bereikt consistent het theoretische minimum aantal transfers (binnen 0–2 transfers vanwege de vereisten voor het doorbreken van cycli) voor alle geteste circuits. In tegenstelling hiertoe overschrijdt ZAC vaak dit theoretische minimum.
• Afstand en Parallellisme:
  • Bij het optimaliseren voor afstand vermindert de voorgestelde methode de totale afgelegde afstand aanzienlijk vergeleken met ZAC (bijv. ~333% verbetering voor het QFT-circuit).
  • Bij het optimaliseren voor parallelle transfers presteert de methode vaak beter dan zowel ZAC als MQT wat betreft het aantal PTO's, met name voor complexe circuits.
• Flexibiliteit: De resultaten benadrukken een trade-off: het optimaliseren voor afstand leidt niet altijd tot het minimaliseren van de PTO's, en vice versa. De GA stelt gebruikers in staat om de objectieffunctie af te stemmen op basis van specifieke hardwareparameters (bijv. de relatieve snelheid van tweejeretbeweging versus trap switching).

Betekenis en Claims
Het artikel claimt zowel een theoretische baseline als een praktisch hulpmiddel te bieden voor efficiënte, architectuurbewuste kwantumcircuitcompilatie.

• Theoretisch: Het stelt vast dat het minimale aantal transfers kan worden bepaald via graafmatching, wat een benchmark biedt voor toekomstige compilerontwikkeling.
• Praktisch: Het biedt een flexibel optimalisatietool waarmee gebruikers hardware-bewuste mappings kunnen genereren. Door bewegingsgeïnduceerde fouten te verminderen en het gebruik van de parallelliteit van atoomtransfers beter te benutten, verbetert de methode direct de uitvoerefficiëntie op NAQC-apparaten.
• Schaalbaarheid: De aanpak wordt beschreven als algemeen en schaalbaar, in staat om diverse gate-sets (inclusclusief multi-qubit gates) te verwerken en aanpasbaar aan toekomstige NAQC-architecturen met extra zones (bijv. voor CCZ-gates).

De auteurs hanteren een bescheiden toon met betrekking tot de uitvoeringstijd, waarbij zij opmerken dat de optimale keuze tussen het minimaliseren van afstand of PTO's afhangt van specifieke hardwareparameters (bijv. SLM/AOD schakelsnelheid versus tweejeretbewegingssnelheid), die variëren per platform. Zij bevelen aan om de mapper met verschillende parameters te draaien om de beste oplossing voor een specifiek apparaat te selecteren.