Algorisme de Grover

En computació quàntica, l'algorisme de Grover és un algorisme quàntic per a la cerca en una seqüència no ordenada de dades amb N components en un temps ${\displaystyle O({\sqrt {N}})}$, i amb una necessitat addicional d'espai d'emmagatzematge d'${\displaystyle O(\log N)}$ (vegeu notació O). Va ser inventat per Lov K. Grover en 1996^[1]

En una cerca normal d'una dada, si tenim una seqüència desordenada s'ha de realitzar una inspecció lineal, que necessita un temps d'${\displaystyle O(N)}$, cosa per la qual l'algorisme de Grover és una millora bastant substancial, evitant, a més, la necessitat de l'ordenació prèvia. El guany obtingut és "només" de l'arrel quadrada, cosa que contrasta amb altres millores dels algorismes quàntics que obtenen millores d'ordre exponencial sobre les seves contrapartides clàssiques.

Igual que altres algorismes de naturalesa quàntica, l'algorisme de Grover és un algorisme de caràcter probabilístic, per la qual cosa produeix la resposta correcta amb una determinada probabilitat d'error, que no obstant això, pot obtenir-se tan baixa com es desitje per mitjà d'iteracions.