💻 computer science

AutoQ 2.0: From Verification of Quantum Circuits to Verification of Quantum Programs (Technical Report)

AutoQ 2.0 is een geavanceerde verificateur die verificatie van quantumcircuits uitbreidt naar volledige quantumprogramma's door theoretische en technische uitdagingen met betrekking tot klassieke besturingsflow aan te pakken, en toont succesvol zijn efficiëntie aan op complexe algoritmen zoals repeat-until-success en op zwakke metingen gebaseerde Grover-zoekalgoritmen.

Oorspronkelijke auteurs: Yu-Fang Chen, Kai-Min Chung, Min-Hsiu Hsieh, Wei-Jia Huang, Ondřej Lengál, Jyun-Ao Lin, Wei-Lun Tsai

Gepubliceerd 2026-05-08

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yu-Fang Chen, Kai-Min Chung, Min-Hsiu Hsieh, Wei-Jia Huang, Ondřej Lengál, Jyun-Ao Lin, Wei-Lun Tsai

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

Het Grote Plaatje: Van Statische Blauwdrukken tot Dynamische Recepten

Stel je voor dat je een huis bouwt.

AutoQ 1.0 (De Oude Versie) was als een tool die alleen statische blauwdrukken kon controleren. Het kon verifiëren of een specifieke, onveranderlijke set muren en balken (een "kwantumschakeling") correct was gebouwd. Maar het kon geen huis aan, waarbij de architect besliste: "Als de wind uit het noorden waait, bouw ik een veranda; anders bouw ik een garage."
AutoQ 2.0 (De Nieuwe Versie) is een tool die dynamische recepten kan controleren. Het begrijpt dat kwantumprogramma's niet alleen statische schakelingen zijn; het zijn instructies die beslissingen kunnen nemen (vertakkingen) en stappen kunnen herhalen (lussen) op basis van wat er tijdens het proces gebeurt.

De auteurs hebben deze nieuwe tool gebouwd om te verifiëren dat deze complexe, besluitvormende kwantumprogramma's precies werken zoals de programmeur bedoeld heeft, zonder dat een mens elke stap handmatig hoeft te controleren.

De Kernuitdaging: Het "Ineenstortings"-Probleem

In de kwantumwereld is er een unieke regel: Meten.
Stel je voor dat je een draaiende munt hebt die tegelijkertijd Kop en Munt is (een superpositie). Het moment dat je ernaar kijkt (het meet), "stort het in" tot óf Kop óf Munt.

De Moeilijkheid: In oudere tools werd de wiskunde rommelig zodra je een munt mat. De kansen moesten "genormaliseerd" worden (opnieuw berekend zodat ze 100% optellen), wat de computerwiskunde ongelooflijk traag en moeilijk maakte.
De AutoQ 2.0 Truc: De auteurs beseften dat ze de wiskunde niet direct hoefden te repareren. Ze besloten om de getallen "rommelig" (ongenormaliseerd) te laten tijdens het proces en alleen te controleren of de vorm van het resultaat correct was. Ze bouwden een speciale "implicatie-test" (een vergelijkingstool) die zegt: "Zelfs als je getallen op- of afgeschaald zijn, zolang het patroon maar overeenkomt, ben je goed." Dit is als controleren of twee kaarten dezelfde wegen hebben, zelfs als de ene kaart in schaal 1:100 is getekend en de andere in 1:1000.

