{
"cells": [
{
"cell_type": "markdown",
"id": "7e5d320e",
"metadata": {},
"source": [
"---\n",
"title: \"Deutschs Algorithmus\"\n",
"description: \"Ein kostenloser Kurs „ IBM ” über Quanteninformation und -berechnung\"\n",
"---\n",
"\n",
"\n",
"\n",
"# Deutschs Algorithmus\n",
"\n",
"Der Algorithmus von Deutsch löst das Paritätsproblem für den Sonderfall, dass $n = 1$ gilt.\n",
"Im Zusammenhang mit dem Quantencomputing wird dieses Problem manchmal als *„Deutsch-Problem“* bezeichnet, und wir werden uns in dieser Lektion an diese Bezeichnung halten.\n",
"\n",
"Um genau zu sein, wird die Eingabe durch eine Funktion $f:\\Sigma \\rightarrow \\Sigma$ von einem Bit zu einem Bit dargestellt.\n",
"Es gibt vier solcher Funktionen:\n",
"\n",
"$$\n",
"\\rule[-10mm]{0mm}{10mm}\n",
"\\begin{array}{c|c}\n",
" a & f_1(a)\\\\\n",
" \\hline\n",
" 0 & 0\\\\\n",
" 1 & 0\n",
"\\end{array}\n",
"\\qquad\n",
"\\begin{array}{c|c}\n",
" a & f_2(a)\\\\\n",
" \\hline\n",
" 0 & 0\\\\\n",
" 1 & 1\n",
"\\end{array}\n",
"\\qquad\n",
"\\begin{array}{c|c}\n",
" a & f_3(a)\\\\\n",
" \\hline\n",
" 0 & 1\\\\\n",
" 1 & 0\n",
"\\end{array}\n",
"\\qquad\n",
"\\begin{array}{c|c}\n",
" a & f_4(a)\\\\\n",
" \\hline\n",
" 0 & 1\\\\\n",
" 1 & 1\n",
"\\end{array}\n",
"$$\n",
"\n",
"Die erste und die letzte dieser Funktionen sind *konstant*, und die beiden mittleren sind *ausgeglichen*, d. h. die beiden möglichen Ausgabewerte für die Funktion treten gleich oft auf, wenn wir über die Eingänge gehen.\n",
"Das Problem von Deutsch besteht darin, zu bestimmen, zu welcher der beiden Kategorien die Eingangsfunktion gehört: konstant oder ausgeglichen.\n",
"\n",
"\n",
" Eingabe: eine Funktion $f:\\{0,1\\}\\rightarrow\\{0,1\\}$ \\ Ausgabe: $0$ wenn $f$ konstant ist, $1$ wenn $f$ ausgeglichen ist\n",
"\n",
"\n",
"Wenn wir die Eingabefunktion „ $f$ “ in Deutschs Problem als zufälligen Zugriff auf eine Zeichenkette betrachten, denken wir an eine Zwei-Bit-Zeichenkette: „ $f(0)f(1)$ “.\n",
"\n",
"$$\n",
"\\begin{array}{cc}\n",
"\\mathsf{function} & \\mathsf{string}\\\\\n",
"\\hline\n",
"f_1 & 00 \\\\\n",
"f_2 & 01 \\\\\n",
"f_3 & 10 \\\\\n",
"f_4 & 11\n",
"\\end{array}\n",
"$$\n",
"\n",
"So gesehen besteht das Problem von Deutsch darin, die Parität (oder, äquivalent dazu, das Exklusiv-ODER) der beiden Bits zu berechnen.\n",
"\n",
"Jeder klassische Abfragealgorithmus, der dieses Problem korrekt löst, muss beide Bits abfragen: $f(0)$ und $f(1)$.\n",
"Wenn wir beispielsweise erfahren, dass $f(1) = 1$ gilt, könnte die Antwort dennoch $0$ oder $1$ lauten, je nachdem, ob $f(0) = 1$ bzw. $f(0) = 0$ gilt.\n",
"In allen anderen Fällen verhält es sich ähnlich: Wenn man nur eines von zwei Bits kennt, liefert dies keinerlei Informationen über deren Parität.\n",
"Die im vorigen Abschnitt beschriebene Boolesche Schaltung ist also hinsichtlich der Anzahl der zur Lösung dieses Problems erforderlichen Abfragen das Beste, was wir erreichen können.\n",
"\n",
"\n",
"\n",
"## Beschreibung des Quantenschaltkreises\n",
"\n",
"Der Deutsch-Algorithmus löst das Deutsch-Problem mit einer einzigen Abfrage und bietet damit einen quantifizierbaren Vorteil von Quantenberechnungen gegenüber klassischen Berechnungen.\n",
"Dies mag ein bescheidener Vorteil sein - eine Abfrage im Gegensatz zu zwei - aber irgendwo müssen wir ja anfangen.\n",
"Wissenschaftliche Fortschritte haben manchmal scheinbar bescheidene Ursprünge.\n",
"\n",
"Hier ist eine Quantenschaltung, die den Deutsch'schen Algorithmus beschreibt:\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"## Analyse\n",
"\n",
"Um den Algorithmus von Deutsch zu analysieren, werden wir die Wirkung der obigen Schaltung nachvollziehen und die Zustände der Qubits zu den in der Abbildung angegebenen Zeitpunkten bestimmen:\n",
"\n",
"\n",
"\n",
"Der Anfangszustand ist $\\vert 1\\rangle \\vert 0 \\rangle$, und die beiden Hadamard-Operationen auf der linken Seite der Schaltung wandeln diesen Zustand um in\n",
"\n",
"$$\n",
"\\vert \\pi_1 \\rangle = \\vert - \\rangle \\vert + \\rangle\n",
"= \\frac{1}{2} \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr) \\vert 0\\rangle\n",
"+ \\frac{1}{2} \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr) \\vert 1\\rangle.\n",
"$$\n",
"\n",
"(Wie immer folgen wir der Qiskit-Konvention zur Anordnung der Qubits, die das oberste Qubit nach rechts und das unterste Qubit nach links setzt) Es mag sich unintuitiv anfühlen, diesen Produktzustand teilweise verteilt zu schreiben (wobei die Zustände von Qubit 1 ausgeklammert bleiben), aber das wird unsere späteren Ausdrücke kompakter machen.\n",
"\n",
"Als Nächstes wird das Tor $U_f$ ausgeführt.\n",
"Gemäß der Definition des Gatters $U_f$ wird der Wert der Funktion $f$ für den klassischen Zustand des oberen/rechten Qubits mit dem unteren/linken Qubit XOR-verknüpft, wodurch $\\vert \\pi_1\\rangle$ in den Zustand umgewandelt wird\n",
"\n",
"$$\n",
"\\vert \\pi_2 \\rangle\n",
"= \\frac{1}{2} \\bigl( \\vert 0 \\oplus f(0) \\rangle - \\vert 1 \\oplus f(0) \\rangle \\bigr) \\vert 0 \\rangle\n",
"+ \\frac{1}{2} \\bigl( \\vert 0 \\oplus f(1) \\rangle - \\vert 1 \\oplus f(1) \\rangle \\bigr) \\vert 1 \\rangle.\n",
"$$\n",
"\n",
"Wir können diesen Ausdruck vereinfachen, indem wir beachten, dass die Formel\n",
"\n",
"$$\n",
"\\vert 0 \\oplus a\\rangle - \\vert 1 \\oplus a\\rangle = (-1)^a \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr)\n",
"$$\n",
"\n",
"gilt für beide möglichen Werte: $a\\in\\Sigma$.\n",
"Genauer gesagt stellen sich die beiden Fälle wie folgt dar.\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"\\vert 0 \\oplus 0\\rangle - \\vert 1 \\oplus 0\\rangle\n",
"& = \\vert 0 \\rangle - \\vert 1 \\rangle\n",
"= (-1)^0 \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr)\\\\\n",
"\\vert 0 \\oplus 1\\rangle - \\vert 1 \\oplus 1\\rangle & = \\vert 1 \\rangle - \\vert 0\\rangle\n",
"= (-1)^1 \\bigl( \\vert 0\\rangle - \\vert 1\\rangle \\bigr)\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"So können wir $\\vert\\pi_2\\rangle$ alternativ wie folgt ausdrücken:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" \\vert\\pi_2\\rangle\n",
" & = \\frac{1}{2} (-1)^{f(0)} \\bigl( \\vert 0 \\rangle - \\vert 1 \\rangle \\bigr) \\vert 0 \\rangle\n",
" + \\frac{1}{2} (-1)^{f(1)} \\bigl( \\vert 0 \\rangle - \\vert 1 \\rangle \\bigr) \\vert 1 \\rangle \\\\\n",
" & = \\vert - \\rangle \\biggl( \\frac{(-1)^{f(0)} \\vert 0\\rangle + (-1)^{f(1)} \\vert 1\\rangle}{\\sqrt{2}}\\biggr).\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Es ist gerade etwas Interessantes passiert!\n",
"Obwohl die Wirkung des $U_f$ Gatters auf Standard-Basiszustände das oberste/rechteste Qubit in Ruhe lässt und den Funktionswert mit dem untersten/linken Qubit XOR-verknüpft, sehen wir hier, dass sich der Zustand des obersten/rechtesten Qubits (im Allgemeinen) geändert hat, während der Zustand des untersten/linken Qubits derselbe bleibt - nämlich der Zustand $\\vert - \\rangle$ vor und nach der Ausführung des $U_f$ Gatters.\n",
"Dieses Phänomen wird als *Phasenrückschlag* bezeichnet, und wir werden in Kürze mehr dazu sagen.\n",
"\n",
"Mit einer letzten Vereinfachung, die darin besteht, den Faktor $(-1)^{f(0)}$ aus der Summe herauszuziehen, erhalten wir diesen Ausdruck für den Zustand $\\vert\\pi_2\\rangle$ :\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" \\vert\\pi_2\\rangle\n",
" & = (-1)^{f(0)} \\vert - \\rangle\n",
" \\biggl( \\frac{\\vert 0\\rangle + (-1)^{f(0) \\oplus f(1)} \\vert 1\\rangle}{\\sqrt{2}}\\biggr) \\\\\n",
" & = \\begin{cases}\n",
" (-1)^{f(0)} \\vert - \\rangle \\vert + \\rangle & \\text{if $f(0) \\oplus f(1) = 0$}\\\\[1mm]\n",
" (-1)^{f(0)} \\vert - \\rangle \\vert - \\rangle & \\text{if $f(0) \\oplus f(1) = 1$}.\n",
" \\end{cases}\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Beachten Sie, dass in diesem Ausdruck im Exponenten von $-1$ die Zahl $f(0) \\oplus f(1)$ steht und nicht $f(1) - f(0)$, wie man es aus rein algebraischer Sicht vielleicht erwarten würde; dennoch erhalten wir in beiden Fällen das gleiche Ergebnis.\n",
"Das liegt daran, dass der Wert $(-1)^k$ für jede ganze Zahl $k$ nur davon abhängt, ob $k$ gerade oder ungerade ist.\n",
"\n",
"Wendet man das letzte Hadamard-Tor auf das obere Qubit an, so erhält man den Zustand\n",
"\n",
"$$\n",
"\\vert \\pi_3 \\rangle =\n",
"\\begin{cases}\n",
" (-1)^{f(0)} \\vert - \\rangle \\vert 0 \\rangle & \\text{if $f(0) \\oplus f(1) = 0$}\\\\[1mm]\n",
" (-1)^{f(0)} \\vert - \\rangle \\vert 1 \\rangle & \\text{if $f(0) \\oplus f(1) = 1$},\n",
"\\end{cases}\n",
"$$\n",
"\n",
"was zum richtigen Ergebnis mit der Wahrscheinlichkeit $1$ führt, wenn das rechte/oberste Qubit gemessen wird.\n",
"\n",
"\n",
"\n",
"## Weitere Anmerkungen zum Phasenrückstoß\n",
"\n",
"Bevor wir weitermachen, wollen wir die obige Analyse aus einem etwas anderen Blickwinkel betrachten, der das Phänomen des Phasenrückpralls etwas näher beleuchten kann.\n",
"\n",
"Zunächst ist zu beachten, dass die folgende Formel für alle Bitauswahlen $b,c\\in\\Sigma$ gilt.\n",
"\n",
"$$\n",
"\\vert b \\oplus c\\rangle = X^c \\vert b \\rangle\n",
"$$\n",
"\n",
"Dies kann überprüft werden, indem man es für die beiden möglichen Werte $c = 0$ und $c = 1$ überprüft:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"\\vert b \\oplus 0 \\rangle & = \\vert b\\rangle = \\mathbb{I} \\vert b \\rangle = X^0 \\vert b \\rangle\\\\\n",
"\\vert b \\oplus 1 \\rangle & = \\vert \\neg b\\rangle = X \\vert b \\rangle = X^1 \\vert b \\rangle.\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Aus dieser Formel ergibt sich, dass\n",
"\n",
"$$\n",
"U_f \\bigl(\\vert b\\rangle \\vert a \\rangle\\bigr)\n",
"= \\vert b \\oplus f(a) \\rangle \\vert a \\rangle\n",
"= \\bigl(X^{f(a)}\\vert b \\rangle\\bigr) \\vert a \\rangle\n",
"$$\n",
"\n",
"für jede Wahl der Bits $a,b\\in\\Sigma$.\n",
"Da diese Formel für $b=0$ und $b=1$ gilt, ergibt sich aufgrund der Linearität, dass\n",
"\n",
"$$\n",
"U_f \\bigl( \\vert \\psi \\rangle \\vert a \\rangle \\bigr) = \\bigl(X^{f(a)}\\vert \\psi \\rangle\\bigr) \\vert a \\rangle\n",
"$$\n",
"\n",
"für alle Qubit-Zustandsvektoren $\\vert \\psi\\rangle$, und daher\n",
"\n",
"$$\n",
"U_f \\bigl( \\vert - \\rangle \\vert a \\rangle \\bigr) = \\bigl(X^{f(a)} \\vert - \\rangle \\bigr) \\vert a \\rangle\n",
"= (-1)^{f(a)} \\vert - \\rangle \\vert a \\rangle.\n",
"$$\n",
"\n",
"Der Schlüssel zum Erfolg ist, dass $X\\vert - \\rangle = - \\vert - \\rangle$ gilt.\n",
"Mathematisch ausgedrückt ist der Vektor $\\vert - \\rangle$ ein *Eigenvektor* der Matrix $X$ mit *dem Eigenwert* $-1$.\n",
"\n",
"Wir werden Eigenvektoren und Eigenwerte in der nächsten Lektion über *Phasenschätzung und Faktorisierung,* in der das Phänomen des Phasenrückschlags auf andere unitäre Operationen verallgemeinert wird, ausführlicher behandeln.\n",
"\n",
"Wenn wir bedenken, dass Skalare frei durch Tensorprodukte fließen, finden wir in der obigen Analyse einen alternativen Weg, wie die Operation $U_f$ $\\vert \\pi_1\\rangle$ in $\\vert \\pi_2\\rangle$ umwandelt:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
" \\vert \\pi_2 \\rangle\n",
" & = U_f \\bigl( \\vert - \\rangle \\vert + \\rangle \\bigr)\\\\\n",
" & = \\frac{1}{\\sqrt{2}} U_f \\bigl(\\vert - \\rangle \\vert 0\\rangle \\bigr)\n",
" + \\frac{1}{\\sqrt{2}} U_f \\bigl(\\vert - \\rangle \\vert 1\\rangle \\bigr)\\\\\n",
" & = \\vert - \\rangle \\biggl( \\frac{(-1)^{f(0)} \\vert 0\\rangle + (-1)^{f(1)} \\vert 1\\rangle}{\\sqrt{2}}\\biggr).\n",
"\\end{aligned}\n",
"$$\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "d0cff57e",
"metadata": {},
"source": [
"\n",
"\n",
"## Implementierung in Qiskit\n",
"\n",
"Schauen wir uns nun an, wie wir Deutschs Algorithmus in Qiskit implementieren können. Wir beginnen mit einer Versionsprüfung und führen dann die Importe durch, die ausschließlich für diese Implementierung erforderlich sind.\n",
"Für die folgenden Implementierungen anderer Algorithmen werden wir die erforderlichen Importe im Interesse einer größeren Modularität separat durchführen.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "baa9bc2c",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2.1.1\n"
]
}
],
"source": [
"from qiskit import __version__\n",
"\n",
"print(__version__)"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "0a706449",
"metadata": {},
"outputs": [],
"source": [
"from qiskit import QuantumCircuit\n",
"from qiskit_aer import AerSimulator"
]
},