⚛️ quantum physics

Compiling Quantum Regular Language States

Dit artikel presenteert een compiler voor het voorbereiden van kwantumtoestanden die structuurbewuste specificaties van reguliere taaltoestanden en hun complementen accepteert, en deze vertaalt naar geminimaliseerde deterministische eindige automaten en matrixproducttoestanden om efficiënte, hardware-bewuste circuits met voorspelbare resourcegaranties te genereren.

Oorspronkelijke auteurs: Armando Bellante, Reinis Irmejs, Marta Florido-Llinàs, María Cea Fernández, Marianna Crupi, Matthew Kiser, J. Ignacio Cirac

Gepubliceerd 2026-02-04

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Armando Bellante, Reinis Irmejs, Marta Florido-Llinàs, María Cea Fernández, Marianna Crupi, Matthew Kiser, J. Ignacio Cirac

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 een quantumcomputer probeert te programmeren. Normaal gesproken is het vertellen van de machine wat ze moet doen alsof je een enorme, complexe stad probeert te beschrijven door elk afzonderlijk straatadres, huisnummer en inwoner op te sommen. Als de stad een miljoen huizen heeft, moet je een miljoen adressen opschrijven. Dit is traag, tijdrovend en onmogelijk voor grote systemen.

Alternatief zou je een specifieke soort stadsindeling kunnen kennen (zoals een raster of een cirkel) en een kant-en-klaar "bouwplan" kunnen gebruiken voor dat specifieke geval. Maar wat als jouw stad een unieke mix van patronen is die niet in een standaard bouwplan past?

Dit artikel introduceert een nieuwe "vertaler" (een compiler) die tussen deze twee extremen in zit. Het stelt gebruikers in staat om een quantumtoestand te beschrijven met behulp van eenvoudige, gestructureerde regels — zoals een recept of een verkeerskaart — in plaats van een enorme lijst met gegevens. De auteurs noemen deze Regular Language States (RLS).

Zo werkt hun systeem, uitgelegd aan de hand van alledaagse analogieën:

1. De Input: Instructies geven in gewone taal

In plaats van de gebruiker te dwingen om elke mogelijke combinatie van bits op te sommen (zoals 001, 110, 101...), kan de gebruiker het patroon op drie eenvoudige manieren beschrijven:

Een Lijst: "Hier zijn de 10 specifieke reeksen die ik wil."
Een Regex (Patroon): "Ik wil alle reeksen die eruitzien als 001 gevolgd door een willekeurig aantal 1en." (Zoals een zoekfilter).
Een Flowchart (DFA): Een eenvoudig diagram dat laat zien hoe je van een "Start"-toestand naar een "Accept"-toestand beweegt op basis van 0'en en 1'en.

De Magische Truk: De gebruiker kan ook zeggen: "Ik wil alles behalve dit patroon." Meestal is het beschrijven van "alles behalve X" een nachtmerrie, omdat de "behalve"-lijst enorm groot is. Deze compiler handelt dit moeiteloos af.

2. De Tussenpersoon: De "Verkeersregelaar" (DFA)

Zodra de gebruiker de instructies geeft, springt de compiler niet direct naar de quantummachine. Eerst zet hij de input om in een Deterministic Finite Automaton (DFA).

Beschouw de DFA als een verkeersregelaar of een draaideur. Het is een simpel mechanisme dat controleert of een reeks bits "toegestaan" of "verboden" is.

De compiler neemt de rommelige input van de gebruiker en polijst deze tot de kleinste, meest efficiënte versie van deze verkeersregelaar.
Waarom dit belangrijk is: In plaats van zware, dure berekeningen uit te voeren op een gigantische lijst met getallen, doet de compiler eenvoudige logische puzzels op deze verkeersregelaar. Dit is veel sneller en brengt de verborgen structuur van de gegevens aan het licht.

3. Het Bouwplan: De "MPS" (Matrix Product State)

Zodra de verkeersregelaar is geoptimaliseerd, vertaalt de compiler deze naar een Matrix Product State (MPS).

Analogie: Stel je de quantumtoestand voor als een lange ketting van kralen. Een MPS breekt deze ketting op in kleine, hanteerbare schakels. Elke schakel hoeft alleen maar iets te weten over zijn directe buren, niet over de hele ketting.
Deze stap comprimeert de informatie. Als het patroon eenvoudig is (zoals een herhalend ritme), blijft de ketting van schakels kort. Als het patroon chaotisch is, worden de schakels groter. De compiler bepaalt automatisch de kleinste grootte die nodig is.

4. De Constructie: Het Circuit bouwen

Nu heeft de compiler het gecomprimeerde bouwplan (de MPS). Hij moet nu het eigenlijke quantumcircuit (de instructies voor de computer) bouwen. Het artikel biedt hiervoor twee manieren aan, afhankelijk van de hardware:

