Der Deutsch-Jozsa-Algorithmus

Für dieses Modul "Qiskit im Klassenzimmer" müssen die Schüler eine funktionierende Python Umgebung mit den folgenden Paketen installiert 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

Um die oben genannten Pakete einzurichten und zu installieren, lesen Sie die Anleitung Qiskit installieren. Um Aufträge auf echten Quantencomputern ausführen zu können, müssen die Schüler ein Konto bei IBM Quantum® einrichten, indem sie die Schritte in der Anleitung zur Einrichtung Ihres IBM Cloud Kontos befolgen.

Dieses Modul wurde getestet und verbrauchte vier Sekunden QPU-Zeit. Dies ist nur eine Schätzung. Ihre tatsächliche Nutzung kann davon abweichen.

# 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'

Schauen Sie sich den Modul-Walkthrough von Dr. Katie McCormick unten an, oder klicken Sie hier, um ihn auf YouTube zu sehen.

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 klassische Computer. Ihre Überlegung war folgende: Für einen klassischen Computer ist es schwierig, Quantensysteme zu simulieren, aber ein Quantencomputer sollte dazu in der Lage sein, dies effizienter zu tun. Und wenn ein Quantencomputer Quantensysteme effizienter simulieren könnte, gäbe es vielleicht auch andere Aufgaben, die er effizienter erledigen könnte als ein klassischer Computer.

Die Logik war gut, aber die Details mussten noch ausgearbeitet werden. Dies begann 1985, als David Deutsch den ersten "universellen Quantencomputer" beschrieb In demselben Papier lieferte er das erste Beispielproblem, bei dem ein Quantencomputer etwas effizienter lösen konnte als ein klassischer Computer. Dieses erste Spielzeugbeispiel ist heute als "Deutsch's Algorithmus" bekannt Die Verbesserung in Deutschs Algorithmus war bescheiden, aber Deutsch arbeitete einige Jahre später mit Richard Jozsa zusammen, um die Kluft zwischen klassischen und Quantencomputern weiter zu vergrößern.

Diese Algorithmen - der von Deutsch und die Deutsch-Jozsa-Erweiterung - sind nicht besonders nützlich, aber aus einigen Gründen dennoch sehr wichtig:

Historisch gesehen waren sie einige der ersten Quantenalgorithmen, die nachweislich ihre klassischen Gegenstücke übertreffen konnten. Wenn wir sie verstehen, können wir nachvollziehen, wie sich das Denken der Gemeinschaft über das Quantencomputing im Laufe der Zeit entwickelt hat.
Sie können uns helfen, einige Aspekte der Antwort auf eine erstaunlich subtile Frage zu verstehen: Was macht das Quantencomputing so leistungsfähig? Manchmal werden Quantencomputer mit riesigen, exponentiell skalierenden Parallelprozessoren verglichen. Aber das ist nicht ganz richtig. Ein Teil der Antwort auf diese Frage liegt in der so genannten "Quantenparallelität", doch die Gewinnung möglichst vieler Informationen in einem einzigen Durchgang ist eine hohe Kunst. Die Algorithmen Deutsch und Deutsch-Jozsa zeigen, wie dies möglich ist.

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

Quantenparallelismus und seine Grenzen

Ein Teil der Leistungsfähigkeit der Quanteninformatik beruht auf der "Quantenparallelität" was im Wesentlichen die Fähigkeit ist, Operationen an mehreren Eingängen gleichzeitig durchzuführen, da die Qubit-Eingangszustände in einer Überlagerung mehrerer klassisch zulässiger Zustände liegen können. JEDOCH kann ein Quantenschaltkreis zwar mehrere Eingangszustände auf einmal auswerten, aber es ist unmöglich, alle Informationen auf einmal zu extrahieren.

Um zu sehen, was ich hier meine, nehmen wir an, wir haben ein Bit, $x$ und eine Funktion, die auf dieses Bit angewendet wird, $f(x)$ . Es gibt vier mögliche Binärfunktionen, die ein einzelnes Bit auf ein anderes einzelnes Bit anwenden:

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

