⚛️ quantum physics

MOSAIQC: Mixed-topology-aware Optimization for Scalable Approximate noise-Informed Quantum circuit Cutting

MosaiQC is een nieuw framework dat een hybride warmstart met verfijningsoptimalisatie en een snelle benaderende quadratic assignment solver gebruikt om mixed-topology, mixed-size hardwarepartities mogelijk te maken, wat de lokale getrouwheid aanzienlijk verbetert terwijl de runtime en sampling-overhead voor schaalbare quantum circuit cutting drastisch wordt verminderd.

Oorspronkelijke auteurs: Koen Mesman, Yinglu Tang, Matthias Moller, Boyang Chen, Sebastian Feld

Gepubliceerd 2026-07-22

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Koen Mesman, Yinglu Tang, Matthias Moller, Boyang Chen, Sebastian Feld

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je probeert een enorme, onmogelijke legpuzzel op te lossen, maar je hebt slechts een pieklein tafeltje om op te werken. Je kunt niet de hele afbeelding tegelijk op de tafel leggen, dus moet je de puzzel opdelen in kleinere stukjes, elk stukje op je kleine tafeltje oplossen, en vervolgens proberen de stukjes weer aan elkaar te lijmen om de uiteindelijke afbeelding te zien. Dit is de dagelijkse strijd van wetenschappers die werken met kwantumcomputers. Deze machines zijn ongelooflijk krachtig, maar momenteel erg klein en fragiel; ze hebben te weinig "qubits" (de puzzelstukjes) om de enorme problemen aan te kunnen die we willen oplossen, en ze worden gemakkelijk verstoord door ruis, zoals een nies die een delicaat kaartenstapje verpest.

Om dit te omzeilen, gebruiken wetenschappers een truc genaamd circuit cutting (circuit-snijden). Het is alsof je die enorme puzzel in hanteerbare secties snijdt, elke sectie oplost op een andere kleine tafel (of zelfs op verschillende computers), en vervolgens een speciaal wiskundig recept gebruikt om de antwoorden weer in elkaar te zetten. Er is echter een addertje onder het gras: elke keer dat je de puzzel snijdt, wordt het recept om de stukjes weer aan elkaar te lijmen exponentieel moeilijker en vereist het dat je miljoenen foto's van de stukjes maakt om het juiste beeld te krijgen. Als je de puzzel te vaak snijdt, wordt de inspanning om de stukjes aan elkaar te lijmen zo groot dat het het doel van de oefening tenietdoet. De grote vraag is: Waar moeten we precies de sneden maken om de puzzelstukjes klein genoeg te houden om op te lossen, maar niet zoveel sneden te maken dat het aan elkaar lijmen een eeuwigheid duurt?

Hier komt een nieuw framework genaamd MosaiQC kijken. Zie MosaiQC als een superintelligente, hypergeorganiseerde puzzelmeester die de puzzel niet zomaar willekeurig in stukken snijdt. In plaats daarvan kijkt het naar de vorm van de puzzelstukken, de grootte van de beschikbare tafels en zelfs hoe wiebelig elke tafel is (de "ruis"). Het gebruikt een slimme mix van strategieën om de perfecte plekken voor de sneden te vinden. Eerst maakt het een snelle, ruwe schatting van waar de sneden moeten komen (als een warming-up stretch). Vervolgens verfijnt het die schatting door kleine bewegingen te testen, stukjes uit te wisselen om te zien of de puzzel beter past. Cruciaal is dat het niet alleen geeft om hoeveel sneden het maakt; het geeft ook om waar de stukjes terechtkomen. Als één tafel wankel is, probeert MosaiQC de belangrijkste, meest fragiele stukken op de meest stabiele tafel te plaatsen om fouten te voorkomen.

Het artikel laat zien dat deze nieuwe methode een game-changer is. Wanneer de onderzoekers MosaiQC testten tegenover oudere methoden, ontdekten ze dat Mosai-QC 2,88 keer sneller was in het uitzoeken waar de sneden moesten komen. Belangrijker nog, het verminderde het aantal sneden met gemiddeld 16,84%, wat klein klinkt, maar eigenlijk betekent dat de inspanning voor het "aan elkaar lijmen" (de sampling overhead) met een verbazingwekkende factor van 5,38 × 10¹¹ daalde. Dat is alsof je van het nodig hebben om een foto van elk zandkorreltje op een strand te maken, overgaat naar het maken van één foto van het hele strand in één shot. Daarnaast verbeterde MosaiQC, door aandacht te besteden aan welke hardware "ruisiger" is, de uiteindelijke nauwkeurigheid van de resultaten met ongeveer 19,56% vergeleken met standaardmethoden.

De auteurs merken er zorgvuldig bij op dat hoewel MosaiQC het plannen van de sneden veel sneller en beter maakt, het fundamentele probleem van het weer aan elkaar lijmen van de stukjes nog steeds veel inspanning vereist als de sneden te talrijk zijn. Echter, door betere sneden te vinden en ze op de beste hardware te plaatsen, suggereert MosaiQC dat we veel grotere kwantumproblemen kunnen oplossen dan voorheen zonder vast te lopen in een compilatie-bottleneck. Het bewijst dat een slimme, flexibele aanpak — die verschillende soorten sneden combineert en zich aanpast aan verschillende hardwaregroottes — het onmogelijke een beetje minder onmogelijk kan maken, wat de weg vrijmaakt voor kwantumcomputers om echte wereldproblemen aan te pakken, zelfs voordat ze tot enorme omvang zijn gegroeid.

