Quanten-Fourier-Transformation

Für dieses Qiskit-in-Classrooms-Modul benötigen die Studierenden eine funktionierende Python-Umgebung mit den folgenden installierten Paketen:

• 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

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

Dieses Modul wurde getestet und benötigte 13 Sekunden QPU-Zeit. Dies ist eine Schätzung nach bestem Wissen; dein tatsächlicher Verbrauch kann abweichen.

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"numpy": "numpy", "qiskit": "qiskit", "qiskit_aer": "qiskit-aer", "qiskit_ibm_runtime": "qiskit-ibm-runtime"}
_missing = [pip for module, pip in _needed.items()
            if importlib.util.find_spec(module) is None]
# One at a time, so a package that fails to install does not block the others
for _pip in _missing:
    %pip install -q {_pip}
if not _missing:
    print("\u2713 All required packages are installed")

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

Einführung

Eine Fourier-Transformation ist ein allgegenwärtiges Werkzeug mit Anwendungen in Mathematik, Physik, Signalverarbeitung, Datenkompression und unzähligen anderen Bereichen. Eine Quanten-Version der Fourier-Transformation, treffend als Quanten-Fourier-Transformation bezeichnet, bildet die Grundlage für einige der wichtigsten Quantenalgorithmen.

Heute werden wir nach einer Wiederholung der klassischen Fourier-Transformation besprechen, wie wir die Quanten-Fourier-Transformation auf einem Quantencomputer implementieren. Anschließend werden wir eine der Anwendungen der Quanten-Fourier-Transformation in einem Algorithmus namens Phasenschätzungsalgorithmus diskutieren. Die Quanten-Phasenschätzung ist eine Subroutine in Shors berühmtem Faktorisierungsalgorithmus, der manchmal als das „Kronjuwel" des Quantencomputings bezeichnet wird. Dieses Modul führt auf ein weiteres Modul hin, das sich ganz Shors Algorithmus widmet, ist aber auch als eigenständiges Modul gedacht. Die Quanten-Fourier-Transformation ist für sich genommen ein faszinierender und nützlicher Algorithmus!

Die klassische Fourier-Transformation

Bevor wir in die Quanten-Fourier-Transformation einsteigen, erinnern wir uns zunächst an die klassische Version. Die Fourier-Transformation ist eine Methode zur Transformation von einer sogenannten „Basis" in eine andere. Du kannst dir zwei Basen als verschiedene Perspektiven desselben Problems vorstellen – beide sind gültige Wege, eine Funktion auszudrücken, aber je nach Problem kann die eine oder die andere aufschlussreicher sein. Einige Beispiele für Paare von Basen, die durch die Fourier-Transformation verbunden sind, sind Ort und Impuls sowie Zeit und Frequenz.

Schauen wir uns ein Beispiel an, wie uns die Fourier-Transformation helfen kann herauszufinden, welche Note ein Instrument spielt, basierend auf seiner Audio-Wellenform. Typischerweise sehen wir die Wellenformen in der Zeitbasis dargestellt – das heißt, die Amplitude der Welle wird als Funktion der Zeit ausgedrückt.

Wir können diese Wellenform fouriertransformieren, um von der Zeitbasis in die Frequenzbasis zu wechseln:

In der Frequenzbasis können wir deutlich einen Peak bei etwa 260 Hz erkennen. Das ist ein mittleres C!

Nun, du hättest vielleicht auch ohne Fourier-Transformation bestimmen können, dass ein mittleres C gespielt wurde, aber was ist, wenn mehrere Noten gleichzeitig gespielt werden? Dann wird die Wellenform komplizierter, wenn wir sie in der Zeitbasis darstellen:

Aber das Frequenzspektrum identifiziert klar drei Peaks:

Das war ein C-Dur-Akkord, der die Noten C, E und G spielt.

Diese Art der Fourier-Analyse kann uns helfen, die Frequenzkomponenten jedes beliebigen komplizierten Signals zu extrahieren.

Diskrete Fourier-Transformation

Die Fourier-Transformation ist für eine Vielzahl von Signalverarbeitungsanwendungen nützlich. Aber in den meisten dieser realen Anwendungen (einschließlich des Musikbeispiels, das wir oben verwendet haben) möchten wir einen diskreten Satz von $N$ Datenpunkten transformieren – keine kontinuierliche Funktion. In diesem Fall verwenden wir die diskrete Fourier-Transformation. Die diskrete Fourier-Transformation (DFT) wirkt auf einen Vektor $(x_0, ..., x_{N-1})$ und bildet ihn auf den Vektor $(y_0, ..., y_{N-1})$ gemäß der Formel ab:

$y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j\omega_N^{jk}$