Wir würden gerne herausfinden, welche dieser Funktionen (1-4) unsere $f(x)$ ist. Klassischerweise müssten wir die Funktion zweimal ausführen - einmal für $x=0$ und einmal für $x=1$ . Aber schauen wir mal, ob wir es mit einer Quantenschaltung besser machen können. Wir können die Funktion mit dem folgenden Tor kennenlernen:

Hier berechnet das Tor $U_f$ $f(x)$ , wobei $x$ der Zustand von Qubit 0 ist, und wendet diesen auf Qubit 1 an. Der sich daraus ergebende 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 brauchen, 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 kommen wir an diese Information?

2.1. Probieren Sie es auf Qiskit aus:

Mit Qiskit wählen wir zufällig eine der vier möglichen Funktionen aus und führen die Schaltung aus. Ihre Aufgabe ist es dann, die Messungen des Quantenschaltkreises zu nutzen, um die Funktion in möglichst wenigen Durchläufen zu lernen.

In diesem ersten Experiment und während des gesamten Moduls werden wir einen Rahmen für Quantencomputer verwenden, der als "Qiskit-Muster" bekannt ist und Arbeitsabläufe in die folgenden Schritte unterteilt:

Schritt 1: Abbildung klassischer Eingaben auf ein Quantenproblem
Schritt 2: Optimieren des Problems für die Quantenausführung
Schritt 3: Ausführung mithilfe von „ IBM Quantum “-Primitiven
Schritt 4: Nachbearbeitung und klassische Analyse

Beginnen wir damit, einige erforderliche Pakete zu laden, darunter die Primitive aus dem „ IBM Quantum “. Außerdem werden wir den am wenigsten ausgelasteten Quantencomputer auswählen, der uns zur Verfügung steht.

Unten finden Sie einen Code, mit dem Sie Ihre Anmeldedaten bei der ersten Verwendung speichern können. Achten Sie darauf, diese Informationen aus dem Notebook zu löschen, nachdem Sie es in Ihrer Umgebung gespeichert haben, damit Ihre Anmeldedaten nicht versehentlich weitergegeben werden, wenn Sie das Notebook freigeben. Weitere Anleitungen finden Sie unter Einrichten Ihres IBM Cloud Kontos und Initialisieren des Dienstes in einer nicht vertrauenswürdigen Umgebung.

# Load IBM Quantum Compute 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)

Output:

ibm_brisbane

Die Zelle unten ermöglicht es Ihnen, zwischen der Verwendung des Simulators und der realen Hardware während des gesamten Notebooks zu wechseln. Wir empfehlen, ihn 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 nun die erforderlichen Pakete geladen haben, können wir mit dem Arbeitsablauf der Qiskit-Muster fortfahren. In der nachstehenden Abbildung wird zunächst eine Funktion erstellt, die eine der vier möglichen Funktionen auswählt, die ein einzelnes Bit in ein anderes einzelnes Bit überführt.

# 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

# you may edit the number inside "twobit_function()" to select among the four valid functions:
# blackbox = twobit_function(2).to_gate()

# blackbox.label = "$U_f$"

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


qc.draw("mpl")

Output:

In der obigen Schaltung bringt das Hadamard-Gatter "H" das Qubit 0, das sich zunächst im Zustand $|0\rangle$ befindet, in den Überlagerungszustand $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ . Dann wertet $U_f$ die Funktion $f(x)$ aus und wendet sie auf das Qubit 1 an.

Als Nächstes müssen wir die Schaltung für den Betrieb auf dem Quantencomputer optimieren und übersetzen:

# 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 unsere transpilierte Schaltung 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)

Output:

