Such-Algorithmus

Auf alle Index-Qubits wird eine HADAMARD-Transformation angewendet, beginnend beim Indexzustand , wodurch der Zustand in eine gleichförmige Überlagerung aller Index-Basiszustände umgewandelt wird:

Der Suchalgorithmus löst dann - wie im Schaltkreis dargestellt - eine wiederholte Anwendung der GROVER-Unterroutine aus.

Die GROVER-Unterroutine ihrerseits besteht, wie im untenstehenden Schaltkreis gezeigt, aus vier Schritten:

1. Anwendung des Orakels ,
2. HADAMARD-Transformation ,
3. Phasenverschiebung , falls ,
4. HADAMARD-Transformation .

Diese vier Schritte können in der Gleichung zusammengefaßt werden, wobei wie oben die gleichförmige Überlagerung aller Index-Basiszustände bezeichnet.

Schließlich wird der Zustand des Indexregisters ausgelesen, was durch Messung der Indexobservablen geschieht. Das Meßergebnis liefert mit hoher Wahrscheinlichkeit (s. unten) eine Lösung des Suchproblems.

Wie oft die GROVER-Unterroutine anzuwenden ist, um die Wahrscheinlichkeit für das Gelingen des Algorithmus zu maximieren, hängt von der Anzahl der Lösungen ab. Der Einfachheit halber kann angenommen werden, daß nur eine Lösung existiert. ¹ Wird die gleichförmige Überlagerung aller falschen Indizes mit bezeichnet, dann liefert die -malige Anwendung der Unterroutine auf den Anfangszustand

mit . Damit das richtige Meßergebnis mit Wahrscheinlichkeit erzielt wird, muß gelten: , also . Ist , dann erhält man für Iterationen die Näherung

Da eine ganze Zahl ist, kann diese Bedingung zwar nicht präzise erfüllt werden, die Irrtumswahrscheinlichkeit beträgt aber nur ungefähr , ist also sehr klein.

Anmerkungen:

¹ Der GROVER-Algorithmus kann jedoch auch auf eine unbekannte Anzahl von Lösungen verallgemeinert werden [23.4].