QSeqSim: A Symbolic Simulator for Qiskit While Loops Using Sequential Quantum Circuits

Dit artikel introduceert QSeqSim, een in Qiskit geïntegreerde symbolische simulator die de efficiënte simulatie van quantumprogramma's met while-lussen mogelijk maakt door deze om te zetten in sequentiële schakelingen en gebruik te maken van BDD-gebaseerde gewogen modeltelling om meetkansen te berekenen voor benchmarks op grote schaal met meerdere iteraties.

De kern

Stel je voor dat je een zeer geavanceerd recept hebt voor een quantumgerecht (een quantumprogramma). De meeste moderne receptboeken, zoals Qiskit, staan je toe instructies te schrijven die zeggen: "Blijf deze stap keer op keer herhalen tot de saus een specifieke kleur krijgt." Dit wordt een while-lus genoemd.

Tot nu toe konden de keukenapparaten (simulatoren) die deze recepten daadwerkelijk bereiden, deze instructie echter niet begrijpen. Als je probeerde een recept met een "blijf koken tot..."-instructie uit te voeren, zou het apparaat crashen of zeggen: "Ik weet niet hoe ik dit moet doen."

QSeqSim is een nieuwe, slimme keukenassistent die specifiek is ontworpen om deze "blijf koken tot"-instructies te verwerken. Hieronder wordt uitgelegd hoe het werkt, met behulp van eenvoudige analogieën:

1. Het Probleem: De "Lus"-Kloof

Denk aan een standaard quantumcircuit als een rechte lijn van dominostenen die één voor één omvallen. Je duwt de eerste om, en ze vallen allemaal in een vaste volgorde. Dit is eenvoudig te simuleren.

Maar een while-lus is als een schuifdeur in een gang. Je loopt door de deur, voert een taak uit, controleert een sensor, en als de sensor zegt "nog niet klaar", glijd je terug door de deur om het opnieuw te doen. De toestand van de kamer (de quantumtoestand) verandert elke keer dat je erdoorheen gaat, en de deur kan op elk moment sluiten.

Huidige tools (zoals Qiskit-Aer) kunnen alleen de rechte lijn van dominostenen verwerken. Ze weten niet hoe ze met de schuifdeur moeten omgaan die terug naar zichzelf loopt. QSeqSim is het eerste instrument dat is gebouwd om dit "schuifdeur"-gedrag op een natuurlijke manier te begrijpen en te simuleren.

2. De Oplossing: Lussen Omzetten in een "Geheugenvoertuig"

Om deze lussen begrijpelijk te maken, vertaalt QSeqSim het quantumprogramma naar een speciaal type machine dat een Sequential Quantum Circuit wordt genoemd.

• De Analogie: Stel je een fabrieksassemblagelijn voor.
  • Externe Qubits: Deze zijn als ruwe materialen die vers worden aangevoerd voor elke enkele doorgang door de lus. Ze worden gemeten (gecontroleerd) en vervolgens weggegooid.
  • Interne Qubits: Deze zijn als het werk in uitvoering op het transportband. Ze blijven in de machine, worden bijgewerkt en worden meegenomen naar de volgende lusiteratie.
  • De Lus: De machine controleert een meter (een meting). Als de meter zegt "doorgaan", loopt het transportband terug, waarbij het bijgewerkte werk in uitvoering naar het begin van de volgende cyclus wordt vervoerd.

QSeqSim behandelt de lus niet als een magische herhalingsknop, maar als een fysieke machine met een terugkoppelingsdraad die het "geheugen" van de vorige stap naar de volgende draagt.