SeqRLSP (De Lopende Band):
- Beste voor: Computers waarbij de qubits in een rij staan en alleen met hun directe buren kunnen communiceren.
- Hoe het werkt: Het bouwt de toestand één kraal tegelijk, terwijl het langs de lijn beweegt. Het is efficiënt en heeft geen extra "hulp"-qubits (ancillae) nodig.
TreeRLSP (Het Boomhut-model):
- Beste voor: Computers waarbij elke qubit met elke andere qubit kan communiceren (all-to-all).
- Hoe het werkt: Het bouwt de toestand in een boomstructuur, waarbij paren van qubits worden gecombineerd, gevolgd door paren van paren, enzovoort. Dit is veel sneller (logaritmische diepte) omdat er veel zaken tegelijkertijd gebeuren.

5. De "Complement"-Superkracht

Een van de grootste claims van het artikel is het afhandelen van complementen (de "NIET"-versie van een toestand).

Het Probleem: Als je een toestand wilt die elke mogelijke reeks bevat, behalve 000, dan is het opsommen van de "toegestane" reeksen onmogelijk (er zijn er miljarden).
De Oplossing: De compiler realiseert zich dat als de "verboden" lijst klein is (slechts 000), de "toegestane" lijst weliswaar enorm is, maar de structuur nog steeds eenvoudig is. Het bewijst dat het bouwen van de "toegestane" toestand evenveel inspanning kost als het bouwen van de "verboden" toestand. Het is alsof je zegt: "Het is net zo makkelijk om een muur rond een kleine tuin te bouwen als een muur rond de rest van de wereld, als je de kaart van de tuin al hebt."

Samenvatting van de Resultaten

De auteurs hebben dit hele systeem gebouwd en getest. Ze hebben aangetoond dat:

Het werkt: Ze hebben succesvol complexe toestanden (zoals Dicke en W-toestanden) en hun complementen gecompileerd.
Het efficiënt is: De tijd die nodig is om te compileren en de grootte van het resulterende circuit zijn voorspelbaar en schalen goed met de complexiteit van het patroon, niet met de omvang van het universum aan mogelijkheden.
Het flexibel is: Het werkt op verschillende soorten quantumhardware (lineaire ketens versus volledig verbonden netwerken).

Kortom, dit artikel biedt een hulpmiddel waarmee programmeurs quantumtoestanden kunnen beschrijven met behulp van eenvoudige regels (zoals een recept) in plaats van enorme datadumps, waarbij de computer automatisch de meest efficiënte manier vindt om ze te bouwen, zelfs voor de "alles behalve dit"-scenario's.

Technische Samenvatting: Compileren van Quantum Regular Language States

Probleemstelling
Huidige compilers voor de voorbereiding van quantumtoestanden opereren op twee uitersten: algemene routines die doeltoestanden behandelen als opaak amplitude-vectoren (vaak waarbij exploitabele structuren worden gemist en inefficiënte circuits ontstaan), en op maat gemaakte constructies voor specifieke, bekende toestandsfamilies (bijv. GHZ-, W- of Dicke-toestanden). Deze kloof laat gebruikers zonder een methode om eenvoudige, op structuur gebaseerde specificaties te verstrekken die geen specifieke toestandsfamilie vereisen, maar toch voorspelbare en efficiënte resource-grenzen garanderen. Bovendien hebben bestaande tools moeite met het "complement"-probleem: het beschrijven van een toestand als de uniforme superpositie van alle bitstrings behalve een kleine set verboden strings. Hoewel de verboden set klein kan zijn, heeft de resulterende toestand een exponentieel grote ondersteuning (support), waardoor standaard sparse-state compilatie onhandelbaar wordt.

Methodologie
De auteurs stellen een modulaire, end-to-end compiler-pipeline voor die formele taalkunde en tensor netwerk synthese overbrugt. De pipeline accepteert drie soorten gebruikersinputs: (i) een eindige verzameling bitstrings, (ii) een reguliere expressie, of (iii) een Deterministische Eindige Automaat (DFA), met een optionele flag om het complement van de taal op te vragen.

De compilatie verloopt via de volgende fasen:

