Deutschs Algorithmus

Deutschs Algorithmus löst das Paritätsproblem für den Spezialfall $n = 1$. Im Kontext des Quantencomputings wird dieses Problem manchmal als Deutschs Problem bezeichnet, und wir folgen dieser Bezeichnung in dieser Lektion.

Genauer gesagt wird die Eingabe durch eine Funktion $f:\Sigma \rightarrow \Sigma$ von einem Bit auf ein Bit dargestellt. Es gibt vier solcher Funktionen:

$$\rule[-10mm]{0mm}{10mm} \begin{array}{c|c} a & f_1(a)\\ \hline 0 & 0\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_2(a)\\ \hline 0 & 0\\ 1 & 1 \end{array} \qquad \begin{array}{c|c} a & f_3(a)\\ \hline 0 & 1\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_4(a)\\ \hline 0 & 1\\ 1 & 1 \end{array}$$

Die erste und letzte dieser Funktionen sind konstant und die mittleren beiden sind balanciert, was bedeutet, dass die beiden möglichen Ausgabewerte der Funktion gleich oft auftreten, wenn wir alle Eingaben durchlaufen. Deutschs Problem besteht darin, zu bestimmen, zu welcher der beiden Kategorien die Eingabefunktion gehört: konstant oder balanciert.

Deutschs Problem

Eingabe: eine Funktion $f:\{0,1\}\rightarrow\{0,1\}$
Ausgabe: $0$, wenn $f$ konstant ist, $1$, wenn $f$ balanciert ist

Wenn wir die Eingabefunktion $f$ in Deutschs Problem als Direktzugriff auf eine Zeichenkette betrachten, denken wir über eine Zwei-Bit-Zeichenkette nach: $f(0)f(1)$.

$$\begin{array}{cc} \mathsf{function} & \mathsf{string}\\ \hline f_1 & 00 \\ f_2 & 01 \\ f_3 & 10 \\ f_4 & 11 \end{array}$$

So betrachtet ist Deutschs Problem die Berechnung der Parität (oder gleichwertig: des exklusiven ODER) der zwei Bits.

Jeder klassische Abfragealgorithmus, der dieses Problem korrekt löst, muss beide Bits abfragen: $f(0)$ und $f(1)$. Wenn wir zum Beispiel wissen, dass $f(1) = 1$ gilt, könnte die Antwort immer noch $0$ oder $1$ sein, je nachdem ob $f(0) = 1$ oder $f(0) = 0$ gilt. Alle anderen Fälle sind ähnlich; wenn man nur eines der beiden Bits kennt, erhält man keinerlei Information über ihre Parität. Der im vorherigen Abschnitt beschriebene Boolesche Circuit ist also das Beste, was wir in Bezug auf die Anzahl der benötigten Abfragen zur Lösung dieses Problems tun können.

Quantencircuit-Beschreibung

Deutschs Algorithmus löst Deutschs Problem mit einer einzigen Abfrage und bietet damit einen messbaren Vorteil von Quanten- gegenüber klassischen Berechnungen. Das mag ein bescheidener Vorteil sein – eine Abfrage statt zwei –, aber irgendwo muss man anfangen. Wissenschaftliche Fortschritte haben manchmal scheinbar bescheidene Ursprünge.

Hier ist ein Quantencircuit, der Deutschs Algorithmus beschreibt:

Analyse

Um Deutschs Algorithmus zu analysieren, verfolgen wir die Wirkung des obigen Circuits und identifizieren die Zustände der Qubits zu den in dieser Abbildung vorgeschlagenen Zeitpunkten:

Der Anfangszustand ist $\vert 1\rangle \vert 0 \rangle$, und die beiden Hadamard-Operationen auf der linken Seite des Circuits transformieren diesen Zustand zu

$$\vert \pi_1 \rangle = \vert - \rangle \vert + \rangle = \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 0\rangle + \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 1\rangle.$$

(Wie immer folgen wir Qiskits Qubit-Ordnungskonvention, bei der das obere Qubit rechts und das untere Qubit links steht.) Es mag sich unintuitiv anfühlen, diesen Produktzustand teilweise verteilt zu schreiben (wobei die Zustände von Qubit 1 ausgefaktorisiert bleiben), aber das wird unsere späteren Ausdrücke kompakter machen.

Als Nächstes wird das $U_f$-Gate ausgeführt. Gemäß der Definition des $U_f$-Gates wird der Wert der Funktion $f$ für den klassischen Zustand des oberen/rechtesten Qubits mit dem unteren/linkesten Qubit XOR-verknüpft, was $\vert \pi_1\rangle$ in den Zustand transformiert:

