QuellengeprüftLevel 3
Deutsch-Jozsa-Algorithmus
Der Deutsch-Jozsa-Algorithmus bestimmt mit nur einer Abfrage, ob eine Boolesche Funktion konstant oder balanciert ist.
In Bewegung sehen
Nach der kostenlosen Registrierung landest du direkt wieder bei diesem Konzept.
Was es bedeutet
Bestimmt ob eine Black-Box-Funktion konstant oder balanciert ist mit einer Abfrage statt 2^(n-1)+1.Alltagsvergleich
Stellen Sie sich eine versiegelte Schalterbox vor, deren Lampe entweder immer gleich ist (konstant) oder bei genau der Hälfte der Eingaben leuchtet (balanciert). Klassisch muss man eventuell mehr als die Hälfte der Eingaben testen; Deutsch-Jozsa lässt die Amplituden interferieren und erkennt mit einer Abfrage, welche Art Box es ist — ohne eine einzelne Ausgabe zu verraten.
Wie eine versiegelte Wahlurne prüfen.
Häufige Missverständnisse
- Speedup ist gegenüber deterministischen Algorithmen.
- Sagt nicht was die Funktion berechnet.
Das Wichtigste
- 1 Orakel-Abfrage für konstant vs balanciert.
- Erster Algorithmus mit bewiesener Quantenüberlegenheit.
- Nutzt Superposition und Interferenz.
Verständnis prüfen
Wie viele Orakel-Abfragen?
- A.n
- B.2^n
- C.1
- D.log(n)
Antwort anzeigen
Antwort: C. 1
Warum: Genau 1 Orakel-Abfrage.
Baut auf
Verwandte Begriffe
Primärquelle: Deutsch & Jozsa, Rapid solution of problems by quantum computation, Proc. R. Soc. A 439, 553 (1992), doi:10.1098/rspa.1992.0167
Praktisch lernen
Dieses Konzept ist Teil eines Curriculums mit 46 Leveln, einem interaktiven Simulator und Lumen — einem Tutor, der seine Antworten prüft und kennzeichnet, wie sicher sie sind. Level 1–5 sind kostenlos.