Die obige Abbildung zeigt ein Histogramm unserer Ergebnisse. Je nach der Anzahl der Aufnahmen, die Sie für die Schaltung in Schritt 3 gewählt haben, können Sie einen oder zwei Balken sehen, die die gemessenen Zustände der beiden Qubits in jeder Aufnahme darstellen. Wie immer bei Qiskit und in diesem Notizbuch verwenden wir die "Little Endian"-Notation, d.h. die Zustände der Qubits 0 bis n werden in aufsteigender Reihenfolge von rechts nach links geschrieben, wobei Qubit 0 immer am weitesten rechts steht.

Da sich Qubit 0 in einem Superpositionszustand befand, wertete die Schaltung die Funktion sowohl für $x=0$ als auch $x=1$ gleichzeitig aus – etwas, was klassische Computer nicht können! Der Haken an der Sache ist jedoch, dass wir etwas über die Funktion $f(x)$ erfahren wollen - wenn wir die Qubits messen, kollabieren wir ihren Zustand. Wenn Sie "Schüsse = 1" wählen, um die Schaltung nur einmal auszuführen, sehen Sie nur einen Balken im obigen Histogramm, und Ihre Informationen über die Funktion sind unvollständig.

Überprüfen Sie Ihr Verständnis

Wie oft müssen wir den obigen Algorithmus ausführen, um die Funktion $f(x)$ zu lernen? Ist dies besser als der klassische Fall? Hätten Sie lieber einen klassischen oder einen Quantencomputer, um dieses Problem zu lösen?

Da die Messung die Überlagerung kollabieren lässt und nur einen Wert liefert, müssen wir die Schaltung mindestens zweimal ausführen, um beide Ausgänge der Funktion $f(0)$ und $f(1)$ zu erhalten. Im besten Fall funktioniert dies genauso gut wie im klassischen Fall, bei dem wir in den ersten beiden Abfragen sowohl $f(0)$ als auch $f(1)$ berechnen. Es besteht jedoch die Möglichkeit, dass wir den Test mehr als zweimal durchführen müssen, da die endgültige Messung probabilistisch ist und bei den ersten beiden Malen denselben Wert $f(x)$ ergeben könnte. Ich würde in diesem Fall lieber einen klassischen Computer haben.

Obwohl die Quantenparallelität bei richtiger Anwendung sehr leistungsfähig sein kann, ist es nicht richtig zu sagen, dass ein Quantencomputer wie ein massiver klassischer Parallelprozessor funktioniert. Durch den Akt der Messung werden die Quantenzustände kollabiert, so dass wir immer nur auf ein einziges Ergebnis der Berechnung zugreifen können.

Deutschs Algorithmus

Die Quantenparallelität allein verschafft uns zwar keinen Vorteil gegenüber klassischen Computern, aber wir können sie mit einem anderen Quantenphänomen, der Interferenz, kombinieren, um eine höhere Geschwindigkeit zu erreichen. Der heute als "Deutsch'scher Algorithmus" bekannte Algorithmus ist das erste Beispiel für einen Algorithmus, dem dies gelingt.

Das Problem

Hier lag das Problem:

Bei einem Eingabebit $x = \{0,1\}$ und einer Eingabefunktion $f(x) = \{0,1\}$ ist zu bestimmen, ob die Funktion ausgeglichen oder konstant ist. Das heißt, wenn sie ausgeglichen ist, dann ist die Ausgabe der Funktion die Hälfte der Zeit 0 und die andere Hälfte der Zeit 1. Wenn sie konstant ist, ist die Ausgabe der Funktion entweder immer 0 oder immer 1. Erinnern Sie sich an die Tabelle der vier möglichen Funktionen, die ein einzelnes Bit in ein anderes einzelnes Bit umwandeln:

$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)$ , ausgeglichen sind.

Der Algorithmus

Deutsch näherte sich diesem Problem mit Hilfe des "Abfragemodells" Im Abfragemodell ist die Eingabefunktion ( $f_i(x)$ oben) in einer "Blackbox" enthalten - wir haben keinen direkten Zugriff auf ihren Inhalt, aber wir können die Blackbox abfragen und erhalten die Ausgabe der Funktion. Wir sagen manchmal, dass ein "Orakel" diese Informationen liefert. Siehe Lektion 1: Quantenabfragealgorithmen des Kurses Grundlagen der Quantenalgorithmen für weitere Informationen über das 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 Blackbox stellen müssen. Im klassischen Fall müsste man, um zu wissen, ob die in der Blackbox enthaltene Funktion ausgeglichen oder konstant ist, die Box zweimal abfragen, um sowohl $f(0)$ als auch $f(1)$ zu erhalten.

