Kvanteberegning: en tutorial

Samuel L. Braunstein

Abstrakt: Se for

deg en datamaskin hvis minne er eksponentielt større enn dens tilsynelatende fysiske størrelse; en datamaskin som kan manipulere et eksponentielt sett med innganger samtidig; en datamaskin som beregner i skumringssonen i Hilbert-rommet. Du tenker på en kvantedatamaskin. Det trengs relativt få og enkle konsepter fra kvantemekanikken for å gjøre kvantedatamaskiner til en mulighet. Subtiliteten har vært å lære å manipulere disse konseptene. Er en slik datamaskin uunngåelig eller vil den være for vanskelig å bygge?

I denne artikkelen gir vi en veiledning om hvordan kvantemekanikk kan brukes til å forbedre beregningen. Utfordringen vår: å løse et eksponentielt vanskelig problem for en konvensjonell datamaskin — det å ta hensyn til et stort antall. Som et forspill gjennomgår vi standardverktøyene for beregning, universelle porter og maskiner. Disse ideene brukes deretter først på klassiske, forsvinnende datamaskiner og deretter på kvantedatamaskiner. En skjematisk modell av en kvantedatamaskin er beskrevet i tillegg til noen av finessene i programmeringen. Shor-algoritmen [1,2] for effektiv faktorisering av tall på en kvantedatamaskin presenteres i to deler: kvanteprosedyren innenfor algoritmen og den klassiske algoritmen som kaller kvanteprosedyren. Den matematiske strukturen i factoring som gjør Shor-algoritmen mulig diskuteres. Vi konkluderer med et syn på gjennomførbarheten og utsiktene for kvanteberegning i de kommende årene.

La oss starte med å beskrive problemet: å faktorisere et tall N i primfaktorene (f.eks. kan tallet 51688 dekomponeres som ). En praktisk måte å kvantifisere hvor raskt en bestemt algoritme kan løse et problem, er å spørre hvordan antall trinn for å fullføre algoritmen skalerer med størrelsen på “inngangen” algoritmen mates. For faktoreringsproblemet er denne inngangen bare talletfaktorisere N vi ønsker å; derfor er lengden på inngangen . (Basen til logaritmen bestemmes av vårt nummereringssystem. En grunntall påsåledes 2 girlengden i binær; en grunntall på 10 i desimal.) `Fornuftige’ algoritmer er de som skaleres som et polynom med små grader i inngangsstørrelsen (med en grad på kanskje 2 eller 3).

På konvensjonelle datamaskiner kjører den best kjente factoring-algoritmen i trinn [3]. Denne algoritmen skalerer derfor eksponentielt med inngangsstørrelsen . For eksempel, i 1994 ble et 129-sifret nummer (kjent som RSA129 [3′]) vellykket faktorisert ved å bruke denne algoritmen på omtrent 1600 arbeidsstasjoner spredt rundt i verden; hele faktoriseringen tok åtte måneder [4]. Ved å bruke dette til å estimere prefaktoren for den eksponentielle skaleringen ovenfor, finner vi at det vil ta omtrent 800 000 år å faktorisere et 250-sifret tall med samme datamaskinkraft; på samme måte ville et 1000-sifret tall kreve år (betydelig lengre enn universets alder). Vanskeligheten med å faktorisere store tall er avgjørende for kryptosystemer med offentlig nøkkel, for eksempel de som brukes av banker. Der er slike koder avhengige av vanskeligheten med å faktorisere tall med rundt 250 sifre.

Nylig ble det utviklet en algoritme for å faktorisere tall på en kvantedatamaskin som kjører i trinn hvor er liten [1]. Dette er omtrent kvadratisk i inngangsstørrelsen, så å faktorisere et 1000- sifret tall med en slik algoritme vil kreve bare noen få millioner trinn. Implikasjonen er at offentlige nøkkelkryptosystemer basert på factoring kan brytes.

For å gi deg en idé om hvordan denne eksponentielle forbedringen kan være mulig, gjennomgår vi et elementært kvantemekanisk eksperiment som viser hvor slik kraft kan ligge skjult [5]. Eksperimentet med to spalter er prototypisk for å observere kvantemekanisk oppførsel: En kilde sender ut fotoner, elektroner eller andre partikler som kommer til et par spalter. Disse partiklene gjennomgår enhetlig evolusjon og til slutt måling. Vi ser et interferensmønster, med begge spaltene åpne, som helt forsvinner hvis en av spaltene dekkes. På en eller annen måte passerer partiklene gjennom begge spaltene parallelt. Hvis slik enhetlig evolusjon skulle representere en beregning (eller en operasjon i en beregning), ville kvantesystemet utføre beregninger parallelt. Kvanteparallellisme kommer gratis. Utgangen fra dette systemet vil bli gitt av den konstruktive interferensen mellom de parallelle beregningene.