Jeg har sett mye mer hype om kvantedatamaskiner på X nylig, så jeg tenkte jeg skulle lage et langt innlegg om dem. Sammendrag: Jeg tror ikke kvanteberegning kommer med det første. Jeg tror dette fordi det ikke har blitt gjort noen fremskritt på mange år med det enkleste problemet kvantedatamaskiner kan brukes til, som er factoring. Kvantefaktorrekorden har vært rundt tallet 15 (ja, 15, 3 x 5!) i et tiår nå, og ingen åpenbar fremgang har skjedd i det siste. Mitt resonnement er nedenfor. Jeg skal bryte ting ned for folk som ikke kan mye matematikk eller informatikk, men dette kan fortsatt skremme folk med mattefobier. Å faktorisere store tall er av interesse fordi flere viktige kryptografiske algoritmer er avhengige av det faktum at det tar veldig lang tid å faktorisere et tilstrekkelig stort tall i primfaktorene ved hjelp av konvensjonelle datamaskiner. Du kan faktorisere et lite tall (for eksempel 21) for hånd veldig raskt, bare prøv å dele det på tallene som starter med 2 og deretter 3 og så videre, og du vil raskt oppdage at 21 er 3 x 7. Dette fungerer imidlertid ikke for veldig store tall fordi plassen til alle tallene du trenger å prøve blir for stor. Hvis du kunne faktorisere tall over omtrent 1200 desimaler i lengde (ikke tallet 1200, som har fire sifre, tall med 1200 sifre!) kan du ødelegge mange kryptografiske systemer som folk bryr seg om, men ingen vet hvordan de skal gjøre det raskt nok på en vanlig datamaskin. (Raskt nok betyr "før alle stjernene på himmelen brenner ut".) For noen år siden viste Peter Shor at du (i det minste i teorien) kunne faktorisere tall veldig raskt ved hjelp av kvantedatamaskiner. Factoring ved hjelp av Shors algoritme er, etter min mening, den mest åpenbare målestokken som er vanskelig å forfalske for kvantedatabehandling. I 2016 ble tallet 15 (ikke et 15-sifret tall, tallet 15!) for første gang tatt med (åpenbart i 3 x 5) i en ren, urigget demonstrasjon av Shors algoritme. Dette er et lite tall, men det var en start. (Det er noen diskusjoner om hvorvidt tallet 21 også har blitt tatt med i en urigget demonstrasjon av Shors algoritme eller ikke.) Men igjen, 15 er et tosifret tall. Vi ønsker å ta hensyn til tall i tusenvis av sifre for å kunne bryte kryptografiske systemer. Siden 2016 har imidlertid ingen større tall blitt tatt med i rene demonstrasjoner av Shors algoritme. (Noen mennesker har hevdet at de har tatt hensyn til større tall ved hjelp av Shors algoritme, men de har alltid brukt triks som krevde at de allerede kjente faktorene for å gjøre det og sette opp kvantedatamaskinen med det som utgjør forhåndskunnskap om svaret, noe som egentlig ikke er poenget. Jeg ser etter *uriggede* demonstrasjoner.) Vi har ventet lenge på at noen skal demonstrere faktorisering av selv et litt større tall enn 15. Du hadde håpet at det kunne være jevn fremgang på dette, med noen som faktoriserer (si) et tall som 77 (7 x 11), og deretter ett som 323 (17 x 19), så noe tusenvis, og så videre. Imidlertid har ingen demonstrert en maskin som kan gjøre noe bedre enn tallet 15 (som et barn kan faktorisere i hodet i 3 og 5 på et øyeblikk), og den rekorden har stått veldig lenge. Så, i det minste på dette problemet, et veldig grunnleggende problem som er lett å forklare, har det ikke vært noen jevn fremgang innen kvanteberegning. Vi har hatt mye hype, mange mennesker som viser frem kvantedatamaskiner som visstnok kjører algoritmer som ikke er fullt så åpenbart rene demonstrasjoner, men vi har ikke sett noe på lenge om factoring. Jeg vil tro at det har vært reell fremgang innen kvantedatabehandling når vi begynner å se større tall tatt med i rene, uriggede demonstrasjoner av Shors algoritme. Jeg vil tro at vi har gjort reelle fremskritt når vi kan gjøre fire desimaler, det vil si tall i tusenvis. Selv en demonstrasjon av noe som kan gjøre et mye større tosifret tall enn 15 ville være velkommen. Imidlertid er ingen maskin som kan gjøre det virkelig på kort sikt. Å kunne knekke koder krever maskiner som kan håndtere tall med *tusenvis* av sifre, men vi har ikke engang tresifrede tall i sikte ennå (eller til og med de fleste tosifrede tall). Så min personlige målestokk er å se enda litt fremgang på dette. Ring meg tilbake når vi har kvantedatamaskiner som kan faktorisere (si) 323 vellykket, i en ren, urigget demo av Shors algoritme som vil håndtere et hvilket som helst sammensatt antall av lignende størrelse. Inntil da tror jeg ikke det er mye av interesse på gang, i hvert fall ikke for meg.

(BTW, jeg vil ikke gi inntrykk av at jeg tror kvanteberegning er umulig eller noe. Jeg sier bare at fra der jeg står, har den siste fremgangen ikke vært åpenbar, og vi er fortsatt langt unna å løse enkle problemer som å faktorisere tall med det.)

Dette betyr forresten heller ikke at selskaper som Google er dumme for å drive ren forskning på kvantedatabehandling. Jeg tror at det er verdt å jobbe med. Det er bare ikke av noen nært forestående praktisk anvendelse. Det kan også være at NSA eller andre slike organisasjoner har gjort større betydelige fremskritt i problemet enn den åpne forskningsverdenen har, men det er åpenbart ikke informasjon jeg ville være kjent med. Til slutt betyr ikke dette at forskning på postkvantekryptografiske algoritmer er en dårlig idé.

I mitt opprinnelige innlegg øverst unngikk jeg å nevne hvor vanskelig skaleringsproblemene er. For det meste konsentrerte jeg meg bare om det faktum at ingenting av skaleringen faktisk har skjedd. Og for å være sikker, på et tidspunkt er det veldig mulig at feilrettingsgreiene vil begynne å vises. Men skalering til å ta hensyn til seriøse tall kommer ikke til å skje dagen etter det.

@defendtheworld Så uansett, igjen: Jeg begynner å tro når jeg ser teknologien gå videre fra faktorisering 15. Og ja, det betyr at en enorm mengde arbeid allerede vil være gjort, men det vil også etterlate en enorm mengde arbeid som gjenstår.