Peter Shor Het was niet de bedoeling om het internet kapot te maken. Maar een algoritme dat hij halverwege de jaren negentig ontwikkelde, dreigde precies dat te doen. In een mijlpaalpapierliet Shor zien hoe een hypothetische computer die gebruik maakte van de eigenaardigheden van de kwantumfysica grote getallen veel sneller in hun priemfactoren kon opsplitsen dan welke gewone klassieke machine dan ook.

Het resultaat had implicaties die veel verder reikten dan de wiskunde. Destijds een essentieel onderdeel van internetbeveiliging genoemd public-key cryptografie gebaseerd op de veronderstelling dat het ontbinden van grote getallen zo rekenkundig moeilijk is dat het feitelijk onmogelijk is. Die veronderstelling ligt vandaag de dag nog steeds ten grondslag aan enkele kritische protocollen. Het algoritme van Shor liet zien dat het spectaculair zou mislukken in een wereld met krachtige quantum computers.

In de afgelopen dertig jaar hebben computerwetenschappers het algoritme van Shor gestroomlijnd ter voorbereiding op de dag dat de kwantumtechnologie volwassen genoeg wordt om het te kunnen uitvoeren. Maar een nieuwe variant, van de computerwetenschapper van de New York University Oded Regev, is sneller in een fundamenteel nieuwe zin. Het is de eerste die de relatie verbetert tussen de grootte van het getal dat wordt meegerekend en het aantal kwantumbewerkingen dat nodig is om dit te ontbinden.

"Het is echt opmerkelijk dat iemand vele, vele jaren later blijkbaar in staat is geweest om de complexiteit van dit resultaat te verbeteren," zei hij Ashley Montanaro, een kwantumcomputeronderzoeker aan de Universiteit van Bristol. “Dit is echt spannend.”

Martin Ekerå, een cryptograaf bij de Zweedse National Communications Security Authority, was het ermee eens dat het artikel van Regev interessant is, maar waarschuwde dat het verslaan van de stand van de techniek in de praktijk verdere optimalisatie vereist. “De oorspronkelijke algoritmen van Shor zijn al verrassend efficiënt, dus het is niet triviaal om grote verbeteringen aan te brengen”, schreef hij in een e-mail.

Regev ontwikkelde zijn nieuwe algoritme door het algoritme van Shor uit te breiden met technieken uit een tak van de cryptografie die zich bezighoudt met hoogdimensionale geometrie.

"Ik had gedacht dat elk algoritme dat met dit basisschema zou werken, gedoemd zou zijn", zegt Shor, een toegepaste wiskundige nu aan het Massachusetts Institute of Technology. "Maar ik had het fout."

Factoren vinden

Kwantumcomputers ontlenen hun kracht aan de bijzondere manier waarop zij informatie verwerken. Klassieke computers gebruiken bits, die zich elk altijd in een van de twee toestanden moeten bevinden, genaamd 0 en 1. Kwantumbits, of ‘qubits’, kunnen zich bovendien in combinaties van hun 0- en 1-toestand bevinden – een fenomeen dat superpositie wordt genoemd. Het is ook mogelijk om meerdere qubits in een collectieve superpositietoestand te brengen: een superpositie van twee qubits heeft vier componenten die tegelijkertijd verschillende berekeningen kunnen uitvoeren, en het aantal van dergelijke componenten groeit exponentieel naarmate het aantal qubits toeneemt. Hierdoor kunnen kwantumcomputers effectief exponentieel veel verschillende berekeningen parallel uitvoeren.

Maar er is een vangst: Het lezen van het resultaat van een berekening die in superpositie is uitgevoerd, onthult alleen het antwoord op het deel dat door één willekeurige component is berekend. Om de voordelen van computergebruik in superpositie te kunnen benutten, moet je op de een of andere manier het eindresultaat in een eenvoudiger toestand plaatsen waarin het veilig is om het resultaat te lezen. Dat is in de meeste gevallen niet mogelijk, en aanvankelijk wist niemand hoe je het voor welk probleem dan ook moest laten werken. “Er waren maar heel weinig mensen die zelfs maar de moed hadden om na te denken over kwantumberekeningen,” zei Regev.

Toen, in 1994, las Shor een krant door de computerwetenschapper Daniel Simon, die liet zien hoe kwantumsuperpositie kan worden benut om een ​​gekunsteld probleem op te lossen. Shor ontdekte hoe hij Simons resultaat kon uitbreiden naar een algemener en praktischer probleem, genaamd menstruatieonderzoek. Er wordt gezegd dat een wiskundige functie periodiek is wanneer de uitvoer ervan herhaaldelijk dezelfde waarden doorloopt naarmate de invoer toeneemt; de lengte van een enkele cyclus staat bekend als de periode van de functie.

