Quantum Computing har nu et kraftfuldt søgeværktøj

Grovers algoritme

Tilbage i 1996 afslørede en computerforsker ved navn Lov Grover ved Bell Labs i New Jersey en usædvanlig algoritme til at søge gennem en database. Søgealgoritmer er blandt de vigtigste inden for datalogi. De muliggør hverdagslige opgaver som at jage telefonbøger, men også mere eksotiske opgaver som at bryde kryptografiske koder. Denne form for algoritme er allestedsnærværende i datalogi.

Så enhver måde at fremskynde opgaven på er enormt vigtig. En standardsøgning tager en periode, der er nogenlunde proportional med antallet af elementer i søgningen. Det skyldes, at algoritmen i værste fald skal søge gennem alle elementerne for kun at finde én.



Men Grovers algoritme er anderledes. Den tid, det tager, er proportional med kvadratroden af ​​antallet af elementer. Dataloger kalder dette en kvadratisk fremskyndelse. Og i en verden, hvor hastighedsstigninger på få brøkdele af en procent er enormt værdifulde, er en kvadratisk speed-up en tårnhøj præstation.

Grovers trick var at bruge de mærkelige, men kraftfulde ideer bag kvantemekanikken. I den klassiske verden er bits kun 0'ere og 1'ere. Men i kvanteverdenen kan en enkelt kvantebit eller qubit være 0 og 1 på samme tid. Fysikere siger, at qubit er i en superposition af tilstande.

Superpositionen er nøglen. I denne tilstand kan en algoritme søge både 0 og 1 på samme øjeblik. Fordi den kan søge i mere end ét element på samme tid, kan en kvantealgoritme søge gennem en liste meget hurtigere end en algoritme, der er begrænset af den klassiske fysiks travle tempo.

Kvantealgoritmer skal implementeres af en kvantecomputer, og i 1996, da Grover lavede sit arbejde, var disse lidt mere end en fjern drøm. Men gennembruddet kom hurtigt. Fysikere demonstrerede den første primitive kvantecomputer i 1998 og viste, hvordan den kunne udføre Grovers algoritme samme år.

Men denne særlige form for kvanteberegning var ekstremt begrænset. Det fungerede på et par qubits, men ikke mere, og selv i princippet kunne det aldrig skaleres op til større beregninger. Dette problem med at bygge og demonstrere skalerbare kvantecomputere har plaget disciplinen lige siden.

Nu, omkring 20 år senere, begynder fysikere at bygge kvantecomputere, der har potentialet til at skalere og derfor er i stand til mere kraftfulde beregninger. Og i dag siger Caroline Figgatt og venner fra University of Maryland, at de har udført Grovers algoritme på en skalerbar kvantecomputer for første gang.

Værket demonstrerer den hurtige fremskyndelse af kvanteberegninger og baner vejen for mere ambitiøst arbejde med algoritmen, der kunne begynde at knække udfordringer i den virkelige verden såsom kodebrud.

Kvantecomputeren, som Figgatt og co arbejder med, består af en streng af fem ytterbium-ioner suspenderet i et elektromagnetisk felt. Hver ion er som en lille magnet, der kan orienteres op eller ned og vendes fra den ene tilstand til den anden med en laser. På denne måde kan hver ion lagre information: for eksempel et 1 for spin op og et 0 for spin ned. Og fordi de er kvanteobjekter, kan ionerne eksistere i en superposition af disse tilstande.

Ionerne interagerer også med hinanden via de frastødende kræfter, der er forbundet med deres positive ladning. Denne interaktion tillader en qubit at interagere med en anden qubit for at behandle information. Dette er essensen af ​​kvanteberegning. Rækkefølgen af ​​trin i denne beregning er kvantealgoritmen, i dette tilfælde Grovers algoritme.

Figgatt og co bruger deres system til at skabe en tre-qubit kvantecomputer, der kan gemme op til otte elementer i en database. De udfører derefter Grovers algoritme for at vise, at det er muligt at finde en genstand betydeligt hurtigere i gennemsnit end en klassisk computer, som ville kræve mindst otte bit. Vi rapporterer resultater for en komplet tre-qubit Grover-søgealgoritme ved hjælp af den skalerbare kvanteberegningsteknologi af fangede atomære ioner, med bedre end klassisk ydeevne, siger Figgatt og co.

Det er et interessant arbejde med et stort potentiale. Dette baner vejen for mere omfattende brug af Grover-søgealgoritmen til at løse større problemer på kvantecomputere, herunder at bruge kredsløbet som en underrutine for andre kvantealgoritmer, siger holdet.

Men arbejdet giver også et interessant indblik i kapløbet om at bygge kraftfulde kvantecomputere. Vinderen af ​​dette løb vil sandsynligvis høste store økonomiske gevinster, men ingen er helt sikre på, hvilken teknologi der er bedst.

Denne verden er blevet kastet i forvirring af en canadisk startup kaldet D-Wave Systems, som har solgt tilsyneladende kraftfulde kvantecomputere til virksomheder som Google og Lockheed Martin. Disse computere fungerer med 1.000 qubits, langt mere end nogen anden teknologi.

Men mange teoretikere siger, at D-Waves påstande er overdrevne, og at dets maskiner ikke kan producere i nærheden af ​​den form for beregningskraft, som andre kvantecomputere burde være i stand til.

Det er derfor, mange grupper forsøger at kommercialisere andre kvanteteknologier, der adskiller sig dramatisk i måden, de opbevarer og behandler kvanteinformation. Disse er forskelligt afhængige af fotoner, elektroner, atomer, ioner og molekyler for at udføre deres kvantebud.

Af disse teknikker er en af ​​de ældste og bedst udviklede ionfælde-kvantecomputere, og University of Maryland-gruppen er verdensledende på dette område. Faktisk har gruppens leder, Chris Monroe, en startup kaldet IonQ, der har til formål at kommercialisere denne teknologi.

Så demonstrationen af ​​en skalerbar kvantecomputer, der kan implementere Grovers algoritme, omend med kun tre qubits, kan ses som en hensigtserklæring.

I 1998, efter den første implementering af Grovers algoritme, var der en række meninger om, hvor lang tid det ville tage fysikere at lave det næste trin skalerbare computere. En række startups er behørigt dannet og kollapset baseret på optimistiske prognoser. Men på det tidspunkt var 20 år i den pessimistiske ende af spektret af forudsigelser. At det har taget så lang tid sætter i perspektiv opgavens sværhedsgrad.

Det er svært at kontrollere universet på kvanteskalaen. Et interessant spørgsmål nu for teknologer og venturekapitalister er, om hastigheden af ​​teknologiske fremskridt kan accelereres væsentligt.

Ref: arxiv.org/abs/1703.10535 : Gennemfør 3-Qubit Grover-søgning på en programmerbar kvantecomputer

skjule