Groverin algoritmi

Kaaviokuva kvanttipiiristä, joka esittää Groverin algoritmiä.Malline:En Oraakkeli U kääntää etsityn tilan omega vaiheen. Diffuusori kääntää kaikki tilat keskiarvon ympäri. Koko operaatio toistetaan neliöjuuri N kertaa.

Groverin algoritmi on kvanttialgoritmi (algoritmi jota ajetaan kvanttitietokoneella). Groverin algoritmin esitti Lov Grover vuonna 1996. Groverin algoritmia voidaan käyttää algoritmisessa etsinnässä, kuten koodinmurtamisessa ja shakin pelaamisessa.

Klassisilla algoritmeilla tarvitaan O(n) askelta tiedon hakemiseen tietokannasta, jossa on n tietuetta. Kvanttitietokoneella tarvitaan O($\sqrt{n}$) kun voidaan hyödyntää samanaikaisesti tapahtuvia operaatioita.

Katso myös

• Kvanttilaskenta