Der Deutsch-Jozsa-Algorithmus

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

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

Natürlich haben wir noch nicht erörtert, welche Probleme dieser Algorithmus löst; dies wird in den beiden folgenden Abschnitten getan.

Das Deutsch-Jozsa-Problem

Wir beginnen mit dem Abfrageproblem, das der Deutsch-Jozsa-Algorithmus ursprünglich lösen sollte und das als Deutsch-Jozsa-Problem bekannt ist.

Die Eingabefunktion für dieses Problem hat die Form „ $f:\Sigma^n \rightarrow \Sigma$ “ für eine beliebige positive ganze Zahl „ $n$ “. Ähnlich wie bei Deutschs Problem besteht die Aufgabe darin, „ $0$ “ auszugeben, wenn „ $f$ “ konstant ist, und „ $1$ “, wenn „ $f$ “ ausgeglichen ist, was wiederum bedeutet, dass die Anzahl der Eingabezeichenfolgen, für die die Funktion den Wert „ $0$ “ annimmt, gleich der Anzahl der Eingabezeichenfolgen ist, für die die Funktion den Wert „ $1$ “ annimmt.

Beachten Sie, dass es, wenn „ $n$ “ größer ist als „ $1$ “, Funktionen der Form „ $f:\Sigma^n \rightarrow \Sigma$ “ gibt, die weder konstant noch ausgeglichen sind. Beispielsweise ist die Funktion „ $f:\Sigma^2\rightarrow\Sigma$ “ wie folgt definiert:

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

fällt in keine dieser beiden Kategorien. Beim Deutsch-Jozsa-Problem kümmern wir uns einfach nicht um Funktionen wie diese - sie werden als "Don't Care"-Eingaben betrachtet. Das heißt, für dieses Problem haben wir eine Zusage, dass $f$ entweder konstant oder ausgeglichen ist.

Deutsch-Jozsa problem

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

Der Deutsch-Jozsa-Algorithmus löst dieses Problem mit einer einzigen Abfrage im folgenden Sinne: Wenn jedes der $n$ Messergebnisse $0$ ist, dann ist die Funktion $f$ konstant; andernfalls, wenn mindestens eines der Messergebnisse $1$ ist, dann ist die Funktion $f$ ausgeglichen. Man könnte es auch so formulieren: Auf die oben beschriebene Schaltung folgt ein klassischer Nachbearbeitungsschritt, bei dem die ODER-Verknüpfung der Messergebnisse berechnet wird, um das Ausgabebit des Deutsch-Jozsa-Problems zu erzeugen.

Algorithmusanalyse

Um die Leistung des Deutsch-Jozsa-Algorithmus für das Deutsch-Jozsa-Problem zu analysieren, ist es hilfreich, zunächst die Wirkung einer einzelnen Schicht von Hadamard-Gattern zu betrachten. Eine Hadamard-Operation kann auf die übliche Weise 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 in Bezug auf ihre Wirkung auf Standard-Basiszustände ausdrücken:

\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 können in einer einzigen Formel zusammengefasst werden,

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,

was für beide Werte von $a\in\Sigma$ gilt.

Nehmen wir nun an, dass wir anstelle eines einzelnen Qubits $n$ Qubits haben und für jedes eine Hadamard-Operation durchgeführt wird. Die kombinierte Operation an den $n$ Qubits wird durch das Tensorprodukt $H\otimes \cdots \otimes H$ ( $n$ mal) beschrieben, das wir der Kürze und Klarheit halber als $H^{\otimes n}$ schreiben. Unter Verwendung der obigen Formel, gefolgt von einer Erweiterung und Vereinfachung, können wir die Wirkung dieser kombinierten Operation auf die Standard-Basiszustände der $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}

Hier schreiben wir übrigens binäre Zeichenfolgen der Länge $n$ gemäß der Indizierungskonvention von Qiskit als $x_{n-1}\cdots x_0$ und $y_{n-1}\cdots y_0$ .

