Kvantumdatamaskiner, du har kanskje hørt, er magiske uber-maskiner som snart vil kurere kreft og global oppvarming ved å prøve alle mulige svar i forskjellige parallelle universer. I 15 år, på min blogg og andre steder, jeg har gruet meg mot denne tegneserieaktige visjonen, og prøvd å forklare det jeg ser på som den mer subtile, men ironisk nok enda mer fascinerende sannheten. Jeg nærmer meg dette som en offentlig tjeneste og nesten min moralske plikt som kvantedataforsker. Akk, arbeidet føles sisyfisk: Den grufulle hypen om kvantedatamaskiner har bare økt med årene, ettersom selskaper og myndigheter har investert milliarder, og etter hvert som teknologien har utviklet seg til programmerbare 50-qubit-enheter som (på visse konstruerte referanser) virkelig kan gi verdens største superdatamaskiner løp for pengene sine. Og akkurat som i kryptovaluta, maskinlæring og andre trendy felt, har det kommet hucksters med penger.

I reflekterende øyeblikk forstår jeg det imidlertid. Realiteten er at selv om du fjernet alle de dårlige insentivene og grådigheten, ville kvanteberegning fortsatt være vanskelig å forklare kort og ærlig uten matematikk. Som kvanteberegningspioneren Richard Feynman en gang sa om kvanteelektrodynamikkarbeidet som ga ham Nobelprisen, hvis det var mulig å beskrive det i noen få setninger, ville det ikke vært verdt en Nobelpris.

Ikke at det har stoppet folk fra å prøve. Helt siden Peter Shor oppdaget i 1994 at en kvantedatamaskin kunne bryte det meste av krypteringen som beskytter transaksjoner på internett, har spenningen rundt teknologien vært drevet av mer enn bare intellektuell nysgjerrighet. Faktisk blir utviklingen på feltet vanligvis dekket som forretnings- eller teknologihistorier snarere enn som vitenskapelige.

Det ville vært greit hvis en bedrifts- eller teknologireporter sannferdig kunne fortelle leserne: "Se, det er alt dette dype kvantestoffet under panseret, men alt du trenger å forstå er bunnlinjen: Fysikere er på nippet til å bygge raskere datamaskiner som vil revolusjonere alt."

Problemet er at kvantedatamaskiner ikke vil revolusjonere alt.

Ja, de kan en dag løse noen få spesifikke problemer i løpet av minutter som (tror vi) vil ta lengre tid enn universets alder på klassiske datamaskiner. Men det er mange andre viktige problemer som de fleste eksperter tror kvantedatamaskiner vil hjelpe bare beskjedent, om i det hele tatt. Mens Google og andre nylig kom med troverdige påstander om at de hadde oppnådd konstruerte kvantehastigheter, var dette bare for spesifikke, esoteriske benchmarks (som jeg bidratt til å utvikle seg). En kvantedatamaskin som er stor og pålitelig nok til å utkonkurrere klassiske datamaskiner i praktiske applikasjoner som å bryte kryptografiske koder og simulere kjemi er sannsynligvis fortsatt et stykke unna.

Men hvordan kan en programmerbar datamaskin være raskere for bare noen problemer? Vet vi hvilke? Og hva betyr en "stor og pålitelig" kvantedatamaskin i denne sammenhengen? For å svare på disse spørsmålene må vi gå inn i de dype tingene.

La oss starte med kvantemekanikk. (Hva kan være dypere?) Konseptet superposisjon er beryktet vanskelig å gjengi i hverdagslige ord. Så, ikke overraskende, velger mange forfattere en enkel utvei: De sier at superposisjon betyr "begge på en gang", slik at en kvantebit, eller qubit, bare er en bit som kan være "både 0 og 1 på samme tid". ,” mens en klassisk bit kan være bare det ene eller det andre. De fortsetter med å si at en kvantedatamaskin ville oppnå sin hastighet ved å bruke qubits for å prøve alle mulige løsninger i superposisjon - det vil si samtidig eller parallelt.

Dette er det jeg har kommet til å tenke på som det grunnleggende feiltrinnet i popularisering av kvantedatabehandling, den som fører til resten. Herfra er det bare et lite hopp til kvantedatamaskiner raskt løser noe sånt som reisende selger problem ved å prøve alle mulige svar på en gang - noe nesten alle eksperter tror de ikke vil kunne gjøre.

Saken er at for at en datamaskin skal være nyttig, må du på et tidspunkt se på den og lese en utdata. Men hvis du ser på en lik superposisjon av alle mulige svar, sier kvantemekanikkens regler at du bare vil se og lese et tilfeldig svar. Og hvis det var alt du ville, kunne du ha valgt en selv.

Hva superposisjon egentlig betyr er "kompleks lineær kombinasjon." Her mener vi "kompleks" ikke i betydningen "komplisert", men i betydningen et reelt pluss et imaginært tall, mens "lineær kombinasjon" betyr at vi legger sammen forskjellige multipler av tilstander. Så en qubit er en bit som har et komplekst tall kalt en amplitude knyttet til muligheten for at den er 0, og en annen amplitude knyttet til muligheten for at den er 1. Disse amplitudene er nært knyttet til sannsynligheter, ved at jo lenger et utfalls amplitude er fra null, jo større er sjansen for å se dette resultatet; mer presist, sannsynligheten er lik avstanden i annen.