Om de periode van een bepaalde functie te vinden met behulp van een kwantumcomputer, begin je met het opzetten van een zeer grote superpositie waarin elke component de uitvoer van de functie berekent voor een andere invoer. Gebruik vervolgens de methode van Shor om die grote superpositie in een eenvoudiger toestand om te zetten en lees het resultaat. Op dat moment kan een klassieke computer het overnemen en de berekening snel voltooien. Over het geheel genomen werkt het periodebepalingsalgoritme van Shor exponentieel sneller dan welk klassiek alternatief dan ook, omdat het tegelijkertijd verschillende uitvoer van de periodieke functie berekent met behulp van superpositie.

Terwijl Shor zocht naar toepassingen voor zijn algoritme voor het vinden van kwantumperioden, herontdekte hij een eerder bekende maar obscure wiskundige stelling: voor elk getal bestaat er een periodieke functie waarvan de perioden verband houden met de belangrijkste factoren van het getal. Dus als er een getal is dat je in factoren wilt betrekken, kun je de overeenkomstige functie berekenen en het probleem vervolgens oplossen met behulp van periodebepaling – “precies waar kwantumcomputers zo goed in zijn”, zei Regev.

Op een klassieke computer zou dit een tergend langzame manier zijn om een ​​groot getal te ontbinden; langzamer zelfs dan alle mogelijke factoren te proberen. Maar de methode van Shor versnelt het proces exponentieel, waardoor het vinden van periodes een ideale manier is om een ​​snel kwantumfactoralgoritme te construeren.

Het algoritme van Shor was een van de weinige vroege resultaten die kwantumcomputing transformeerde van een obscuur deelgebied van de theoretische informatica tot de moloch die het nu is. Maar het algoritme in de praktijk brengen is een hele klus, omdat kwantumcomputers notoir gevoelig zijn voor fouten: naast de qubits die nodig zijn om hun berekeningen uit te voeren, hebben ze nog vele andere nodig. extra werk om te voorkomen dat ze falen. A recente paper door Ekerå en de Google-onderzoeker Craig Gidney schat dat het gebruik van het algoritme van Shor om een ​​beveiligingsstandaardnummer van 2,048 bits (ongeveer 600 cijfers lang) te factoriseren een kwantumcomputer met 20 miljoen qubits zou vereisen. De moderne machines van vandaag hebben er hooguit een paar honderd.

Dat is de reden waarom sommige cruciale internetprotocollen nog steeds afhankelijk zijn van hoe moeilijk het is om grote getallen in factoren te verwerken, maar onderzoekers willen niet te zelfgenoegzaam worden. theoretisch en technologische innovaties zouden het vereiste aantal qubits verder kunnen verlagen, en er is geen bewijs dat het algoritme van Shor optimaal is. Er zou een beter kwantumfactoralgoritme kunnen bestaan ​​dat nog niemand heeft ontdekt.

Als dat zo is, zei Regev, ‘moeten we het zo vroeg mogelijk weten, voordat het te laat is.’

Verdwaald in de bomen

Regev begon zijn academische carrière eind jaren negentig, toen cryptografen op zoek waren naar een nieuwe vorm van cryptografie met publieke sleutels die niet kwetsbaar was voor het algoritme van Shor. De meest veelbelovende aanpak, genaamd roostergebaseerde cryptografie, is afhankelijk van de schijnbare moeilijkheid van rekenproblemen waarbij hoogdimensionale reeksen punten of roosters betrokken zijn. Eén zo'n probleem lijkt op de taak om de boom te lokaliseren die zich het dichtst bij een willekeurig punt in een bos bevindt.

“Als het een honderddimensionaal bos is, dan is dat veel ingewikkelder dan wanneer het een tweedimensionaal bos is,” zei Greg Kuperberg, een wiskundige aan de Universiteit van Californië, Davis.

Regev begon roostergebaseerde cryptografie te bestuderen als postdoc, aanvankelijk als aanvaller. Hij wilde de nieuwe aanpak aan een stresstest onderwerpen door zwakheden te vinden die een kwantumcomputer zou kunnen misbruiken. Maar hij kon geen enkele vooruitgang boeken, en hij vroeg zich al snel af of daar een diepere reden voor was. In 2005 vond hij een manier om die mislukte aanvallen om te zetten in een vorm van op roosters gebaseerde cryptografie superieur aan alle andere varianten.

"Oded is absoluut briljant met roosters", zei Kuperberg.