Diese Formel ist ein nützliches Hilfsmittel für die Analyse der obigen Quantenschaltung. Nachdem die erste Schicht von Hadamard-Gattern durchgeführt wurde, ist der Zustand der $n+1$ Qubits (einschließlich des linken/unteren Qubits, das getrennt vom Rest behandelt wird)

\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 Operation $U_f$ durchgeführt wird, wird dieser Zustand 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 Phänomen des Phasenrückschlags, das wir bei der Analyse von Deutschs Algorithmus gesehen haben.

Dann wird die zweite Schicht von Hadamard-Gattern 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 genauere Kenntnisse über die Funktion $f$ lassen sich nicht allzu viele Rückschlüsse auf die Wahrscheinlichkeiten für verschiedene Messergebnisse ziehen.

Glücklicherweise brauchen wir nur die Wahrscheinlichkeit zu wissen, dass jedes der Messergebnisse $0$ ist - denn das ist die Wahrscheinlichkeit, mit der der Algorithmus feststellt, dass $f$ konstant ist. Für diese Wahrscheinlichkeit gibt es 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{if $f$ is constant}\\[1mm] 0 & \text{if $f$ is balanced} \end{cases}

Beachten Sie, dass diese Werte der Wahrscheinlichkeit entsprechen, den Zustand $\vert 0^{\otimes n} \rangle$ zu messen, und nicht direkt dem endgültigen klassischen Ausgabebit des Deutsch-Jozsa-Problems. Der Algorithmus gibt „ $0$ “ aus, wenn alle Messergebnisse „ $0$ “ lauten (was darauf hindeutet, dass „ $f$ “ konstant ist), und andernfalls „ $1$ “ (was darauf hindeutet, dass „ $f$ “ ausgeglichen ist).

Genauer gesagt: Ist $f$ konstant, dann gilt entweder $f(x_{n-1}\cdots x_0) = 0$ für jede Zeichenkette $x_{n-1}\cdots x_0$ , wobei in diesem Fall der Wert der Summe $2^n$ beträgt, oder $f(x_{n-1}\cdots x_0) = 1$ für jede Zeichenkette $x_{n-1}\cdots x_0$ , wobei in diesem Fall der Wert der Summe $-2^n$ beträgt. Durch Division durch $2^n$ und Quadrierung des Absolutwerts erhält man $1$ .

Ist hingegen $f$ ausgeglichen, so nimmt $f$ bei der Hälfte der Zeichenfolgen $x_{n-1}\cdots x_0$ den Wert $0$ an und bei der anderen Hälfte den Wert $1$ , sodass sich die Terme $+1$ und $-1$ in der Summe aufheben und der Wert $0$ übrig bleibt.

Wir kommen zu dem Schluss, dass der Algorithmus korrekt funktioniert, sofern das Versprechen eingehalten wird.

Klassische Schwierigkeit

Der Deutsch-Jozsa-Algorithmus funktioniert jedes Mal, gibt immer die richtige Antwort, wenn das Versprechen erfüllt ist, und erfordert eine einzige Abfrage. Wie verhält sich dies im Vergleich zu klassischen Abfragealgorithmen für das Deutsch-Jozsa-Problem?

Erstens: Jeder deterministische klassische Algorithmus, der das Deutsch-Jozsa-Problem korrekt löst, muss exponentiell viele Abfragen durchführen: $2^{n-1} + 1$ im ungünstigsten Fall sind mehrere Abfragen erforderlich. Wenn ein deterministischer Algorithmus $f$ auf $2^{n-1}$ oder weniger verschiedene Zeichenketten abfragt und jedes Mal denselben Funktionswert erhält, dann sind beide Antworten möglich. Die Funktion könnte konstant sein, oder sie könnte ausgeglichen sein, aber durch Pech geben die Abfragen alle denselben Funktionswert zurück.

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

Der Haken an der Sache ist jedoch, dass probabilistische klassische Algorithmen das Deutsch-Jozsa-Problem mit sehr hoher Wahrscheinlichkeit mit nur wenigen Abfragen lösen können. Insbesondere, wenn wir einfach ein paar verschiedene Zeichenketten der Länge $n$ zufällig auswählen und $f$ nach diesen Zeichenketten abfragen, ist es unwahrscheinlich, dass wir für alle den gleichen Funktionswert erhalten, wenn $f$ ausgeglichen ist.

