Ik heb de laatste tijd veel meer hype gezien over quantumcomputers op X, dus dacht ik dat ik een lange post over hen zou doen. Samenvatting: Ik geloof niet dat quantumcomputing binnenkort komt. Ik denk dit omdat er al jaren geen vooruitgang is geboekt op het meest eenvoudige probleem waarvoor quantumcomputers kunnen worden gebruikt, namelijk factorizatie. Het quantumfactoringrecord staat al een decennium op het getal 15 (ja, 15, 3 x 5!) en er is de laatste tijd geen duidelijke vooruitgang geboekt. Mijn redenering staat hieronder. Ik ga dingen uitleggen voor mensen die niet veel wiskunde of informatica weten, maar dit kan nog steeds mensen met wiskundeangst afschrikken. Het factoriseren van grote getallen is interessant omdat verschillende belangrijke cryptografische algoritmen afhankelijk zijn van het feit dat het heel lang duurt om een voldoende groot getal in zijn priemfactoren te factoriseren met conventionele computers. Je kunt een klein getal (zeg 21) heel snel met de hand factoriseren, probeer het gewoon te delen door de getallen te beginnen met 2, dan 3, enzovoort, en je zult snel ontdekken dat 21 3 x 7 is. Echter, dit werkt niet voor echt grote getallen omdat de ruimte van alle getallen die je zou moeten proberen te groot wordt. Als je getallen van ongeveer 1200 decimale cijfers in lengte zou kunnen factoriseren (niet het getal 1200, dat heeft vier cijfers, maar getallen met 1200 cijfers!) zou je veel cryptografische systemen kunnen breken waar mensen om geven, maar niemand weet hoe je dat snel genoeg op een normale computer kunt doen. (Snel genoeg betekent "voordat alle sterren aan de hemel uitbranden.") Enkele jaren geleden toonde Peter Shor aan dat je (in theorie althans) getallen heel snel kunt factoriseren met quantumcomputers. Factoriseren met Shor's Algoritme is, naar mijn mening, de meest voor de hand liggende moeilijk te vervalsen benchmark voor quantumcomputing. In 2016 werd het getal 15 (niet een 15-cijferig getal, het getal 15!) voor de eerste keer gefactoriseerd (natuurlijk in 3 x 5) in een schone, niet-gemanipuleerde demonstratie van Shor's Algoritme. Dit is een klein getal, maar het was een begin. (Er is enige discussie over of het getal 21 ook in een niet-gemanipuleerde demonstratie van Shor's algoritme is gefactoriseerd of niet.) Maar nogmaals, 15 is een twee-cijferig getal. We willen getallen in de duizenden cijfers factoriseren om cryptografische systemen te kunnen breken. Echter, sinds 2016 zijn er geen grotere getallen gefactoriseerd in schone demonstraties van Shor's algoritme. (Sommige mensen hebben beweerd dat ze grotere getallen hebben gefactoriseerd met Shor's Algoritme, maar ze hebben altijd trucs gebruikt die vereisten dat ze de factoren al wisten om het te doen en de quantumcomputer op te zetten met wat neerkomt op voorkennis van het antwoord, wat echt niet het punt is. Ik zoek naar *niet-gemanipuleerde* demonstraties.) We wachten al een lange tijd op iemand die zelfs een iets groter getal dan 15 kan demonstreren. Je zou hopen dat er gestage vooruitgang op dit gebied zou zijn, met iemand die (zeg) een getal als 77 (7 x 11) factoriseert, en dan een zoals 323 (17 x 19), dan iets in de duizenden, enzovoort. Echter, niemand heeft een machine gedemonstreerd die iets beter kan doen dan het getal 15 (wat een kind in zijn hoofd in 3 en 5 kan factoriseren in een paar momenten) en dat record staat al heel lang. Dus, over dit probleem tenminste, een echt basisprobleem dat gemakkelijk uit te leggen is, is er geen gestage vooruitgang in quantumcomputing geweest. We hebben veel hype gehad, veel mensen die quantumcomputers laten zien die zogenaamd algoritmen uitvoeren die niet zo duidelijk schone demonstraties zijn, maar we hebben al een lange tijd niets gezien over factorizatie. Ik zal geloven dat er echte vooruitgang is geboekt in quantumcomputing wanneer we grotere getallen beginnen te zien die gefactoriseerd worden in schone, niet-gemanipuleerde demonstraties van Shor's Algoritme. Ik zal geloven dat we echte vooruitgang hebben geboekt wanneer we vier decimale cijfers kunnen doen, dat wil zeggen, getallen in de duizenden. Zelfs een demonstratie van iets dat een veel groter twee-cijferig getal dan 15 zou kunnen doen, zou welkom zijn. Echter, geen machine die dat kan, staat echt op de korte termijn horizon. Nu, het kunnen breken van codes vereist machines die getallen met *duizenden* cijfers kunnen verwerken, maar we hebben zelfs nog geen drie-cijferige getallen in zicht (of zelfs de meeste twee-cijferige getallen). Dus, mijn persoonlijke benchmark is het zien van zelfs een beetje vooruitgang op dit gebied. Bel me terug wanneer we quantumcomputers hebben die (zeg) 323 succesvol kunnen factoriseren, in een schone, niet-gemanipuleerde demonstratie van Shor's Algoritme die elk samengesteld getal van vergelijkbare grootte zou kunnen verwerken. Tot die tijd denk ik niet dat er veel van belang aan de hand is, althans niet voor mij.

Ik weet niets van dit gebied van de wiskunde, maar het feit dat serieuze wiskundigen praten over hoe goed AI-systemen hen hebben geholpen, is zeer indrukwekkend.