Der Deutsch-Jozsa-Algorithmus

Für dieses Qiskit-in-Classrooms-Modul müssen Studierende eine funktionierende Python-Umgebung mit den folgenden installierten Paketen haben:

• qiskit v2.1.0 oder neuer
• qiskit-ibm-runtime v0.40.1 oder neuer
• qiskit-aer v0.17.0 oder neuer
• qiskit.visualization
• numpy
• pylatexenc

Zum Einrichten und Installieren der oben genannten Pakete siehe die Anleitung Qiskit installieren. Um Jobs auf echten Quantencomputern auszuführen, müssen Studierende ein Konto bei IBM Quantum® einrichten, indem sie den Schritten in der Anleitung IBM Cloud-Konto einrichten folgen.

Dieses Modul wurde getestet und verwendete vier Sekunden QPU-Zeit. Dies ist nur eine Schätzung. Dein tatsächlicher Verbrauch kann abweichen.

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

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Schau dir die Modul-Einführung von Dr. Katie McCormick unten an, oder klicke hier, um sie auf YouTube anzusehen.

---

Einführung

In den frühen 1980er Jahren hatten Quantenphysiker und Informatiker eine vage Vorstellung davon, dass die Quantenmechanik genutzt werden könnte, um Berechnungen durchzuführen, die weitaus leistungsfähiger sind als das, was klassische Computer leisten können. Ihre Argumentation war folgende: Es ist für einen klassischen Computer schwierig, Quantensysteme zu simulieren, aber ein Quantencomputer sollte dies effizienter können. Und wenn ein Quantencomputer Quantensysteme effizienter simulieren könnte, gäbe es vielleicht auch andere Aufgaben, die er effizienter als ein klassischer Computer ausführen könnte.

Die Logik war stichhaltig, aber die Details mussten noch ausgearbeitet werden. Dies begann 1985, als David Deutsch den ersten „universellen Quantencomputer" beschrieb. In derselben Arbeit lieferte er das erste Beispielproblem, für das ein Quantencomputer etwas effizienter lösen konnte als ein klassischer Computer. Dieses erste Spielzeugbeispiel ist heute als „Deutsch-Algorithmus" bekannt. Die Verbesserung in Deutschs Algorithmus war bescheiden, aber Deutsch arbeitete einige Jahre später mit Richard Jozsa zusammen, um die Lücke zwischen klassischen und Quantencomputern weiter zu vergrößern.

Diese Algorithmen — Deutschs und die Deutsch-Jozsa-Erweiterung — sind nicht besonders nützlich, aber sie sind aus mehreren Gründen dennoch wirklich wichtig:

1. Historisch gesehen waren sie einige der ersten Quantenalgorithmen, bei denen nachgewiesen wurde, dass sie ihre klassischen Gegenstücke übertreffen. Sie zu verstehen kann uns helfen zu verstehen, wie sich das Denken der Gemeinschaft über Quantencomputing im Laufe der Zeit entwickelt hat.
2. Sie können uns helfen, einige Aspekte der Antwort auf eine überraschend subtile Frage zu verstehen: Was verleiht dem Quantencomputing seine Leistungsfähigkeit? Manchmal werden Quantencomputer mit riesigen, exponentiell skalierenden Parallelprozessoren verglichen. Aber das ist nicht ganz richtig. Während ein Teil der Antwort auf diese Frage im sogenannten „Quantenparallelismus" liegt, ist das Extrahieren möglichst vieler Informationen in einem einzigen Durchlauf eine subtile Kunst. Die Deutsch- und Deutsch-Jozsa-Algorithmen zeigen, wie dies gelingen kann.

In diesem Modul lernen wir den Deutsch-Algorithmus, den Deutsch-Jozsa-Algorithmus und was sie uns über die Leistungsfähigkeit des Quantencomputings lehren.

Quantenparallelismus und seine Grenzen

Ein Teil der Leistungsfähigkeit des Quantencomputings leitet sich vom „Quantenparallelismus" ab, der im Wesentlichen die Fähigkeit ist, Operationen auf mehreren Eingaben gleichzeitig durchzuführen, da die Qubit-Eingabezustände in einer Superposition mehrerer klassisch erlaubter Zustände sein könnten. JEDOCH: Während ein Quantenschaltkreis möglicherweise mehrere Eingabezustände gleichzeitig auswerten kann, ist es unmöglich, all diese Informationen auf einmal zu extrahieren.

Um zu verstehen, was ich hier meine, nehmen wir an, wir haben ein Bit $x$ und eine auf dieses Bit angewandte Funktion $f(x)$. Es gibt vier mögliche binäre Funktionen, die ein einzelnes Bit auf ein anderes einzelnes Bit abbilden:

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

Wir möchten herausfinden, welche dieser Funktionen (1-4) unser $f(x)$ ist. Klassisch müssten wir die Funktion zweimal ausführen — einmal für $x=0$, einmal für $x=1$. Aber sehen wir, ob wir es mit einem Quantenschaltkreis besser machen können. Wir können mit dem folgenden Gate etwas über die Funktion lernen:

Hier berechnet das $U_f$-Gate $f(x)$, wobei $x$ der Zustand von Qubit 0 ist, und wendet das auf Qubit 1 an. Der resultierende Zustand $|x\rangle|y\oplus f(x)\rangle$ wird also einfach zu $|x\rangle|f(x)\rangle$, wenn $|y\rangle = |0\rangle$. Dies enthält alle Informationen, die wir benötigen, um die Funktion $f(x)$ zu kennen: Qubit 0 sagt uns, was $x$ ist, und Qubit 1 sagt uns, was $f(x)$ ist. Wenn wir also $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ initialisieren, dann wird der Endzustand beider Qubits sein: $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$. Aber wie greifen wir auf diese Informationen zu?

2.1. Probiere es mit Qiskit:

Mit Qiskit werden wir zufällig eine der vier möglichen Funktionen oben auswählen und den Schaltkreis ausführen. Deine Aufgabe ist es dann, die Messungen des Quantenschaltkreises zu verwenden, um die Funktion mit so wenigen Durchläufen wie möglich zu ermitteln.

In diesem ersten Experiment und im gesamten Modul werden wir ein Framework für Quantencomputing namens „Qiskit Patterns" verwenden, das Arbeitsabläufe in die folgenden Schritte unterteilt:

• Schritt 1: Klassische Eingaben auf ein Quantenproblem abbilden
• Schritt 2: Problem für die Quantenausführung optimieren
• Schritt 3: Mit Qiskit Runtime Primitives ausführen
• Schritt 4: Nachbearbeitung und klassische Analyse

Beginnen wir mit dem Laden einiger notwendiger Pakete, einschließlich der Qiskit Runtime Primitives. Wir werden auch den am wenigsten ausgelasteten verfügbaren Quantencomputer auswählen.

Es gibt unten Code zum Speichern deiner Anmeldedaten bei der ersten Verwendung. Stelle sicher, dass du diese Informationen nach dem Speichern in deiner Umgebung aus dem Notebook löschst, damit deine Anmeldedaten nicht versehentlich weitergegeben werden, wenn du das Notebook teilst. Siehe IBM Cloud-Konto einrichten und Service in einer nicht vertrauenswürdigen Umgebung initialisieren für weitere Hinweise.

# Load the Qiskit Runtime service
from qiskit_ibm_runtime import QiskitRuntimeService

# Load the Runtime primitive and session
from qiskit_ibm_runtime import SamplerV2 as Sampler

# Syntax for first saving your token.  Delete these lines after saving your credentials.
# QiskitRuntimeService.save_account(channel='ibm_quantum_platform', instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

# Use the least busy backend, or uncomment the loading of a specific backend like "ibm_brisbane".
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_brisbane")
print(backend.name)

sampler = Sampler(mode=backend)

ibm_brisbane

Die folgende Zelle ermöglicht es dir, im gesamten Notebook zwischen der Verwendung des Simulators und realer Hardware umzuschalten. Wir empfehlen, sie jetzt auszuführen:

# Load the backend sampler
from qiskit.primitives import BackendSamplerV2

# Load the Aer simulator and generate a noise model based on the currently-selected backend.
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel

# Alternatively, load a fake backend with generic properties and define a simulator.

noise_model = NoiseModel.from_backend(backend)

# Define a simulator using Aer, and use it in Sampler.
backend_sim = AerSimulator(noise_model=noise_model)
sampler_sim = BackendSamplerV2(backend=backend_sim)

# You could also define a simulator-based sampler using a generic backend:
# backend_gen = GenericBackendV2(num_qubits=18)
# sampler_gen = BackendSamplerV2(backend=backend_gen)

Nachdem wir die notwendigen Pakete geladen haben, können wir mit dem Qiskit-Patterns-Arbeitsablauf fortfahren. Im folgenden Mapping-Schritt erstellen wir zunächst eine Funktion, die unter den vier möglichen Funktionen auswählt, die ein einzelnes Bit auf ein anderes einzelnes Bit abbilden.

# Step 1: Map

from qiskit import QuantumCircuit

qc = QuantumCircuit(2)

def twobit_function(case: int):
    """
    Generate a valid two-bit function as a `QuantumCircuit`.
    """
    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

# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
# blackbox = twobit_function(2).to_gate()  # you may edit the number inside "twobit_function()" to select among the four valid functions
# blackbox.label = "$U_f$"

qc.h(0)
qc.barrier()
qc.compose(twobit_function(2), inplace=True)
qc.measure_all()

qc.draw("mpl")

Im obigen Schaltkreis bringt das Hadamard-Gate „H" Qubit 0, das anfänglich im Zustand $|0\rangle$ ist, in den Superpositionszustand $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. Dann wertet $U_f$ die Funktion $f(x)$ aus und wendet das auf Qubit 1 an.

Als nächstes müssen wir den Schaltkreis optimieren und transpilieren, um ihn auf dem Quantencomputer auszuführen:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