$$\vert \pi_2 \rangle = \frac{1}{2} \bigl( \vert 0 \oplus f(0) \rangle - \vert 1 \oplus f(0) \rangle \bigr) \vert 0 \rangle + \frac{1}{2} \bigl( \vert 0 \oplus f(1) \rangle - \vert 1 \oplus f(1) \rangle \bigr) \vert 1 \rangle.$$

Wir können diesen Ausdruck vereinfachen, indem wir beobachten, dass die Formel

$$\vert 0 \oplus a\rangle - \vert 1 \oplus a\rangle = (-1)^a \bigl( \vert 0\rangle - \vert 1\rangle \bigr)$$

für beide möglichen Werte $a\in\Sigma$ gilt. Expliziter sind die zwei Fälle wie folgt.

$$\begin{aligned} \vert 0 \oplus 0\rangle - \vert 1 \oplus 0\rangle & = \vert 0 \rangle - \vert 1 \rangle = (-1)^0 \bigl( \vert 0\rangle - \vert 1\rangle \bigr)\\ \vert 0 \oplus 1\rangle - \vert 1 \oplus 1\rangle & = \vert 1 \rangle - \vert 0\rangle = (-1)^1 \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \end{aligned}$$

Damit können wir $\vert\pi_2\rangle$ alternativ so ausdrücken:

$$\begin{aligned} \vert\pi_2\rangle & = \frac{1}{2} (-1)^{f(0)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 0 \rangle + \frac{1}{2} (-1)^{f(1)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 1 \rangle \\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

Etwas Interessantes ist gerade passiert! Obwohl die Wirkung des $U_f$-Gates auf Standard-Basiszustände das obere/rechteste Qubit unverändert lässt und den Funktionswert mit dem unteren/linkesten Qubit XOR-verknüpft, sehen wir hier, dass sich der Zustand des oberen/rechtesten Qubits (im Allgemeinen) geändert hat, während der Zustand des unteren/linkesten Qubits unverändert geblieben ist – er ist sowohl vor als auch nach der Ausführung des $U_f$-Gates im Zustand $\vert - \rangle$. Dieses Phänomen ist als Phase Kickback bekannt, und wir werden gleich mehr darüber sagen.

Mit einer letzten Vereinfachung, nämlich dem Herausziehen des Faktors $(-1)^{f(0)}$ aus der Summe, erhalten wir diesen Ausdruck für den Zustand $\vert\pi_2\rangle$:

$$\begin{aligned} \vert\pi_2\rangle & = (-1)^{f(0)} \vert - \rangle \biggl( \frac{\vert 0\rangle + (-1)^{f(0) \oplus f(1)} \vert 1\rangle}{\sqrt{2}}\biggr) \\ & = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert + \rangle & \text{falls $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert - \rangle & \text{falls $f(0) \oplus f(1) = 1$}. \end{cases} \end{aligned}$$

Beachte, dass wir in diesem Ausdruck $f(0) \oplus f(1)$ im Exponenten von $-1$ haben statt $f(1) - f(0)$, was man aus rein algebraischer Sicht erwarten könnte, aber wir erhalten in beiden Fällen dasselbe Ergebnis. Das liegt daran, dass der Wert $(-1)^k$ für eine ganze Zahl $k$ nur davon abhängt, ob $k$ gerade oder ungerade ist.

Das Anwenden des abschließenden Hadamard-Gates auf das obere Qubit hinterlässt uns mit dem Zustand

$$\vert \pi_3 \rangle = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert 0 \rangle & \text{falls $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert 1 \rangle & \text{falls $f(0) \oplus f(1) = 1$}, \end{cases}$$

was mit Wahrscheinlichkeit $1$ zum korrekten Ergebnis führt, wenn das rechte/oberste Qubit gemessen wird.

Weitere Bemerkungen zum Phase Kickback

Bevor wir weitermachen, betrachten wir die obige Analyse aus einem etwas anderen Blickwinkel, der das Phase-Kickback-Phänomen beleuchten kann.

Zunächst beachte, dass die folgende Formel für alle Bits $b,c\in\Sigma$ gilt.

$$\vert b \oplus c\rangle = X^c \vert b \rangle$$

Das kann überprüft werden, indem man es für die zwei möglichen Werte $c = 0$ und $c = 1$ prüft:

$$\begin{aligned} \vert b \oplus 0 \rangle & = \vert b\rangle = \mathbb{I} \vert b \rangle = X^0 \vert b \rangle\\ \vert b \oplus 1 \rangle & = \vert \neg b\rangle = X \vert b \rangle = X^1 \vert b \rangle. \end{aligned}$$

Mit dieser Formel sehen wir, dass

$$U_f \bigl(\vert b\rangle \vert a \rangle\bigr) = \vert b \oplus f(a) \rangle \vert a \rangle = \bigl(X^{f(a)}\vert b \rangle\bigr) \vert a \rangle$$

für jede Wahl von Bits $a,b\in\Sigma$ gilt. Da diese Formel für $b=0$ und $b=1$ gilt, sehen wir durch Linearität, dass

$$U_f \bigl( \vert \psi \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)}\vert \psi \rangle\bigr) \vert a \rangle$$

für alle Qubit-Zustandsvektoren $\vert \psi\rangle$ gilt, und daher

$$U_f \bigl( \vert - \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)} \vert - \rangle \bigr) \vert a \rangle = (-1)^{f(a)} \vert - \rangle \vert a \rangle.$$