Terwijl Regev in de loop der jaren het algoritme van Shor aan opeenvolgende generaties studenten leerde, vroeg hij zich af of de technieken die hij had gebruikt voor het aanvallen van op roosters gebaseerde cryptografie daadwerkelijk nuttig zouden kunnen zijn bij het factoriseren van algoritmen. Dat komt omdat één stap in de laatste, klassieke fase van Shor's algoritme neerkomt op het vinden van het dichtstbijzijnde punt in een eendimensionaal rooster. Dat eendimensionale probleem is triviaal eenvoudig, maar de gelijkenis met het analoge probleem in honderden dimensies waarvan de hardheid ten grondslag ligt aan op roosters gebaseerde cryptografie was onmiskenbaar.

"Als je iemand bent die net als ik roosters maakt, denk je: 'Oké, er is hier een rooster aan de hand'", zei Regev. “Maar het was mij niet duidelijk hoe ik daar gebruik van moest maken.” Jarenlang speelde hij met andere ideeën voor nieuwe algoritmen voor kwantumfactoring, maar hij kwam nooit verder. Afgelopen winter keerde hij terug naar het probleem en besloot dat verleidelijke verband tussen factoring en op roosters gebaseerde cryptografie vast te stellen. Deze keer vond hij succes.

Extra afmetingen

Regev wist dat hij moest beginnen met het generaliseren van de periodieke functie die de kern vormt van Shors algoritme, van één dimensie naar vele dimensies. In het algoritme van Shor omvat deze functie het herhaaldelijk vermenigvuldigen van een willekeurig getal, genaamd g, met zichzelf. Maar de periode van deze functie is het aantal keren dat je moet vermenigvuldigen g voordat de uitvoer van de functie zich begint te herhalen – kan erg groot zijn, en dat betekent dat een kwantumcomputer grote getallen moet vermenigvuldigen in sommige componenten van de superpositie die hij gebruikt om de periodieke functie te berekenen. Deze grote vermenigvuldigingen vormen het rekentechnisch duurste onderdeel van het algoritme van Shor.

De analoge tweedimensionale functie gebruikt in plaats daarvan een paar getallen, g₁ en g₂. Het houdt vermenigvuldiging in g₁ met zichzelf vele malen en dan herhaaldelijk vermenigvuldigen met g₂. De periode van deze functie is ook tweedimensionaal: hij wordt gedefinieerd door het aantal g₁ vermenigvuldigingen en g₂ vermenigvuldigingen die er samen voor zorgen dat de uitvoer van de functie begint te herhalen. Er zijn veel verschillende combinaties van g₁ en g₂ vermenigvuldigingen die het lukken.

Regev heeft de technische details doorgenomen om het algoritme te generaliseren naar een willekeurig aantal dimensies, niet slechts twee, maar zijn eerste resultaten waren niet bemoedigend. Om de periodieke functie in veel dimensies te berekenen, zou de kwantumcomputer nog steeds veel getallen met elkaar moeten vermenigvuldigen. Elk getal hoefde niet zo vaak te worden vermenigvuldigd als in het eendimensionale geval, maar er waren wel duidelijker getallen om te vermenigvuldigen. Het geheel leek een wasbeurt.

"Je denkt: 'Geweldig, ik heb gewoon alles in hoge dimensies gedaan, en het is precies dezelfde speelduur als die van Shor'", zei Regev. “Daar zat ik een tijdje mee vast.” Toen besefte hij dat hij het probleem kon omzeilen door de volgorde van de vermenigvuldigingen te veranderen. In plaats van herhaaldelijk getallen aan één enkel product te koppelen dat in de loop van de kwantumberekening steeds groter zou worden, begon hij met paren van kleine getallen, vermenigvuldigde hij de resulterende producten met elkaar en ging hij verder naar boven. Het totale aantal vermenigvuldigingen veranderde niet veel, maar nu gaat het bijna allemaal om relatief kleine getallen, waardoor de berekening sneller gaat.

“Dat maakt het verschil in de wereld”, zegt hij Vinod Vaikuntanathan, een cryptograaf bij MIT.

In eerste instantie leek het erop dat Regev zojuist het ene probleem door het andere had vervangen. Hij had de kwantumberekening van de periodieke functie versneld door het aantal dimensies te vergroten, maar de daaropvolgende klassieke berekening die nodig was om de periode te extraheren was nu vergelijkbaar met het lokaliseren van het dichtstbijzijnde roosterpunt in een hoogdimensionale ruimte – een taak waarvan algemeen wordt aangenomen dat deze hard zijn. De analogie met op roosters gebaseerde cryptografie die de aanleiding vormde voor zijn nieuwe aanpak leek tot mislukken gedoemd.

