Grover-algoritmus

A Wikipédiából, a szabad enciklopédiából

A Grover-algoritmus egy kvantumalgoritmus, mellyel egy rendezetlen, N elemű halmazban/adatbázisban O(N1/2) idő, és O(logN) tárhely felhasználásával lehet keresni. 1996-ban alkotta meg Lov Grover.

Klasszikus, bináris elven működő számítógépekkel rendezetlen halmazban/adatbázisban lineárisan, O(N) idő alatt tudunk keresni. A Grover-algoritmus ennél jóval gyorsabb, sőt, bizonyítható, hogy ez a lehetséges leggyorsabb kvantumalgoritmus a probléma megoldására.