Genauer gesagt: Wenn wir die Eingabezeichenfolgen $k$ $x^1,\ldots,x^k \in \Sigma^n$ gleichmäßig zufällig auswählen, $f(x^1),\ldots,f(x^k)$ berechnen und $0$ als Antwort geben, wenn die Funktionswerte alle gleich sind, und $1$ , wenn dies nicht der Fall ist, dann liegen wir immer richtig, wenn $f$ konstant ist, und liegen in dem Fall falsch, dass $f$ ausgeglichen ist, mit einer Wahrscheinlichkeit von gerade $2^{-k + 1}$ . Nehmen wir beispielsweise $k = 11$ , dann liefert dieser Algorithmus mit einer Wahrscheinlichkeit von mehr als $99.9$ % die richtige Antwort.

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

Deutsch-Jozsa mit Qiskit

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 Abfragegatter für eine zufällig ausgewählte Funktion implementiert, die das Versprechen für das Deutsch-Jozsa-Problem erfüllt. Mit einer Wahrscheinlichkeit von 50 % ist die Funktion konstant, und mit einer Veränderung von 50 % ist die Funktion ausgeglichen. Für jede dieser beiden Möglichkeiten wird die Funktion gleichmäßig aus den Funktionen dieses Typs ausgewä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

Wir können die Quantenschaltungsimplementierung des Abfragetors wie üblich mit der Methode draw zeigen.

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

Output:

Als Nächstes definieren wir eine Funktion, die den Deutsch-Jozsa-Schaltkreis erzeugt, indem wir eine Quantenschaltkreis-Implementierung eines Abfrage-Gatters als Argument nehmen.

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 die Deutsch-Jozsa-Schaltung einmal durchläuft.

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 Quantenschaltkreis-Implementierung eines Abfrage-Gatters für diese Funktion anzeigen und dann den Deutsch-Jozsa-Algorithmus für diese Funktion ausführen.

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

Output:

'balanced'

Das Bernstein-Vazirani-Problem

Als Nächstes werden wir ein Problem erörtern, das als Bernstein-Vazirani-Problem bekannt ist. Es wird auch Fourier-Sampling-Problem genannt, obwohl es allgemeinere Formulierungen dieses Problems gibt, die ebenfalls diesen Namen tragen.

Zunächst wollen wir einige Bezeichnungen einführen. Für zwei beliebige Binärzeichenfolgen $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 binäres Punktprodukt. Eine andere Möglichkeit der Definition lautet wie folgt.

x \cdot y = \begin{cases} 1 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ is odd}\\[0.5mm] 0 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ is even} \end{cases}

Beachten Sie, dass es sich hierbei um eine symmetrische Operation handelt, was bedeutet, dass sich das Ergebnis nicht ändert, wenn wir $x$ und $y$ vertauschen; daher können wir dies tun, wann immer es uns zweckmäßig erscheint. Manchmal ist es hilfreich, sich das binäre Skalarprodukt $x \cdot y$ als die Parität der Bits von $x$ an den Stellen vorzustellen, an denen die Zeichenkette $y$ ein $1$ enthält, oder – was gleichbedeutend ist – als die Parität der Bits von $y$ an den Stellen, an denen die Zeichenkette $x$ ein $1$ enthält.

Mit dieser Notation in der Hand 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$ \ Ausgabe: die Zeichenkette $s$

Wir brauchen eigentlich keinen neuen Quantenalgorithmus für dieses Problem; der Deutsch-Jozsa-Algorithmus löst es. Im Interesse der Klarheit bezeichnen wir die obige Quantenschaltung, die den klassischen Nachbearbeitungsschritt der Berechnung des ODERs nicht enthält, als Deutsch-Jozsa-Schaltung.

Algorithmusanalyse