De Motor: "Level-Gesynchroniseerde Boomautomata" (LSTA's)

Om deze complexe programma's te hanteren, gebruikt de tool een speciale datastructuur genaamd LSTA's.

De Analogie: Denk aan een kwantumtoestand als een gigantische, vertakkende boom. Elke tak vertegenwoordigt een mogelijk pad dat de kwantumcomputer kan nemen.
Het Probleem: Standaard tools proberen elk enkel blaadje op de boom te tekenen. Als je 100 qubits (kwantumbits) hebt, heeft de boom meer blaadjes dan er atomen in het universum zijn. Het is onmogelijk om ze allemaal te tekenen.
De Oplossing (LSTA's): In plaats van elk blaadje te tekenen, gebruiken LSTA's een "sjabloon" of een "patroon". Ze zeggen: "Alle takken op dit niveau zien er zo uit."
Het "Gesynchroniseerde" Deel: Dit is de magische saus. In een kwantumprogramma, als je een beslissing neemt in één deel van de boom, beïnvloedt dat de hele boom op dat niveau. LSTA's zorgen ervoor dat alle takken op dezelfde "verdieping" van de boom het eens zijn over dezelfde keuze. Het is als een koor waar iedereen op dezelfde toonhoogte hetzelfde nootje moet zingen; als één persoon een ander nootje zingt, breekt de hele harmonie. Hierdoor kan de tool enorme kwantumtoestanden comprimeren tot een klein, hanteerbaar bestand.

Hoe Het Werkt: De Drie Stappen

Wanneer je een kwantumprogramma wilt verifiëren met AutoQ 2.0, gedraag je je als een leraar die het huiswerk van een student nakijkt:

De Opzet (Pre-condities): Je vertelt de tool: "Begin met een munt die zo draait." (Dit is de invoertoestand).
De Lus (Invarianten): Als het programma een lus heeft (een "herhaal tot" instructie), moet je een "Lus-invariant" verstrekken.
- Analogie: Stel je een hardloper voor die rondjes loopt. Je vertelt de tool: "Ongeacht hoeveel rondjes ze lopen, ze zullen altijd op de baan blijven." Je hoeft niet elke stap te controleren; je moet alleen bewijzen dat als ze aan het begin van een ronde op de baan zijn, ze aan het einde van de ronde nog steeds op de baan zullen zijn.
Het Doel (Post-condities): Je vertelt de tool: "Het programma moet eindigen met de munt die Kop laat zien."

De tool voert het programma vervolgens virtueel uit, gebruikmakend van zijn "patroon" (LSTA) om de toestand bij te houden. Het controleert:

Is het programma correct gestart?
Houdt de lus de hardloper op de baan (de invariant)?
Eindigde het programma met de munt die Kop laat zien?

Realistische Tests: Wat Hebben Ze Geverifieerd?

De auteurs hebben AutoQ 2.0 getest op twee zeer moeilijke soorten kwantumprogramma's die eerdere tools niet automatisch konden hanteren:

Herhaal-Tot-Succes (RUS):
- Het Scenario: Stel je voor dat je probeert een taart te bakken, maar je weet niet of de oven warm genoeg is. Je zet de taart in, controleert de temperatuur, en als het te koud is, haal je hem eruit, wacht je even en probeer je het opnieuw. Je blijft dit herhalen tot de taart klaar is.
- Het Resultaat: AutoQ 2.0 verifieerde deze "probeer-opnieuw"-algoritmes direct.
Zwakke-Meting Grover's Zoekalgoritme:
- Het Scenario: Grover's algoritme is een beroemde methode om een naald in een hooiberg te vinden. De "Zwakke-Meting" versie is een lastige nieuwe manier om dit te doen waarbij je zachtjes in de hooiberg glijpt zonder het hele ding direct in te laten storten, waardoor je kunt blijven zoeken zelfs als je de naald niet direct vindt.
- Het Resultaat: Dit is een enorm programma. De auteurs verifieerden een versie met 100 qubits (een enorm aantal voor kwantumcomputing) in ongeveer 20 minuten. Dit is een enorme schaalvergroting ten opzichte van wat eerder mogelijk was.

De Conclusie

AutoQ 2.0 is een doorbraak omdat het de eerste tool is die complexe kwantumprogramma's die lussen en besluitvorming gebruiken, automatisch kan verifiëren. Dit doet het door slimme "patroonherkenning" (LSTA's) te gebruiken om niet vast te lopen in onmogelijke wiskunde, en door slim om te gaan met de rommelige wiskunde van kwantummetingen.

Het heeft succesvol bewezen dat deze geavanceerde kwantumrecepten correct werken, zelfs voor zeer grote systemen, zonder dat een mens het zware werk van het bewijs moet doen.

Technische Samenvatting: AutoQ 2.0: Van verificatie van quantumcircuits naar verificatie van quantumprogramma's

1. Probleemstelling

Quantumprogramma's breiden quantumcircuits uit door klassieke besturingsflowconstructies zoals vertakkingen en lussen op te nemen. Hoewel quantumcircuits (het domein van AutoQ 1.0) volstaan voor het definiëren van statische reeksen poorten, vereisen geavanceerde quantumalgoritmen—zoals Repeat-Until-Success (RUS)-algoritmen en op zwakke meting gebaseerde versies van Grover's zoekalgoritme—dynamische besturing op basis van klassieke waarden die uit qubit-metingen worden verkregen.

Het verifiëren van deze programma's brengt aanzienlijke uitdagingen met zich mee die niet voorkomen bij circuit-only verificatie:

Meting en Normalisatie: Meting doet quantumtoestanden instorten en levert klassieke waarden (0 of 1) op die de besturingsflow aansturen. Dit proces vereist vaak normalisatie van waarschijnlijkheidsamplitudes, wat formeel redeneren bemoeilijkt.
Redeneren over Besturingsflow: Het verifiëren van lussen en vertakkingen vereist het hanteren van toestandsruimten die evolueren op basis van meetuitkomsten, een taak die moeilijk is voor bestaande geautomatiseerde hulpmiddelen.
Gebrek aan Geautomatiseerde Hulpmiddelen: Hoewel deductieve verificatietools bestaan voor klassieke programma's (bijv. Dafny, KeY) en sommige quantumtools bestaan (bijv. CoqQ, Qbricks), missen ze óf volledige automatisering óf vereisen ze aanzienlijke handmatige inspanning (bijv. het leveren van complexe Hermitische operatoren of uitgebreide bewijszoektochten). Bestaande geautomatiseerde tools richten zich vaak op circuit-equivalentie of specifieke geparametriseerde programma's, en missen algemene ondersteuning voor besturingsflow in quantumprogramma's.

2. Methodologie

AutoQ 2.0 adresseert deze uitdagingen door het vorige circuitverificatiekader uit te breiden tot volledige quantumprogramma's. De kernmethodologie steunt op Level-Synchronized Tree Automata (LSTA's) en een nieuwe implicatie-test aanpak.

