Groverin algoritmi

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

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

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

Katso myös

• Kvanttilaskenta