Der Deutsch-Jozsa-Algorithmus

Deutschs Algorithmus übertrifft alle klassischen Algorithmen für ein Abfrageproblem, der Vorteil ist jedoch recht bescheiden: eine Abfrage gegenüber zwei. Der Deutsch-Jozsa-Algorithmus erweitert diesen Vorteil – und kann tatsächlich zur Lösung zweier verschiedener Abfrageprobleme eingesetzt werden.

Hier ist eine Quantenschaltkreisbeschreibung des Deutsch-Jozsa-Algorithmus. Ein zusätzlicher klassischer Nachverarbeitungsschritt, der in der Abbildung nicht gezeigt wird, kann je nach dem zu lösenden Problem ebenfalls erforderlich sein.

Natürlich haben wir noch nicht besprochen, welche Probleme dieser Algorithmus löst; das geschieht in den beiden folgenden Abschnitten.

Das Deutsch-Jozsa-Problem

Beginnen wir mit dem Abfrageproblem, für das der Deutsch-Jozsa-Algorithmus ursprünglich entwickelt wurde, dem sogenannten Deutsch-Jozsa-Problem.

Die Eingabefunktion für dieses Problem hat die Form $f:\Sigma^n \rightarrow \Sigma$ für eine beliebige positive ganze Zahl $n$. Wie bei Deutschs Problem besteht die Aufgabe darin, $0$ auszugeben, wenn $f$ konstant ist, und $1$, wenn $f$ balanciert ist, wobei letzteres wieder bedeutet, dass die Anzahl der Eingabezeichenketten, für die die Funktion den Wert $0$ annimmt, gleich der Anzahl der Eingabezeichenketten ist, für die sie den Wert $1$ annimmt.

Beachte, dass es bei $n$ größer als $1$ Funktionen der Form $f:\Sigma^n \rightarrow \Sigma$ gibt, die weder konstant noch balanciert sind. Zum Beispiel fällt die Funktion $f:\Sigma^2\rightarrow\Sigma$, definiert als

$$\begin{aligned} f(00) & = 0 \\ f(01) & = 0 \\ f(10) & = 0 \\ f(11) & = 1 \end{aligned}$$

in keine dieser beiden Kategorien. Beim Deutsch-Jozsa-Problem kümmern wir uns einfach nicht um solche Funktionen – sie gelten als „Don't-care"-Eingaben. Das heißt, für dieses Problem haben wir ein Versprechen, dass $f$ entweder konstant oder balanciert ist.

Deutsch-Jozsa-Problem

Eingabe: eine Funktion $f:\{0,1\}^n\rightarrow\{0,1\}$
Versprechen: $f$ ist entweder konstant oder balanciert
Ausgabe: $0$, wenn $f$ konstant ist, $1$, wenn $f$ balanciert ist

Der Deutsch-Jozsa-Algorithmus löst dieses Problem mit einer einzigen Abfrage in folgendem Sinne: Wenn jedes der $n$ Messergebnisse $0$ ist, dann ist die Funktion $f$ konstant; wenn hingegen mindestens eines der Messergebnisse $1$ ist, dann ist die Funktion $f$ balanciert. Anders ausgedrückt: Auf den oben beschriebenen Schaltkreis folgt ein klassischer Nachverarbeitungsschritt, in dem das ODER der Messergebnisse berechnet wird, um die Ausgabe zu erzeugen.

Algorithmusanalyse

Um die Leistung des Deutsch-Jozsa-Algorithmus für das Deutsch-Jozsa-Problem zu analysieren, ist es hilfreich, zunächst über die Wirkung einer einzelnen Schicht von Hadamard-Gates nachzudenken. Eine Hadamard-Operation kann wie üblich als Matrix ausgedrückt werden:

$$H = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix},$$

aber wir können diese Operation auch über ihre Wirkung auf Standardbasiszustände beschreiben:

$$\begin{aligned} H \vert 0\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} \vert 1 \rangle\\[3mm] H \vert 1\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle - \frac{1}{\sqrt{2}} \vert 1 \rangle. \end{aligned}$$

Diese beiden Gleichungen lassen sich zu einer einzigen Formel zusammenfassen:

$$H \vert a \rangle = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} (-1)^a \vert 1 \rangle = \frac{1}{\sqrt{2}} \sum_{b\in\{0,1\}} (-1)^{ab} \vert b\rangle,$$

die für beide Wahlen $a\in\Sigma$ gilt.