Um zu analysieren, wie die Deutsch-Jozsa-Schaltung für eine Funktion funktioniert, die das Versprechen für das Bernstein-Vazirani-Problem erfüllt, beginnen wir mit einer kurzen Beobachtung. Unter Verwendung des binären Punktprodukts können wir alternativ die Wirkung von $n$ Hadamard-Gattern auf die Standard-Basiszustände von $n$ Qubits 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 hängt der Wert $(-1)^k$ für jede ganze Zahl $k$ nur davon ab, ob $k$ gerade oder ungerade ist.

Bei der Deutsch-Jozsa-Schaltung ist der Zustand der $n+1$ Qubits nach der ersten Schicht von Hadamard-Gattern folgendermaßen

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

Anschließend wird das Abfragetor ausgeführt, das (durch das Phänomen des Phasenrückschlags) den Zustand in

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

Unter Verwendung unserer Formel für die Wirkung einer Schicht von Hadamard-Gattern sehen wir, dass die zweite Schicht von Hadamard-Gattern 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 im Exponenten von „ $-1$ “ innerhalb der Summe einige Vereinfachungen vornehmen. Uns wird versprochen, dass $f(x) = s\cdot x$ für eine beliebige Zeichenkette $s = s_{n-1} \cdots s_0$ gilt, sodass wir den Zustand wie folgt ausdrücken können:

\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 es sich bei $s\cdot x$ und $x\cdot y$ um binäre Werte handelt, können wir die Addition durch die Exklusiv-ODER-Verknüpfung ersetzen - wiederum, weil es für eine ganze Zahl im Exponenten von $-1$ nur darauf ankommt, ob sie gerade oder ungerade ist. Wenn man die Symmetrie des binären Punktprodukts nutzt, erhält man diesen 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.

(Der Klarheit halber wurden Klammern hinzugefügt, obwohl sie eigentlich nicht notwendig sind, da es üblich ist, das binäre Punktprodukt mit höherem Vorrang zu behandeln als das Exklusiv-ODER)

An dieser Stelle werden wir die folgende Formel verwenden.

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

Wir können die Formel durch eine ähnliche Formel für Bits erhalten,

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

zusammen mit einer Erweiterung des binären Punktprodukts und des bitweisen Exklusiv-ODERs:

\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}

Auf diese Weise lässt sich der Zustand der Schaltung 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.

Der letzte Schritt besteht darin, eine weitere Formel anzuwenden, die für jede Binärzeichenfolge $z = z_{n-1}\cdots z_0$ funktioniert.

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

Hier verwenden wir eine einfache Notation für Zeichenketten, auf die wir im weiteren Verlauf der Lektion noch mehrmals zurückkommen werden: „ $0^n$ “ ist die Zeichenkette, die ausschließlich aus Nullen besteht und die Länge $n$ hat.

Eine einfache Möglichkeit, zu belegen, dass diese Formel funktioniert, besteht darin, die beiden Fälle getrennt zu betrachten. Gilt $z = 0^n$ , so gilt $z\cdot x = 0$ für jede Zeichenkette $x\in\Sigma^n$ ; somit ist der Wert jedes Terms in der Summe $1$ , und wir erhalten $1$ , indem wir summieren und durch $2^n$ dividieren. Ist hingegen eines der Bits von $z$ gleich $1$ , so ist das binäre Skalarprodukt $z\cdot x$ bei genau der Hälfte der möglichen Werte für $x\in\Sigma^n$ gleich $0$ und bei der anderen Hälfte gleich $1$ – denn der Wert des binären Skalarprodukts $z\cdot x$ kehrt sich um (von $0$ zu $1$ oder von $1$ zu $0$ ), wenn wir ein beliebiges Bit von $x$ an einer Stelle umkehren, an der $z$ ein $1$ enthält.

Wenn wir nun diese Formel anwenden, um den Zustand der Schaltung vor den Messungen zu vereinfachen, 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 gilt: „ $s\oplus y = 0^n$ “ genau dann, wenn „ $y = s$ “ gilt. Somit ergeben die Messungen genau die von uns gesuchte Zeichenfolge „ $s$ “.

