QuellengeprüftLevel 3
Deutsch-Jozsa-Algorithmus
Der Deutsch-Jozsa-Algorithmus bestimmt mit nur einer Abfrage, ob eine Boolesche Funktion konstant oder balanciert ist.
Was es bedeutet
Bestimmt ob eine Black-Box-Funktion konstant oder balanciert ist mit einer Abfrage statt 2^(n-1)+1.Alltagsvergleich
Wie prüfen ob eine Münze fair ist.
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
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, dessen Antworten vor der Anzeige geprüft werden. Level 1–5 sind kostenlos.