Angenommen, wir haben nicht nur ein einzelnes Qubit, sondern $n$ Qubits, und auf jedes wird eine Hadamard-Operation angewendet. Die kombinierte Operation auf den $n$ Qubits wird durch das Tensorprodukt $H\otimes \cdots \otimes H$ ($n$-mal) beschrieben, das wir zur Kürze und Klarheit als $H^{\otimes n}$ schreiben. Mithilfe der obigen Formel, gefolgt von Expansion und Vereinfachung, können wir die Wirkung dieser kombinierten Operation auf die Standardbasiszustände von $n$ Qubits wie folgt ausdrücken:

$$\begin{aligned} & H^{\otimes n} \vert x_{n-1} \cdots x_1 x_0 \rangle \\ & \qquad = \bigl(H \vert x_{n-1} \rangle \bigr) \otimes \cdots \otimes \bigl(H \vert x_{0} \rangle \bigr) \\ & \qquad = \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{n-1}\in\Sigma} (-1)^{x_{n-1} y_{n-1}} \vert y_{n-1} \rangle \Biggr) \otimes \cdots \otimes \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{0}\in\Sigma} (-1)^{x_{0} y_{0}} \vert y_{0} \rangle \Biggr) \\ & \qquad = \frac{1}{\sqrt{2^n}} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle. \end{aligned}$$

Binäre Zeichenketten der Länge $n$ schreiben wir dabei als $x_{n-1}\cdots x_0$ und $y_{n-1}\cdots y_0$, entsprechend Qiskits Indexierungskonvention.

Diese Formel liefert uns ein nützliches Werkzeug zur Analyse des obigen Quantenschaltkreises. Nach der ersten Schicht von Hadamard-Gates ist der Zustand der $n+1$ Qubits (einschließlich des linksten/untersten Qubits, das separat behandelt wird) gegeben durch:

$$\bigl( H \vert 1 \rangle \bigr) \bigl( H^{\otimes n} \vert 0 \cdots 0 \rangle \bigr) = \vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \vert x_{n-1} \cdots x_0 \rangle.$$

Wenn die $U_f$-Operation ausgeführt wird, wird dieser Zustand umgewandelt in

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \vert x_{n-1} \cdots x_0 \rangle,$$

durch genau das gleiche Phase-Kickback-Phänomen wie in der Analyse von Deutschs Algorithmus.

Dann wird die zweite Schicht von Hadamard-Gates ausgeführt, die (nach der obigen Formel) diesen Zustand umwandelt in:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0) + x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle.$$

Dieser Ausdruck sieht etwas kompliziert aus, und ohne mehr über die Funktion $f$ zu wissen, lässt sich nicht viel über die Wahrscheinlichkeiten verschiedener Messergebnisse aussagen.

Glücklicherweise müssen wir nur die Wahrscheinlichkeit kennen, dass alle Messergebnisse $0$ sind – denn das ist die Wahrscheinlichkeit, dass der Algorithmus ermittelt, dass $f$ konstant ist. Diese Wahrscheinlichkeit hat eine einfache Formel:

$$\Biggl\vert \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \Biggr\vert^2 = \begin{cases} 1 & \text{wenn $f$ konstant ist}\\[1mm] 0 & \text{wenn $f$ balanciert ist} \end{cases}$$

Im Einzelnen gilt: Wenn $f$ konstant ist, nimmt $f(x_{n-1}\cdots x_0)$ entweder für jede Zeichenkette $x_{n-1}\cdots x_0$ den Wert $0$ an – dann ist der Summenwert $2^n$ – oder für jede Zeichenkette den Wert $1$ – dann ist der Summenwert $-2^n$. Durch Division durch $2^n$ und Quadrieren des Absolutwerts ergibt sich $1$.

Wenn hingegen $f$ balanciert ist, nimmt $f$ den Wert $0$ bei der Hälfte der Zeichenketten $x_{n-1}\cdots x_0$ und den Wert $1$ bei der anderen Hälfte an, sodass sich die $+1$- und $-1$-Terme in der Summe aufheben und wir den Wert $0$ erhalten.

Wir schlussfolgern, dass der Algorithmus korrekt arbeitet, sofern das Versprechen erfüllt ist.

Klassische Schwierigkeit

Der Deutsch-Jozsa-Algorithmus funktioniert immer, liefert stets die richtige Antwort, wenn das Versprechen eingehalten wird, und benötigt nur eine einzige Abfrage. Wie verhält sich das im Vergleich zu klassischen Abfragealgorithmen für das Deutsch-Jozsa-Problem?

