Grover-Algorithmus

Der Grover-Algorithmus ist ein Quantenalgorithmus zur Suche in einer unsortierten Datenbank mit ${\displaystyle N}$ Einträgen in ${\displaystyle {\mathcal {O}}\left({\sqrt {N}}\right)}$ Schritten und mit ${\displaystyle {\mathcal {O}}\left(\log N\right)}$ Speicherbedarf (siehe O-Notation). Er wurde von Lov Grover im Jahre 1996 veröffentlicht und gehört zu den ersten Quantenalgorithmen, für die bewiesen wurde, dass sie mit der Problemgröße besser skalieren als der beste klassische Algorithmus. Im Fall des Grover-Algorithmus handelt es sich um einen quadratischen Speedup.

Auf einem klassischen Computer ist der prinzipiell schnellstmögliche Suchalgorithmus in einer unsortierten Datenbank die lineare Suche, die ${\displaystyle {\mathcal {O}}\left(N\right)}$ Rechenschritte erfordert. Der Grover-Algorithmus liefert damit eine quadratische Beschleunigung, was für große ${\displaystyle N}$ beträchtlich ist.

Wie die meisten Quantenalgorithmen ist der Grover-Algorithmus ein probabilistischer Algorithmus, d. h., er gibt die korrekte Antwort mit hoher Wahrscheinlichkeit, wobei die Wahrscheinlichkeit einer fehlerhaften Antwort durch wiederholte Ausführung des Algorithmus verkleinert werden kann.