Der Schlüssel, der das funktionieren lässt, ist, dass $X\vert - \rangle = - \vert - \rangle$ gilt. Mathematisch gesprochen ist der Vektor $\vert - \rangle$ ein Eigenvektor der Matrix $X$ mit dem Eigenwert $-1$.

Eigenvektoren und Eigenwerte werden wir in der bevorstehenden Lektion über Phasenschätzung und Faktorisierung ausführlicher besprechen, wo das Phase-Kickback-Phänomen auf andere unitäre Operationen verallgemeinert wird.

Unter Berücksichtigung, dass Skalare sich frei durch Tensorprodukte bewegen, finden wir eine alternative Weise zu erklären, wie die Operation $U_f$ $\vert \pi_1\rangle$ in der obigen Analyse in $\vert \pi_2\rangle$ transformiert:

$$\begin{aligned} \vert \pi_2 \rangle & = U_f \bigl( \vert - \rangle \vert + \rangle \bigr)\\ & = \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 0\rangle \bigr) + \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 1\rangle \bigr)\\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

Implementierung in Qiskit

Schauen wir nun, wie Deutschs Algorithmus in Qiskit implementiert werden kann. Wir beginnen mit einer Versionsüberprüfung und führen dann die für diese Implementierung erforderlichen Importe durch. Für die Implementierungen der anderen Algorithmen, die folgen, werden wir die erforderlichen Importe separat durchführen, um eine bessere Modularität zu gewährleisten.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-aer

from qiskit import __version__

print(__version__)

2.1.1

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

Zuerst definieren wir einen Quantencircuit, der ein Abfrage-Gate für eine der vier Funktionen $f_1,$ $f_2,$ $f_3,$ oder $f_4$ von einem Bit auf ein Bit implementiert, wie zuvor beschrieben. Wie bereits erwähnt, ist die Implementierung von Abfrage-Gates kein eigentlicher Teil von Deutschs Algorithmus; hier zeigen wir im Grunde nur eine Möglichkeit, die Eingabe in Form einer Circuit-Implementierung eines Abfrage-Gates vorzubereiten.

def deutsch_function(case: int):
    # This function generates a quantum circuit for one of the 4 functions
    # from one bit to one bit

    if case not in [1, 2, 3, 4]:
        raise ValueError("`case` must be 1, 2, 3, or 4.")

    f = QuantumCircuit(2)
    if case in [2, 3]:
        f.cx(0, 1)
    if case in [3, 4]:
        f.x(1)
    return f

Wir können sehen, wie jeder Circuit mit der draw-Methode aussieht. Hier ist der Circuit für die Funktion $f_3$.

display(deutsch_function(3).draw(output="mpl"))

Als Nächstes erstellen wir den eigentlichen Quantencircuit für Deutschs Algorithmus, wobei wir das Abfrage-Gate durch eine Quantencircuit-Implementierung ersetzen, die als Argument übergeben wird. Gleich werden wir einen der vier durch die zuvor definierte Funktion deutsch_function definierten Circuits einstecken. Barrieren sind enthalten, um die visuelle Trennung zwischen der Abfrage-Gate-Implementierung und dem Rest des Circuits zu zeigen.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in Deutsch's algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)

    qc.x(n)
    qc.h(range(n + 1))

    qc.barrier()
    qc.compose(function, inplace=True)
    qc.barrier()

    qc.h(range(n))
    qc.measure(range(n), range(n))

    return qc

Auch hier können wir sehen, wie der Circuit mit der draw-Methode aussieht.

display(compile_circuit(deutsch_function(3)).draw(output="mpl"))

Schließlich erstellen wir eine Funktion, die den zuvor definierten Circuit einmal ausführt und das entsprechende Ergebnis ausgibt: „constant" oder „balanced".

def deutsch_algorithm(function: QuantumCircuit):
    # Determine if a one-bit function is constant or balanced.

    qc = compile_circuit(function)

    result = AerSimulator().run(qc, shots=1, memory=True).result()
    measurements = result.get_memory()
    if measurements[0] == "0":
        return "constant"
    return "balanced"

Wir können Deutschs Algorithmus nun auf jede der vier oben definierten Funktionen anwenden.

f = deutsch_function(3)
display(deutsch_algorithm(f))

'balanced'