Klassische Schwierigkeit

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

Dies lässt sich durch ein so genanntes informationstheoretisches Argument begründen, das in diesem Fall sehr einfach ist. Jede klassische Abfrage enthüllt ein einziges Bit an Informationen über die Lösung, und es gibt $n$ Bits an Informationen, die aufgedeckt werden müssen - also werden mindestens $n$ Abfragen benötigt.

Tatsächlich lässt sich das Bernstein-Vazirani-Problem klassisch lösen, indem man die Funktion für jede der Zeichenfolgen $n$ abfragt, die ein einzelnes $1$ an jeder möglichen Position enthalten, und $0$ für alle anderen Bits, wodurch die Bits von $s$ nacheinander ermittelt werden. Daher liegt der Vorteil von Quantenalgorithmen gegenüber klassischen Algorithmen bei diesem Problem darin, dass nur eine Abfrage von $1$ erforderlich ist, während bei klassischen Algorithmen $n$ Abfragen nötig sind.

Bernstein-Vazirani mit Qiskit

Wir haben die oben beschriebene Deutsch-Jozsa-Schaltung bereits implementiert und werden sie nun nutzen, um das Bernstein-Vazirani-Problem zu lösen. Zunächst definieren wir eine Funktion, die ein Abfrage-Gate für das Bernstein-Vazirani-Problem implementiert, wobei eine beliebige binäre Zeichenkette $s$ gegeben ist.

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"))

Output:

Nun können wir eine Funktion erstellen, die die Deutsch-Jozsa-Schaltung auf die Funktion anwendet, indem wir die zuvor definierte Funktion compile_circuit verwenden.

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")))

Output:

'1011'

Anmerkung zur Nomenklatur

Im Zusammenhang mit dem Bernstein-Vazirani-Problem wird der Deutsch-Jozsa-Algorithmus häufig als "Bernstein-Vazirani-Algorithmus" bezeichnet Dies ist leicht irreführend, denn der Algorithmus ist der Deutsch-Jozsa-Algorithmus, wie Bernstein und Vazirani in ihrer Arbeit sehr deutlich gemacht haben.

Nachdem Bernstein und Vazirani gezeigt hatten, dass der Deutsch-Jozsa-Algorithmus das Bernstein-Vazirani-Problem (wie oben beschrieben) löst, definierten sie ein viel komplizierteres Problem, das so genannte rekursive Fourier-Problem. Dabei handelt es sich um ein hochgradig konstruiertes Problem, bei dem die Lösungen für verschiedene Instanzen des Problems effektiv neue Ebenen des Problems freischalten, die in einer baumartigen Struktur angeordnet sind. Das Bernstein-Vazirani-Problem ist im Grunde nur der Basisfall dieses komplizierteren Problems.

Das rekursive Fourier-Sampling-Problem war das erste bekannte Beispiel für ein Abfrageproblem, bei dem Quantenalgorithmen einen so genannten Super-Polynomialvorteil gegenüber probabilistischen Algorithmen haben und damit den Vorteil von Quantenalgorithmen gegenüber klassischen Algorithmen übertreffen, den der Deutsch-Jozsa-Algorithmus bietet. Intuitiv gesprochen, vergrößert die rekursive Version des Problems den Vorteil von $1$ gegenüber $n$ der Quantenalgorithmen auf etwas viel Größeres.

Der schwierigste Aspekt der mathematischen Analyse, der diesen Vorteil begründet, ist der Nachweis, dass klassische Abfragealgorithmen das Problem nicht lösen können, ohne viele Abfragen zu machen. Das ist ganz 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 dafür sind ein viel einfacheres Beispiel für einen superpolynomiellen (und tatsächlich exponentiellen) Vorteil von Quanten- gegenüber klassischen Algorithmen, und aus diesem Grund wird das rekursive Fourier-Sampling-Problem weniger häufig diskutiert. Dennoch ist es ein interessantes Rechenproblem für sich.

War diese Seite hilfreich?

Melden Sie auf GitHub einen Fehler, einen Tippfehler oder fordern Sie Inhalte an.