2.1 Formeel Model: Level-Synchronized Tree Automata (LSTA's)

Het hulpmiddel stelt verzamelingen van quantumtoestanden (precondities, postcondities en lusinvarianten) voor met LSTA's.

Structuur: LSTA's zijn symbolische boomautomata ontworpen om quantumtoestanden te coderen als perfecte binaire bomen, waarbij takken computationele basis-toestanden voorstellen en bladeren complexe waarschijnlijkheidsamplitudes voorstellen.
Synchronisatie: Een kernkenmerk van LSTA's is het "keuze"-mechanisme. Transities op hetzelfde boomniveau moeten een gemeenschappelijke keuzemengeling delen. Hierdoor kunnen LSTA's verstrengelde toestanden en superposities compact voorstellen die standaard boomautomata niet kunnen, door te waarborgen dat alleen geldige combinaties van takken (die een keuze delen) worden gegenereerd.
Invoerformaat: Gebruikers specificeren precondities, postcondities en lusinvarianten als .lsta-bestanden, die de automata definiëren die de verzamelingen van geldige quantumtoestanden herkennen.

2.2 Verificatiekader

Het verificatieproces is geautomatiseerd en volgt een deductieve stijl:

Programma-uitvoering: Het hulpmiddel voert quantumpoorten (bijv. $H$ , $CX$, $T$ ) uit op de LSTA die de preconditie voorstelt.
Hanteren van Meting en Vertakkingen:
- Wanneer een meting $M_i = b$ plaatsvindt, wordt de LSTA opgesplitst in twee kopieën die overeenkomen met uitkomsten $b=0$ en $b=1$ .
- Het algoritme werkt de boom bij door de waarschijnlijkheidsamplitudes van de niet-overeenkomende takken op nul te zetten (bijv. als $M_1=0$ , worden de amplitudes van de $1$-subboom onder $x_1$ op 0 gezet).
- Cruciaal normaliseert het hulpmiddel de amplitudes niet tijdens deze stap. Het behoudt de ruwe amplitudes om complexe rekenkunde tijdens de uitvoering te vermijden, en schuift normalisatiecontroles uit naar de uiteindelijke implicatietest.
- Vertakkingsinstructies worden afgehandeld door de resulterende LSTA's voor zowel het waar- als het onwaar-pad te berekenen en hun vereniging te nemen.
Hanteren van Lussen:
- Voor while-lussen moet de gebruiker een lusinvariant als LSTA verstrekken.
- Het hulpmiddel verifieert dat de invariant inductief is: deze moet alle toestanden bestrijken die bereikbaar zijn voor de lus, en het uitvoeren van de lusbody op de invariant (geconditioneerd op de lusverlenging) moet resulteren in toestanden die nog steeds door de invariant worden bestreken.
- De toestanden bij het verlaten van de lus worden overbenaderd door de invariant, geconditioneerd op het beëindigen van de lus.
Implicatietest (tot op schaling):
- De laatste stap controleert of de verzameling bereikbare toestanden (voorgesteld door een LSTA $R$ ) is opgenomen in de postconditie (LSTA $Q$ ).
- Omdat normalisatiefactoren tijdens de uitvoering werden genegeerd, gebruikt het hulpmiddel een gespecialiseerde implicatie tot op schaling ( $|=_{uts}$ ) relatie.
- $A |=_{uts} B$ geldt als elke boom in $A$ een lineair geschaalde versie is van een boom in $B$ (d.w.z. $T_A = r \cdot T_B$ voor een zekere niet-nul scalair $r$ ).
- Deze controle wordt uitgevoerd met een graafzoekalgoritme dat de LSTA's niveau voor niveau doorloopt, toestanden en termen in kaart brengt, en uiteindelijk een SMT-oplosser (Z3) oproept om het bestaan van een schalingsfactor $r$ te verifiëren die aan de globale constraints voldoet.

3. Belangrijkste Bijdragen

Uitbreiding tot Quantumprogramma's: AutoQ 2.0 is het eerste hulpmiddel dat geautomatiseerde deductieve verificatie biedt voor quantumprogramma's met lussen en vertakkingen, en zo verder gaat dan de circuit-only reikwijdte van AutoQ 1.0.
Geautomatiseerd Hanteren van Meting: Het hulpmiddel introduceert algoritmen om LSTA's op te splitsen op basis van meetuitkomsten en de resulterende toestandsruimten te beheren zonder handmatige tussenkomst.
Normalisatie-vrije Verificatie: Door een implicatietest te ontwerpen die werkt met niet-genormaliseerde toestanden (tot op schaling), vermijdt het hulpmiddel de rekenkundige complexiteit van het normaliseren van amplitudes tijdens de uitvoeringsfase, wat de efficiëntie aanzienlijk verbetert.
LSTA-gebaseerde Invarianten: Het kader maakt gebruik van LSTA's om lusinvarianten voor te stellen, waardoor een compacte representatie van complexe quantumtoestanden mogelijk is die vereist zijn voor iteratieve algoritmen.
Schaalbaarheid: De aanpak ondersteunt verificatie van programma's met een groot aantal qubits (tot 100 qubits in de gerapporteerde benchmarks) door te profiteren van de compactheid van LSTA's en efficiënte SMT-oplossing.

4. Experimentele Resultaten

De auteurs evalueerden AutoQ 2.0 op twee klassen van geavanceerde quantumprogramma's:

Repeat-Until-Success (RUS) Algoritmen: Gebruikt voor het genereren van niet-standaard quantumpoorten (bijv. specifieke unitairen zoals $(2X + \sqrt{2}Y + Z)/\sqrt{7}$ $(2 X + 2 Y + Z) / 7$ ).
- Resultaat: Alle RUS-benchmarks werden direct geverifieerd (0,0s).
Op Zwakke Meting Gebaseerde Grover's Zoek: Een versie van Grover's algoritme die geen voorafgaande kennis van het aantal oplossingen vereist.
- Resultaat: Het hulpmiddel slaagde erin instanties met tot 100 qubits (specifiek, 101 qubits in de tabel) te verifiëren in ongeveer 11 seconden (voor het geval van 101 qubits) tot 20 minuten (zoals vermeld in het abstract voor het geval van 100 qubits, hoewel de tabel 11s toont voor 101 qubits; het abstract verwijst waarschijnlijk naar een specifieke configuratie of omvat opstarttijd). De verificatietijd schaalt redelijk met het aantal qubits en poorten.

De experimenten werden uitgevoerd op een server met een AMD EPYC 7742-processor en 1.152 GiB RAM.

5. Betekenis en Claims

Het artikel claimt dat AutoQ 2.0 momenteel het enige hulpmiddel is dat quantumprogramma's kan verifiëren met een dergelijk hoog niveau van automatisering. In tegenstelling tot bestaande tools die vertrouwen op bewijsassistenten (waarvoor aanzienlijke menselijke inspanning vereist is) of zich uitsluitend richten op circuit-equivalentie, overbrugt AutoQ 2.0 de kloof tussen formele verificatietheorie en praktisch quantumprogrammeren door besturingsflow en meting automatisch te hanteren.

De auteurs positioneren het hulpmiddel als een belangrijke stap richting formele verificatie van complexe quantumalgoritmen, en tonen aan dat geautomatiseerde deductieve verificatie haalbaar is voor programma's die niet kunnen worden uitgedrukt als simpele quantumcircuits. Ze merken nederig op dat hoewel de huidige implementatie niet-geneste besturingsflow en pure toestanden afhandelt, toekomstig werk gericht is op het automatiseren van invariantengeneratie en het uitbreiden van de ondersteuning naar gemengde toestanden die voortvloeien uit complexere lussen.