Groverio algoritmas
Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Groverio algoritmas (ang. Grover's algorithm) yra kvantinis algoritmas skirtas ieškojimui nestrukturizuotoje (nesutvarkytoje) duomenų bazėje su N kintamųjų per O() laiką ir užimantis O(lg N) (labai mažai užima) saugojimo vietos. Algoritmas buvo sugalvotas L. Groverio (Lov Grover) 1996 m.
Klasiškai, ieškant nesutvarkytoje duomenų bazėje reikia linijinio ieškojimo per O(N) laiką. Groverio algoritmas kuris užima O(N1/2) laiko, yra greičiausias įmanomas kvantinis algoritmas skirtas ieškojimui nesutvarkytoje duomenų bazėje. Jis suteikia „tiktai“ kvadratinį pagreitėjimą, skirtingai nuo kitų kvantinių algoritmų, kurie gali suteikti eksponentinį paspartėjimą nei jų klasikiniai atitikmenys. Bet netgi kvadratinis paspartėjimas žymus, kai N yra didelis. Pavyzdžiui, su tam tikru N tokios pat spartos kvantiniam kompiuteriui kaip klasikinis prireiktų, taikant Groverio algoritmą 4 mėnesių, tuo tarpu klasikiniam kompiuteriui prireiktų 1013 metų (toks yra Visatos amžius).