In Deutschs Quantenalgorithmus hat er jedoch einen Weg gefunden, die Informationen mit nur einer Abfrage zu erhalten! Er nahm eine Anpassung an der obigen "Quantenparallelität"-Schaltung vor, so dass er einen Überlagerungszustand auf beiden Qubits vorbereitete, anstatt nur auf Qubit 0. Die beiden Ausgänge der Funktion, $f(0)$ und $f(1)$ , gaben 0 zurück, wenn sie entweder beide 0 oder beide 1 waren (die Funktion war konstant), und gaben 1 zurück, wenn sie unterschiedlich waren (die Funktion war ausgeglichen). Auf diese Weise konnte Deutsch mit einer einzigen Abfrage zwischen einer konstanten und einer ausgeglichenen Funktion unterscheiden.

Hier ist ein Schaltplan von Deutschs Algorithmus:

Schaltplan des Deutsch'schen Algorithmus

Um zu verstehen, wie dieser Algorithmus funktioniert, betrachten wir die Quantenzustände der Qubits an den drei im obigen Diagramm angegebenen Punkten. Versuchen Sie, die Staaten selbst herauszufinden, bevor Sie die Antworten anklicken:

Überprüfen Sie Ihr Verständnis

Wie lautet die Adresse $|\pi_1\rangle$ ?

Die Anwendung einer Hadamard-Transformation verwandelt den Zustand $|0\rangle$ in $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ und den Zustand $|1\rangle$ in $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ . Der vollständige Zustand wird also: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

Wie lautet die Adresse $|\pi_2\rangle$ ?

Bevor wir $U_f$ anwenden, sollten wir uns daran erinnern, was es bewirkt. Es ändert den Zustand von Qubit 1 in Abhängigkeit vom Zustand von Qubit 0. Es ist also sinnvoll, den Zustand von Qubit 0 herauszurechnen: $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$ . Wenn $f(0)=f(1)$ , dann transformieren sich die beiden Terme auf die gleiche Weise und das relative Vorzeichen zwischen den beiden Termen bleibt positiv, aber wenn $f(0)\neq f(1)$ , dann bedeutet das, dass der zweite Term ein negatives Vorzeichen gegenüber dem ersten Term annimmt und den Zustand des Qubits 0 von $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ auf $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ ändert:
$|\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}$

Wie lautet die Adresse $|\pi_3\rangle$ ?

Der Zustand von Qubit 0 ist nun entweder $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ oder $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$ , je nach Funktion. Die Anwendung der Hadamard-Methode ergibt entweder $|0\rangle$ oder $|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 Sie Ihre Antworten auf die obigen Fragen durchgehen, stellen Sie fest, dass etwas Überraschendes passiert. Obwohl $U_f$ nichts explizit mit dem Zustand von Qubit 0 macht, weil es Qubit 1 basierend auf dem Zustand von Qubit 0 verändert, kann es passieren, dass dies eine Phasenverschiebung in Qubit 0 verursacht. Dies ist als „Phase-Kickback“-Phänomen bekannt und wird in Lektion 1: Quantenabfragealgorithmen des Kurses „Grundlagen der Quantenalgorithmen“ ausführlicher behandelt.

Da wir nun wissen, wie dieser Algorithmus funktioniert, wollen wir ihn mit Qiskit implementieren.

## 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
    # you may edit the number (1-4) inside "twobit_function()" to select among the four valid functions
).to_gate()
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")

Output:

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

Output:

{'1': 1}
balanced

Der Deutsch-Jozsa-Algorithmus