Men amplituder er ikke sannsynligheter. De følger forskjellige regler. For eksempel, hvis noen bidrag til en amplitude er positive og andre er negative, så kan bidragene forstyrre destruktivt og kansellere hverandre, slik at amplituden er null og det tilsvarende utfallet aldri blir observert; likeledes kan de forstyrre konstruktivt og øke sannsynligheten for et gitt utfall. Målet med å utforme en algoritme for en kvantedatamaskin er å koreografere et mønster av konstruktiv og destruktiv interferens slik at bidragene til dens amplitude opphever hverandre for hvert feil svar, mens bidragene for det riktige svaret forsterker hverandre. Hvis, og bare hvis, du kan ordne det, vil du se det riktige svaret med stor sannsynlighet når du ser. Den vanskelige delen er å gjøre dette uten å vite svaret på forhånd, og raskere enn du kunne gjort det med en klassisk datamaskin.

For XNUMX år siden viste Shor hvordan man gjør alt dette for problemet med faktorisering av heltall, som bryter de mye brukte kryptografiske kodene som ligger til grunn for mye av netthandelen. Vi vet nå hvordan vi gjør det for noen andre problemer også, men bare ved å utnytte de spesielle matematiske strukturene i disse problemene. Det er ikke bare å prøve alle mulige svar på en gang.

Det som kompliserer vanskeligheten er at hvis du vil snakke ærlig om kvanteberegning, trenger du også det konseptuelle vokabularet til teoretisk informatikk. Jeg blir ofte spurt om hvor mange ganger raskere en kvantedatamaskin vil være enn dagens datamaskiner. En million ganger? En milliard?

Dette spørsmålet går glipp av poenget med kvantedatamaskiner, som er å oppnå bedre "skaleringsadferd", eller kjøretid som en funksjon av n, antall biter med inndata. Dette kan bety å ta et problem der den beste klassiske algoritmen trenger en rekke trinn som vokser eksponentielt med n, og løse det ved hjelp av en rekke trinn som vokser bare som n². I slike tilfeller, for små n, å løse problemet med en kvantedatamaskin vil faktisk være tregere og dyrere enn å løse det klassisk. Det er bare som n vokser at kvantehastigheten først dukker opp og så til slutt kommer til å dominere.

Men hvordan kan vi vite at det ikke finnes noen klassisk snarvei - en konvensjonell algoritme som vil ha lignende skaleringsadferd som kvantealgoritmens? Selv om dette spørsmålet vanligvis blir ignorert i populære kontoer, er dette spørsmålet sentralt i forskningen på kvantealgoritmer, hvor vanskeligheten ofte ikke er å bevise at en kvantedatamaskin kan gjøre noe raskt, men på en overbevisende måte å argumentere for at en klassisk datamaskin ikke kan det. Akk, det viser seg å være svimlende vanskelig å bevise at problemer er vanskelige, som illustrert av den berømte P versus NP problem (som spør, grovt sett, om ethvert problem med raskt kontrollerbare løsninger også kan løses raskt). Dette er ikke bare et akademisk spørsmål, et spørsmål om å prikke i-er: I løpet av de siste tiårene har antatte kvantehastigheter gjentatte ganger forsvunnet når klassiske algoritmer ble funnet med lignende ytelse.

Merk at etter å ha forklart alt dette, har jeg fortsatt ikke sagt et ord om den praktiske vanskeligheten med å bygge kvantedatamaskiner. Problemet, med et ord, er dekoherens, som betyr uønsket interaksjon mellom en kvantedatamaskin og dens miljø - elektriske felt i nærheten, varme gjenstander og andre ting som kan registrere informasjon om qubits. Dette kan resultere i for tidlig "måling" av qubitene, som kollapser dem ned til klassiske biter som enten er definitivt 0 eller definitivt 1. Den eneste kjente løsningen på dette problemet er kvantefeilkorreksjon: et opplegg, foreslått på midten av 1990-tallet, som smart koder hver qubit av kvanteberegningen til den kollektive tilstanden til dusinvis eller til og med tusenvis av fysiske qubits. Men forskerne begynner først nå å få slik feilretting til å fungere i den virkelige verden, og å faktisk ta den i bruk vil ta mye lengre tid. Når du leser om det siste eksperimentet med 50 eller 60 fysiske qubits, er det viktig å forstå at qubitene ikke er feilkorrigert. Før de er det, forventer vi ikke å kunne skalere utover noen hundre qubits.

Når noen forstår disse konseptene, vil jeg si at de er klare til å begynne å lese - eller muligens til og med skrive - en artikkel om det siste fremskrittet innen kvanteberegning. De vil vite hvilke spørsmål de skal stille i den konstante kampen for å skille virkelighet fra hype. Å forstå disse tingene er virkelig mulig - tross alt er det ikke rakettvitenskap; det er bare kvanteberegning!