Input naar Automaat: De gebruikersinput wordt omgezet in een DFA. Als een verzameling strings wordt verstrekt, wordt een Directed Acyclic Graph DFA (DAG-DFA) geconstrueerd. Als een reguliere expressie wordt verstrekt, wordt deze gecompileerd naar een DFA (mogelijk via een NFA).
Minimalisatie en Complement: De DFA wordt geminimaliseerd met behulp van Hopcroft's algoritme om een canonieke minimale DFA te verkrijgen. Als een complement wordt opgevraagd, wordt de automaat aangepast door accepterende en niet-accepterende toestanden te wisselen (en een sink-toestand toe te voegen indien nodig) alvorens opnieuw te minimaliseren. De auteurs bewijzen dat de grootte van de minimale DFA voor een complement met maximaal 1 toeneemt ten op rispetto van de basis-taal.
Automaat naar Matrix Product State (MPS): De minimale DFA (of DAG-DFA) wordt in kaart gebracht naar een MPS. De DFA-toestanden komen overeen met de bond-indices, en input-symbolen met de fysieke indices. Dit levert een intermediaire representatie (IR) op waarbij de bond-dimensie $D$ gelijk is aan het aantal toestanden in de minimale DFA (of de maximale laaggrootte voor DAG-DFAs).
MPS naar Isometrieën: De MPS wordt gedecomposeerd in een netwerk van isometrieën. De auteurs schetsen twee backend-strategieën:
- SeqRLSP: Een sequentiële SVD-sweep (van links naar rechts en van rechts naar links) die een circuit met lineaire diepte en zonder ancilla produceert, geschikt voor Linear Nearest-Neighbor (LNN) architecturen. Deze pass optimaliseert ook de bond-dimensies om overeen te komen met de exacte Schmidt-rang $\chi$ van de doeltoestand.
- TreeRLSP: Een hiërarchisch, boom-gebaseerd SVD-schema dat een circuit met logaritmische diepte produceert, geschikt voor all-to-all connectiviteit.
Circuit Synthese: De isometrieën worden opgevuld tot machten van twee, ingebed in unitaries, en getranspileerd naar de native gate-set van de doelhardware.

Belangrijkste Bijdragen

Structuur-bewuste Specificatie: Het artikel introduceert een specificatiemethode met behulp van reguliere talen (regex, DFA of eindige verzamelingen) die gebruikers in staat stelt om grote, gestructureerde ondersteuningen beknopt te beschrijven zonder dat zij een specifieke toestandsfamilie hoeven te identificeren.
Natieve Complement Afhandeling: De compiler ondersteunt van nature de synthese van complement-toestanden. Het demonstreert dat het complement van een reguliere taal-toestand gecompileerd kan worden met dezelfde asymptotische quantumkosten als de basisbeschrijving, aangezien de maximale Schmidt-rang met maximaal 1 toeneemt.
End-to-End Pipeline: Het werk overbrugt de kloof tussen reguliere taaltheorie en MPS-gebaseerde circuit-synthese door een verenigde compiler te bieden met twee hardware-bewuste backends (SeqRLSP en TreeRLSP).
Theoretische Grenzen: De auteurs bieden expliciete grenzen voor de circuitdiepte en het aantal gates schalend met de systeemgrootte $N$ en de maximale Schmidt-rang $\chi$ . Ze stellen ook compile-tijd grenzen vast, waarbij ze aantonen dat de DFA-minimalisatiestap dure lineaire algebra-operaties verplaatst naar eenvoudigere automata-manipulaties.
Empirische Evaluatie: De volledige pipeline is geïmplementeerd en getest tegen algemene (Qiskit), sparse-state (Qualtran) en gespecialiseerde baselines. Evaluaties omvatten Dicke-toestanden, W-toestanden, willekeurige uniforme superposities en hun complementen.

Resultaten

Resource Efficiëntie: De compiler bereikt een lineaire diepte voor LNN-architecturen en een logaritmische diepte voor all-to-all architecturen. De resource-kosten schalen met de maximale Schmidt-rang $\chi$ in plaats van de volledige Hilbert-ruimte dimensie $2^N$ .
Complement Prestaties: De experimenten bevestigen dat het voorbereiden van een complement-toestand niet leidt tot een exponentiële overhead in circuitdiepte of gate-aantal vergeleken met de basis-toestand, mits de onderliggende taal regulier is.
Compile Tijd: Het gebruik van DFA-minimalisatie vóór de MPS-conversie vermindert de compile-tijd aanzienlijk vergeleken met methoden die direct op grote tensor-representaties of amplitude-vectoren opereren.
Benchmarking: Op Dicke- en W-toestanden evenaart of overtreft de voorgestelde methode gespecialiseerde routines, terwijl het een algemenere specificatie-interface biedt. Voor complement-toestanden, waar sparse-state compilers falen door de dichte ondersteuning, slaagt de voorgestelde methode efficiënt.

Betekenis
Het artikel beweert een "tussenoplossing" te bieden die de inefficiëntie vermijdt van het behandelen van gestructureerde toestanden als opaak vectoren, en de starheid vermijdt van het vereisen dat gebruikers specifieke toestandsfamilies kennen. Door gebruik te maken van de correspondentie tussen reguliere talen en MPS, ontdekt de compiler automatisch verborgen structuren en comprimeert het de toestandsbeschrijving. Dit maakt de efficiënte voorbereiding van toestanden en hun complementen mogelijk met voorspelbare resource-garanties, een capaciteit die niet wordt ondersteund door bestaande algemene of sparse-state compilers. Het werk suggereert dat formele taaltheorie een krachtig, schaalbaar framework biedt voor quantum-toestand synthese, met name voor toestanden die gedefinieerd worden door combinatorische restricties of symmetrieën.