
{
"cell_type": "markdown",
"id": "0af39df9",
"metadata": {},
"source": [
"Zunächst definieren wir einen Quantenschaltkreis, der ein Abfragegatter für eine der vier zuvor beschriebenen Funktionen „ $f_1$ “, „ $f_2$ “, „ $f_3$ “ oder „ $f_4$ “ von einem Bit zu einem Bit implementiert. Wie bereits erwähnt, ist die Implementierung von Abfrage-Gates nicht wirklich Teil des Deutsch-Algorithmus selbst;\n",
"hier zeigen wir im Wesentlichen nur eine Möglichkeit, die Eingabe vorzubereiten, und zwar in Form einer Schaltungsimplementierung eines Abfrage-Gates.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "ba5a708f",
"metadata": {},
"outputs": [],
"source": [
"def deutsch_function(case: int):\n",
" # This function generates a quantum circuit for one of the 4 functions\n",
" # from one bit to one bit\n",
"\n",
" if case not in [1, 2, 3, 4]:\n",
" raise ValueError(\"`case` must be 1, 2, 3, or 4.\")\n",
"\n",
" f = QuantumCircuit(2)\n",
" if case in [2, 3]:\n",
" f.cx(0, 1)\n",
" if case in [3, 4]:\n",
" f.x(1)\n",
" return f"
]
},
{
"cell_type": "markdown",
"id": "46eccf09",
"metadata": {},
"source": [
"Mit dieser `draw` Methode können wir sehen, wie die einzelnen Schaltungen aussehen. Hier ist der Schaltplan für die Funktion „ $f_3$ “.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "787e3c81",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"display(deutsch_function(3).draw(output=\"mpl\"))"
]
},
{
"cell_type": "markdown",
"id": "b6fa5b7b",
"metadata": {},
"source": [
"Als Nächstes werden wir die eigentliche Quantenschaltung für den Deutsch-Algorithmus erstellen, indem wir das Abfragegatter durch eine Quantenschaltungsimplementierung ersetzen, die als Argument angegeben wird. In Kürze werden wir einen der vier Schaltkreise anschließen, die durch die zuvor definierte Funktion `deutsch_function` festgelegt sind.\n",
"Um die visuelle Trennung zwischen der Implementierung des Abfragegatters und dem Rest der Schaltung zu verdeutlichen, sind Barrieren eingefügt.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "379aac92",
"metadata": {},
"outputs": [],
"source": [
"def compile_circuit(function: QuantumCircuit):\n",
" # Compiles a circuit for use in Deutsch's algorithm.\n",
"\n",
" n = function.num_qubits - 1\n",
" qc = QuantumCircuit(n + 1, n)\n",
"\n",
" qc.x(n)\n",
" qc.h(range(n + 1))\n",
"\n",
" qc.barrier()\n",
" qc.compose(function, inplace=True)\n",
" qc.barrier()\n",
"\n",
" qc.h(range(n))\n",
" qc.measure(range(n), range(n))\n",
"\n",
" return qc"
]
},
{
"cell_type": "markdown",
"id": "e5112614",
"metadata": {},
"source": [
"Auch hier können wir sehen, wie die Schaltung nach der Methode `draw` aussieht.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "27b41067",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"display(compile_circuit(deutsch_function(3)).draw(output=\"mpl\"))"
]
},
{
"cell_type": "markdown",
"id": "d24d14eb",
"metadata": {},
"source": [
"Schließlich erstellen wir eine Funktion, die den zuvor definierten Schaltkreis einmal durchläuft und das entsprechende Ergebnis ausgibt: \"konstant\" oder \"ausgeglichen\"\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "5b31e311",
"metadata": {},
"outputs": [],
"source": [
"def deutsch_algorithm(function: QuantumCircuit):\n",
" # Determine if a one-bit function is constant or balanced.\n",
"\n",
" qc = compile_circuit(function)\n",
"\n",
" result = AerSimulator().run(qc, shots=1, memory=True).result()\n",
" measurements = result.get_memory()\n",
" if measurements[0] == \"0\":\n",
" return \"constant\"\n",
" return \"balanced\""
]
},
{
"cell_type": "markdown",
"id": "3d0868ed",
"metadata": {},
"source": [
"Wir können nun den Deutsch'schen Algorithmus auf jede der vier oben definierten Funktionen anwenden.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "33b8355d",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'balanced'"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"f = deutsch_function(3)\n",
"display(deutsch_algorithm(f))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"id": "a1b8767d",
"source": "© IBM Corp., 2017-2026"
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3"
}
},
"nbformat": 4,
"nbformat_minor": 5
}