QuellengeprüftLevel 3

Grovers Algorithmus

Grovers Algorithmus bietet quadratische Beschleunigung für unstrukturierte Suche mit O(√N) Abfragen.

Was es bedeutet

Verwendet Phasenorakel und Grover-Diffusion iterativ.Optimal für unstrukturierte Suche.

Alltagsvergleich

Wie ein Resonanzeffekt.
Wie Quanten-Echolot.

Häufige Missverständnisse

  • Quadratisch, nicht exponentiell.
  • Zu viele Iterationen verringern Erfolgswahrscheinlichkeit.

Das Wichtigste

  • O(√N) Abfragen.
  • Phasenorakel + Amplitudenverstärkung.
  • Nachweislich optimal.

Verständnis prüfen

Zeitkomplexität von Grovers Suche?

  1. A.O(N)
  2. B.O(log N)
  3. C.O(√N)
  4. D.O(N²)
Antwort anzeigen

Antwort: C. O(√N)

Warum: O(√N) Orakel-Abfragen.

Baut auf

QubitSuperpositionHadamard-GatterQuantenmessungBornsche Regel

Primärquelle: Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79, 325 (1997), doi:10.1103/PhysRevLett.79.325

Praktisch lernen

Dieses Konzept ist Teil eines Curriculums mit 46 Leveln, einem interaktiven Simulator und Lumen — einem Tutor, dessen Antworten vor der Anzeige geprüft werden. Level 1–5 sind kostenlos.

Kostenlos startenZum Curriculum