wobei wir $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$ setzen. (Beachte, dass es andere Konventionen mit einem Minuszeichen im Exponenten gibt, also sei vorsichtig, wenn du die DFT anderswo siehst.) Erinnere dich, dass $e^{2\pi i \frac{jk}{N}}$ eine periodische Funktion mit der Periode $\frac{N}{k}$ ist. Durch die Multiplikation mit dieser Funktion ist die Fourier-Transformation also im Wesentlichen eine Möglichkeit, die (diskrete) Funktion $\{x_{j}\}$ in eine Linearkombination ihrer periodischen Bestandteilfunktionen zu zerlegen, jede mit der Periode $\frac{N}{k}$.

Die Quanten-Fourier-Transformation

Nun haben wir also gesehen, wie die Fourier-Transformation verwendet wird, um eine Funktion als Linearkombination eines neuen Satzes sogenannter „Basisfunktionen" darzustellen. Basistransformationen werden regelmäßig auch an Qubit-Zuständen durchgeführt. Zum Beispiel kann der Zustand eines einzelnen Qubits $|\psi\rangle$ in der Rechenbasis ausgedrückt werden als $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$, mit den Basiszuständen $|0\rangle$ und $|1\rangle$, oder in der $X$-Basis als $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ mit den Basiszuständen $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$ und $|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$. Beide sind gleichermaßen gültig, aber je nach Art des Problems, das du lösen möchtest, kann eine natürlicher sein als die andere.

Qubit-Zustände können auch in der Fourier-Basis ausgedrückt werden, wobei ein Zustand als Linearkombination der Fourier-Basiszustände $|\phi_y\rangle$ anstelle der üblichen Rechenbasis-Zustände $|x\rangle$ dargestellt wird. Dazu musst du eine Quanten-Fourier-Transformation (QFT) anwenden:

$| \phi_y \rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\omega_N^{y x} \vert x \rangle$

mit $\omega_N^{yx} = e^{\frac{2\pi i y x}{N}}$ wie oben, und $N$ ist die Anzahl der Basiszustände in deinem Quantensystem. Beachte, dass wir nun mit Qubits arbeiten: $m$ Qubits ergeben $2^m$ Basiszustände, also $N=2^m$. Hier werden die Basiszustände als einzelne Zahl $|x\rangle$ geschrieben, wobei $x$ von $0$ bis $N-1$ reicht, aber du siehst die Basiszustände möglicherweise typischerweise als $|00...00\rangle$, $|00...01\rangle$, $|00...11\rangle$, ..., $|11...11\rangle$ ausgedrückt, wobei jede Binärziffer den Zustand von Qubit 0 bis $m-1$ darstellt, von rechts nach links. Es gibt eine einfache Möglichkeit, diese Binärzustände in eine einzelne Zahl umzuwandeln: behandle sie einfach wie Binärzahlen! Also ist $|00...00\rangle = |0\rangle$, $|00...01\rangle = |1\rangle$, $|00...10\rangle = |2\rangle$, $|00...11\rangle = |3\rangle$, und so weiter, bis hin zu $|11...11\rangle = |2^m -1\rangle = |N-1\rangle$.

Intuition für die Fourier-Basiszustände aufbauen

Wir haben also gerade besprochen, was die Rechenbasis-Zustände sind und wie sie geordnet werden: Sie sind die Menge der Zustände, bei denen jedes Qubit entweder in $0$ oder $1$ ist, und wir ordnen sie vom Zustand, in dem alle Qubits $0$ sind, $|00...00\rangle$, bis zum Zustand, in dem alle $1$ sind, $|11...11\rangle$.

Aber wie können wir die Fourier-Basiszustände verstehen? Alle Fourier-Basiszustände sind gleichmäßige Überlagerungen aller Rechenbasis-Zustände, aber jeder Zustand unterscheidet sich von den anderen in der Periodizität der Phase der Komponenten. Um dies konkreter zu verstehen, schauen wir uns die vier Fourier-Basiszustände eines Zwei-Qubit-Systems an. Der niedrigste Fourier-Zustand ist einer, dessen Phase überhaupt nicht variiert:

$|\phi_0\rangle = \frac{1}{2} (|00\rangle + |01\rangle + |10\rangle + |11\rangle)$

Wir können diesen Zustand visualisieren, indem wir die komplexe Amplitude jedes Terms auftragen. Die rote Linie führt das Auge und zeigt dir, wie die Phase dieser Amplitude in der komplexen Ebene als Funktion des Rechenbasis-Zustands umläuft. Für $|\phi_0\rangle$ bleibt die Phase konstant:

Der nächste Fourier-Basiszustand ist derjenige, dessen Komponentenphasen genau einmal von $0$ bis $2\pi$ umlaufen:

$|\phi_1\rangle = \frac{1}{2} (|00\rangle + e^{i\pi/2}|01\rangle + e^{i\pi}|10\rangle + e^{3i\pi/2}|11\rangle) = \frac{1}{2}(|00\rangle + i|01\rangle - |10\rangle - i|11\rangle)$

