DEUTSCHs Algorithmus ist der einfachste Quantenalgorithmus, der eine bestimmte Aufgabe effizienter als ein klassischer Algorithmus lösen kann. Daher ist er gut für illustrative Zwecke geeignet, auch wenn die durch ihn gelöste Aufgabe keinen bekannten praktischen Zweck erfüllt.
Die folgende Aufgabe betrifft eine Funktion 
mit zweiwertigem Definitionsbereich und Bild. Falls 
, dann heißt 
konstant , anderenfalls alternierend . Für eine beliebige Funktion , die in Form einer black box vorliegt, z.B. eines in seiner internen Funktion unbekannten elektronischen Schaltkreises, der für die beiden möglichen Eingangswerte 0 und 
berechnet, soll bestimmt werden, ob konstant oder alternierend ist.
Im klassischen Fall muß der Schaltkreis für zweimal durchaufen werden, um sowohl 
als auch 
zu berechnen. DEUTSCH's Quantenalgorithmus löst das Problem, indem der zu gehörige Quantenschaltkreis 
nur einmal durchlaufen wird. Dieser Schaltkreis realisiert folgende unitäre Operation auf einem Register von zwei Qubits:
 |
(22.21) |
die binäre Addition, also die Addition modulo 2 bezeichnet (
, 
, 
, und 
.) Auf die Frage, wie die Operation aus 1- und 2-Qubit-Gattern kontruiert werden kann, verweisen wir auf [23.4]. Dort wird gezeigt, daß zu jedem klassischen Schaltkreis ein Quantenschaltkreis existiert, der mit etwa der gleichen Zahl elementarer Operationen auskommt.
Man beginnt mit dem Quantenregister im Anfangszustand 
, und wendet eine Verkettung von und 1-Qubit-HADAMARD-Gattern an, um den folgenden Endzustand 
zu berechnen:
 |
(22.22) |
Schließlich wird am ersten Qubit die Observable 
gemessen. Die möglichen Meßergebnisse (Eigenwerte von 
) sind also und 0, mit entsprechenden Eigenzuständen 
und 
.
Nachfolgende Tabelle zeigt die Endzuständen und die entsprechenden Meßergebnisse für alle möglichen Funktionen .
und entsprechende Meßergebnisse für alle möglichen Funktionen in DEUTSCH's Algorithmus.
| Funktionswerte | Typ | Endzustand |
Meßergebnis |
|---|---|---|---|
| f(0) = 0, f(1) = 0 | konstant |  |
0 |
| f(0) = 0, f(1) = 1 | alternierend |  |
1 |
| f(0) = 1, f(1) = 0 | alternierend |  |
1 |
| f(0) = 1, f(1) = 1 | konstant |  |
0 |
Wie man sieht, befindet sich das erste Qubit in allen Fällen im Eigenzustand oder , so daß das entsprechende Meßergebnis 0 oder jeweils mit Sicherheit eintritt. Ferner ist aus der Tabelle ersichtlich, daß der DEUTSCH-Algorithmus die oben gestellte Aufgabe tatsächlich löst: Erhält man nämlich als Meßergebnis 0, so ist konstant. Mißt man dagegen den Wert , so ist alternierend.