← Nieuwste papers
⚛️ kwantumfysica

Formally verified harness for Shor's order finding algorithm with O(n2+ϵ)O(n^{2+\epsilon}) gate cost

Dit artikel presenteert een formeel geverifieerde harness die recursieve circuitontwerpbeleid uit externe bronnen, zoals AI-agenten, inzuigt om automatisch machine-gecontroleerde bewijzen van wiskundige correctheid en O(n2+ϵ)O(n^{2+\epsilon}) gate-kosten schaling voor de orde-vinding van Shor te genereren, waardoor een open uitdaging wordt mogelijk gemaakt voor het ontdekken van efficiëntere kwantumfactorisatiecircuits met gegarandeerde correctheid.

Oorspronkelijke auteur: Anirudh Suresh, Joshua M. Courtney, Runzhou Tao, Yudong Cao

Gepubliceerd 2026-11-17
📖 9 min leestijd🧠 Diepgaand

Oorspronkelijke auteur: Anirudh Suresh, Joshua M. Courtney, Runzhou Tao, Yudong Cao

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 auteur. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

In het landschap van de moderne informatica bestaat er een fundamentele spanning tussen de snelheid van berekeningen en de veiligheid van geheimen. Decennialang heeft de veiligheid van digitale communicatie vertrouwd op een wiskundig slot: de moeilijkheid om een groot getal af te breken in zijn twee priemgetal-bouwstenen. Terwijl klassieke computers moeite hebben met deze taak en duizenden jaren nodig hebben om één enkele code te kraken, zou een theoretische machine gebouwd op de wetten van de kwantumfysica dit in een fractie van een seconde kunnen oplossen. Deze potentiële dreiging heeft wetenschappers gedreven om het blauwdruk voor een dergelijke machine te verfijnen, specifiek een algoritme dat bekend staat als het algoritme van Shor. De uitdaging is nooit geweest of het algoritme in theorie werkt, maar hoe men de fysieke machinerie kan bouwen om het efficiënt uit te voeren. De flessenhals ligt in de rekenkunde: de specifieke stappen die vereist zijn voor het vermenigvuldigen en delen van getallen binnen het kwantumsysteem. Jarenlang vereisten de meest efficiënte bekende methoden voor deze stappen een aantal operaties dat zo snel groeide met de grootte van het getal, dat zelfs de krachtigste toekomstige computers niet genoeg middelen zouden hebben om de taak uit te voeren.

Een team van onderzoekers heeft nu een nieuw kader geïntroduceerd dat ontworpen is om door deze complexe ontwerpruimte te navigeren, een manier biedt om snellere, efficiëntere circuits te vinden terwijl gegarandeerd wordt dat de wiskunde correct blijft. Ze noemen hun creatie ForShor, een formeel geverifieerde harness die fungeert als zowel een scheidsrechter als een bouwer. In plaats van wetenschappers te vragen om handmatig elke mogelijke variatie van het kwantumcircuit te construeren—een taak die gevoelig is voor menselijke fouten en onmogelijk grondig te controleren is—hebben zij een systeem gebouwd waarin onderzoekers een set regels, of een "beleid" (policy), kunnen indienen die beschrijft hoe de vermenigvuldiging moet worden opgesplitst. Het systeem controleert deze regels vervolgens automatisch tegen een rigoureuze wiskundige standaard. Als de regels slagen, genereert het systeem een volledig, geverifieerd kwantumprogramma en berekent het exact hoeveel fysieke componenten, bekend als gates, nodig zouden zijn om het uit te voeren. Deze aanpak maakt een open zoektocht naar betere ontwerpen mogelijk, waarbij menselijke experts en kunstmatige intelligentie-agenten kunnen concurreren om het meest efficiënte pad te vinden, terwijl het systeem tegelijkertijd waarborgt dat het resulterende circuit wiskundig solide is en klaar is voor realistische bronestimatie.