Zunächst muss jeder deterministische klassische Algorithmus, der das Deutsch-Jozsa-Problem korrekt löst, exponentiell viele Abfragen machen: Im schlechtesten Fall sind $2^{n-1} + 1$ Abfragen erforderlich. Die Begründung: Wenn ein deterministischer Algorithmus $f$ bei höchstens $2^{n-1}$ verschiedenen Zeichenketten abfragt und dabei jedes Mal denselben Funktionswert erhält, sind beide Antworten noch möglich. Die Funktion könnte konstant sein, oder sie könnte balanciert sein, aber durch Pech liefern alle Abfragen zufällig denselben Funktionswert.

Die zweite Möglichkeit mag unwahrscheinlich erscheinen – aber bei deterministischen Algorithmen gibt es keine Zufälligkeit oder Unsicherheit, sodass sie bei bestimmten Funktionen systematisch versagen. Damit haben wir in dieser Hinsicht einen erheblichen Vorteil von Quanten- gegenüber klassischen Algorithmen.

Es gibt allerdings einen Haken: Probabilistische klassische Algorithmen können das Deutsch-Jozsa-Problem mit sehr hoher Wahrscheinlichkeit und nur wenigen Abfragen lösen. Wenn wir einfach einige verschiedene Zeichenketten der Länge $n$ zufällig wählen und $f$ auf diesen Zeichenketten abfragen, ist es unwahrscheinlich, dass wir bei balanciertem $f$ für alle dieselben Funktionswerte erhalten.

Konkret: Wenn wir $k$ Eingabezeichenketten $x^1,\ldots,x^k \in \Sigma^n$ gleichmäßig zufällig wählen, $f(x^1),\ldots,f(x^k)$ auswerten und $0$ antworten, wenn alle Funktionswerte gleich sind, und $1$, wenn nicht, dann liegen wir immer richtig, wenn $f$ konstant ist, und liegen im Fall eines balancierten $f$ nur mit der Wahrscheinlichkeit $2^{-k + 1}$ falsch. Wählen wir etwa $k = 11$, beantwortet dieser Algorithmus die Frage mit einer Wahrscheinlichkeit von mehr als $99,9$% korrekt.

Aus diesem Grund haben wir noch immer einen recht bescheidenen Vorteil von Quanten- gegenüber klassischen Algorithmen – aber es ist dennoch ein quantifizierbarer Vorteil, der eine Verbesserung gegenüber Deutschs Algorithmus darstellt.

Deutsch-Jozsa mit Qiskit

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

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
import numpy as np

Um den Deutsch-Jozsa-Algorithmus in Qiskit zu implementieren, definieren wir zunächst eine Funktion dj_query, die einen Quantenschaltkreis erzeugt, der ein Query-Gate für eine zufällig gewählte Funktion implementiert, die das Versprechen des Deutsch-Jozsa-Problems erfüllt. Mit 50-prozentiger Wahrscheinlichkeit ist die Funktion konstant und mit 50-prozentiger Wahrscheinlichkeit balanciert. In beiden Fällen wird die Funktion gleichmäßig aus den Funktionen des jeweiligen Typs gewählt. Das Argument ist die Anzahl der Eingabebits der Funktion.

def dj_query(num_qubits):
    # Create a circuit implementing for a query gate for a random function
    # satisfying the promise for the Deutsch-Jozsa problem.

    qc = QuantumCircuit(num_qubits + 1)

    if np.random.randint(0, 2):
        # Flip output qubit with 50% chance
        qc.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance
        return qc

    # Choose half the possible input strings
    on_states = np.random.choice(
        range(2**num_qubits),  # numbers to sample from
        2**num_qubits // 2,  # number of samples
        replace=False,  # makes sure states are only sampled once
    )

    def add_cx(qc, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc.x(qubit)
        return qc

    for state in on_states:
        qc.barrier()  # Barriers are added to help visualize how the functions are created.
        qc = add_cx(qc, f"{state:0b}")
        qc.mcx(list(range(num_qubits)), num_qubits)
        qc = add_cx(qc, f"{state:0b}")

    qc.barrier()

    return qc

Die Quantenschaltkreisimplementierung des Query-Gates können wir wie gewohnt mit der Methode draw anzeigen.

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

Als Nächstes definieren wir eine Funktion, die den Deutsch-Jozsa-Schaltkreis erstellt und eine Quantenschaltkreisimplementierung eines Query-Gates als Argument entgegennimmt.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in the Deutsch-Jozsa algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)
    qc.h(range(n + 1))
    qc.compose(function, inplace=True)
    qc.h(range(n))
    qc.measure(range(n), range(n))
    return qc