Technische Samenvatting: MOSAIQC

Probleemstelling

Huidige kwantumcomputers, met name in het NISQ-tijdperk (Noisy Intermediate-Scale Quantum), missen de qubit-bronnen en de fideliteit die vereist zijn voor het uitvoeren van de meeste praktische kwantumalgoritmen. Om deze hardwarebeperkingen te omzeilen, is "kwantumcircuit-cutting" (of circuit-knitting) ontstaan als een techniek om grote algoritmen op te delen in kleinere partities die uitvoerbaar zijn op beschikbare hardware. Deze aanpak introduceert echter een aanzienlijke sampling-overhead die exponentieel schaalt met het aantal benodigde sneden voor exacte staat-reconstructie.

Bestaande optimalisatieframeworks voor het bepalen van locaties voor sneden kampen met verschillende kritieke beperkingen:

Schaalbaarheid: Exacte methoden (bijv. Mixed Integer Programming, SMT-solvers) vertonen vaak factoriële of exponentiële computationele complexiteit, wat ze onhaalbaar maakt voor circuits die de duizend-qubit-grens naderen.
Beperkingen in Snede-types: Veel heuristieken optimaliseren voor ofwel draad-sneden (wire cuts) of poort-sneden (gate cuts) in isolatie, maar combineren deze zelden binnen een enkel optimalisatieproces.
Hardware-bewustzijn: De meeste benaderingen gaan uit van homogene hardware-partities en negeren de specifieke ruiskenmerken en connectiviteitsbeperkingen van heterogene kwantum-backends, wat leidt tot suboptimale uitvoering-fideliteit.
Trade-offs: Het balanceren van de minimalisatie van de sampling-overhead met de maximalisatie van de hardware-fideliteit (ruisreductie) is een complex multi-objective probleem dat bestaande schaalbare heuristieken vaak niet gezamenlijk kunnen adresseren.

Methodologie

Het paper presenteert MosaiQC, een heuristisch optimalisatieframework ontworpen om sampling-overhead, hardware-bewuste plaatsing en gemengde gate/draad-sneden gezamenlijk te optimaliseren, terwijl een polynomiale runtime-complexiteit behouden blijft. Het framework werkt via een hiërarchische, vierfasen optimalisatiepijplijn:

1. Graafrepresentatie

Om de computationele overhead te verminderen, wordt het kwantumcircuit en de hardwaretopologie getransformeerd naar compacte graafrepresentaties in plaats van te vertrouwen op herhaalde Directed Acyclic Graph (DAG) evaluaties.

Connectiviteitsgraaf: Representeert qubits als knopen en 2-qubit gates als randen, gewogen door het aantal gates.
Temporele afhankelijkheden: Worden apart opgeslagen om draad-sneden efficiënt te kunnen evalueren wanneer partities qubits delen.
Hardwaretopologie: Gemodelleerd als een gewogen graaf waarbij de randgewichten ruismetrieken (bijv. $1-q$ en $2-q$ gate-fouten) en routingkosten (geschat via Floyd-Warshall kortste paden) bevatten.

2. Initiële Partitiering (Warm-Start)

Het framework maakt gebruik van de METIS bibliotheek om een globale graaf-partitiering uit te voeren. Deze stap genereert een initiële oplossing die voldoet aan de hardwarecapaciteitsbeperkingen en biedt een hoogwaardig startpunt voor daaropvolgende verfijning. Deze fase richt zich primair op gate-sneden of draad-sneden afzonderlijk om een baseline vast te stellen.

3. Lokale Verfijning

Een Tabu Search algoritme verfijnt de initiële partitie iteratief door middel van lokale bewegingen:

Het toevoegen van knopen aan partities (onderhevig aan capaciteit).
Het verplaatsen van knopen tussen partities.
Het wisselen (swappen) van knopen op de grenzen van partities.
Evaluatie van Gemengde Sneden: De kostenfunctie houdt expliciet rekening met zowel gate- als draad-sneden. De overhead wordt berekend als $Overhead = (GateCost)^g \cdot 16^w$ , waarbij $g$ en $w$ respectievelijk de aantallen gate- en draad-sneden zijn. Om de berekening te optimaliseren, wordt de logaritme van deze kosten gebruikt tijdens de zoektocht.
Lokale Evaluatiestrategie: In plaats van de globale graaf opnieuw te evalueren, gebruikt het framework een lokale draad-snede lookup-strategie gebaseerd op qubit-niveau graafrepresentaties, wat de complexiteit aanzienlijk vermindert tot $O((a+1)p \log p)$ voor overlappende partities.

4. Hardware-Bewuste Partitie-Toewijzing

Om de uitvoering-fideliteit te optimaliseren, gebruikt MosaiQC een Quadratic Assignment Problem (QAP) solver met het Frank-Wolfe algoritme.