De kern van het probleem ligt in de manier waarop het algoritme de vermenigvuldiging afhandelt. Om een groot getal te ontbinden, moet de kwantumcomputer een enorme reeks vermenigvuldigingen uitvoeren. De onderzoekers richtten zich op een specifieke techniek genaamd recursieve Toom-Cook-vermenigvuldiging, die werkt als een geavanceerde vorm van lang delen. In plaats van twee grote getallen direct te vermenigvuldigen, splitst de methode ze op in kleinere brokken, vermenigvuldigt die brokken en combineert de resultaten vervolgens weer. De efficiëntie van dit proces hangt volledig af van hoe de brokken worden verdeeld en hoe de resultaten worden samengevoegd. Er zijn talloze manieren om deze stappen te arrangeren, wat een enorme ontwerpruimte creëert. De onderzoekers ontdekten dat hoewel er een exacte wiskundige methode bestaat om de absoluut beste rangschikking te vinden, het computationeel onmogelijk is om deze uit te voeren voor de groottes van getallen die in de moderne cryptografie worden gebruikt. Het aantal mogelijkheden is zo groot dat zelfs met de snelste supercomputers het controleren van elke optie langer zou duren dan het huidige universum oud is.

Om dit op te lossen, creëerde het team een systeem dat het creatieve werk van het ontwerpen van het circuit scheidt van het tijdrovende werk van het verifiëren ervan. Een deelnemer aan hun uitdaging dient een "beleid" in, wat in essentie een set instructies is die de computer vertelt hoe de getallen te splitsen en welke operaties op elk stap uitgevoerd moeten worden. Het systeem controleert vervolgens of deze instructies een strikte set logische regels volgen. Deze regels zorgen ervoor dat de stappen omkeerbaar zijn, dat er geen informatie verloren gaat en dat het eindresultaat wiskundig equivalent is aan de beoogde vermenigvuldiging. Als het beleid deze controle doorstaat, construeert het systeem automatisch het volledige kwantumcircuit en berekent het de bronkosten. Dit proces is geformaliseerd op een manier die geen ruimte laat voor twijfel; het systeem bewijst dat elk geldig beleid een correct resultaat zal produceren, ongeacht wie het ontwerp heeft gemaakt of hoe complex het ontwerp is.

De resultaten van deze aanpak zijn significant. Door de zoektocht naar betere ontwerpen toe te staan zonder de angst om fouten te introduceren, hebben de onderzoekers aangetoond dat het mogelijk is om het aantal operaties dat vereist is voor het algoritme van Shor te verminderen. Hun analyse laat zien dat met de juiste ontwerpkeuzes het aantal operaties veel langzamer kan schalen dan voorheen gedacht, bewegend van een kubische groeivoet naar iets dat dichter bij een kwadratische groei ligt. Dit betekent dat voor zeer grote getallen de nieuwe methode aanzienlijk minder middelen zou kunnen vereisen dan de standaard benaderingen. De onderzoekers waarschuwen echter voorzichtig dat hoewel de theoretische verbeteringen substantieel zijn, de huidige beste ontwerpen nog steeds een aantal fysieke componenten vereisen dat ver buiten de reikwijdte van de huidige technologie ligt. Voor een getal zo groot als die in de huidige encryptie worden gebruikt, schat het systeem dat het meest efficiënte bekende ontwerp nog steeds meer dan een biljoen specifieke operaties, bekend als T-gates, zou vereisen.

Het project benadrukt ook een nieuwe manier van wetenschap bedrijven in het tijdperk van kunstmatige intelligentie. Het raamwerk is ontworpen als een open uitdaging, waarbij zowel menselijke onderzoekers als AI-agenten worden uitgenodigd om hun eigen ontwerpen in te dienen. Het systeem fungeert als een neutrale rechter, die elk inzending accepteert die aan de wiskundige criteria voldoet en die niet voldoen afwijst. Dit creëert een veilige omgeving voor innovatie, waar het risico op een gebrekkig ontwerp wordt geëlimineerd door de door machines gecontroleerde verificatie. De onderzoekers ontdekten dat het vinden van de optimale oplossing zelfs binnen een beperkte set ontwerpkeuzes ongelooflijk moeilijk is. Ze testten hun systeem met een specifiek voorbeeld met een getal van 2048 bits, een grootte die veel wordt gebruikt in encryptie. Het systeem bevestigde dat hoewel er in theorie een exacte optimale oplossing bestaat, het vinden ervan via brute force onmogelijk is. In plaats daarvan staat het systeem heuristische zoektochten toe, waarbij intelligente agenten de ontwerpruimte kunnen verkennen en betere oplossingen kunnen voorstellen die vervolgens direct worden geverifieerd.

Een van de belangrijkste bevindingen is dat de efficiëntie van het algoritme sterk afhangt van de grootte van het getal dat gefactoreerd wordt. De onderzoekers ontdekten dat de beste manier om de getallen te splitsen verandert naarmate de getallen groter worden. Een ontwerp dat goed werkt voor een klein getal, kan inefficiënt zijn voor een groter getal. Hun systeem kan dit opvangen door verschillende splitsingsstrategieën op verschillende stadia van de berekening toe te staan. Deze flexibiliteit is cruciaal voor het verleggen van de grenzen van wat mogelijk is. Het team vergeleek hun resultaten met eerdere methoden en stelde vast dat hun aanpak een duidelijk voordeel biedt in termen van het aantal vereiste operaties, maar alleen voor getallen die aanzienlijk groter zijn dan de huidige in gebruik zijnde getallen. Voor de standaard 2048-bits getallen is de verbetering aanwezig, maar nog niet groot genoeg om de taak haalbaar te maken met nabije technologie.

Het werk overbrugt ook de kloof tussen abstracte wiskundige bewijzen en praktische engineering. Het systeem neemt de geverifieerde wiskundige beschrijving van het circuit en vertaalt deze naar een formaat dat kan worden gebruikt door softwaretools die ontworpen zijn om de benodigde fysieke middelen te schatten. Deze vertaling is een kritische stap, aangezien het onderzoekers in staat stelt precies te zien hoeveel qubits, of kwantumbits, en hoeveel foutcorrectiecomponenten vereist zouden zijn om het algoritme op een echte machine uit te voeren. De onderzoekers gebruikten deze pijplijn om gedetailleerde schattingen te genereren voor diverse scenario's, waarmee zij bevestigden dat de theoretische verbeteringen standhouden wanneer ze worden vertaald naar concrete bronnenaantallen. Ze vonden dat het aantal operaties op een voorspelbare manier groeit, volgens de wiskundige patronen die zij hebben bewezen.

Ondanks de vooruitgang erkennen de onderzoekers dat er nog veel werk te doen is. De huidige schattingen zijn gebaseerd op geïdealiseerde modellen van de kwantumcomputer, en de echte wereld van hardware zal extra uitdagingen introduceren, zoals ruis en de noodzaak voor foutcorrectie. Het systeem houdt nog geen rekening met de fysieke lay-out van de machine of de tijd die nodig is om informatie tussen verschillende delen van de processor te verplaatsen. Dit zijn de volgende grenzen voor het vakgebied. De mogelijkheid om de correctheid van het algoritme formeel te verifiëren terwijl tegelijkertijd gezocht wordt naar het meest efficiënte ontwerp, is echter een grote stap voorwaarts. Het biedt een solide fundament waarop toekomstige verbeteringen kunnen worden gebouwd, waarbij wordt gewaarborgd dat elk nieuw idee wordt getoetst aan de hoogste standaarden van wiskundige strengheid.

Het project dient als een bewijs van concept voor een nieuw tijdperk van quantum software engineering. Door formele verificatie te combineren met open, automatische zoektochten, hebben de onderzoekers een instrument gecreëerd dat de complexiteit van kwantumalgoritmen kan afhandelen op een manier die voorheen onmogelijk was. Deze aanpak versnelt niet alleen de zoektocht naar betere algoritmen, maar bouwt ook vertrouwen in de resultaten, aangezien elke claim wordt ondersteund door een door een machine gecontroleerd bewijs. Naarmate het veld van quantum computing zich blijft ontwikkelen, zullen instrumenten zoals deze essentieel zijn voor het navigeren door de enorme ontwerpruimte en het omzetten van theoretische mogelijkheden in praktische realiteiten. De onderzoekers hebben hun raamwerk publiekelijk beschikbaar gesteld, waarbij zij de wereldwijde gemeenschap uitnodigen om bij te dragen aan de zoektocht naar de meest efficiënte manier om grote getallen te ontbinden, een taak die een van de belangrijkste uitdagingen in het veld blijft.

Verdrinkt u in papers in uw vakgebied?

Ontvang dagelijkse digests van de nieuwste papers die bij uw onderzoekswoorden passen — met technische samenvattingen, in uw taal.

Probeer Digest →