Schließlich führen wir unseren transpilierten Schaltkreis auf dem Quantencomputer aus und visualisieren unsere Ergebnisse:

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.meas.get_counts()

# Step 4: Visualize and analyze results

## Analysis
from qiskit.visualization import plot_histogram

plot_histogram(counts)

Oben ist ein Histogramm unserer Ergebnisse. Abhängig von der Anzahl der Shots, die du für die Ausführung des Schaltkreises in Schritt 3 oben gewählt hast, könntest du einen oder zwei Balken sehen, die die gemessenen Zustände der beiden Qubits in jedem Shot darstellen. Wie immer bei Qiskit und in diesem Notebook verwenden wir die „Little-Endian"-Notation, was bedeutet, dass die Zustände der Qubits 0 bis n in aufsteigender Reihenfolge von rechts nach links geschrieben werden, sodass Qubit 0 immer ganz rechts steht.

Da Qubit 0 in einem Superpositionszustand war, hat der Schaltkreis also die Funktion für beide $x=0$ und $x=1$ gleichzeitig ausgewertet — etwas, das klassische Computer nicht können! Aber der Haken kommt, wenn wir etwas über die Funktion $f(x)$ erfahren wollen — wenn wir die Qubits messen, kollabieren wir ihren Zustand. Wenn du „shots = 1" wählst, um den Schaltkreis nur einmal auszuführen, wirst du nur einen Balken im obigen Histogramm sehen, und deine Informationen über die Funktion werden unvollständig sein.

Überprüfe dein Verständnis

Lies die Frage(n) unten, denke über deine Antwort nach und klicke dann auf das Dreieck, um die Lösung anzuzeigen.

Wie oft müssen wir den obigen Algorithmus ausführen, um die Funktion $f(x)$ zu ermitteln? Ist das besser als im klassischen Fall? Hättest du lieber einen klassischen oder einen Quantencomputer, um dieses Problem zu lösen?

Antwort:

Da die Messung die Superposition kollabiert und nur einen Wert zurückgibt, müssen wir den Schaltkreis mindestens zweimal ausführen, um beide Ausgaben der Funktion $f(0)$ und $f(1)$ zu erhalten. Im besten Fall ist die Leistung genauso gut wie im klassischen Fall, wo wir sowohl $f(0)$ als auch $f(1)$ in den ersten beiden Abfragen berechnen. Aber es besteht die Chance, dass wir ihn mehr als zweimal ausführen müssen, da die endgültige Messung probabilistisch ist und die ersten beiden Male denselben $f(x)$-Wert zurückgeben könnte. In diesem Fall hätte ich lieber einen klassischen Computer.

Obwohl Quantenparallelismus also bei richtiger Anwendung leistungsfähig sein kann, ist es nicht korrekt zu sagen, dass ein Quantencomputer wie ein massiver, klassischer Parallelprozessor funktioniert. Der Akt der Messung kollabiert die Quantenzustände, sodass wir immer nur auf eine einzelne Ausgabe der Berechnung zugreifen können.

Der Deutsch-Algorithmus

Während Quantenparallelismus allein uns keinen Vorteil gegenüber klassischen Computern verschafft, können wir ihn mit einem anderen Quantenphänomen, der Interferenz, kombinieren, um eine Beschleunigung zu erzielen. Der heute als „Deutsch-Algorithmus" bekannte Algorithmus ist das erste Beispiel eines Algorithmus, der dies erreicht.

Das Problem

Hier war das Problem:

Gegeben ein Eingabebit $x = \{0,1\}$ und eine Eingabefunktion $f(x) = \{0,1\}$, bestimme, ob die Funktion balanciert oder konstant ist. Das heißt, wenn sie balanciert ist, dann ist die Ausgabe der Funktion die Hälfte der Zeit 0 und die andere Hälfte 1. Wenn sie konstant ist, dann ist die Ausgabe der Funktion entweder immer 0 oder immer 1. Erinnere dich an die Tabelle der vier möglichen Funktionen, die ein einzelnes Bit auf ein anderes einzelnes Bit abbilden:

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

Die erste und die letzte Funktion, $f_1(x)$ und $f_4(x)$, sind konstant, während die beiden mittleren Funktionen, $f_2(x)$ und $f_3(x)$, balanciert sind.

Der Algorithmus

Die Art, wie Deutsch dieses Problem anging, war über das „Abfragemodell". Im Abfragemodell ist die Eingabefunktion ($f_i(x)$ oben) in einer „Black Box" enthalten — wir haben keinen direkten Zugriff auf ihren Inhalt, aber wir können die Black Box abfragen und sie gibt uns die Ausgabe der Funktion. Manchmal sagen wir, dass ein „Orakel" diese Information liefert. Siehe Lektion 1: Quanten-Abfragealgorithmen des Kurses „Grundlagen der Quantenalgorithmen" für mehr zum Abfragemodell.