Op een koude ochtend in maart, voordat hij naar een seminar aan de Universiteit van Princeton ging, wachtte Regev op de collega met wie hij aan het carpoolen was. "Ik kwam vroeg aan en hij was te laat om de auto op te halen", zei hij. Terwijl hij zat te wachten, kwam plotseling het laatste stukje van de puzzel naar hem toe. “Dat was het moment waarop alles op zijn plek viel, maar het was wel even aan het bakken.”

Het kwam allemaal neer op het juiste aantal dimensies. Toen de roosterdimensie te laag was, kon zijn algoritme niet optimaal profiteren van de versnelling door het vermenigvuldigen van kleinere getallen. Als het te hoog was, was de kwantumberekening snel, maar voor het klassieke deel moest een onbetaalbaar moeilijk roosterprobleem worden opgelost. Regev had vanaf het begin geweten dat hij, om enige hoop op succes te hebben, ergens daar tussenin moest werken, maar het was niet duidelijk of er een goede plek bestond. Die ochtend in maart besefte hij hoe hij de details van het algoritme kon aanpassen, zodat het snel in enkele tientallen dimensies kon werken.

Schrijven in het zand

De verbetering was diepgaand. Het aantal elementaire logische stappen in het kwantumgedeelte van het algoritme van Regev is evenredig met n^1.5 bij het factoriseren van een n-bitnummer, in plaats van n² zoals in het algoritme van Shor. Het algoritme herhaalt dat kwantumdeel enkele tientallen keren en combineert de resultaten om een ​​hoogdimensionaal rooster in kaart te brengen, waaruit het de periode kan afleiden en het getal kan ontbinden. Het algoritme als geheel werkt dus misschien niet sneller, maar het versnellen van het kwantumgedeelte door het aantal vereiste stappen te verminderen zou het gemakkelijker kunnen maken om het in de praktijk te brengen.

Uiteraard is de tijd die nodig is om een ​​kwantumalgoritme uit te voeren slechts een van de vele overwegingen. Even belangrijk is het aantal benodigde qubits, wat analoog is aan het geheugen dat nodig is om tussenwaarden op te slaan tijdens een gewone klassieke berekening. Het aantal qubits dat het algoritme van Shor nodig heeft om een ​​factor te bepalen n-bitgetal is evenredig met n, terwijl het algoritme van Regev in zijn oorspronkelijke vorm een ​​aantal qubits vereist dat evenredig is aan n^1.5 — een groot verschil voor 2,048-bits getallen.

Bij klassiek computergebruik is snelheid meestal een belangrijker overweging dan geheugen, omdat klassieke bits extreem robuust zijn: u kunt een bestand op uw computer opslaan en hoeft zich geen zorgen te maken dat het willekeurig verandert als u het later opnieuw opent. Quantum computing-onderzoekers hebben niet altijd zoveel geluk.

“Onze qubits proberen voortdurend uit elkaar te vallen, en wij proberen te voorkomen dat ze uit elkaar vallen”, zegt Gidney. “Het is alsof je in het zand probeert te schrijven en de wind het wegblaast.” Dat betekent dat de extra qubits die het algoritme van Regev nodig heeft een groot nadeel kunnen zijn.

Maar Regevs artikel is niet het einde van het verhaal. Twee weken geleden vonden Vaikuntanathan en zijn afgestudeerde student Seyoon Ragavan een manier om het geheugengebruik van het algoritme te verminderen. Hun variant van het algoritme van Regev vereist, net als het oorspronkelijke algoritme van Shor, een aantal qubits dat evenredig is aan n dan n^1.5. Ekerå schreef in een e-mail dat het werk “ons een stuk dichter bij een implementatie brengt die in de praktijk efficiënter zou zijn.”

De bredere les van Regevs nieuwe algoritme, afgezien van de implicaties voor factoring, is dat onderzoekers op het gebied van kwantumcomputers altijd open moeten staan ​​voor verrassingen, zelfs bij problemen die al tientallen jaren worden bestudeerd.

“Deze variant van mijn algoritme was dertig jaar lang onontdekt en kwam uit de lucht vallen”, zegt Shor. “Er zijn waarschijnlijk nog veel andere kwantumalgoritmen te vinden.”

Noot van de redactie: Oded Regev ontvangt financiering van de Simons Foundation, die ook dit redactioneel onafhankelijke tijdschrift financiert. Financieringsbeslissingen van de Simons Foundation hebben geen invloed op onze dekking. Meer details zijn beschikbaar Hier.

Quanta voert een reeks onderzoeken uit om ons publiek beter van dienst te zijn. Neem onze lezersenquête informatica en je doet mee om gratis te winnen Quanta koopwaar.