⚛️ quantum physics

Distance-Finding Algorithms for Quantum Codes and Circuits

Deze paper introduceert en benchmarkt een breed scala aan methoden voor het bepalen van de afstand van klassieke en quantum-codes, waarbij de QDistEvol-algoritme specifiek goed presteert voor quantum LDPC-codes, en presenteert de bijbehorende tools in het Python-pakket codeDistance.

Oorspronkelijke auteurs: Mark Webster, Abraham Jacob, Oscar Higgott

Gepubliceerd 2026-03-25

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Mark Webster, Abraham Jacob, Oscar Higgott

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 enorme, ondoordringbare kasteelmuur bouwt om je kostbaarste schatten (in dit geval: kwantumbitjes of "qubits") te beschermen tegen de chaos van de buitenwereld. Deze muur is een kwantumfoutcorrectiecode.

Maar hoe weet je of je muur wel echt sterk genoeg is? Als je muur te dun is, breekt hij al bij de eerste storm. Als hij te dik is, kost hij onnodig veel bouwmaterialen en tijd. De afstand (distance) van zo'n code is precies dat maatstaf: het is het minimum aantal "breuken" of fouten die nodig zijn om je schat te vernietigen zonder dat je het merkt. Hoe groter de afstand, hoe sterker de muur.

Het probleem? Het berekenen van deze afstand voor moderne, geavanceerde muren (zoals Quantum LDPC-codes) is als proberen het zwaarste gewicht te vinden in een berg van miljoenen stenen, terwijl je blind bent. De bestaande methoden zijn vaak te traag of te onnauwkeurig.

Dit artikel is een grote test (benchmark) van verschillende manieren om die afstand te vinden. De auteurs, Mark Webster, Abraham Jacob en Oscar Higgott, hebben een heel arsenaal aan gereedschappen getest om te zien welke het beste werkt.

Hier is een simpele uitleg van wat ze hebben gedaan, met behulp van alledaagse metaforen:

1. De Twee Soorten Zoekers: De "Perfecte" vs. De "Snelle"

De auteurs hebben alle methoden in twee groepen verdeeld:

De Exacte Methodes (De Perfecte Detectives):
- Voorbeeld: Brouwer-Zimmermann, MIP (Mixed Integer Programming).
- Hoe het werkt: Deze detectives laten geen steen op de andere. Ze kijken naar elke mogelijke combinatie van fouten om de écht zwaarste te vinden.
- Voordeel: Je krijgt 100% zekerheid over het antwoord.
- Nadeel: Het duurt eeuwen. Het kan dagen duren om een antwoord te krijgen, en als de computer te lang doet, stopt hij misschien halverwege zonder een definitief antwoord.
- Metafoor: Het is alsof je elke mogelijke route door een stad afloopt om de langste weg te vinden. Je vindt hem zeker, maar je bent er de hele dag mee bezig.
De Heuristische Methodes (De Snelle Schatzoekers):
- Voorbeeld: Random Information Set, QDistEvol, Syndroom-decoders.
- Hoe het werkt: Deze gebruiken slimme gissingen, geluk en evolutionaire trucs. Ze zoeken niet naar alles, maar naar de beste kans.
- Voordeel: Ze zijn razendsnel.
- Nadeel: Ze geven geen 100% garantie. Ze zeggen: "Ik heb een fout gevonden van gewicht X, dus de muur is minstens zo sterk." Soms vinden ze de echte zwaarste fout niet, maar ze geven wel een goede schatting.
- Metafoor: Het is alsof je een vlieger in een groot park laat vliegen. Als hij vastzit in een boom, weet je dat er een boom is. Je weet misschien niet waar de hoogste boom staat, maar je weet dat je muur daar niet doorheen breekt.

2. De Nieuwe Ster: QDistEvol

Een van de belangrijkste ontdekkingen in dit papier is een verbeterde versie van een algoritme genaamd QDistEvol.

De Metafoor: Stel je voor dat je op zoek bent naar de beste sleutel voor een slot. De oude methode (QDistRnd) gooide willekeurig duizenden sleutels in het slot. De nieuwe methode (QDistEvol) werkt als een evolutionair proces:
1. Ze maken een groep sleutels.
2. Ze kijken welke het beste past.
3. Ze nemen de beste sleutels, "kruisen" ze met elkaar en maken kleine aanpassingen (mutaties).
4. Na een paar generaties hebben ze een super-sleutel die bijna altijd werkt.
Het Resultaat: Voor de nieuwste, meest belovende codes (LDPC-codes) werkt QDistEvol veel beter dan de oude methoden. Het vindt sneller de juiste afstand en is veel betrouwbaarder.

3. De Uitdaging: Circuits vs. Codes

Het artikel maakt een belangrijk onderscheid:

De Code: De blauwdruk van de muur (de theorie).
Het Circuit: De daadwerkelijke bouw, inclusief de werknemers die fouten kunnen maken tijdens het bouwen.
Het probleem: Het berekenen van de sterkte van de bouwwerkzaamheden (het circuit) is veel moeilijker dan de theorie. De "detector matrix" (de lijst met alle mogelijke fouten) is hier gigantisch groot. Het is alsof je niet alleen de muur moet testen, maar ook elke baksteen, elke metselaar en elke regenbui die erop kan vallen. De auteurs tonen aan dat hun methoden ook hier goed werken, vooral als je eerst wat "ruis" weghaalt (filteren).

4. De Gouden Tips (Wat werkt het beste?)

De auteurs hebben een "keuzehulp" gemaakt voor wetenschappers die nieuwe codes ontwerpen:

Voor kleine, simpele codes: Gebruik Magma (een krachtige, dure software). Die is als een meester-detective die alles tot in de puntjes uitzoekt.
Voor de nieuwe, grote LDPC-codes: Gebruik QDistEvol (heuristisch) of m4riCC (exact). Dit zijn de snelste en slimste gereedschappen voor de moderne bouw.
Voor circuits: Soms helpt het om eerst de "detector matrix" te filteren (een soort vuilnisbak leegmaken) voordat je begint met rekenen. Dit maakt de berekening veel sneller.

Conclusie

Dit papier is als een grote handleiding voor de bouwvakkers van de kwantumcomputer. Het vertelt ons: "Gebruik niet zomaar een hamer om te boren; gebruik de juiste boor voor het juiste materiaal."

Door te laten zien welke algoritmen het snelst en nauwkeurigst zijn, helpen ze de wetenschap om sneller de beste kwantumcodes te vinden. Dit is cruciaal, want zonder sterke codes kunnen we geen betrouwbare kwantumcomputers bouwen. De auteurs hebben al hun gereedschappen en testdata openbaar gemaakt in een pakket genaamd codeDistance, zodat iedereen het kan gebruiken om de volgende generatie kwantumcomputers te bouwen.

Titel: Afstandsbepalende Algoritmen voor Quantum Codes en Circuits

Auteurs: Mark Webster, Abraham Jacob en Oscar Higgott (UCL en Google Quantum AI)

1. Het Probleem

De minimale afstand ( $d$ ) van een klassieke of quantum foutcorrectiecode (QEC) is een cruciale maatstaf voor de prestaties, omdat deze aangeeft hoeveel fysieke fouten nodig zijn om een ondetecteerbare logische fout te veroorzaken.

Uitdaging: Hoewel quantum LDPC (Low-Density Parity-Check) codes veelbelovend zijn voor het verminderen van de overhead bij fault-tolerant quantum computing, is het berekenen van hun afstand computatieel zeer intensief.
Complexiteit: Het berekenen van de circuit-afstand (onder circuit-niveau foutmodellen) is aanzienlijk moeilijker dan het vinden van de code-afstand. De detector-foutmatrix van een circuit is vaak twee ordes van grootte groter dan de check-matrix van de code zelf.
Noodzaak: Er is een dringende behoefte aan efficiënte algoritmen om kandidaat-codes en circuits snel te filteren (via boven- en ondergrenzen) voordat er grote investeringen worden gedaan in het ontwerpen van fault-tolerant circuits of het optimaliseren van decoders.

2. Methodologie

De auteurs hebben een uitgebreide benchmark uitgevoerd op een breed scala aan datasets, waaronder klassieke codes, quantum stabilisatorcodes (zowel CSS als non-CSS) en syndrome-extractie circuits.

Categorisatie van Algoritmen: De methoden zijn ingedeeld in twee categorieën:
1. Exacte Methoden: Garanderen de exacte afstand, maar hebben een lange runtime (bijv. Brouwer-Zimmermann, Mixed Integer Programming (MIP), SAT-solvers, Connected Cluster).
2. Heuristische Methoden: Hebben een kortere runtime en leveren vaak een onder- of bovengrens op, maar garanderen niet de exacte waarde (bijv. Random Information Set, Syndrome Decoders, Stim Undetectable Error methoden).
Datasets: Er zijn diverse code-families getest, waaronder:
- Klassieke codes (CodeTables, Lifted Product).
- Quantum codes (Hyperbolische oppervlak- en kleurencodes, Bivariate Bicycle codes, Quantum Tanner codes).
- Syndrome-extractie circuits (Surface codes, Colour codes, Bivariate Bicycle circuits).
Implementatie: De auteurs hebben de codeDistance Python-package ontwikkeld, die wrappers bevat voor bestaande implementaties en nieuwe implementaties biedt, waaronder een verbeterde versie van het QDistEvol algoritme.
Vergelijking: De prestaties werden gemeten op basis van:
- Succespercentage (het vinden van de laagste bekende afstand).
- Verwerkingstijd per succesvolle trial.
- Beperkingen zoals een maximale runtime van 8 uur voor exacte methoden en 48 uur voor heuristische methoden.