Um festzustellen, ob ein Quantenalgorithmus effizienter ist als ein klassischer Algorithmus im Abfragemodell, können wir einfach die Anzahl der Abfragen vergleichen, die wir in jedem Fall an die Black Box stellen müssen. Im klassischen Fall müssten wir die Box zweimal abfragen, um zu wissen, ob die in der Black Box enthaltene Funktion balanciert oder konstant ist, um sowohl $f(0)$ als auch $f(1)$ zu erhalten.

In Deutschs Quantenalgorithmus fand er jedoch einen Weg, die Information mit nur einer Abfrage zu erhalten! Er nahm eine Anpassung am „Quantenparallelismus"-Schaltkreis oben vor, sodass er einen Superpositionszustand auf beiden Qubits vorbereitete, anstatt nur auf Qubit 0. Dann interferierten die beiden Ausgaben der Funktion, $f(0)$ und $f(1)$, um 0 zurückzugeben, wenn sie entweder beide 0 oder beide 1 waren (die Funktion war konstant), und 1 zurückzugeben, wenn sie verschieden waren (die Funktion war balanciert). Auf diese Weise konnte Deutsch mit einer einzigen Abfrage zwischen einer konstanten und einer balancierten Funktion unterscheiden.

Hier ist ein Schaltkreisdiagramm von Deutschs Algorithmus:

Um zu verstehen, wie dieser Algorithmus funktioniert, betrachten wir die Quantenzustände der Qubits an den drei im Diagramm oben markierten Punkten. Versuche, die Zustände selbst auszurechnen, bevor du klickst, um die Antworten anzuzeigen:

Überprüfe dein Verständnis

Lies die Fragen unten, denke über deine Antworten nach und klicke dann auf die Dreiecke, um die Lösungen anzuzeigen.

Was ist der Zustand $|\pi_1\rangle$?

Antwort:

Das Anwenden eines Hadamard transformiert den Zustand $|0\rangle$ zu $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ und den Zustand $|1\rangle$ zu $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Der Gesamtzustand wird also: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

Was ist der Zustand $|\pi_2\rangle$?

Antwort:

Bevor wir $U_f$ anwenden, erinnern wir uns daran, was es tut. Es ändert den Zustand von Qubit 1 basierend auf dem Zustand von Qubit 0. Es ist also sinnvoll, den Zustand von Qubit 0 herauszufaktorisieren: $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$. Wenn dann $f(0)=f(1)$, werden die beiden Terme auf die gleiche Weise transformiert und das relative Vorzeichen zwischen den beiden Termen bleibt positiv, aber wenn $f(0)\neq f(1)$, dann nimmt der zweite Term ein Minuszeichen relativ zum ersten Term auf, wodurch der Zustand von Qubit 0 von $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ zu $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ wechselt. Also:

$$|\pi_2\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}] & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle-|1\rangle}{\sqrt{2}}] &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

Was ist der Zustand $|\pi_3\rangle$?

Antwort:

Jetzt ist der Zustand von Qubit 0 entweder $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ oder $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$, abhängig von der Funktion. Das Anwenden des Hadamard ergibt dann entweder $|0\rangle$ bzw. $|1\rangle$.

$$|\pi_3\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|0\rangle & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|1\rangle &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

Wenn du deine Antworten auf die obigen Fragen durchgehst, beachte, dass etwas etwas Überraschendes passiert. Obwohl $U_f$ nichts explizit am Zustand von Qubit 0 ändert, kann es, da es Qubit 1 basierend auf dem Zustand von Qubit 0 ändert, zu einer Phasenverschiebung in Qubit 0 kommen. Dies ist als das „Phase-Kickback"-Phänomen bekannt und wird ausführlicher in Lektion 1: Quanten-Abfragealgorithmen des Kurses „Grundlagen der Quantenalgorithmen" besprochen.

Nachdem wir nun verstehen, wie dieser Algorithmus funktioniert, implementieren wir ihn mit Qiskit.

## Deutsch's algorithm:

## Step 1: Map the problem

# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
blackbox = twobit_function(
    3
).to_gate()  # you may edit the number (1-4) inside "twobit_function()" to select among the four valid functions
blackbox.label = "$U_f$"

qc_deutsch = QuantumCircuit(2, 1)

qc_deutsch.x(1)
qc_deutsch.h(range(2))

qc_deutsch.barrier()
qc_deutsch.compose(twobit_function(2), inplace=True)
qc_deutsch.barrier()

qc_deutsch.h(0)
qc_deutsch.measure(0, 0)

qc_deutsch.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_deutsch)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)
if "1" in counts:
    print("balanced")
else:
    print("constant")

{'1': 1}
balanced

Der Deutsch-Jozsa-Algorithmus