Schließlich wird eine Funktion definiert, die den Deutsch-Jozsa-Schaltkreis einmal ausführt.

def dj_algorithm(function: QuantumCircuit):
    # Determine if a function is constant or balanced.

    qc = compile_circuit(function)

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

Wir können unsere Implementierung testen, indem wir eine Funktion zufällig auswählen, die Quantenschaltkreisimplementierung des Query-Gates für diese Funktion anzeigen und dann den Deutsch-Jozsa-Algorithmus auf diese Funktion anwenden.

f = dj_query(3)
display(f.draw("mpl"))
display(dj_algorithm(f))

'balanced'

Das Bernstein-Vazirani-Problem

Als Nächstes besprechen wir ein Problem, das als Bernstein-Vazirani-Problem bekannt ist. Es wird auch als Fourier-Sampling-Problem bezeichnet, obwohl es allgemeinere Formulierungen dieses Problems gibt, die ebenfalls unter diesem Namen bekannt sind.

Zunächst führen wir eine Notation ein. Für beliebige zwei binäre Zeichenketten $x = x_{n-1} \cdots x_0$ und $y = y_{n-1}\cdots y_0$ der Länge $n$ definieren wir

$$x \cdot y = x_{n-1} y_{n-1} \oplus \cdots \oplus x_0 y_0.$$

Wir bezeichnen diese Operation als das binäre Skalarprodukt. Eine alternative Definition lautet wie folgt:

$$x \cdot y = \begin{cases} 1 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ ist ungerade}\\[0.5mm] 0 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ ist gerade} \end{cases}$$

Beachte, dass dies eine symmetrische Operation ist, d. h. das Ergebnis ändert sich nicht, wenn wir $x$ und $y$ vertauschen, was wir also nach Belieben tun können. Manchmal ist es hilfreich, das binäre Skalarprodukt $x \cdot y$ als die Parität der Bits von $x$ an den Stellen zu betrachten, an denen die Zeichenkette $y$ eine $1$ hat – oder äquivalent dazu als die Parität der Bits von $y$ an den Stellen, an denen die Zeichenkette $x$ eine $1$ hat.

Mit dieser Notation können wir nun das Bernstein-Vazirani-Problem definieren.

Bernstein-Vazirani-Problem

Eingabe: eine Funktion $f:\{0,1\}^n\rightarrow\{0,1\}$
Versprechen: es existiert eine binäre Zeichenkette $s = s_{n-1} \cdots s_0$, für die $f(x) = s\cdot x$ für alle $x\in\Sigma^n$ gilt
Ausgabe: die Zeichenkette $s$

Wir brauchen für dieses Problem keinen neuen Quantenalgorithmus; der Deutsch-Jozsa-Algorithmus löst es. Der Übersichtlichkeit halber bezeichnen wir den obigen Quantenschaltkreis, der den klassischen Nachverarbeitungsschritt zur Berechnung des ODER nicht enthält, als Deutsch-Jozsa-Schaltkreis.

Algorithmusanalyse

Um zu analysieren, wie der Deutsch-Jozsa-Schaltkreis bei einer Funktion funktioniert, die das Versprechen des Bernstein-Vazirani-Problems erfüllt, beginnen wir mit einer kurzen Beobachtung. Mithilfe des binären Skalarprodukts können wir die Wirkung von $n$ Hadamard-Gates auf die Standardbasiszustände von $n$ Qubits alternativ wie folgt beschreiben:

$$H^{\otimes n} \vert x \rangle = \frac{1}{\sqrt{2^n}} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert y\rangle$$

Ähnlich wie bei der Analyse von Deutschs Algorithmus liegt das daran, dass der Wert $(-1)^k$ für eine beliebige ganze Zahl $k$ nur davon abhängt, ob $k$ gerade oder ungerade ist.

Für den Deutsch-Jozsa-Schaltkreis gilt: Nach der ersten Schicht von Hadamard-Gates ist der Zustand der $n+1$ Qubits

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} \vert x \rangle.$$

Dann wird das Query-Gate ausgeführt, das (durch das Phase-Kickback-Phänomen) den Zustand umwandelt in

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} (-1)^{f(x)} \vert x \rangle.$$