Und wir können dieses Umlaufen im Diagramm der komplexen Amplitude gegenüber dem Rechenbasis-Zustand sehen:

Jeder Zustand hat also eine Phase, die $2\pi/4$ Radiant höher ist als der vorherige Zustand, wenn sie in der Standardreihenfolge angeordnet werden, da wir in diesem Beispiel vier Basiszustände haben ($N=4$). Der nächste Basiszustand läuft zweimal von 0 bis 2$\pi$ um:

$|\phi_2\rangle = \frac{1}{2} (|00\rangle + e^{i\pi}|01\rangle + e^{2i\pi}|10\rangle + e^{3i\pi}|11\rangle) = \frac{1}{2} (|00\rangle - |01\rangle + |10\rangle - |11\rangle)$

Schließlich ist die höchste Fourier-Komponente diejenige mit der am schnellsten variierenden Phase. Für unser Beispiel mit zwei Qubits ist es diejenige, deren Phasen dreimal von 0 bis $2\pi$ umlaufen:

$|\phi_3\rangle = \frac{1}{2} (|00\rangle + e^{3i\pi/2}|01\rangle + e^{6i\pi/2}|10\rangle + e^{9i\pi/2}|11\rangle) = \frac{1}{2} (|00\rangle - i|01\rangle - |10\rangle + i|11\rangle)$

Im Allgemeinen gibt es für einen $m$-Qubit-Zustand $2^m$ Fourier-Basiszustände, deren Frequenz in der Phasenvariation von konstant für $|\phi_0\rangle$ bis schnell variierend für $|\phi_{2^m-1}\rangle$ reicht, wobei $2^m-1$ Umläufe um $2\pi$ über die Superposition der Zustände vollendet werden. Wenn wir also eine QFT eines Quantenzustands durchführen, machen wir im Wesentlichen die gleiche grundlegende Analyse, die wir für die musikalische Wellenform in der Einführung gemacht haben. Wir bestimmen die Fourier-Frequenzkomponenten, die zur Erzeugung des betrachteten Quantenzustands beitragen.

Einige Beispiel-QFTs ausprobieren

Versuchen wir, unsere Intuition für die Quanten-Fourier-Transformation weiter aufzubauen, indem wir einen Zustand in der Rechenbasis erstellen und dann schauen, was passiert, wenn wir die QFT darauf anwenden. Vorerst werden wir die QFT einfach als Black Box behandeln, die wir mit dem QFTGate aus der Qiskit Circuit Library anwenden. Später werden wir uns detailliert mit ihrer Implementierung befassen.

Wir beginnen mit dem Laden der notwendigen Pakete und der Auswahl eines Geräts, auf dem wir unseren Circuit ausführen:

import numpy as np
from qiskit import QuantumCircuit
from qiskit.visualization import plot_histogram
from qiskit.circuit.library import QFTGate

# 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

service = QiskitRuntimeService()

# Use the least busy backend
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_pinguino2")

print(backend.name)

ibm_pinguino2

Wenn du keine verfügbare Zeit auf deinem Konto hast oder aus irgendeinem Grund einen Simulator verwenden möchtest, kannst du die folgende Zelle ausführen, um einen Simulator einzurichten, der das oben ausgewählte Quantengerät nachahmt:

# 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

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)

# Alternatively, load a fake backend with generic properties and define a simulator.
from qiskit.providers.fake_provider import GenericBackendV2

backend_gen = GenericBackendV2(num_qubits=18)
sampler_gen = BackendSamplerV2(backend=backend_gen)

Einzelner Rechenbasis-Zustand

Zuerst versuchen wir, einen einzelnen Rechenbasis-Zustand zu transformieren. Wir beginnen mit der Erstellung eines zufälligen Rechenbasis-Zustands:

# Step 1: Map

qubits = 4
N = 2**qubits

qc = QuantumCircuit(qubits)

# flip state of random qubits to put in a random single computational basis state
for i in range(1, qubits):
    if np.random.randint(0, 2):
        qc.x(i)

# make a copy of the above circuit. (to be used when we apply the QFT in next part)
qc_qft = qc.copy()

qc.measure_all()
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 OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

Jetzt transformieren wir diesen Zustand mit QFTGate mittels Fourier-Transformation:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.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_qft)

# Step 3: Run the job on a real quantum computer - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