Der Deutsch-Algorithmus war ein wichtiger erster Schritt bei der Demonstration, wie ein Quantencomputer effizienter sein könnte als ein klassischer Computer, aber es war nur eine bescheidene Verbesserung: Er benötigte nur eine Abfrage im Vergleich zu zwei im klassischen Fall. 1992 erweiterten Deutsch und sein Kollege Richard Jozsa den ursprünglichen Zwei-Qubit-Algorithmus auf mehr Qubits. Das Problem blieb dasselbe: Bestimme, ob eine Funktion balanciert oder konstant ist. Aber diesmal bildet die Funktion $n$ Bits auf ein einzelnes Bit ab. Entweder gibt die Funktion gleich häufig 0 und 1 zurück (sie ist balanciert) oder die Funktion gibt immer 1 oder immer 0 zurück (sie ist konstant).

Hier ist ein Schaltkreisdiagramm des Algorithmus:

Dieser Algorithmus funktioniert auf die gleiche Weise wie der Deutsch-Algorithmus: Das Phase-Kickback ermöglicht es, den Zustand von Qubit 0 auszulesen, um festzustellen, ob die Funktion konstant oder balanciert ist. Es ist etwas schwieriger zu erkennen als beim Zwei-Qubit-Deutsch-Algorithmus, da die Zustände Summen über die $n$ Qubits enthalten werden, und das Ausrechnen dieser Zustände wird als optionale Übung für dich am Ende des Moduls belassen. Der Algorithmus gibt eine Bitfolge aus lauter Nullen zurück, wenn die Funktion konstant ist, und eine Bitfolge mit mindestens einer 1, wenn die Funktion balanciert ist.

Um zu sehen, wie der Algorithmus in Qiskit funktioniert, müssen wir zunächst unser Orakel generieren: die zufällige Funktion, die garantiert entweder konstant oder balanciert ist. Der untenstehende Code generiert zu 50% eine balancierte und zu 50% eine konstante Funktion. Mach dir keine Sorgen, wenn du dem Code nicht vollständig folgen kannst — er ist kompliziert und nicht notwendig für unser Verständnis des Quantenalgorithmus.

from qiskit import QuantumCircuit
import numpy as np

def dj_function(num_qubits):
    """
    Create a random Deutsch-Jozsa function.
    """

    qc_dj = QuantumCircuit(num_qubits + 1)
    if np.random.randint(0, 2):
        # Flip output qubits with 50% chance
        qc_dj.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance.
        return qc_dj

    # If the "if" statement above was "TRUE" then we've returned the constant
    # function and the function is complete. If not, we proceed in creating our
    # balanced function. Everything below is to produce the balanced function:

    # select half of all possible states at random:
    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_dj, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc_dj.x(qubit)
        return qc_dj

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

    # qc_dj.barrier()

    return qc_dj

n = 3  # number of input qubits

oracle = dj_function(n)

display(oracle.draw("mpl"))

Dies ist die Orakelfunktion, die entweder balanciert oder konstant ist. Kannst du durch Betrachten erkennen, ob die Ausgabe des letzten Qubits von den Werten abhängt, die für die ersten $n$ Qubits eingegeben werden? Wenn die Ausgabe des letzten Qubits von den ersten $n$ Qubits abhängt, kannst du erkennen, ob diese abhängige Ausgabe balanciert ist oder nicht?

Wir können anhand des obigen Schaltkreises erkennen, ob die Funktion balanciert oder konstant ist, aber denke daran, dass wir diese Funktion im Rahmen dieses Problems als „Black Box" betrachten. Wir können nicht in die Box hineinschauen, um das Schaltkreisdiagramm zu sehen. Stattdessen müssen wir die Box abfragen.

Um die Box abzufragen, verwenden wir den Deutsch-Jozsa-Algorithmus und bestimmen, ob die Funktion konstant oder balanciert ist:

blackbox = oracle.to_gate()
blackbox.label = "$U_f$"

qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(blackbox, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()

qc_dj.draw("mpl")

# Step 1: Map the problem

qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(oracle, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()

qc_dj.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_dj)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

if (
    "0" * n in counts
):  # The D-J algorithm returns all zeroes if the function was constant
    print("constant")
else:
    print("balanced")  # anything other than all zeroes means the function is balanced.

{'110': 1}
balanced

Oben ist in der ersten Zeile der Ausgabe die Bitfolge der Messergebnisse. Die zweite Zeile gibt aus, ob die Bitfolge darauf hindeutet, dass die Funktion balanciert oder konstant war. Wenn die Bitfolge nur Nullen enthielt, war sie konstant; wenn nicht, war sie balanciert. Mit nur einem einzigen Durchlauf des obigen Quantenschaltkreises können wir also bestimmen, ob die Funktion konstant oder balanciert ist!

Überprüfe dein Verständnis

Lies die Fragen unten, denke über deine Antworten nach und klicke dann auf die Dreiecke, um die Lösungen anzuzeigen.

Wie viele Abfragen würde ein klassischer Computer benötigen, um mit 100%iger Sicherheit festzustellen, ob eine Funktion konstant oder balanciert ist? Denke daran, dass eine einzelne klassische Abfrage es dir nur erlaubt, die Funktion auf eine einzelne Bitfolge anzuwenden.

Antwort:

Es gibt $2^n$ mögliche Bitfolgen zu überprüfen, und im schlimmsten Fall müsstest du $2^n/2+1$ davon testen. Wenn die Funktion zum Beispiel konstant wäre und du immer wieder „1" als Ausgabe der Funktion messen würdest, dann könntest du dir nicht sicher sein, dass sie wirklich konstant ist, bis du über die Hälfte der Ergebnisse überprüft hast. Vorher könntest du einfach bei einer balancierten Funktion sehr viel Pech gehabt haben, immer wieder „1" zu messen. Es ist wie eine Münze immer wieder zu werfen und sie landet jedes Mal auf Kopf. Es ist unwahrscheinlich, aber nicht unmöglich.

Wie würde sich deine obige Antwort ändern, wenn du nur so lange messen müsstest, bis ein Ergebnis (balanciert oder konstant) wahrscheinlicher ist als das andere? Wie viele Abfragen wären in diesem Fall nötig?

Antwort:

In diesem Fall könntest du einfach zweimal messen. Wenn die beiden Messungen unterschiedlich sind, weißt du, dass die Funktion balanciert ist. Wenn die beiden Messungen gleich sind, könnte sie balanciert oder konstant sein. Die Wahrscheinlichkeit, dass sie bei diesen Messungen balanciert ist, beträgt: $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$. Dies ist weniger als 1/2, also ist es in diesem Fall wahrscheinlicher, dass die Funktion konstant ist.

Der Deutsch-Jozsa-Algorithmus zeigte also eine exponentielle Beschleunigung gegenüber einem deterministischen klassischen Algorithmus (einem, der die Antwort mit 100%iger Sicherheit liefert), aber keine signifikante Beschleunigung gegenüber einem probabilistischen (einem, der ein Ergebnis liefert, das wahrscheinlich die richtige Antwort ist).

Das Bernstein-Vazirani-Problem

1997 verwendeten Ethan Bernstein und Umesh Vazirani den Deutsch-Jozsa-Algorithmus, um ein spezifischeres, eingeschränkteres Problem im Vergleich zum Deutsch-Jozsa-Problem zu lösen. Anstatt einfach zwischen zwei verschiedenen Klassen von Funktionen zu unterscheiden, wie im D-J-Fall, nutzten Bernstein und Vazirani den Deutsch-Jozsa-Algorithmus, um tatsächlich eine in einer Funktion kodierte Zeichenkette zu lernen. Hier ist das Problem:

Die Funktion $f:\{0,1\}^n \rightarrow \{0,1\}$ nimmt weiterhin eine $n$-Bit-Zeichenkette und gibt ein einzelnes Bit aus. Aber jetzt, anstatt zu versprechen, dass die Funktion balanciert oder konstant ist, wird jetzt versprochen, dass die Funktion das Skalarprodukt zwischen der Eingabezeichenkette $x$ und einer geheimen $n$-Bit-Zeichenkette $s$ ist, modulo 2. (Dieses Skalarprodukt modulo 2 wird „binäres Skalarprodukt" genannt.) Das Problem besteht darin, herauszufinden, was die geheime $n$-Bit-Zeichenkette ist.

Anders ausgedrückt: Uns wird eine Black-Box-Funktion $f: {0,1}^n \rightarrow {0,1}$ gegeben, die $f(x) = s \cdot x$ für eine bestimmte Zeichenkette $s$ erfüllt, und wir wollen die Zeichenkette $s$ herausfinden.

Schauen wir uns an, wie der D-J-Algorithmus dieses Problem löst:

1. Zuerst wird ein Hadamard-Gate auf die $n$ Eingangs-Qubits angewendet, und ein NOT-Gate plus ein Hadamard wird auf das Ausgangs-Qubit angewendet, wodurch der Zustand wird:

$$|\Psi\rangle = |-\rangle_{n} \otimes |+\rangle_{n-1} \otimes |+\rangle_{n-2} \otimes ... \otimes |+\rangle_0$$

Der Zustand der Qubits 1 bis $n$ kann einfacher als Summe über alle $2^n$ $n$-Qubit-Basiszustände $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$ geschrieben werden. Wir nennen die Menge dieser Basiszustände $\Sigma^n$. (Siehe Grundlagen der Quantenalgorithmen für weitere Details.)

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{|x\rangle}$$

2. Als nächstes wird das $U_f$-Gate auf die Qubits angewendet. Dieses Gate nimmt die ersten n Qubits als Eingabe (die sich jetzt in einer gleichmäßigen Superposition aller möglichen n-Bit-Zeichenketten befinden) und wendet die Funktion $f(x)=s \cdot x$ auf das Ausgangs-Qubit an, sodass dieses Qubit jetzt im Zustand ist: $|- \oplus f(x)\rangle$. Dank des Phase-Kickback-Mechanismus bleibt der Zustand dieses Qubits unverändert, aber einige der Terme im Eingabe-Qubit-Zustand erhalten ein Minuszeichen:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{(-1)^{f(x)}|x\rangle}$$

3. Jetzt werden die nächsten Hadamards auf die Qubits 0 bis $n-1$ angewendet. Die Minuszeichen in diesem Fall zu verfolgen, kann knifflig sein. Es ist hilfreich zu wissen, dass das Anwenden einer Schicht von Hadamards auf $n$ Qubits in einem Standard-Basiszustand $|x\rangle$ geschrieben werden kann als:

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

Der Zustand wird also:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{2^n}\sum\limits_{x \in \Sigma^n}\sum\limits_{y \in \Sigma^n}{(-1)^{(s \cdot x) + (x \cdot y)}|y\rangle}$$

4. Der nächste Schritt ist, die ersten $n$ Bits zu messen. Aber was werden wir messen? Es stellt sich heraus, dass sich der obige Zustand zu: $|\Psi\rangle = |-\rangle \otimes |s\rangle$ vereinfacht, aber das ist alles andere als offensichtlich. Wenn du die Mathematik nachvollziehen möchtest, siehe John Watrous' Kurs Grundlagen der Quantenalgorithmen. Der Punkt ist jedoch, dass der Phase-Kickback-Mechanismus dazu führt, dass die Eingangs-Qubits im Zustand $|s\rangle$ sind. Um also herauszufinden, was die geheime Zeichenkette $s$ war, musst du einfach die Qubits messen!

Überprüfe dein Verständnis

Lies die Fragen unten, denke über deine Antworten nach und klicke dann auf die Dreiecke, um die Lösungen anzuzeigen.

Überprüfe, dass der Zustand aus Schritt 3 oben tatsächlich der Zustand $|s\rangle$ ist, für den Spezialfall $n=1$.

Antwort:

Wenn du die beiden Summationen explizit ausschreibst, solltest du einen Zustand mit vier Termen erhalten (lassen wir den Ausgabezustand $|-\rangle$ hierfür weg):

$$|\Psi\rangle = \frac{1}{2}[|0\rangle + (-1)^s |0\rangle + |1\rangle + (-1)^{(s+1)} |1\rangle]$$

Wenn $s=0$, dann addieren sich die ersten beiden Terme konstruktiv und die letzten beiden Terme heben sich auf, sodass $|\Psi\rangle = |0\rangle$ bleibt. Wenn $s=1$, dann addieren sich die letzten beiden Terme konstruktiv und die ersten beiden Terme heben sich auf, sodass $|\Psi\rangle = |1\rangle$ bleibt. In beiden Fällen ist also $|\Psi\rangle = |s\rangle$. Hoffentlich gibt dir dieser einfachste Fall ein Gefühl dafür, wie der allgemeine Fall mit $n$ Qubits funktioniert: Alle Terme, die nicht $|s\rangle$ sind, interferieren destruktiv und es bleibt nur der Zustand $|s\rangle$ übrig.

Wie kann derselbe Algorithmus sowohl das Bernstein-Vazirani- als auch das Deutsch-Jozsa-Problem lösen? Um das zu verstehen, denke über Bernstein-Vazirani-Funktionen nach, die die Form $f(x) = s \cdot x$ haben. Sind diese Funktionen auch Deutsch-Jozsa-Funktionen? Das heißt, bestimme, ob Funktionen dieser Form das Versprechen des Deutsch-Jozsa-Problems erfüllen: dass sie entweder konstant oder balanciert sind. Wie hilft uns das zu verstehen, wie derselbe Algorithmus zwei verschiedene Probleme löst?

Antwort:

Jede Bernstein-Vazirani-Funktion der Form $f(x) = s \cdot x$ erfüllt auch das Versprechen des Deutsch-Jozsa-Problems: Wenn s=00...00, dann ist die Funktion konstant (gibt immer 0 für jede Zeichenkette x zurück). Wenn s eine andere Zeichenkette ist, dann ist die Funktion balanciert. Das Anwenden des Deutsch-Jozsa-Algorithmus auf eine dieser Funktionen löst also gleichzeitig beide Probleme! Es gibt die Zeichenkette zurück, und wenn diese Zeichenkette 00...00 ist, dann wissen wir, dass sie konstant ist; wenn mindestens eine „1" in der Zeichenkette ist, wissen wir, dass sie balanciert ist.

Wir können auch experimentell überprüfen, dass dieser Algorithmus das Bernstein-Vazirani-Problem erfolgreich löst. Zuerst erstellen wir die B-V-Funktion, die in der Black Box lebt:

# Step 1: Map the problem

def bv_function(s):
    """
    Create a Bernstein-Vazirani function from a string of 1s and 0s.
    """
    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc

display(bv_function("1000").draw("mpl"))

string = "1000"  # secret string that we'll pretend we don't know or have access to
n = len(string)

qc = QuantumCircuit(n + 1, n)
qc.x(n)
qc.h(range(n + 1))
qc.barrier()
# qc.compose(oracle, inplace = True)
qc.compose(bv_function(string), inplace=True)
qc.barrier()
qc.h(range(n))
qc.measure(range(n), range(n))

qc.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

{'0000': 1}

Mit nur einer einzigen Abfrage gibt der Deutsch-Jozsa-Algorithmus also die in der Funktion verwendete Zeichenkette $s$ zurück: $f(x)=x \cdot s$, wenn wir ihn auf das Bernstein-Vazirani-Problem anwenden. Mit einem klassischen Algorithmus würde man $n$ Abfragen benötigen, um dasselbe Problem zu lösen.

Fazit

Wir hoffen, dass wir dir durch die Untersuchung dieser einfachen Beispiele eine bessere Intuition dafür gegeben haben, wie Quantencomputer Superposition, Verschränkung und Interferenz nutzen können, um ihre Überlegenheit gegenüber klassischen Computern zu erreichen.

Der Deutsch-Jozsa-Algorithmus hat eine enorme historische Bedeutung, weil er der erste war, der eine Beschleunigung gegenüber einem klassischen Algorithmus demonstrierte, aber es war nur eine polynomielle Beschleunigung. Der Deutsch-Jozsa-Algorithmus ist nur der Anfang der Geschichte.

Nachdem sie den Algorithmus zur Lösung ihres Problems verwendet hatten, nutzten Bernstein und Vazirani dies als Grundlage für ein komplizierteres, rekursives Problem namens rekursives Fourier-Sampling-Problem. Ihre Lösung bot eine superpolynomielle Beschleunigung gegenüber klassischen Algorithmen. Und noch vor Bernstein und Vazirani hatte Peter Shor bereits seinen berühmten Algorithmus entwickelt, der es Quantencomputern ermöglichte, große Zahlen exponentiell schneller zu faktorisieren als jeder klassische Algorithmus. Diese Ergebnisse zeigten zusammen das aufregende Potenzial zukünftiger Quantencomputer und spornten Physiker und Ingenieure an, diese Zukunft Wirklichkeit werden zu lassen.

Fragen

Dozenten können Versionen dieser Notebooks mit Lösungsschlüsseln und Hinweisen zur Einordnung in gängige Lehrpläne anfordern, indem sie diese kurze Umfrage zur Verwendung der Notebooks ausfüllen.

Zentrale Konzepte

• Die Deutsch- und Deutsch-Jozsa-Algorithmen verwenden Quantenparallelismus in Kombination mit Interferenz, um schneller eine Antwort auf ein Problem zu finden, als es ein klassischer Computer kann.
• Der Phase-Kickback-Mechanismus ist ein kontraintuitives Quantenphänomen, das Operationen auf einem Qubit auf die Phase eines anderen Qubits überträgt. Die Deutsch- und Deutsch-Jozsa-Algorithmen nutzen diesen Mechanismus.
• Der Deutsch-Jozsa-Algorithmus bietet eine polynomielle Beschleunigung gegenüber jedem deterministischen klassischen Algorithmus.
• Der Deutsch-Jozsa-Algorithmus kann auf ein anderes Problem angewendet werden, das Bernstein-Vazirani-Problem, um eine in einer Funktion versteckte Zeichenkette zu finden.

Wahr/Falsch

1. W/F Deutschs Algorithmus ist ein Spezialfall des Deutsch-Jozsa-Algorithmus, bei dem die Eingabe ein einzelnes Qubit ist.
2. W/F Die Deutsch- und Deutsch-Jozsa-Algorithmen verwenden Quanten-Superposition und Interferenz, um ihre Effizienz zu erreichen.
3. W/F Der Deutsch-Jozsa-Algorithmus erfordert mehrere Funktionsauswertungen, um festzustellen, ob eine Funktion konstant oder balanciert ist.
4. W/F Der „Bernstein-Vazirani-Algorithmus" ist tatsächlich derselbe wie der Deutsch-Jozsa-Algorithmus, angewendet auf ein anderes Problem.
5. W/F Der Bernstein-Vazirani-Algorithmus kann mehrere geheime Zeichenketten gleichzeitig finden.

Kurzantwort

1. Wie lange würde ein klassischer Algorithmus im schlimmsten Fall brauchen, um das Deutsch-Jozsa-Problem zu lösen?

2. Wie lange würde ein klassischer Algorithmus brauchen, um das Bernstein-Vazirani-Problem zu lösen? Welche Beschleunigung bietet der DJ-Algorithmus in diesem Fall?

3. Beschreibe den Phase-Kickback-Mechanismus und wie er zur Lösung des Deutsch-Jozsa- und Bernstein-Vazirani-Problems funktioniert.

Herausforderungsproblem

1. Der Deutsch-Jozsa-Algorithmus: Erinnere dich daran, dass du oben eine Frage hattest, in der du die Zwischenzustände $\pi_1$ und $\pi_2$ des Deutsch-Algorithmus ausrechnen solltest. Mache dasselbe für die $(n+1)$-Qubit-Zwischenzustände $\pi_1$ und $\pi_2$ des Deutsch-Jozsa-Algorithmus, für den speziellen Fall $n=2$. Überprüfe dann, dass $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$, ebenfalls für den speziellen Fall $n=2$.