Forskere implementerer 3-qubit Grover-søgning på en kvantecomputer

Søger stort, uordnede databaser for en ønsket vare er en tidskrævende opgave for klassiske computere, men kvantecomputere forventes at udføre disse søgninger meget hurtigere. Tidligere forskning har vist, at Grovers søgealgoritme, foreslået i 1996, er en optimal kvantesøgningsalgoritme, hvilket betyder, at ingen anden kvantealgoritme kan søge hurtigere. Imidlertid, implementering af Grovers algoritme på et kvantesystem har været udfordrende.

Nu i en ny undersøgelse, forskere har implementeret Grovers algoritme med fangede atomioner. Algoritmen bruger tre qubits, som svarer til en database med 8 (2 ³ ) varer. Når det bruges til at søge efter et eller to elementer i databasen, Grover -algoritmens succes sandsynligheder var - som forventet - betydeligt højere end de bedste teoretiske succes sandsynligheder for klassiske computere.

Forskerne, Caroline Figgatt et al., ved University of Maryland og National Science Foundation, har offentliggjort et papir om deres resultater i et nyligt nummer af Naturkommunikation .

"Dette arbejde er den første implementering af en 3-qubit Grover-søgealgoritme i et skalerbart kvanteberegningssystem, "Fortalte Figgatt Phys.org . "Desuden dette er den første implementering af algoritmen ved hjælp af boolske orakler, som direkte kan sammenlignes med en klassisk søgning."

Den klassiske tilgang til at søge i en database er ligetil. I bund og grund, algoritmen gætter tilfældigt et element, eller "løsning". Så, for eksempel, for en enkelt søgning iteration på en database med 8 elementer, en klassisk algoritme foretager en tilfældig forespørgsel og, hvis det mislykkes, det giver endnu et tilfældigt gæt - i alt, gætter 2 ud af 8 varer, hvilket resulterer i en succesrate på 25%.

Grovers algoritme, på den anden side, initialiserer først systemet i en kvantesuperposition af alle 8 tilstande, og bruger derefter en kvantefunktion kaldet et orakel til at markere den korrekte løsning. Som et resultat af disse kvantestrategier, for en enkelt søgning iteration på en database med 8 elementer, den teoretiske succesrate stiger til 78%. Med en højere succesrate kommer hurtigere søgetider, da der i gennemsnit er behov for færre forespørgsler for at nå frem til det korrekte svar.

Ved implementeringen af ​​Grovers algoritme rapporteret her, succesraten var lavere end den teoretiske værdi - cirka 39% eller 44%, afhængigt af det anvendte orakel - men stadig markant højere end den klassiske succesrate.

Forskerne testede også Grovers algoritme på databaser, der har to korrekte løsninger, i hvilket tilfælde de teoretiske succesrater er 47% og 100% for klassiske og kvante computere, henholdsvis. Implementeringen demonstreret her opnåede succesrater på 68% og 75% for de to orakeltyper - igen, bedre end den højeste teoretiske værdi for klassiske computere.

Forskerne forventer, at i fremtiden, denne implementering af Grovers algoritme kan skaleres op til større databaser. Når databasens størrelse stiger, kvantefordelen i forhold til klassiske computere bliver endnu større, det er her, fremtidige applikationer vil gavne.

"Bevæger sig fremad, vi planlægger at fortsætte med at udvikle systemer med forbedret kontrol over flere qubits, "Sagde Figgatt.

© 2018 Phys.org