Wie du sehen kannst, messen wir die Besetzungen jedes Zustands als mehr oder weniger gleich, mit kleinen Abweichungen durch experimentelles und statistisches Rauschen. Wenn du also die QFT eines einzelnen Rechenbasis-Zustands nimmst, ist das Ergebnis eine gleichmäßige Überlagerung aller Zustände. Wenn du mit Fourier-Transformationen vertraut bist, überrascht dich das wahrscheinlich nicht. Ein grundlegendes Prinzip, das uns helfen kann, eine intuitive Verbindung zwischen einer Funktion und ihrer Fourier-Transformation herzustellen, ist, dass die Breite einer Funktion umgekehrt proportional zur Breite ihrer Fourier-Transformation ist. Etwas, das in der Zeit sehr lokalisiert ist, wie zum Beispiel ein sehr kurzer Puls, benötigt also einen breiten Bereich von Frequenzen, um diesen Puls zu erzeugen. Dieses Signal wird im Fourier-Raum sehr breit sein.

Diese Tatsache hängt tatsächlich mit der quantenmechanischen Unschärfe zusammen! Heisenbergs Unschärferelation wird typischerweise als $\Delta x \Delta p \ge \hbar / 2$ formuliert. Wenn also die Ortsunschärfe ($\Delta x$) klein ist, muss die Impulsunschärfe ($\Delta p$) groß sein, und umgekehrt. Es stellt sich heraus, dass die Transformation von der Ortsbasis $x$ zur Impulsbasis $p$ durch eine Fourier-Transformation bewerkstelligt wird.

Hinweis: Bedenke, dass wir Besetzungen in jedem der Basiszustände messen, sodass wir Informationen über die relativen Phasen zwischen den verschiedenen Teilen der Überlagerung verlieren. Während also die QFT jedes einzelnen Rechenbasis-Zustands die gleiche gleichmäßige Verteilung der Besetzung über alle Basiszustände ergibt, werden die Phasen nicht notwendigerweise gleich sein.

Zwei Rechenbasis-Zustände

Nun schauen wir, was passiert, wenn wir eine Überlagerung von Rechenbasis-Zuständen präparieren. Was denkst du, wie die Fourier-Transformation in diesem Fall aussehen wird?

Wählen wir die Überlagerung:

$|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle) = \frac{1}{\sqrt{2}} (|000...0\rangle + |100...0\rangle)$

# Step 1: Map
qubits = 4
N = 2**qubits

qc = QuantumCircuit(qubits)

# To make this state, we just need to apply a Hadamard to the last qubit

qc.h(qubits - 1)

qc_qft = qc.copy()

qc.measure_all()

qc.draw("mpl")

# First, let's go through steps 2-4 for the first circuit, qc

# 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 - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

Jetzt transformieren wir diesen Zustand mit QFTGate mittels Fourier-Transformation:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.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_qft)

# Step 3: Run the job on a real quantum computer OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

Das hier könnte etwas überraschender sein. Es sieht so aus, als wäre die QFT des Zustands $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ eine Überlagerung aller geraden Basiszustände. Aber wenn wir an unsere Visualisierung jedes Basiszustands $|\phi_y\rangle$ zurückdenken und daran, wie die Phase jeder Komponente $y$ Mal um $2\pi$ umläuft, dann könnte der Grund für dieses Ergebnis klar werden.

Überprüfe dein Verständnis

Erkläre anhand des obigen Hinweises, warum das Ergebnis, das wir für die QFT von $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ erhalten haben, zu erwarten ist.

Answer

Der ursprüngliche Zustand hat eine relative Phase von 0 (oder einem ganzzahligen Vielfachen von $2\pi$) zwischen den beiden Teilen der Überlagerung. Wir wissen also, dass dieser Zustand Fourier-Komponenten hat, deren Phasen ebenfalls auf diese Weise übereinstimmen: diejenigen, die eine Phasenverschiebung von 0 zwischen dem |0000>-Term und dem |1000>-Term aufweisen. Jeder Fourier-Basiszustand $|\phi_y\rangle$ besteht aus Termen, deren Phase mit einer Rate von $2\pi y/N$ akkumuliert, was bedeutet, dass in der üblichen Reihenfolge jeder Term in der Überlagerung eine Phase von $2\pi y/N$ mehr hat als der vorherige Term. Am Halbierungspunkt $N/2$ soll also die Phase $2\pi y/N * N/2$ ein ganzzahliges Vielfaches von $2\pi$ sein. Das passiert, wenn $y$ gerade ist.

Welche Rechenbasis-Zustandsüberlagerung würde einer QFT mit Peaks auf jeder ungeraden Binärzahl entsprechen?

Answer

Wenn du die QFT des Zustands $\psi = |0\rangle - |N/2\rangle$ nehmen würdest, dann würdest du Peaks auf jedem ungeraden binärnummerierten Zustand sehen.

Den QFT-Algorithmus aufschlüsseln

Nachdem wir nun mehr Intuition für die Beziehung zwischen Qubit-Zuständen in der Rechenbasis und der Fourier-Basis gewonnen haben, schauen wir uns den QFT-Algorithmus selbst an. Mit anderen Worten: Welche Gates implementieren wir tatsächlich auf dem Quantencomputer, um diese Transformation zu erreichen?

