Messung der Geschwindigkeit von Grovers Algorithmus

Die Laufzeitkomplexität ist natürlich proportional zur Anzahl der Groverschen Diffusionsoperatoren im Quantenschaltkreis.

Wie Sie wahrscheinlich wissen, sind Quantenalgorithmen probabilistisch. Sie können die Anzahl der Grover-Operatoren und damit die Laufzeit des Algorithmus frei wählen. Je mehr Tore Sie setzen, desto länger dauert die Ausführung, aber die Wahrscheinlichkeit, die richtige Antwort zu erhalten, steigt.

Es ist jedoch nur sinnvoll, neue Gatter hinzuzufügen, bis zu einem bestimmten Zeitpunkt, an dem die Wahrscheinlichkeit, eine richtige Antwort zu erhalten, so leicht ansteigt, dass dieser Vorteil die Kosten für das Hinzufügen von +1 Gatter zur Laufzeit nicht deckt.

Dies geschieht ungefähr bei der Anzahl der Tore$\sim \sqrt{N}$Wo$N$ist die Größe des Suchbereichs für den Algorithmus. Deshalb wird gesagt, dass die asymptotische Laufzeitkomplexität von Grovers Algorithmus ist$O(\sqrt{N})$, der im Vergleich zum klassischen Algorithmus mit Laufzeitkomplexität eine quadratische Quantenbeschleunigung bietet$O(N)$.

Um Ihre Frage zu beantworten: Wenn Sie mit dem Algorithmus herumspielen möchten, sollten Sie eine andere Anzahl von Grover-Diffusionsgattern ausprobieren$k$irgendwo her$k = 1$bis zu$k = N$. Die Laufzeitkosten des Algorithmus sind proportional zu$k$, während der IBM-Simulator (oder ein anderer) die Wahrscheinlichkeit berechnet, die richtige Antwort für Sie zu erhalten. So können Sie sehen, welche$k$ist das Beste. Wie bereits erwähnt, wird dies voraussichtlich weiter zunehmen$k_{\text{best}} \sim \sqrt{N}$.