Deutschs Algorithmus war ein wichtiger erster Schritt, um zu zeigen, wie ein Quantencomputer effizienter sein könnte als ein klassischer Computer, aber er war nur eine bescheidene Verbesserung: Er erforderte nur eine Abfrage, im Vergleich zu zwei im klassischen Fall. Im Jahr 1992 erweiterten Deutsch und sein Kollege Richard Jozsa den ursprünglichen Zwei-Qubit-Algorithmus auf weitere Qubits. Die Aufgabe blieb dieselbe: Bestimmen, ob eine Funktion ausgeglichen oder konstant ist. Aber diesmal geht die Funktion von $n$ Bits auf ein einziges Bit über. Entweder gibt die Funktion gleich oft 0 und 1 zurück (sie ist ausgeglichen ) oder die Funktion gibt immer 1 oder immer 0 zurück (sie ist konstant ).

Hier ist ein Schaltplan für den Algorithmus:

Dieser Algorithmus funktioniert auf die gleiche Weise wie der Algorithmus von Deutsch: Mit dem Phasen-Kickback kann man den Zustand von Qubit 0 auslesen, um festzustellen, ob die Funktion konstant oder ausgeglichen ist. Es ist etwas schwieriger zu sehen als im Fall des Deutsch'schen Algorithmus mit zwei Qubits, da die Zustände Summen über die $n$ Qubits enthalten, und daher wird die Berechnung dieser Zustände als optionale Übung am Ende des Moduls angeboten. Der Algorithmus gibt einen Bitstring mit allen 0en zurück, wenn die Funktion konstant ist, und einen Bitstring mit mindestens einer 1, wenn die Funktion ausgeglichen ist.

Um zu sehen, wie der Algorithmus in Qiskit funktioniert, müssen wir zunächst unser Orakel erzeugen: die Zufallsfunktion, die garantiert entweder konstant oder ausgeglichen ist. Der folgende Code erzeugt in 50 % der Fälle eine ausgeglichene Funktion und in 50 % der Fälle eine konstante Funktion. Machen Sie sich keine Sorgen, wenn Sie dem Code nicht ganz folgen können - er ist kompliziert und für unser Verständnis des Quantenalgorithmus nicht notwendig.

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

Output:

Dies ist die Orakelfunktion, die entweder ausgeglichen oder konstant ist. Kannst du erkennen, ob die Ausgabe auf dem letzten Qubit von den Werten abhängt, die für die ersten $n$ Qubits eingegeben wurden? Wenn die Ausgabe für das letzte Qubit von den ersten $n$ Qubits abhängt, kann man dann feststellen, ob diese abhängige Ausgabe ausgeglichen ist oder nicht?

Anhand der obigen Schaltung können wir erkennen, ob die Funktion ausgeglichen oder konstant ist, aber denken Sie daran, dass wir diese Funktion für dieses Problem als "Black Box" betrachten Wir können nicht in die Schachtel schauen, um uns den Schaltplan anzuschauen. Stattdessen müssen wir die Box abfragen.

Um die Box abzufragen, verwenden wir den Deutsch-Jozsa-Algorithmus und bestimmen, ob die Funktion konstant oder ausgeglichen 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")

Output:

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

Output:

# 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.

Output:

{'110': 1}
balanced

Die erste Zeile der Ausgabe oben ist die Bitfolge der Messergebnisse. Die zweite Zeile gibt aus, ob die Bitfolge impliziert, dass die Funktion ausgeglichen oder konstant war. Enthielt die Bitfolge nur Nullen, so war sie konstant, andernfalls war sie ausgeglichen. Mit nur einem einzigen Durchlauf der obigen Quantenschaltung können wir also feststellen, ob die Funktion konstant oder ausgeglichen ist!

Überprüfen Sie Ihr Verständnis

Wie viele Abfragen bräuchte ein klassischer Computer, um mit 100%iger Sicherheit festzustellen, ob eine Funktion konstant oder ausgeglichen ist? Denken Sie daran, dass eine einzelne Abfrage klassischerweise nur die Anwendung der Funktion auf einen einzigen Bitstring erlaubt.