Fangen wir klein an, mit einem einzelnen Qubit. Das bedeutet, wir haben zwei Basiszustände. QFT$_2$ transformiert die Rechenbasis-Zustände $|0\rangle$ und $|1\rangle$ in die Fourier-Basiszustände $\phi_0$ und $\phi_1$:

$|\phi_0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$|\phi_1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

Überprüfe dein Verständnis

Verwende die Gleichung für die QFT aus dem vorherigen Abschnitt, um die beiden obigen Fourier-Basiszustände zu verifizieren.

Answer

Die allgemeine QFT-Formel lautet:

$| \phi_y \rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\omega_N^{y x} \vert x \rangle$

Für ein einzelnes Qubit ($n=1$) ist $N=2^n=2$ und $\omega_N^{xy} = e^{2\pi i \frac {y x}{2}}$. Wir erhalten also

$| \phi_0 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {0 \times 0}{2}}|0\rangle + e^{2\pi i \frac {0 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$| \phi_1 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {1 \times 0}{2}}|0\rangle + e^{2\pi i \frac {1 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

Schau dir diese beiden Gleichungen an. Du kennst vielleicht schon ein Quantengatter, das zur Implementierung dieser Transformation verwendet werden kann. Es gibt nämlich ein Gate, das die Rechenbasis-Zustände $|0\rangle$ und $|1\rangle$ in die jeweiligen Fourier-Basiszustände $|\phi_0\rangle$ und $|\phi_1\rangle$ transformiert. Es ist ein Hadamard-Gate! Das wird noch deutlicher, wenn wir eine Matrixdarstellung der QFT$_N$-Operation einführen:

$\text{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} \omega_N^{xy} \vert x \rangle \langle y \vert$

Falls du mit dieser Notation zur Darstellung eines Quantenoperators nicht vertraut bist, ist das kein Problem! Es ist eine Möglichkeit, eine $N \times N$-Matrix darzustellen, wobei $x$ und $y$ die Spalten und Zeilen der Matrix indexieren, von $0$ bis $N-1$, und $\omega_N^{xy}$ der Wert des jeweiligen Eintrags ist. Der Eintrag in der 0-ten Spalte und 2-ten Zeile wäre beispielsweise einfach $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$.

In dieser Darstellung wird jeder der Rechenbasis-Zustände einem der Basisvektoren zugeordnet:

$$\begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}, |1\rangle = \begin{pmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{pmatrix}, |N-1\rangle = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{pmatrix}.$$

Wenn du mehr über diese Darstellung erfahren möchtest, siehe John Watrous' Lektion über mehrere Systeme im Kurs Grundlagen der Quanteninformation.

Versuchen wir, die Matrix für QFT$_4$ zu konstruieren. Mit der obigen Formel finden wir, dass

\text\{QFT\}_4 = \frac\{1\}\{2\} \begin\{pmatrix\} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end\{pmatrix\}

Um diese Matrix auf einem Quantencomputer zu implementieren, müssen wir herausfinden, welche Kombination von Gates, angewendet auf welche Qubits, uns eine unitäre Transformation ergibt, die der obigen Matrix entspricht. Wir wissen bereits, dass eines der benötigten Gates das Hadamard ist. Ein weiteres Gate, das wir brauchen, ist das kontrollierte Phasen-Gate, das eine relative Phase $\alpha$ auf den Zustand des Ziel-Qubits anwendet, solange das Kontroll-Qubit im Zustand $|1\rangle$ ist. In Matrixform sieht das so aus:

\text\{CP\}_\alpha = \begin\{pmatrix\} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & e^\{i\alpha\} \\ \end\{pmatrix\}

Da nur der Zustand $|11\rangle$ verändert wird, spielt es eigentlich keine Rolle, welches Qubit als „Kontroll-" und welches als „Ziel-"Qubit betrachtet wird. Das Ergebnis ist in beiden Fällen dasselbe.

Schließlich brauchen wir auch einige SWAP-Gates. Ein SWAP-Gate tauscht die Zustände zweier Qubits. Es sieht so aus:

\text\{SWAP\}_\alpha = \begin\{pmatrix\} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end\{pmatrix\}

Das Verfahren zur Konstruktion eines QFT$_{2^m}$-Circuits auf $m$ Qubits ist iterativ – du wendest zuerst QFT$_{2^{m-1}}$ auf die Qubits $1$ bis $m-1$ an und fügst dann einige Gates zwischen Qubit $0$ und den anderen $m-1$ Qubits hinzu. Aber um QFT$_{2^{m-1}}$ anzuwenden, musst du zuerst QFT$_{2^{m-2}}$ auf die Qubits 2 bis $m-1$ anwenden und dann einige Gates zwischen Qubit 1 und den verbleibenden Qubits $2$ bis $m-1$ hinzufügen. Es ist wie eine russische Matroschka-Puppe: Jede Puppe fügt einen Faktor zwei in der Dimension des QFT-Circuits hinzu, wobei die kleinste Puppe ganz im Zentrum QFT$_2$ oder das Hadamard-Gate ist.

Um eine Puppe in die nächstgrößere Puppe zu setzen und damit die Dimension der QFT um den Faktor zwei zu erhöhen, folgst du immer demselben Verfahren:

1. Wende zuerst QFT$_{2^{m-1}}$ auf die untersten $m-1$ Qubits an. Das ist deine „kleinere Puppe" des russischen Matroschka-Sets, die du bald in die nächstgrößere Puppe setzen wirst.

2. Verwende das nächsthöhere Qubit als Kontrolle und wende kontrollierte Phasen-Gates auf jedes der unteren $m-1$ Qubits an, mit Phasen auf die Standardbasiszustände jedes der verbleibenden $m-1$ Qubits.

3. Führe ein Hadamard auf demselben obersten Qubit durch, das als Kontrolle in den Phasen-Gates verwendet wurde.

4. Verwende SWAP-Gates, um die Reihenfolge der Qubits zu permutieren, sodass das niedrigstwertige (obere) Bit zum höchstwertigen (unteren) Bit wird und alle anderen um eins nach oben rücken.

Wir haben bereits die QFTGate-Funktion aus der Qiskit Circuit Library verwendet, aber jetzt schauen wir in einige dieser QFT-Gates hinein, um das obige Verfahren zu verifizieren. Das können wir mit decompose() tun.

qc = QuantumCircuit(1)
qc.compose(QFTGate(1), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(2)
qc.compose(QFTGate(2), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(3)
qc.compose(QFTGate(3), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(4)
qc.compose(QFTGate(4), inplace=True)
qc.decompose().draw("mpl")

Hoffentlich kannst du anhand der ersten vier QFTs erkennen, wie jede in die nächstgrößere geschachtelt ist. Dir ist vielleicht aufgefallen, dass einige der Phasen-Gates nicht genau dem oben beschriebenen Verfahren entsprechen und die SWAPs nicht nach jeder Subroutine erscheinen, sondern nur ganz am Ende der vollständigen QFT. Das spart uns unnötige Gates, die den Circuit länger und fehleranfälliger machen würden. Anstatt den SWAP nach jeder geschachtelten Puppe zu implementieren, verfolgt der Circuit, wo sich jeder Qubit-Zustand befinden sollte, und passt die Qubits, auf die er die Phasen-Gates anwendet, entsprechend an. Dann bringt ein abschließender Satz von SWAPs am Ende alles an seinen richtigen Platz.

Die QFT anwenden: Phasenschätzung

Schauen wir, wie die QFT zur Lösung eines nützlichen Problems im Quantencomputing eingesetzt werden kann. Die Berechnung der inversen Quanten-Fourier-Transformation ist ein notwendiger Schritt in einem Algorithmus namens Quanten-Phasenschätzung (QPE), die selbst eine Subroutine in vielen anderen Algorithmen ist, einschließlich des „Kronjuwels" der Quantenalgorithmen, Shors Faktorisierungsalgorithmus.

Das Ziel der QPE ist die Schätzung der Eigenwerte eines unitären Operators. Unitäre Operatoren sind allgegenwärtig im Quantencomputing, und oft ist das Finden der Eigenwerte ihrer zugehörigen Eigenvektoren ein notwendiger Schritt in einem größeren Algorithmus. Je nach Problem kann ein Eigenwert eine Energie eines Hamiltonians in einem Simulationsproblem darstellen, kann uns helfen, Primfaktoren einer Zahl in Shors Algorithmus zu finden, oder kann andere wesentliche Informationen enthalten. QPE ist eine der wichtigsten und am weitesten verbreiteten Subroutinen im Quantencomputing.

Was hat das nun mit einer Quanten-Fourier-Transformation zu tun? Nun, wie du dich vielleicht erinnerst, hat jeder Eigenwert $\lambda$ eines unitären Operators einen Betrag $|\lambda| = 1$. Wir können also jeden Eigenwert als komplexe Zahl mit Betrag eins schreiben:

$\lambda = e^{2\pi i \theta}$

wobei $\theta$ eine reelle Zahl zwischen 0 und 1 ist. Wenn du mehr Informationen über unitäre Matrizen möchtest, siehe John Watrous' Lektion zu diesem Thema in Grundlagen der Quanteninformation.

Beachte, dass $\lambda$ periodisch in $\theta$ ist. Das könnte dir bereits nahelegen, dass eine QFT beteiligt sein könnte, da wir gesehen haben, wie nützlich QFTs für die Analyse periodischer Funktionen sind. Im Folgenden werden wir den Algorithmus durchgehen und genau sehen, wie die QFT ins Spiel kommt.

Wie QPE funktioniert

Zunächst beginnen wir mit dem einfachsten QPE-Algorithmus, der die Phase grob auf eine einzige Binärziffer Genauigkeit schätzt. Mit anderen Worten, dieser Algorithmus kann zwischen $\theta = 0$ und $\theta = 1/2$ unterscheiden, aber nicht besser. Hier ist das Schaltkreisdiagramm:

Die Qubits werden im Zustand $|\pi_0\rangle = |\psi\rangle|0\rangle$ präpariert, wobei Qubit $0$ im Zustand $|0\rangle$ ist und die verbleibenden Qubits im Zustand $|\psi\rangle$, der ein Eigenzustand von $U$ ist. Nach dem ersten Hadamard wird der Qubit-Zustand zu:

$|\pi_1\rangle = \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + |1\rangle)$

Das nächste Gate ist ein „kontrolliertes-$U$"-Gate. Dieses wendet die unitäre Operation $U$ auf die unteren Qubits an, die sich im Zustand $|\psi\rangle$ befinden, wenn Qubit 0 im Zustand $|1\rangle$ ist, tut aber nichts mit $|\psi\rangle$, wenn Qubit 0 im Zustand $|0\rangle$ ist. Dies transformiert die Qubits in den Zustand:

$|\pi_2\rangle = \frac{1}{\sqrt{2}}( |\psi\rangle|0\rangle + e^{2\pi i \theta}|\psi\rangle|1\rangle)$ $= \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + e^{2\pi i \theta}|1\rangle)$

Etwas Seltsames ist gerade passiert: Das kontrollierte-$U$-Gate verwendet Qubit $0$ nur als Kontroll-Qubit, sodass man denken könnte, dass dieses Gate den Zustand von Qubit 0 überhaupt nicht ändern würde. Aber irgendwie tut es das! Obwohl die Operation auf die unteren Qubits angewendet wurde, besteht die Gesamtwirkung des Gates darin, die Phase von Qubit $0$ zu ändern. Dies ist als „Phase-Kickback-Mechanismus" bekannt und wird in vielen Quantenalgorithmen verwendet, einschließlich Deutsch-Jozsa und Grovers Algorithmen. Wenn du mehr über den Phase-Kickback-Mechanismus erfahren möchtest, siehe John Watrous' Lektion über Quanten-Abfragealgorithmen in Grundlagen der Quantenalgorithmen.

Nach dem Phase-Kickback wenden wir noch ein Hadamard auf Qubit $0$ an, was zum Zustand führt:

$|\pi_3\rangle = |\psi\rangle ( \frac{1+e^{2\pi i \theta}}{2} |0\rangle + \frac{1 - e^{2\pi i \theta}}{2}|1\rangle) = |\psi\rangle ( \cos(\pi\theta) |0\rangle - i \sin(\pi\theta)|1\rangle)$

Wenn wir also Qubit $0$ am Ende messen, werden wir $|0\rangle$ mit 100%iger Sicherheit messen, wenn $\theta = 0$, und wir werden $|1\rangle$ mit 100%iger Sicherheit messen, wenn $\theta = \frac{1}{2}$ (und wenn unser Quantencomputer perfekt ist, ohne Rauschen). Wenn $\theta$ etwas anderes ist, ist die abschließende Messung nur probabilistisch und sagt uns nur begrenzt etwas aus.

QPE mit mehr Präzision: mehr Qubits

Wir können dieses einfache Konzept zu einem komplizierteren Algorithmus mit beliebiger Präzision erweitern. Wenn wir statt nur Qubit $0$ zum Messen der Phase $m$ Qubits $0$ bis $m-1$ verwenden, können wir die Phase mit $m$ Bit Präzision schätzen. Schauen wir, wie das funktioniert:

Dieser präzisere QPE-Circuit beginnt genauso wie die Ein-Bit-Version: Hadamards werden auf die ersten $m$ Qubits angewendet, und die verbleibenden Qubits werden im Zustand $|\psi\rangle$ präpariert, was den Zustand erzeugt:

$|\pi_1\rangle = \frac{1}{2^{m/2}}|\psi\rangle(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)...(|0\rangle+|1\rangle)$

Nun werden die kontrollierten unitären Operationen angewendet. Qubit $0$ dient als Kontroll-Qubit für dieselbe unitäre Operation $U$ wie zuvor. Aber jetzt steuert Qubit $1$ die unitäre Operation $U^2$, also einfach die zweimalige Anwendung von $U$. Der Eigenwert von $U^2$ ist also $e^{2*2\pi i \theta}$. Im Allgemeinen dient jedes Qubit $k$ von 0 bis $m-1$ als Kontroll-Qubit für die unitäre Operation $U^{2^k}$. Das bedeutet, jedes dieser Qubits erfährt einen Phase-Kickback von $e^{2^k*2\pi i \theta}$. Das ergibt den Zustand:

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} (|0\rangle+e^{2^{m-1}2\pi i \theta}|1\rangle)(|0\rangle+e^{2^{m-2}2\pi i \theta}|1\rangle)...(|0\rangle+e^{2\pi i \theta}|1\rangle)$

Das kann als Summe über die Rechenbasis-Zustände umgeschrieben werden:

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} \sum_{k=0}^{2^{m}-1} e^{2\pi i k \theta} |k\rangle$

Kommt dir die Summe bekannt vor? Es ist eine QFT! Erinnere dich an die Gleichung für eine Quanten-Fourier-Transformation:

$\text{QFT}_{2^m}| y \rangle = \frac{1}{\sqrt{2^m}}\sum_{x=0}^{2^m-1}\omega_{2^m}^{y x} \vert x \rangle$

Wenn also die Phase $\theta = y/2^m$ für eine ganze Zahl $y$ zwischen $0$ und $2^m-1$ ist, dann ergibt die inverse QFT dieses Zustands den Zustand:

$|\pi_3\rangle = |\psi\rangle \otimes |y\rangle$

und aus $|y\rangle$ können wir $\theta$ ableiten.

Wenn $\theta/2^m$ kein ganzzahliges Vielfaches ist, dann wird die inverse QFT $\theta$ nur approximieren. Wie gut sie $\theta$ approximiert, ist probabilistisch, was bedeutet, dass wir nicht immer die beste Approximation erhalten, aber sie wird ziemlich nahe sein, und je mehr Qubits $m$ du verwendest, desto besser wird die Approximation. Um zu erfahren, wie man diese Approximation von $\theta$ quantifizieren kann, schaue dir John Watrous' Lektion über Phasenschätzung und Faktorisierung in Grundlagen der Quantenalgorithmen an.

Fazit

Dieses Modul gab einen Überblick darüber, was eine QFT ist, wie sie auf einem Quantencomputer implementiert wird und wie nützlich sie bei der Lösung von Problemen sein kann. Wir haben dir einen Vorgeschmack auf ihre Nützlichkeit gegeben, als wir gesehen haben, wie sie in der Quanten-Phasenschätzung verwendet werden kann, um etwas über die Eigenwerte einer unitären Matrix zu erfahren.

Zentrale Konzepte

• Die Quanten-Fourier-Transformation ist das Quantenanalogon zur diskreten Fourier-Transformation.

• Die QFT ist ein Beispiel für eine Basistransformation.

• Das Verfahren der Quanten-Phasenschätzung beruht auf dem Phase-Kickback-Mechanismus der kontrollierten unitären Operationen sowie einer inversen QFT.

• QFT und QPE sind beide weit verbreitete Subroutinen in zahlreichen Quantenalgorithmen.

Fragen

Wahr/Falsch

1. W/F Die Quanten-Fourier-Transformation ist das Quantenanalogon der klassischen diskreten Fourier-Transformation (DFT).

2. W/F Die QFT kann nur mit Hadamard- und CNOT-Gates implementiert werden.

3. W/F Die QFT ist eine Schlüsselkomponente von Shors Algorithmus.

4. W/F Die Ausgabe der Quanten-Phasenschätzung ist ein Quantenzustand, der den Eigenvektor des Operators darstellt.

5. W/F QPE erfordert die Verwendung der inversen Quanten-Fourier-Transformation (QFT$^\dag$).

6. W/F In der QPE liefert der Algorithmus bei exakt mit $n$ Bits darstellbarer Phase $\phi$ das korrekte Ergebnis mit Wahrscheinlichkeit 1.

Kurzantworten

1. Wie viele Qubits werden benötigt, um eine QFT an einem System mit $2^n$ Datenpunkten durchzuführen?

2. Kann die QFT auf einen Zustand angewendet werden, der kein Rechenbasis-Zustand ist? Wenn ja, was passiert?

3. Wie beeinflusst die Anzahl der Kontroll-Qubits in der QPE die Auflösung der resultierenden Phasenschätzung?

Aufgaben

1. Verwende Matrixmultiplikation, um zu verifizieren, dass die Schritte im QFT-Algorithmus tatsächlich die $\text{QFT}_4$-Matrix ergeben:

$$\text{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{pmatrix}$$

(Du musst das nicht von Hand machen!)

Bonusaufgaben

1. Erstelle einen Vier-Qubit-Zustand, der eine gleichmäßige Überlagerung aller ungeraden Rechenbasen ist: $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. Führe dann eine QFT auf dem Zustand durch. Was ist der resultierende Zustand? Erkläre, warum dein Ergebnis sinnvoll ist, unter Verwendung deines Wissens über Fourier-Transformationen.