Mithilfe unserer Formel für die Wirkung einer Schicht von Hadamard-Gates erkennen wir, dass die zweite Schicht von Hadamard-Gates diesen Zustand dann umwandelt in

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{f(x) + x \cdot y} \vert y \rangle.$$

Nun können wir einige Vereinfachungen im Exponenten von $-1$ im Innern der Summe vornehmen. Da versprochen wird, dass $f(x) = s\cdot x$ für eine Zeichenkette $s = s_{n-1} \cdots s_0$ gilt, können wir den Zustand ausdrücken als

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{s\cdot x + x \cdot y} \vert y \rangle.$$

Da $s\cdot x$ und $x\cdot y$ binäre Werte sind, können wir die Addition durch das exklusive ODER ersetzen – wieder weil für eine ganze Zahl im Exponenten von $-1$ nur relevant ist, ob sie gerade oder ungerade ist. Unter Nutzung der Symmetrie des binären Skalarprodukts ergibt sich dieser Ausdruck für den Zustand:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\cdot x) \oplus (y \cdot x)} \vert y \rangle.$$

(Die Klammern wurden zur Verdeutlichung hinzugefügt, sind aber eigentlich nicht notwendig, da es üblich ist, dem binären Skalarprodukt gegenüber dem exklusiven ODER Vorrang zu geben.)

An dieser Stelle nutzen wir die folgende Formel:

$$(s\cdot x) \oplus (y \cdot x) = (s \oplus y) \cdot x$$

Diese Formel ergibt sich aus einer ähnlichen Formel für Bits,

$$(a c) \oplus (b c) = (a \oplus b) c,$$

zusammen mit einer Expansion des binären Skalarprodukts und des bitweisen exklusiven ODER:

$$\begin{aligned} (s\cdot x) \oplus (y \cdot x) & = (s_{n-1} x_{n-1}) \oplus \cdots \oplus (s_{0} x_{0}) \oplus (y_{n-1} x_{n-1}) \oplus \cdots \oplus (y_{0} x_{0}) \\ & = (s_{n-1} \oplus y_{n-1}) x_{n-1} \oplus \cdots \oplus (s_{0} \oplus y_{0}) x_{0} \\ & = (s \oplus y) \cdot x \end{aligned}$$

Damit können wir den Zustand des Schaltkreises unmittelbar vor den Messungen wie folgt ausdrücken:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle.$$

Im letzten Schritt nutzen wir eine weitere Formel, die für jede binäre Zeichenkette $z = z_{n-1}\cdots z_0$ gilt:

$$\frac{1}{2^n} \sum_{x \in \Sigma^n} (-1)^{z \cdot x} = \begin{cases} 1 & \text{wenn $z = 0^n$}\\ 0 & \text{wenn $z\neq 0^n$} \end{cases}$$

Hier verwenden wir eine einfache Notation für Zeichenketten, die wir in dieser Lektion noch mehrfach nutzen werden: $0^n$ ist die Zeichenkette aus lauter Nullen der Länge $n$.

Ein einfacher Weg, diese Formel zu begründen, besteht darin, die beiden Fälle getrennt zu betrachten. Gilt $z = 0^n$, so ist $z\cdot x = 0$ für jede Zeichenkette $x\in\Sigma^n$; jeder Term in der Summe hat den Wert $1$, und durch Summation und Division durch $2^n$ erhalten wir $1$. Falls hingegen eines der Bits von $z$ gleich $1$ ist, dann ist das binäre Skalarprodukt $z\cdot x$ für genau die Hälfte der möglichen Wahlen $x\in\Sigma^n$ gleich $0$ und für die andere Hälfte gleich $1$ – denn der Wert des binären Skalarprodukts $z\cdot x$ kippt (von $0$ auf $1$ oder von $1$ auf $0$), wenn wir ein beliebiges Bit von $x$ an einer Stelle umkehren, an der $z$ eine $1$ hat.

Wenn wir diese Formel nun auf den Zustand des Schaltkreises vor den Messungen anwenden, erhalten wir

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle = \vert - \rangle \otimes \vert s \rangle,$$

da $s\oplus y = 0^n$ genau dann gilt, wenn $y = s$. Die Messungen liefern also genau die gesuchte Zeichenkette $s$.

Klassische Schwierigkeit

