Groverin algoritmi

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(${\displaystyle {\sqrt {n}}}$) kun voidaan hyödyntää samanaikaisesti tapahtuvia operaatioita.

Groverin algoritmilla etsittäessä avaimen tarjoama suoja on ${\displaystyle {2^{n/2}}}$, jolloin 128-bittinen avain (${\displaystyle 2^{128}}$) tarjoaa vain 64-bittiseen avaimeen (${\displaystyle 2^{64}}$) verrattavan suojauksen.

Katso myös

• Kvanttilaskenta

Lähteet