3. Belangrijkste Bijdragen

Benchmarking: Een systematische vergelijking van een groot aantal bestaande en nieuwe algoritmen op diverse code-families en circuit-structuren.
QDistEvol Algoritme: De auteurs hebben het QDistEvol-algoritme (gebaseerd op evolutionaire zoekalgoritmen) verfijnd. Dit algoritme gebruikt genetische operaties (mutatie, selectie) op kolom-permutaties om laag-gewicht codewoorden te vinden. De benchmark toont aan dat dit algoritme significant nauwkeuriger is dan andere heuristische methoden voor quantum LDPC codes.
Adaptatie van Bestaande Methodes: Bestaande methoden voor CSS-codes zijn aangepast en geoptimaliseerd voor klassieke codes, non-CSS quantum codes en circuits. Dit omvat het gebruik van verschillende blokkrepresentaties (2-blok, 3-blok, 4-blok) afhankelijk van het algoritme en het type code.
Open Source: Alle algoritmen en testdata zijn beschikbaar gesteld via de codeDistance Python-package, wat de gemeenschap in staat stelt om afstandsbepalingen te herhalen en uit te breiden.
DEM Filtering: Voor circuits met zeer grote Detector Error Models (DEMs) is een filtertechniek ontwikkeld om het aantal foutmechanismen en detectoren te reduceren, waardoor berekeningen haalbaar worden.

4. Resultaten

De benchmarkresultaten tonen duidelijke trends afhankelijk van het type code en circuit:

Exacte Methoden:
- Magma (Brouwer-Zimmermann): Werkt uitstekend voor kleine tot middelgrote klassieke en quantum codes, maar wordt traag voor zeer grote LDPC-codes.
- MIP (Gurobi, SCIP): Biedt goede all-round prestaties. Gurobi is vaak sneller, terwijl SCIP soms nauwkeurigere grenzen geeft bij vroegtijdige stopzetting.
- Connected Cluster (m4riCC): Zeer effectief voor codes met Tanner-graaf van lage graad (zoals hyperbolische oppervlak- en kleurencodes), maar minder geschikt voor codes met hoge graad.
- SAT Solvers (CLISAT): Presteren over het algemeen minder goed dan MIP-methoden in termen van snelheid en nauwkeurigheid.
Heuristische Methoden:
- QDistEvol: Biedt de beste prestaties voor high-rate LDPC codes (zoals Bivariate Bicycle en Lifted Product codes) met een aanzienlijk hoger succespercentage dan random information set methoden.
- QDistRnd / m4riRW: Effectief voor kleinere codes en klassieke codes, maar minder nauwkeurig voor complexe LDPC families.
- BP-OSD (Syndrome Decoder): Werkt goed voor zeer grote hyperbolische oppervlakcodes en circuits waar de check-matrix zeer spaarzaam is, maar presteert minder goed voor andere families.
- Stim-gebaseerde methoden (GEStim, UEStim): Zeer snel en nauwkeurig voor topologische codes met lage graad (waar fouten maximaal 2 of 3 detectoren flippen), maar minder effectief voor algemene LDPC codes.
Circuits: Voor syndrome-extractie circuits is het filteren van het DEM essentieel. Zonder filtering konden veel algoritmen geen resultaten leveren binnen de tijdslimiet. Na filtering presteerden zowel exacte als heuristische methoden aanzienlijk beter.

5. Betekenis en Conclusie

Dit werk biedt een cruciale leidraad voor onderzoekers en ingenieurs die nieuwe quantum foutcorrectiecodes en circuits ontwerpen.

Keuzehulp: De auteurs bieden specifieke aanbevelingen per dataset (zie Tabel 30 en 31 in het paper) over welk algoritme het meest geschikt is voor een bepaald type code of circuit.
Versnelling van Ontwerp: Door snelle en betrouwbare afstandsbepaling mogelijk te maken, kunnen onderzoekers onbelovende code-families sneller uitsluiten en hun focus leggen op de meest veelbelovende kandidaten.
Toekomstgericht: De ontwikkeling van QDistEvol en de open-source beschikbaarheid van de tools vormen een belangrijke stap in de richting van het schaalbaar maken van fault-tolerant quantum computing, waarbij de prestaties van LDPC codes centraal staan.

Kortom, het paper demonstreert dat er geen "one-size-fits-all" oplossing is, maar dat door de juiste combinatie van exacte en heuristische methoden, afhankelijk van de code-structuur, de afstandsbepaling voor de nieuwste generatie quantum codes haalbaar en efficiënt kan worden gemaakt.