Während der Deutsch-Jozsa-Schaltkreis das Bernstein-Vazirani-Problem mit einer einzigen Abfrage löst, muss jeder klassische Abfragealgorithmus mindestens $n$ Abfragen machen, um dieses Problem zu lösen.

Dies lässt sich mit einem sogenannten informationstheoretischen Argument begründen, das in diesem Fall sehr einfach ist. Jede klassische Abfrage enthüllt ein einzelnes Bit an Information über die Lösung, und es gibt $n$ Bits, die aufgedeckt werden müssen – daher sind mindestens $n$ Abfragen notwendig.

Es ist tatsächlich möglich, das Bernstein-Vazirani-Problem klassisch zu lösen, indem man die Funktion auf jeder der $n$ Zeichenketten abfragt, die an jeder möglichen Stelle eine einzelne $1$ und überall sonst eine $0$ haben, und so die Bits von $s$ einzeln enthüllt. Der Vorteil von Quanten- gegenüber klassischen Algorithmen für dieses Problem beträgt daher 1 Abfrage gegenüber $n$ Abfragen.

Bernstein-Vazirani mit Qiskit

Den Deutsch-Jozsa-Schaltkreis haben wir bereits oben implementiert, und hier nutzen wir ihn zur Lösung des Bernstein-Vazirani-Problems. Zunächst definieren wir eine Funktion, die ein Query-Gate für das Bernstein-Vazirani-Problem für eine beliebige binäre Zeichenkette $s$ implementiert.

def bv_query(s):
    # Create a quantum circuit implementing a query gate for the
    # Bernstein-Vazirani problem.

    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc

display(bv_query("1011").draw(output="mpl"))

Nun können wir eine Funktion erstellen, die den Deutsch-Jozsa-Schaltkreis auf die Funktion anwendet, unter Verwendung der zuvor definierten Funktion compile_circuit.

def bv_algorithm(function: QuantumCircuit):
    qc = compile_circuit(function)
    result = AerSimulator().run(qc, shots=1, memory=True).result()
    return result.get_memory()[0]

display(bv_algorithm(bv_query("1011")))

'1011'

Anmerkung zur Nomenklatur

Im Kontext des Bernstein-Vazirani-Problems wird der Deutsch-Jozsa-Algorithmus häufig als „Bernstein-Vazirani-Algorithmus" bezeichnet. Das ist leicht irreführend, denn der Algorithmus ist der Deutsch-Jozsa-Algorithmus, wie Bernstein und Vazirani in ihrer Arbeit ausdrücklich klargestellt haben.

Was Bernstein und Vazirani getan haben, nachdem sie gezeigt hatten, dass der Deutsch-Jozsa-Algorithmus das Bernstein-Vazirani-Problem löst (wie es oben formuliert ist), war die Definition eines viel komplizierteren Problems, bekannt als das rekursive Fourier-Sampling-Problem. Dies ist ein hoch konstruiertes Problem, bei dem Lösungen verschiedener Instanzen des Problems neue Ebenen des Problems erschließen, die in einer baumartigen Struktur angeordnet sind. Das Bernstein-Vazirani-Problem ist im Wesentlichen nur der Basisfall dieses komplizierteren Problems.

Das rekursive Fourier-Sampling-Problem war das erste bekannte Beispiel eines Abfrageproblems, bei dem Quantenalgorithmen einen sogenannten superpolynomialen Vorteil gegenüber probabilistischen Algorithmen haben und damit den Vorteil von Quanten- gegenüber klassischen Algorithmen des Deutsch-Jozsa-Algorithmus übertreffen. Intuitiv gesprochen verstärkt die rekursive Version des Problems den Vorteil von 1 gegenüber $n$ Abfragen auf etwas viel Größeres.

Der schwierigste Aspekt der mathematischen Analyse, die diesen Vorteil belegt, besteht darin zu zeigen, dass klassische Abfragealgorithmen das Problem nicht ohne viele Abfragen lösen können. Das ist typisch; bei vielen Problemen kann es sehr schwierig sein, kreative klassische Ansätze auszuschließen, die sie effizient lösen.

Simons Problem und der im nächsten Abschnitt beschriebene Algorithmus dazu bieten ein viel einfacheres Beispiel für einen superpolynomialen (und tatsächlich exponentiellen) Vorteil von Quanten- gegenüber klassischen Algorithmen, weshalb das rekursive Fourier-Sampling-Problem seltener besprochen wird. Es ist dennoch ein interessantes Berechnungsproblem für sich.