Deutsch-Jozsa-Algorithmus

Der 1992 veröffentlichte Deutsch-Jozsa-Algorithmus war der erste Quantenalgorithmus, der eine exponentielle Beschleunigung gegenüber jedem möglichen klassischen Algorithmus bewies, wenn auch nur für ein gezielt konstruiertes Problem. Gegeben eine verborgene Funktion, die garantiert entweder konstant ist (liefert für jede Eingabe denselben Ausgabewert) oder ausgeglichen (liefert für genau die Hälfte aller Eingaben 0 und für die andere Hälfte 1), benötigt ein klassischer Algorithmus im schlimmsten Fall bis zu 2^(n-1) + 1 Abfragen, um dies zu unterscheiden, während der Deutsch-Jozsa-Algorithmus die Antwort mit einer einzigen Abfrage bestimmt, indem er das Eingaberegister in Superposition versetzt, die Funktion als Quantenorakel anwendet und Interferenz nutzt, sodass nur konstante oder nur ausgeglichene Funktionen ein bestimmtes Messergebnis erzeugen. Der Algorithmus hat keine bekannte praktische Anwendung. Seine Bedeutung ist historisch und pädagogisch: Er demonstrierte den zentralen Mechanismus, Orakelabfragen plus Interferenz, auf dem später wirklich nützliche Algorithmen wie die von Grover und Shor aufbauen, und wird üblicherweise zusammen mit den verwandten Algorithmen von Bernstein-Vazirani und Simon als Standardeinführung in die Quanten-Abfragekomplexität gelehrt, bevor man zur Grover-Suche übergeht.