3. De Motor: Het "Slimme Archiefsysteem" (BDD's)

Het simuleren van quantumcomputers is moeilijk omdat het aantal mogelijkheden explosief groeit (zoals proberen elke mogelijke route die een reiziger in een gigantisch doolhof zou kunnen nemen, bij te houden).

QSeqSim maakt gebruik van een techniek genaamd Binary Decision Diagrams (BDD's).

• De Analogie: Stel je een enorme bibliotheek voor met elke mogelijke uitkomst van je quantumlus. Een normale computer probeert elk boek in de bibliotheek één voor één te lezen.
• De Truc van QSeqSim: In plaats van elk boek te lezen, gebruikt QSeqSim een slim archiefsysteem. Het merkt op dat veel paden in het doolhof identiek zijn. Het groepeert ze samen in één map.
  • Als 1.000 paden allemaal naar hetzelfde resultaat leiden, berekent QSeqSim ze niet 1.000 keer; het berekent ze één keer en zegt: "Deze map vertegenwoordigt alle 1.000 paden."
  • Hierdoor kan het omgaan met lussen met meer dan 1.000 qubits en meer dan 10 iteraties zonder overweldigd te raken, iets wat eerdere tools niet konden.

4. Wat Het Kan (De Resultaten)

De auteurs hebben QSeqSim getest op drie soorten "recepten" (benchmarks) om te zien hoe goed het de "schuifdeur"-lussen verwerkt:

• Repeat-Until-Success (RUS): Een recept dat zegt: "Blijf deze truc proberen tot het werkt." QSeqSim simuleerde dit perfect, zelfs toen de lus 100 keer moest worden uitgevoerd.
• Quantum Random Walks: Stel je een dronken persoon voor die over een rooster loopt, bij elke stap een munt opgooit om te beslissen welke kant op te gaan, en controleert of ze tegen een muur lopen. QSeqSim simuleerde een wandeling met meer dan 1.000 stappen (qubits) en 10+ lussen.
• Grover's Search: Een beroemd zoekalgoritme dat lussen gebruikt om een naald in een hooiberg te vinden. QSeqSim kon dit simuleren met honderden qubits.

5. Waarom Dit Belangrijk Is (Voor Nu)

Het artikel beweert dat QSeqSim een specifieke kloof opvult: het is het eerste instrument dat Qiskit-programma's met while-lussen daadwerkelijk kan uitvoeren.

Voorheen, als een programmeur een lus schreef, moest deze handmatig worden uitgerold (elke enkele stap opschrijven) of kon het helemaal niet worden uitgevoerd. Nu kunnen ze de lus natuurlijk schrijven, en QSeqSim vertaalt deze naar een "geheugenvoertuig", gebruikt zijn slimme archiefsysteem om de kansen van verschillende uitkomsten te berekenen en vertelt je precies wat er gebeurt.

Kortom: QSeqSim is een vertaler en een rekenmachine die quantumcomputers eindelijk in staat stelt instructies te begrijpen en uit te voeren die zeggen: "Dit keer na keer herhalen tot het resultaat goed is."

Technische samenvatting

Technische Samenvatting: QSeqSim

Probleemstelling

Ondanks de snelle evolutie van quantum-programmeerframeworks bestaat er een aanzienlijke kloof tussen de expressiviteit van moderne quantumtalen en de mogelijkheden van huidige uitvoeringsbackends. Specifiek ondersteunen Qiskit en OpenQASM 3, hoewel ze high-level besturingsflowconstructies zoals while-lussen ondersteunen (waardoor patronen zoals Repeat-Until-Success (RUS), zwak gemeten Grover-zoekopdrachten en feedback-gebaseerde quantumrandom walks mogelijk zijn), geen Qiskit-native tool die in staat is deze programma's te simuleren.

De standaardsimulator, Qiskit-Aer, en huidige cloudhardware-backends ondersteunen het while_loop-construct niet. Pogingen om dergelijke programma's uit te voeren resulteren in parsing- of compilatiefouten, omdat de besturingsflow niet kan worden omgezet naar een circuitvorm die deze simulators kunnen verwerken. Bijgevolg bestaat er geen uitvoeringsengine die de beoogde iteratieve semantiek van niet-triviale while-lusprogramma's binnen het Qiskit-ecosysteem realiseert.

Methodologie

De auteurs presenteren QSeqSim, een symbolische simulatiebackend geïntegreerd met Qiskit die deze kloof overbrugt door while-lusprogramma's te interpreteren als Sequential Quantum Circuits (SQCs). De methodologie omvat drie kerncomponenten:

1. Semantisch Kader: Van Combinatorisch naar Sequentieel

QSeqSim herdefinieert het uitvoeringsmodel voor Qiskit-programma's die klassieke besturing bevatten:

• Vertaling: Het neemt QuantumCircuit-objecten, vertaalt deze naar OpenQASM 3 en parseert ze naar een Abstract Syntax Tree (AST).
• Decompositie: De parser classificeert circuitblokken in drie types:
  • CQC (Combinational Quantum Circuits): Rechtlijnige poortsegmenten.
  • DQC (Dynamic Quantum Circuits): Blokken met metingen halverwege het circuit en conditionele vertakking (if/else, switch).
  • SQC (Sequential Quantum Circuits): Blokken die while-lussen vertegenwoordigen.
• Staatpartitionering: Voor SQC's partitioneert het systeem qubits expliciet in interne qubits (toestand die wordt behouden en teruggekoppeld over iteraties heen) en externe qubits (iteratie-gescopeerde qubits die worden gemeten en verworpen). Dit biedt een precieze semantiek voor quantumtoestandsfeedback.

2. Symbolische Uitvoeringsengine (BDD-gebaseerd)

De kern van QSeqSim is een op Binary Decision Diagram (BDD) gebaseerde engine die bestaande Booleaanse coderingen van quantumcircuits (specifiek het werk van Tsai et al.) uitbreidt om sequentieel gedrag te hanteren:

• Symbolische Operatoren: De engine introduceert twee specifieke operatoren om toestandsontwikkeling over lusiteraties heen te beheren:
  • Staatcompositie: Tensoriseert de huidige interne staat met een verse externe inputstaat.
  • Staatbehoud: Voert een partiële trace uit om gemeten externe qubits te verwijderen terwijl de bijgewerkte interne staat voor de volgende iteratie behouden blijft.
• Operationele Semantiek: De simulator voert het programma uit met behulp van een small-step operationele semantiek, waarbij while-lussen worden ontvouwd door de body herhaaldelijk uit te voeren totdat de lusguard (afgeleid van klassieke bits) false evalueert.

3. Efficiënte Kansberekening

Een grote uitdaging bij symbolische simulatie is het berekenen van meetkansen voor grote, gestructureerde beslisdiagrammen zonder expliciete enumeratie.

• Weighted Model Counting (WMC): In plaats van hyper-functieconstructies te gebruiken, maakt QSeqSim gebruik van weighted model counting op gestructureerde en sparse BDD's. Dit stelt het systeem in staat bijdragen van basisstaten te aggregeren in tijd die evenredig is met de BDD-grootte, waardoor kansenvragen die nodig zijn voor metingen halverwege het circuit en lusguards efficiënt worden verwerkt.

Belangrijkste Bijdragen

Het artikel claimt de volgende primaire bijdragen:

1. Eerste Qiskit-backend met directe while-lusondersteuning: QSeqSim is de eerste tool die Qiskit-programma's met while-lussen direct uitvoert door deze naar OpenQASM 3 te verlagen en een uitvoerbare small-step semantiek te bieden.
2. Uitbreiding naar sequentiële Booleaanse modellen: Het breidt BDD-gebaseerde coderingen uit van puur combinatorische circuits naar algemene sequentiële circuits door symbolische operatoren voor staatcompositie en -behoud in te voeren, waardoor het modelleren van expliciete toestandsfeedback mogelijk wordt.
3. Schaalbare symbolische simulatie: Door gebruik te maken van volwassen BDD-backends en WMC-technieken, bereikt QSeqSim efficiënte simulatie van door while-lussen veroorzaakte sequentiële circuits, en schaalt het verder dan de mogelijkheden van bestaande tools.

Experimentele Resultaten

De auteurs evalueerden QSeqSim op een MacBook Air (M2, 16 GB) met behulp van drie benchmarkcategorieën:

• Repeat-Until-Success (RUS): Het systeem simuleerde RUS-circuits met variërende unitaires succesvol. Terwijl korte lussen (10 iteraties) in minder dan een seconde werden voltooid, toonden langere lussen (100 iteraties) looptijden variërend van ~1,5s tot ~108s, wat een gevoeligheid aantoont voor de impact van de specifieke unitaire op de BDD-structuur.
• Quantum Random Walk (QRW): De tool schaalde naar circuits met meer dan 1000 qubits (specifiek $N=1024$ positieplaatsen) voor meer dan 10 lusiteraties. De prestaties werden echter beperkt door het aantal poorten per iteratie; voor $N=1024$ waren slechts tot 13 iteraties haalbaar binnen een time-out van 30 minuten.
• Grover's Search: Vergelijkbare schaalbaarheidstrends werden waargenomen. Voor 256 qubits verwerkte het systeem tot 5 iteraties voordat het time-outte, wat aangeeft dat hoewel BDD's diepe lussen goed hanteren, zeer grote multi-qubit-operatoren gecombineerd met herhaalde iteratie computationeel intensief blijven.
• Random While-Loops: Op 100-qubit random circuits bleef QSeqSim hanteerbaar, met mediane looptijden die onder de één minuut bleven over verschillende poort- en meetdichtheden.

De tool toonde ook bruikbaarheid in bereikbaarheidsanalyse, waarbij exacte kansen werden berekend voor specifieke toestandsconfiguraties (bijvoorbeeld een wandelaar die een specifieke positie bereikt) en meetuitkomstpatronen (bijvoorbeeld lusbeëindigingskansen) zonder steekproefruis.

Betekenis en Claims

Het artikel positioneert QSeqSim als een noodzakelijke brug tussen de hoge expressiviteit van quantum-programmeertalen en de beperkingen van huidige simulators. De betekenis ligt in:

• Aanbieden van Formele Analyse: Door een native uitvoeringsengine voor while-lussen te bieden, maakt het formele verificatie en analyse van quantumprogramma's met feedback en meetgecontroleerde iteratie mogelijk, wat eerder ontoegankelijk was in het Qiskit-ecosysteem.
• Schaalbaarheid via Symboliek: Het toont aan dat symbolische simulatie met BDD's en weighted model counting effectief sequentiële quantumcircuits met aanzienlijke qubit-aantallen en lusdieptes kan verwerken, en dat het voor deze specifieke gestructureerde problemen beter presteert dan naïeve statevector-simulatie.
• Fundering voor Toekomstig Werk: De auteurs merken op dat hoewel de huidige implementatie draait op handelshardware, de architectuur is ontworpen om toekomstige implementatie op serverklasse-machines met parallelisme te ondersteunen om nog grootschaligere simulaties en formele verificatietaken te hanteren.