211service.com
Quantum Computing har nå et kraftig søkeverktøy
Grovers algoritme
Tilbake i 1996 avduket en dataforsker ved navn Lov Grover ved Bell Labs i New Jersey en uvanlig algoritme for å søke gjennom en database. Søkealgoritmer er blant de viktigste innen informatikk. De muliggjør dagligdagse oppgaver som å lete gjennom telefonbøker, men også mer eksotiske oppgaver som å bryte kryptografiske koder. Denne typen algoritme er allestedsnærværende i informatikk.
Så enhver måte å fremskynde oppgaven på er enormt viktig. Et standardsøk tar en tidsperiode som er omtrent proporsjonal med antall elementer i søket. Det er fordi, i verste fall, må algoritmen søke gjennom alle elementene for å finne bare ett.
Men Grovers algoritme er annerledes. Tiden det tar er proporsjonal med kvadratroten av antall elementer. Informatikere kaller dette en kvadratisk hastighetsøkning. Og i en verden hvor hastighetsøkninger på noen få brøkdeler av prosent er enormt verdifulle, er en kvadratisk hastighetsøkning en ruvende prestasjon.
Grovers triks var å bruke de merkelige, men kraftige ideene bak kvantemekanikken. I den klassiske verden er bits bare 0-er og 1-ere. Men i kvanteverdenen kan en enkelt kvantebit, eller qubit, være 0 og 1 samtidig. Fysikere sier at qubiten er i en superposisjon av tilstander.
Superposisjonen er nøkkelen. I denne tilstanden kan en algoritme søke både 0 og 1 på samme øyeblikk. Fordi den kan søke i mer enn ett element på samme tid, kan en kvantealgoritme søke gjennom en liste mye raskere enn en algoritme begrenset av klassisk fysikks ploddingshastighet.
Kvantealgoritmer må implementeres av en kvantedatamaskin, og i 1996, da Grover gjorde arbeidet sitt, var disse lite mer enn en fjern drøm. Men gjennombruddet kom raskt. Fysikere demonstrerte den første primitive kvantedatamaskinen i 1998 og viste hvordan den kunne utføre Grovers algoritme samme år.
Men denne spesielle formen for kvanteberegning var ekstremt begrenset. Den fungerte på noen få qubits, men ikke mer, og selv i prinsippet kunne den aldri skaleres opp til større beregninger. Dette problemet med å bygge og demonstrere skalerbare kvantedatamaskiner har plaget disiplinen siden den gang.
Nå, rundt 20 år senere, begynner fysikere å bygge kvantedatamaskiner som har potensiale til å skalere og som dermed er i stand til kraftigere beregninger. Og i dag sier Caroline Figgatt og venner fra University of Maryland at de har utført Grovers algoritme på en skalerbar kvantedatamaskin for første gang.
Arbeidet demonstrerer den raske hastigheten til kvanteberegninger og baner vei for mer ambisiøst arbeid med algoritmen som kan begynne å ta knekken på virkelige utfordringer som kodebryting.
Kvantedatamaskinen som Figgatt og co jobber med består av en streng av fem ytterbiumioner suspendert i et elektromagnetisk felt. Hvert ion er som en liten magnet som kan orienteres opp eller ned og snus fra den ene tilstanden til den andre med en laser. På denne måten kan hvert ion lagre informasjon: en 1 for spinn opp og en 0 for spinn ned, for eksempel. Og fordi de er kvanteobjekter, kan ionene eksistere i en superposisjon av disse tilstandene.
Ionene samhandler også med hverandre via de frastøtende kreftene knyttet til deres positive ladning. Denne interaksjonen lar en qubit samhandle med en annen qubit for å behandle informasjon. Dette er essensen av kvanteberegning. Rekkefølgen på trinnene i denne beregningen er kvantealgoritmen, i dette tilfellet Grovers algoritme.
Figgatt og co bruker systemet sitt til å lage en tre-qubit kvantedatamaskin som kan lagre opptil åtte elementer i en database. De utfører deretter Grovers algoritme for å vise at det er mulig å finne en gjenstand betydelig raskere, i gjennomsnitt, enn en klassisk datamaskin som vil kreve minst åtte bits. Vi rapporterer resultater for en komplett tre-qubit Grover-søkealgoritme som bruker den skalerbare kvanteberegningsteknologien til fangede atomære ioner, med bedre enn klassisk ytelse, sier Figgatt og co.
Det er et interessant arbeid med betydelig potensial. Dette baner vei for mer omfattende bruk av Grover-søkealgoritmen for å løse større problemer på kvantedatamaskiner, inkludert å bruke kretsen som en subrutine for andre kvantealgoritmer, sier teamet.
Men arbeidet gir også et interessant innblikk i kappløpet om å bygge kraftige kvantedatamaskiner. Vinneren av dette løpet vil sannsynligvis høste store økonomiske belønninger, men ingen er helt sikre på hvilken teknologi som er best.
Denne verdenen har blitt kastet i forvirring av en kanadisk oppstart kalt D-Wave Systems som har solgt tilsynelatende kraftige kvantedatamaskiner til selskaper som Google og Lockheed Martin. Disse datamaskinene opererer med 1000 qubits, langt mer enn noen annen teknologi.
Men mange teoretikere sier at D-Waves påstander er overdrevne og at maskinene ikke kan produsere i nærheten av den typen beregningskraft som andre kvantedatamaskiner burde være i stand til.
Det er derfor mange grupper prøver å kommersialisere andre kvanteteknologier som skiller seg dramatisk i måten de lagrer og behandler kvanteinformasjon. Disse er forskjellig avhengige av fotoner, elektroner, atomer, ioner og molekyler for å gjøre sine kvantebud.
Av disse teknikkene er en av de eldste og best utviklede kvantedatabehandling ionefeller, og University of Maryland-gruppen er verdensledende på dette området. Faktisk har gruppens leder, Chris Monroe, en oppstart kalt IonQ som tar sikte på å kommersialisere denne teknologien.
Så demonstrasjonen av en skalerbar kvantedatamaskin som kan implementere Grovers algoritme, om enn med bare tre qubits, kan sees på som en intensjonserklæring.
I 1998, etter den første implementeringen av Grovers algoritme, var det en rekke meninger om hvor lang tid det ville ta fysikere å gjøre neste trinn skalerbare datamaskiner. En rekke startups ble behørig dannet og kollapset basert på optimistiske prognoser. Men på den tiden var 20 år ved den pessimistiske slutten av spekteret av spådommer. Det at det har tatt så lang tid setter i perspektiv hvor vanskelig oppgaven er.
Det er vanskelig å kontrollere universet på kvanteskalaen. Et interessant spørsmål nå for teknologer og venturekapitalister er om hastigheten på teknologisk fremgang kan akselereres betydelig.
Ref: arxiv.org/abs/1703.10535 : Fullfør 3-Qubit Grover-søk på en programmerbar kvantedatamaskin