Es gibt $2^n$ mögliche Bitstrings, die zu prüfen sind, und im schlimmsten Fall müssten Sie $2^n/2+1$ davon testen. Wäre die Funktion beispielsweise konstant und man würde immer wieder "1" als Ausgabe der Funktion messen, könnte man nicht sicher sein, dass sie wirklich konstant ist, bis man mehr als die Hälfte der Ergebnisse überprüft hat. Davor hatte man vielleicht einfach nur Pech, wenn man bei einer ausgeglichenen Funktion immer wieder eine "1" gemessen hat. Es ist, als ob man eine Münze immer wieder wirft und sie jedes Mal Kopf zeigt. Es ist unwahrscheinlich, aber nicht unmöglich.

Wie würde sich Ihre obige Antwort ändern, wenn Sie einfach nur so lange messen müssten, bis ein Ergebnis (ausgeglichen oder konstant) wahrscheinlicher ist als das andere? Wie viele Abfragen wären in diesem Fall erforderlich?

In diesem Fall könnten Sie einfach zweimal messen. Wenn die beiden Messungen unterschiedlich sind, wissen Sie, dass die Funktion ausgeglichen ist. Wenn die beiden Messungen gleich sind, könnte es sich um ein Gleichgewicht oder eine Konstante handeln. Die Wahrscheinlichkeit, dass sie mit dieser Messreihe ausgeglichen ist, ist: $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$ . Das ist weniger als 1/2, also ist es wahrscheinlicher, dass die Funktion in diesem Fall konstant ist.

Der Deutsch-Jozsa-Algorithmus zeigte also einen exponentiellen Geschwindigkeitszuwachs gegenüber einem deterministischen klassischen Algorithmus (der die Antwort mit 100%iger Sicherheit liefert), aber keinen signifikanten Geschwindigkeitszuwachs gegenüber einem probabilistischen Algorithmus (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 als das Deutsch-Jozsa-Problem zu lösen. Anstatt einfach zu versuchen, zwischen zwei verschiedenen Klassen von Funktionen zu unterscheiden, wie im D-J-Fall, verwendeten Bernstein und Vazirani den Deutsch-Jozsa-Algorithmus, um tatsächlich eine in einer Funktion kodierte Zeichenfolge zu lernen. Hier ist das Problem:

Die Funktion $f:\{0,1\}^n \rightarrow \{0,1\}$ nimmt immer noch eine $n$ -Bit-Zeichenkette und gibt ein einzelnes Bit aus. Aber anstatt zu versprechen, dass die Funktion ausgeglichen oder konstant ist, wird uns jetzt versprochen, dass die Funktion das Punktprodukt zwischen der Eingabezeichenfolge $x$ und einer geheimen $n$ -Bitzeichenfolge $s$ ist, modulo 2. (Dieses Punktprodukt modulo 2 wird als "binäres Punktprodukt" bezeichnet.) Das Problem besteht darin, herauszufinden, wie die geheime $n$ -Bit-Zeichenkette lautet.

Anders ausgedrückt: Wir haben eine Blackbox-Funktion $f: {0,1}^n \rightarrow {0,1}$ , die $f(x) = s \cdot x$ für eine Zeichenkette $s$ erfüllt, und wir wollen die Zeichenkette $s$ lernen.

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

Zunächst wird ein Hadamard-Gatter auf die $n$ -Eingangs-Qubits angewandt, und ein NICHT-Gatter plus ein Hadamard-Gatter wird auf das Ausgangs-Qubit angewandt, wodurch der Zustand hergestellt 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 eine Summe über alle $2^n$ der $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 Einzelheiten)

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

Als nächstes wird das $U_f$ Gate auf die Qubits angewendet. Dieses Gatter nimmt die ersten n Qubits als Eingabe (die sich nun in einer gleichwertigen Überlagerung aller möglichen n-Bit-Zeichenketten befinden) und wendet die Funktion $f(x)=s \cdot x$ auf das Ausgangs-Qubit an, so dass sich dieses Qubit nun im Zustand: $|- \oplus f(x)\rangle$ befindet. Dank des Phase-Kickback-Mechanismus bleibt der Zustand dieses Qubits unverändert, aber einige der Terme im Zustand des Eingangsqubits erhalten ein Minuszeichen:

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

Nun wird der nächste Satz von Hadamards auf die Qubits 0 bis $n-1$ angewendet. Die Minuszeichen im Auge zu behalten, kann in diesem Fall knifflig sein. Es ist hilfreich zu wissen, dass die Anwendung einer Hadamard-Schicht auf $n$ Qubits in einem Standard-Basiszustand $|x\rangle$ wie folgt geschrieben werden kann:

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

So wird der Zustand:

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

Der nächste Schritt besteht darin, die ersten $n$ Bits zu messen. Aber was werden wir messen? Es stellt sich heraus, dass der obige Zustand zu vereinfachen: $|\Psi\rangle = |-\rangle \otimes |s\rangle$ , aber das ist alles andere als offensichtlich. Wenn Sie sich mit den mathematischen Grundlagen befassen möchten, lesen Sie den Kurs Grundlagen der Quantenalgorithmen von John Watrous. Der Punkt ist jedoch, dass der Mechanismus der Phasenrückkopplung dazu führt, dass sich die Eingabe-Qubits im Zustand $|s\rangle$ befinden. Um also herauszufinden, was der geheime String $s$ war, muss man einfach die Qubits messen!

Überprüfen Sie Ihr Verständnis

Überprüfen Sie, ob der Zustand aus Schritt 3 oben tatsächlich der Zustand $|s\rangle$ für den Sonderfall $n=1$ ist.

