Laufzeit von Grovers Algorithmus

Was ist die Zeitkomplexität (nicht die Abfragekomplexität) von Grovers Algorithmus? Es scheint mir klar , dass es , da es Iterationen und jede Iteration erfordert die Verwendung des Reflexionsbetrieb wiederum die Zeit in Anspruch nimmt Verwendung eines beliebigen Standardsatzes von Universaltoren.$\Omega(\log(N) \sqrt{N})$$\Omega(\sqrt{N})$$\Omega(\log(N))$

Das Problem ist, dass ich nicht einmal eine einzige Referenz finden kann, die besagt, dass die zeitliche Komplexität von Grovers Algorithmus $\Omega(\log(N) \sqrt{N})$ . Wikipedia und mehrere andere Webseiten sagen, dass $O(\sqrt{N})$ Zeitkomplexität ist. Das Papier von Grover behauptet $O(\sqrt{N})$ "Schritte".

Vermisse ich etwas? Vielleicht definieren die Leute die Reflexionsoperation als Einheitszeit. Aber das macht für mich keinen Sinn, denn wenn wir es schaffen, willkürlichen Unitaries zu erlauben, sich Zeit zu nehmen, gibt es keinen Unterschied zwischen der Komplexität von Abfragen und der Komplexität von Zeit.

Die Frage wird normalerweise aus folgendem Grund als strittig angesehen. Der Algorithmus von Grover ist ein kombinatorischer Suchalgorithmus, um eine Lösung für ein beliebiges Prädikat zu finden. Ja, $\Theta(\log N)$ ist die Quantum-Gate-Komplexität in jeder Stufe des Black-Box-Algorithmus, aber auch das Prädikat muss berechnet werden. Die Quantum-Gate-Komplexität ist $\Omega(\log N)$ , da sonst nicht die gesamte Eingabe gelesen würde und Sie einige der Eingabebits von der Suche verwerfen könnten. Andererseits könnte ein interessantes Prädikat viel länger dauern. Daher wird die Anzahl der Aufrufe des Prädikats als Standardmünze angesehen, genau wie für das klassische Analogon von Grovers Algorithmus, nämlich das zufällige Erraten.

Es stellt sich heraus, dass es eine Möglichkeit gibt, den Algorithmus von Grover mit weniger als Gattern zu implementieren ! Aus diesem Grund konnte kein Verweis gefunden werden, der angibt, dass -Tore benötigt werden. Zumindest in dem Fall, in dem es einen markierten Gegenstand gibt, ist es möglich, es besser zu machen.$O(\sqrt{N}\log N)$$\Omega(\sqrt{N}\log N)$

Ein aktueller Preprint von Arunachalam und de Wolf bietet einen neuen Algorithmus zur Lösung des Suchproblems mit einem markierten Element mit Abfragekomplexität und nur Tore (aus der Tormenge Toffoli + alle Ein-Qubit-Tore).$O(\sqrt{N})$$O(\sqrt{N}\log(\log^* N))$

Beachten Sie, dass die Funktion so langsam wächst, dass selbst wenn die Anzahl der Atome im Universum ist, höchstens 3 beträgt.$\log(\log^* N)$$N$$\log(\log^* N)$