Doel: Een permutatiematrix vinden die circuit-partities naar hardware-backends mapt om de verwachte fideliteit te maximaliseren (ruis te minimaliseren).
Scoring: Het algoritme minimaliseert de spoorwaarde (trace) van het product van de circuit-partitiematrix en de hardware-ruis-topologiematrix. Ruisgewichten worden logaritmisch getransformeerd ( $w = \ln(1 - \epsilon_{noise})$ ) om verschillende schalen effectief te behandelen.
Adaptieve Kostenfunctie: Om de balans te vinden tussen de computationele kosten van QAP-evaluaties en de kwaliteit van de optimalisatie, gebruikt het framework een adaptieve kostenfunctie ( $S_{adapt}$ ) die de snede-overhead normaliseert ten opzichte van de QAP-plaatsingsscore. QAP-evaluaties worden op vaste intervallen uitgevoerd in plaats van bij elke iteratie.

Belangrijkste Bijdragen

Het paper claimt de volgende specifieke bijdragen:

Joint Optimization Framework: Een heuristisch framework dat gemengde draad- en gate-sneden optimaliseert binnen één enkele procedure, een capaciteit die zelden wordt gedemonstreerd door bestaande schaalbare tools.
Lokale Draad-Snede Evaluatie: Een strategie gebaseerd op qubit-niveau graafrepresentaties die de computationele complexiteit van herhaalde DAG-gebaseerde optimalisatie vermindert.
Heterogene Hardware Ondersteuning: Een abstractielaag die kwantum-backends ondersteunt met variërende qubit-capaciteiten en ruiskenmerken, wat mix-size hardware-partities mogelijk maakt.
Hardware-Bewuste Plaatsing: Een methode die gebruikmaakt van dubbel gewogen graaf-matching (opgelost via Frank-Wolfe) om partities op hardware te plaatsen, waarbij expliciet wordt geoptimaliseerd voor ruisreductie.
Schaalbare Hybride Strategie: Een combinatie van globale METIS-partitiering voor warm-start initialisatie en lokale Tabu Search-verfijning, wat een polynomiale runtime-complexiteit bereikt van $O(k \cdot n_q + m \cdot n_q^3)$ .

Resultaten

Het framework werd geëvalueerd tegen de Qiskit circuit-cutting add-on (gebruikmakend van Dijkstra's algoritme) en exhaustieve zoekmethoden over diverse benchmarks (bijv. Adder, BV, AQFT, QAOA, VQE) en circuitgroottes (6 tot 1000 qubits).

Runtime Prestaties: MosaiQC behaalde een 2,88× geometrisch gemiddelde versnelling in runtime vergeleken met de baseline. Cruciaal is dat het succesvol circuits tot 1000 qubits optimaliseerde, terwijl de baseline vaak vastliep (time-out) of te maken kreeg met geheugenoverloop.
Sampling-Overhead: Het framework demonstreerde een gemiddelde reductie van 16,84% in het aantal sneden vergeleken met de baseline. Dit resulteerde in een verbetering van de geometrische gemiddelde sampling-overhead van ongeveer $5,38 \cdot 10^{11}\times$ (vanwege de exponentiële aard van de overhead).
Fideliteit Verbetering: De hardware-bewuste plaatsingsstrategie toonde een sterke Pearson-correlatie ( $r \approx 0,83 - 0,87$ ) tussen de QAP-score en de gemeten fideliteit. In fideliteit-benchmarks behaalde MoseliQC een gemiddelde lokale fideliteitsverbetering van +19,56% ± 6,17% over de baseline wanneer de ruisgewicht-prioriteit werd gehanteerd.
Convergentie: De hybride warm-start benadering verminderde het aantal benodigde iteraties voor convergentie aanzienlijk vergeleken met alleen verfijningsbenaderingen, waardoor werd voorkomen dat de optimizer vroegtijdig in lokale minima terechtkwam.

Betekenis en Claims

De auteurs positioneren MosaiQC als een noodzakelijke evolutie in kwantum-compilertools. Zij stellen dat naarmate kwantumcircuits opschalen richting de duizend-qubit-regime, de optimalisatie van de plaatsing van de sneden zelf geen computationele bottleneck mag worden.

Het paper stelt dat MosaiQC een superieur evenwicht tussen runsnelheid en oplossingskwaliteit demonstreert, door fundamentele functies toe te voegen (gemengde sneden, ondersteuning voor heterogene hardware en ruis-bewuste plaatsing) die door de meeste concurrenten worden uitgesloten. Hoewel erkend wordt dat praktische circuit-cutting fundamenteel beperkt blijft door de exponentiële sampling-overhead die nodig is voor reconstructie, betogen de auteurs dat MosaiQC een praktisch fundament legt voor schaalbare circuit-cutting in toekomstige heterogene kwantumcomputersystemen. Het werk suggereert dat schaalbare heuristische optimalisatie de computationele overhead van de plaatsing van circuit-sneden substantieel kan verminderen, waardoor de uitvoering van algoritmen mogelijk wordt die anders onhaalbaar zouden zijn op de huidige hardware.