Wenn Sie die beiden Summen explizit ausschreiben, sollten Sie einen Zustand mit vier Termen erhalten (lassen wir dafür den Ausgangszustand $|-\rangle$ 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, so dass wir $|\Psi\rangle = |0\rangle$ erhalten. Wenn $s=1$ , dann addieren sich die letzten beiden Terme konstruktiv und die ersten beiden Terme heben sich auf, so dass wir $|\Psi\rangle = |1\rangle$ erhalten. In beiden Fällen also $|\Psi\rangle = |s\rangle$ . Ich hoffe, dieser einfachste Fall gibt Ihnen einen Eindruck davon, wie der allgemeine Fall mit $n$ Qubits funktioniert: alle Terme, die nicht $|s\rangle$ sind, interferieren, so dass nur der Zustand $|s\rangle$ übrig bleibt.

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

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 (liefert immer 0 für jede Zeichenkette x). Ist s eine beliebige andere Zeichenkette, so ist die Funktion ausgeglichen. Die Anwendung des Deutsch-Jozsa-Algorithmus auf eine dieser Funktionen löst also beide Probleme gleichzeitig! Es gibt die Zeichenkette zurück, und wenn diese Zeichenkette 00...00 ist, dann wissen wir, dass sie konstant ist; wenn es mindestens eine "1" in der Zeichenkette gibt, dann wissen wir, dass sie ausgeglichen ist.

Wir können auch überprüfen, dass dieser Algorithmus das Bernstein-Vazirani-Problem erfolgreich löst, indem wir ihn experimentell testen. Zunächst erstellen wir die B-V-Funktion, die sich in der Blackbox befindet:

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

Output:

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

Output:

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

Output:

{'0000': 1}

Mit einer einzigen Abfrage liefert der Deutsch-Jozsa-Algorithmus also die in der Funktion $s$ verwendete Zeichenkette: $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 das gleiche Problem zu lösen.

Fazit

Wir hoffen, dass wir Ihnen durch die Untersuchung dieser einfachen Beispiele ein besseres Verständnis dafür vermitteln konnten, wie Quantencomputer Überlagerung, Verschränkung und Interferenz nutzen können, um ihre Leistungsfähigkeit gegenüber klassischen Computern zu steigern.

Der Deutsch-Jozsa-Algorithmus ist von großer historischer Bedeutung, da er als erster einen Geschwindigkeitszuwachs gegenüber einem klassischen Algorithmus nachweisen konnte, allerdings nur einen polynomiellen. 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 diesen als Grundlage für ein komplizierteres, rekursives Problem, das so genannte rekursive Fourier-Sampling-Problem. Ihre Lösung bot eine super-polynomielle Beschleunigung gegenüber klassischen Algorithmen. Und noch vor Bernstein und Vazirani hatte Peter Shor seinen berühmten Algorithmus entwickelt, der es Quantencomputern ermöglichte, große Zahlen exponentiell schneller zu faktorisieren als jeder klassische Algorithmus es könnte. Diese Ergebnisse zeigten das aufregende Versprechen zukünftiger Quantencomputer und spornten Physiker und Ingenieure an, diese Zukunft Wirklichkeit werden zu lassen.

Fragen

Lehrkräfte können Versionen dieser Hefte mit Antwortschlüsseln und Hinweisen zur Einordnung in gängige Lehrpläne anfordern, indem sie diese kurze Umfrage zur Verwendung der Hefte ausfüllen.

Kritische Konzepte

der Deutsch- und der Deutsch-Jozsa-Algorithmus nutzen die Quantenparallelität in Verbindung mit Interferenz, um eine Antwort auf ein Problem schneller zu finden als ein klassischer Computer.
der Phasenrückstoß-Mechanismus ist ein kontraintuitives Quantenphänomen, bei dem Operationen auf einem Qubit auf die Phase eines anderen Qubits übertragen werden. Die Algorithmen Deutsch und Deutsch-Jozsa 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, das so genannte Bernstein-Vazirani-Problem, angewendet werden, um eine versteckte Zeichenkette zu finden, die in einer Funktion kodiert ist.

True/false

T/F Der Deutsch-Algorithmus ist ein Spezialfall des Deutsch-Jozsa-Algorithmus, bei dem die Eingabe ein einzelnes Qubit ist.
T/F Die Algorithmen Deutsch und Deutsch-Jozsa nutzen Quantenüberlagerung und Interferenz, um ihre Effizienz zu erreichen.
T/F Der Deutsch-Jozsa-Algorithmus erfordert mehrere Funktionsbewertungen, um festzustellen, ob eine Funktion konstant oder ausgeglichen ist.
T/F Der "Bernstein-Vazirani-Algorithmus" ist eigentlich dasselbe wie der Deutsch-Jozsa-Algorithmus, nur auf ein anderes Problem angewandt.
T/F Der Bernstein-Vazirani-Algorithmus kann mehrere geheime Zeichenfolgen gleichzeitig finden.

Kurze Antwort

Wie lange würde ein klassischer Algorithmus brauchen, um das Deutsch-Jozsa-Problem im schlimmsten Fall zu lösen?
Wie lange würde ein klassischer Algorithmus brauchen, um das Bernstein-Vazirani-Problem zu lösen? Welchen Geschwindigkeitszuwachs bietet der DJ-Algorithmus in diesem Fall?
Beschreiben Sie den Phase-Kickback-Mechanismus und wie er zur Lösung der Deutsch-Jozsa- und Bernstein-Vazirani-Probleme funktioniert.

Herausforderungsproblem

Der Deutsch-Jozsa-Algorithmus: Erinnern Sie sich an die obige Frage, in der Sie aufgefordert wurden, die Zwischenzustände der Qubits $\pi_1$ und $\pi_2$ des Deutsch'schen Algorithmus zu berechnen. Dasselbe gilt für die $n+1$ -Qubit-Zwischenzustände $\pi_1$ und $\pi_2$ des Deutsch-Jozsa-Algorithmus, für den speziellen Fall, dass $n=2$ . Überprüfen Sie dann, dass $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$ wiederum für den speziellen Fall, dass $n=2$ .

War diese Seite hilfreich?

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