Quanten-Fourier-Transformation

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 Jobs 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 13 Sekunden QPU-Zeit. Dies ist eine Schätzung nach bestem Wissen und Gewissen; Ihr tatsächlicher Verbrauch 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'

Einführung

Die Fourier-Transformation ist ein allgegenwärtiges Werkzeug, das in der Mathematik, der Physik, der Signalverarbeitung, der Datenkompression und unzähligen anderen Bereichen Anwendung findet. Eine Quantenversion der Fourier-Transformation, treffend Quanten-Fourier-Transformation genannt, bildet die Grundlage für einige der wichtigsten Quantenalgorithmen.

Nach einer Erinnerung an die klassische Fourier-Transformation werden wir heute darüber sprechen, wie wir die Quanten-Fourier-Transformation auf einem Quantencomputer implementieren. Dann werden wir eine der Anwendungen der Quanten-Fourier-Transformation für einen Algorithmus namens Phasenschätzungsalgorithmus diskutieren. Die Quantenphasenschätzung ist eine Unterroutine in Shors berühmtem Factoring-Algorithmus, der manchmal als "Kronjuwel" der Quanteninformatik bezeichnet wird. Dieses Modul baut auf einem anderen Modul auf, das sich mit dem Shor-Algorithmus befasst, aber es ist auch als eigenständiges Modul gedacht. Die Quanten-Fourier-Transformation ist ein faszinierender und nützlicher Algorithmus für sich!

Die klassische Fourier-Transformation

Bevor wir uns mit der Quanten-Fourier-Transformation befassen, sollten wir uns zunächst an die klassische Version erinnern. Die Fourier-Transformation ist eine Methode zur Umwandlung von einer sogenannten "Basis" in eine andere. Man kann sich zwei Basen als unterschiedliche Sichtweisen desselben Problems vorstellen - beide sind gültige Möglichkeiten, eine Funktion auszudrücken, aber je nach Problemstellung ist die eine oder die andere vielleicht aufschlussreicher. Einige Beispiele für Basenpaare, die durch Fourier-Transformation verbunden sind, sind Position und Impuls sowie Zeit und Frequenz.

Anhand eines Beispiels soll gezeigt werden, wie die Fourier-Transformation uns dabei helfen kann, anhand der Audiowellenform herauszufinden, welche Note ein Instrument spielt. Normalerweise werden die Wellenformen in der Zeitbasis dargestellt, d. h. die Amplitude der Welle wird als Funktion der Zeit ausgedrückt.

Durch Fourier-Transformation können wir diese Wellenform von der Zeitbasis in die Frequenzbasis überführen:

Auf der Frequenzbasis ist eine deutliche Spitze bei etwa 260 Hz zu erkennen. Das ist ein mittleres C!

Nun hätten Sie vielleicht feststellen können, dass ein mittleres C gespielt wurde, ohne eine Fourier-Transformation zu verwenden, aber was ist, wenn mehrere Noten gleichzeitig gespielt werden? Dann wird die Wellenform komplizierter, wenn wir sie auf der Zeitbasis darstellen:

Im Frequenzspektrum sind jedoch eindeutig drei Spitzen zu erkennen:

Dies war ein C-Dur-Akkord mit den Noten C, E und G.

Diese Art der Fourier-Analyse kann uns dabei helfen, die Frequenzkomponenten von komplizierten Signalen aller Art 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) wollen wir eine diskrete Menge von $N$ Datenpunkten transformieren - nicht eine 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 gemäß der Formel auf den Vektor $(y_0, ..., y_{N-1})$ 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}}$ nehmen. (Beachten Sie, dass es auch andere Konventionen gibt, die ein Minuszeichen im Exponentialwert haben, seien Sie also vorsichtig, wenn Sie die DFT in freier Wildbahn sehen) Es sei daran erinnert, dass $e^{2\pi i \frac{jk}{N}}$ eine periodische Funktion mit der Periode $\frac{N}{k}$ ist. Durch Multiplikation mit dieser Funktion ist die Fourier-Transformation also im Wesentlichen eine Möglichkeit, die (diskrete) Funktion $\{x_{j}\}$ in eine Linearkombination ihrer einzelnen periodischen Funktionen zu zerlegen, die jeweils eine Periode $\frac{N}{k}$ haben.

Die Quanten-Fourier-Transformation

Wir haben nun gesehen, wie die Fourier-Transformation verwendet wird, um eine Funktion als Linearkombination einer neuen Gruppe von so genannten "Basisfunktionen" darzustellen Auch für Qubit-Zustände werden regelmäßig Basistransformationen durchgeführt. Der Zustand eines einzelnen Qubits $|\psi\rangle$ kann zum Beispiel in der Berechnungsbasis $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$ mit den Basiszuständen $|0\rangle$ und $|1\rangle$ oder in der Basis $X$ $|\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)$ ausgedrückt werden. Beide sind gleichermaßen gültig, aber je nach Art des Problems, das Sie zu lösen versuchen, könnte eines natürlicher sein als das 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$ ausgedrückt wird, anstatt der üblichen, rechnerischen Basiszustände, $|x\rangle$. Dazu müssen Sie eine Quanten-Fourier-Transformation (QFT) durchführen:

$| \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 Ihrem Quantensystem. Beachten Sie, dass wir jetzt mit Qubits arbeiten und $m$ Qubits Ihnen $2^m$ Basiszustände liefern, sodass $N=2^m$. Hier werden die Basiszustände als einzelne Zahl geschrieben: $|x\rangle$, wobei $x$ von $0$ bis $N-1$ reicht. Häufiger werden die Basiszustände jedoch 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$ von rechts nach links darstellt. Es gibt eine einfache Möglichkeit, diese binären Zustände in eine einzige Zahl umzuwandeln: Behandeln Sie sie einfach wie Binärzahlen! Also, $|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 entwickeln

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

Aber wie können wir die Fourier-Basiszustände sinnvoll nutzen? Alle Fourier-Basiszustände sind gleiche Überlagerungen aller Berechnungsbasiszustände, aber jeder Zustand unterscheidet sich von den anderen durch die Periodizität der Phase der Komponenten. Um dies konkreter zu verstehen, betrachten wir die vier Fourier-Basiszustände eines Zwei-Qubit-Systems. Der niedrigste Fourier-Zustand ist ein Zustand, dessen Phase sich überhaupt nicht ändert:

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

Wir können diesen Zustand veranschaulichen, indem wir die komplexe Amplitude der einzelnen Terme aufzeichnen. Die rote Linie zeigt Ihnen, wie sich die Phase dieser Amplitude in Abhängigkeit vom Zustand der Berechnungsgrundlage um die komplexe Ebene windet. Bei $|\phi_0\rangle$ bleibt die Phase konstant:

Der nächste Fourier-Basiszustand ist derjenige, dessen Phasen der Komponenten nur einmal von $0$ auf $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 diese Wicklung im Diagramm der komplexen Amplitude gegen den Berechnungsbasiszustand sehen:

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

$|\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 sich am schnellsten ändernden Phase. In unserem Beispiel mit zwei Qubits ist es dasjenige, dessen Phase dreimal von 0 auf $2\pi$ wechselt:

$|\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 Phasenänderung von konstant für $|\phi_0\rangle$ bis zu schnell variierend für $|\phi_{2^m-1}\rangle$ reicht und $2^m-1$ Windungen um $2\pi$ über die Überlagerung der Zustände vervollständigt. Wenn wir also eine QFT eines Quantenzustands durchführen, führen wir im Wesentlichen dieselbe grundlegende Analyse durch, die wir für die musikalische Wellenform in der Einleitung durchgeführt haben. Wir bestimmen die Fourier-Frequenzkomponenten, die zur Erzeugung des interessierenden Quantenzustands beitragen.

Probieren Sie einige Beispiel-QFTs aus

Versuchen wir, unser Gespür für die Quanten-Fourier-Transformation weiter auszubauen, indem wir einen Zustand in der Rechenbasis definieren und dann beobachten, was passiert, wenn wir die QFT darauf anwenden. Vorerst betrachten wir die QFT einfach als eine Blackbox, die wir mithilfe der QFTGate aus der Qiskit-Schaltkreisbibliothek anwenden. Später werden wir uns näher mit den Einzelheiten der Umsetzung befassen.

Wir beginnen damit, die erforderlichen Pakete zu laden und ein Gerät auszuwählen, auf dem unsere Schaltung laufen soll:

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)

Output:

ibm_pinguino2

Wenn Sie auf Ihrem Konto keine Zeit zur Verfügung haben oder aus irgendeinem Grund einen Simulator verwenden möchten, können Sie die unten stehende 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 Rechengrundzustand

Versuchen wir zunächst, einen einzelnen Zustand der Berechnungsgrundlage zu transformieren. Wir beginnen mit der Erstellung eines zufälligen Berechnungsstatus:

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

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

Output:

Nun wollen wir diesen Zustand mit QFTGate Fourier-transformieren:

# Step 1: Map

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

Output:

Wie Sie sehen, messen wir, dass die Populationen der einzelnen Zustände mehr oder weniger gleich sind, abgesehen von einigen experimentellen und statistischen Störungen. Nimmt man also die QFT eines einzelnen Basiszustandes, so ist das Ergebnis eine gleichwertige Überlagerung aller Zustände. Wenn Sie mit Fourier-Transformationen vertraut sind, wird Sie das wahrscheinlich nicht überraschen. Ein Grundprinzip, das uns helfen kann, eine intuitive Verbindung zwischen einer Funktion und ihrer Fouriertransformation herzustellen, ist, dass die Breite einer Funktion umgekehrt proportional zur Breite ihrer Fouriertransformation ist. Für etwas, das zeitlich sehr begrenzt ist, wie z. B. ein sehr kurzer Impuls, ist ein breites Spektrum an Frequenzen erforderlich, um diesen Impuls zu erzeugen. Dieses Signal wird im Fourier-Raum sehr breit sein.

Diese Tatsache hängt tatsächlich mit der Quantenunsicherheit zusammen! Die Heisenbergsche Unschärferelation wird üblicherweise als $\Delta x \Delta p \ge \hbar / 2$ angegeben. Wenn also die Unsicherheit in $x$ ( $\Delta x$ ) klein ist, muss die Unsicherheit im Impuls ( $\Delta p$ ) groß sein, und umgekehrt. Es stellt sich heraus, dass die Umwandlung von der Positionsbasis $x$ in die Impulsbasis $p$ durch eine Fourier-Transformation erreicht wird.

Hinweis: Beachten Sie, dass wir die Populationen in jedem der Basiszustände messen, so dass wir Informationen über die relativen Phasen zwischen den verschiedenen Teilen der Überlagerung verlieren. Während also die QFT eines einzelnen Basiszustands die gleiche gleichmäßige Verteilung der Population über alle Basiszustände ergibt, sind die Phasen nicht notwendigerweise die gleichen.

Zwei rechnerische Grundzustände

Sehen wir uns nun an, was passiert, wenn wir eine Überlagerung von Berechnungsbasiszuständen vorbereiten. Wie wird die Fourier-Transformation in diesem Fall aussehen?

Entscheiden wir uns für 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")

Output:

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

Output:

Nun wollen wir diesen Zustand mit QFTGate Fourier-transformieren:

# Step 1: Map

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

Output:

Dieser Fall könnte etwas überraschender sein. Es sieht so aus, als ob die QFT des Zustands $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ eine Superposition aller geraden Basiszustände ist. Aber wenn wir an unsere Visualisierung der einzelnen Basiszustände $|\phi_y\rangle$ zurückdenken und daran, wie die Phase jeder Komponente $2\pi$ $y$ mal umkreist, dann wird der Grund für dieses Ergebnis vielleicht klar.

Überprüfen Sie Ihr Verständnis

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

• Antwort

  Der ursprüngliche Zustand hat eine relative Phase von 0 (oder ein ganzzahliges Vielfaches 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 Term |0000> und dem Term |1000> haben. Jeder Fourier-Basiszustand $|\phi_y\rangle$ setzt sich aus Termen zusammen, deren Phase sich mit der Rate $2\pi y/N$ akkumuliert. Das bedeutet, dass jeder Term in der Überlagerung eine Phase von $2\pi y/N$ hat, die größer ist als die des vorhergehenden Terms, wenn er in der üblichen Weise angeordnet ist. Auf halber Strecke $N/2$ soll also die Phase $2\pi y/N * N/2$ ein ganzzahliges Vielfaches von $2\pi$ sein. Dies ist der Fall, wenn $y$ gerade ist.

Welche Überlagerung von Zuständen würde einer Quantenfeldtheorie entsprechen, bei der die Spitzen bei jeder ungeraden Zweierzahl auftreten?

• Antwort

  Nimmt man die QFT des Zustands $\psi = |0\rangle - |N/2\rangle$, dann würde man bei jedem ungeraden binär nummerierten Zustand Spitzenwerte sehen.

Den QFT-Algorithmus aufschlüsseln

Nachdem wir nun ein besseres Verständnis für die Beziehung zwischen Qubitzuständen in der Berechnungsbasis und der Fourier-Basis gewonnen haben, wollen wir uns nun mit dem QFT-Algorithmus selbst befassen. Mit anderen Worten: Welche Gatter implementieren wir tatsächlich auf dem Quantencomputer, um diese Transformation zu erreichen?

Fangen wir klein an, mit einem einzigen Qubit. Das bedeutet also, dass wir zwei Basiszustände haben werden. QFT $_2$ transformiert die Rechenbasiszustä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üfen Sie Ihr Verständnis

Verwende die Gleichung für die Quantenfeldtheorie aus dem vorigen Abschnitt, um die beiden oben genannten Fourier-Basiszustände zu überprüfen.

• Antwort

  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$ ), $N=2^n=2$, und $\omega_N^{xy} = e^{2\pi i \frac {y x}{2}}$. Wir haben 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)$

Schauen Sie sich diese beiden Gleichungen an. Vielleicht kennen Sie bereits ein Quantengatter, mit dem sich diese Transformation durchführen lässt. Das heißt, es gibt ein Tor, das die Rechenbasiszustände $|0\rangle$ und $|1\rangle$ in die entsprechenden Fourier-Basiszustände $|\phi_0\rangle$ und $|\phi_1\rangle$ transformiert. Es ist ein Hadamard-Tor! Dies 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$

Wenn Sie mit dieser Notation für den Ausdruck eines Quantenoperators nicht vertraut sind, ist das kein Problem! Es ist eine Art, eine $N \times N$ Matrix darzustellen, wobei $x$ und $y$ die Spalten und Zeilen der Matrix von $0$ bis $N-1$ indizieren und $\omega_N^{xy}$ der Wert des jeweiligen Eintrags ist. Der Eintrag in der 0. Spalte und in der 2. Zeile wäre zum Beispiel einfach $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$.

In dieser Darstellung ist jeder Zustand der Berechnungsgrundlage mit einem der Basisvektoren verbunden:

Wenn Sie mehr über diese Darstellung erfahren möchten, lesen Sie John Watrous' Lektion über multiple Systeme im Kurs Grundlagen der Quanteninformation.

Versuchen wir, die Matrix für die 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 Gattern, die auf welche Qubits angewendet werden, eine unitäre Transformation ergeben, die der obigen Matrix entspricht. Eines der Tore, die benötigt werden, kennen wir bereits: das Hadamard-Tor. Ein weiteres Gatter, das wir brauchen, ist das phasengesteuerte Gatter, das eine relative Phase $\alpha$ auf den Zustand des Ziel-Qubits anwendet, solange sich das Kontroll-Qubit im Zustand $|1\rangle$ befindet. In Matrixform sieht das wie folgt 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$ geändert wird, ist es eigentlich egal, welches Qubit als "Kontrolle" und welches als "Ziel" betrachtet wird Das Ergebnis ist in beiden Fällen dasselbe.

Schließlich brauchen wir auch einige SWAP-Gates. Ein SWAP-Gatter vertauscht die Zustände von zwei Qubits. 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 einer QFT $_{2^m}$ Schaltung auf $m$ Qubits ist iterativ - man wendet zuerst QFT $_{2^{m-1}}$ auf die Qubits $1$ bis $m-1$ an und fügt dann einige Gatter zwischen dem Qubit $0$ und den anderen $m-1$ Qubits hinzu. Aber um die QFT $_{2^{m-1}}$ anzuwenden, muss man zuerst die QFT $_{2^{m-2}}$ auf die Qubits 2 bis $m-1$ anwenden und dann einige Gatter zwischen Qubit 1 und den restlichen Qubits $2$ bis $m-1$ hinzufügen. Es ist wie eine russische Schachtelpuppe: Jede Puppe erhöht die Dimension des QFT-Schaltkreises um den Faktor zwei, wobei die kleinste Puppe in der Mitte die QFT $_2$ oder das Hadamard-Gatter ist.

Um eine Puppe in die nächstgrößere Puppe zu stecken und damit die Dimension der QFT um den Faktor zwei zu vergrößern, geht man immer nach dem gleichen Verfahren vor:

1. Zunächst wird die QFT $_{2^{m-1}}$ auf die untersten $m-1$ Qubits angewendet. Dies ist die "kleinere Puppe" des russischen Nistpuppensets, die du bald in die nächstgrößere Puppe stecken wirst.
2. Verwenden Sie das nächsthöhere Qubit als Kontrolle und wenden Sie kontrollierte Phasentore auf jedes der unteren $m-1$ Qubits an, mit Phasen zu den Standard-Basiszuständen jedes der verbleibenden $m-1$ Qubits.
3. Führen Sie ein Hadamard-Verfahren für das oberste Qubit durch, das als Kontrolle für die Phasentore verwendet wurde.
4. Verwenden Sie SWAP-Gatter, um die Reihenfolge der Qubits zu vertauschen, so dass das niedrigstwertige (obere) Bit zum höchstwertigen (unteren) Bit wird und alle anderen sich um eins nach oben verschieben.

Wir haben bereits die Funktion QFTGate aus der Qiskit-Schaltkreisbibliothek verwendet, aber jetzt wollen wir einen Blick in einige dieser QFT-Gatter werfen, um das obige Verfahren zu überprüfen. Wir können dies mit decompose() tun.

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

Output:

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

Output:

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

Output:

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

Output:

Anhand der ersten vier QFTs können Sie also hoffentlich erkennen, wie jede einzelne in die nächstgrößere verschachtelt ist. Sie haben vielleicht bemerkt, dass einige der Phasentore nicht genau so sind, wie in der oben beschriebenen Prozedur vorgeschrieben, und dass die SWAPs nicht nach jeder Unterroutine erscheinen, sondern erst ganz am Ende der vollständigen QFT. Dies erspart uns unnötige Gatter, die die Schaltung länger und fehleranfälliger machen würden. Anstatt den SWAP nach jeder verschachtelten Puppe zu implementieren, verfolgt die Schaltung, wo sich jedes Qubit befinden sollte, und passt die Qubits, auf die sie die Phasengatter anwendet, entsprechend an. Eine letzte Reihe von SWAPs am Ende bringt dann alles an seinen Platz.

Wenden Sie die QFT an: Phasenschätzung

Sehen wir uns an, wie die QFT zur Lösung eines nützlichen Problems in der Quanteninformatik verwendet werden kann. Die Berechnung der inversen Quanten-Fourier-Transformation ist ein notwendiger Schritt in einem Algorithmus, der als Quanten-Phasenschätzung (Quantum Phase Estimation, QPE) bekannt ist und selbst eine Unterroutine in vielen anderen Algorithmen ist, einschließlich des "Kronjuwels" der Quantenalgorithmen, dem Shor-Faktorisierungsalgorithmus.

Das Ziel von QPE ist es, die Eigenwerte eines unitären Operators zu schätzen. Unitäre Operatoren sind in der Quanteninformatik allgegenwärtig, und oft ist die Ermittlung der Eigenwerte ihrer zugehörigen Eigenvektoren ein notwendiger Schritt in einem größeren Algorithmus. Je nach Problemstellung kann ein Eigenwert die Energie eines Hamiltonianers in einem simulationsartigen Problem darstellen, uns helfen, Primfaktoren einer Zahl im Shor-Algorithmus zu finden, oder andere wichtige Informationen enthalten. QPE ist eines der wichtigsten und am häufigsten verwendeten Unterprogramme im Quantencomputing.

Was hat das nun mit einer Quanten-Fourier-Transformation zu tun? Wie Sie sich vielleicht erinnern, hat jeder Eigenwert $\lambda$ eines unitären Operators den Betrag $|\lambda| = 1$. Wir können also jeden Eigenwert als eine komplexe Zahl mit dem Betrag eins schreiben:

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

wobei $\theta$ eine reelle Zahl zwischen 0 und 1 ist. Wenn Sie weitere Informationen zu unitären Matrizen wünschen, sehen Sie sich die Lektion von John Watrous zu diesem Thema in „Grundlagen der Quanteninformation“ an.

Beachten Sie, dass $\lambda$ in $\theta$* periodisch* ist. Dies könnte bereits darauf hindeuten, 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

Beginnen wir mit dem einfachsten QPE-Algorithmus, der die Phase grob auf eine einzige Binärstelle genau schätzt. Mit anderen Worten, dieser Algorithmus kann zwischen $\theta = 0$ und $\theta = 1/2$ unterscheiden, kann aber nicht mehr als das. Hier ist der Schaltplan:

Die Qubits werden im Zustand $|\pi_0\rangle = |\psi\rangle|0\rangle$ vorbereitet, wobei sich das Qubit $0$ im Zustand $|0\rangle$ und die übrigen Qubits im Zustand $|\psi\rangle$ befinden, der ein Eigenzustand von $U$ ist. Nach dem ersten Hadamard wird der Qubit-Zustand:

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

Das nächste Tor ist ein "gesteuertes $U$ " Tor. Dies wendet die unitäre Operation $U$ auf die unteren Qubits an, die sich im Zustand $|\psi\rangle$ befinden, wenn sich das Qubit 0 im Zustand $|1\rangle$ befindet, tut aber nichts auf $|\psi\rangle$, wenn sich das Qubit 0 im Zustand $|0\rangle$ befindet. 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$ Gatter verwendet nur das Qubit $0$ als Kontroll-Qubit, so dass man meinen könnte, dass dieses Gatter den Zustand von Qubit 0 überhaupt nicht verändern würde. Aber irgendwie tut es das doch! Obwohl die Operation auf die unteren Qubits angewendet wurde, besteht der Gesamteffekt des Gatters darin, die Phase des Qubits $0$ zu ändern. Dies ist als "Phase Kickback-Mechanismus" bekannt und wird in vielen Quantenalgorithmen verwendet, einschließlich der Algorithmen von Deutsch-Josza und Grover. Wenn Sie mehr über den Phase-Kickback-Mechanismus erfahren möchten, lesen Sie John Watrous' Lektion über Quantenabfragealgorithmen in Grundlagen der Quantenalgorithmen.

Nach dem Phasenkickback wenden wir ein weiteres Hadamard-Verfahren auf das Qubit $0$ an, was zu dem 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 am Ende das Qubit $0$ 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 endgültige Messung nur probabilistisch und sagt uns nur so viel.

QPE mit höherer Präzision: mehr Qubits

Wir können dieses einfache Konzept auf einen komplizierteren Algorithmus mit beliebiger Genauigkeit erweitern. Wenn wir zur Messung der Phase nicht nur das Qubit $0$ verwenden, sondern auch die Qubits $m$ $0$ bis $m-1$, dann können wir die Phase mit der Genauigkeit von $m$ schätzen. Schauen wir mal, wie das funktioniert:

Diese präzisere QPE-Schaltung beginnt genauso wie die Ein-Bit-Version: Hadamards werden auf die ersten $m$ Qubits angewandt, und die restlichen Qubits werden im Zustand $|\psi\rangle$ vorbereitet, wodurch der Zustand entsteht:

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

Jetzt werden die kontrollierten Einheiten angewendet. Qubit $0$ ist das Steuerelement für die gleiche einheitliche $U$ wie zuvor. Aber jetzt ist das Qubit $1$ die Steuerung für das unitäre $U^2$, das einfach $U$ zweimal angewendet wird. Der Eigenwert von $U^2$ ist also $e^{2*2\pi i \theta}$. Im Allgemeinen ist jedes Qubit $k$ von 0 bis $m-1$ die Steuerung für die Unitary $U^{2^k}$. Das bedeutet, dass jedes dieser Qubits einen Phasenrückschlag von $e^{2^k*2\pi i \theta}$ erfährt. Dies führt zu dem 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)$

Dies kann als Summe über die Zustände der Berechnungsbasis 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 Ihnen die Summe bekannt vor? Es ist ein QFT! Erinnern Sie sich 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 ganzzahlige $y$ zwischen $0$ und $2^m-1$ liegt, dann führt die inverse QFT dieses Zustands zu diesem Zustand:

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

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

Wenn $\theta/2^m$ jedoch kein ganzzahliges Vielfaches ist, dann wird die inverse QFT nur eine Annäherung an $\theta$ liefern. Wie gut $\theta$ angenähert wird, ist probabilistisch, d.h. wir werden nicht immer die beste Annäherung erhalten, aber sie wird ziemlich nahe sein, und je mehr Qubits $m$ verwendet werden, desto besser wird die Annäherung sein. Wie diese Annäherung an $\theta$ quantifiziert werden kann, erfahren Sie in John Watrous' Lektion über Phasenschätzung und Faktorisierung in Grundlagen der Quantenalgorithmen.

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 Ihnen einen Vorgeschmack auf seine Nützlichkeit gegeben, als wir gesehen haben, wie es in der Quantenphasenschätzung verwendet werden kann, um etwas über die Eigenwerte einer Einheitsmatrix zu erfahren.

Kritische Konzepte

• Die Quanten-Fourier-Transformation ist das Quanten-Analogon zur Diskreten Fourier-Transformation.
• Die QFT ist ein Beispiel für eine Basistransformation.
• Das Verfahren zur Quanten-Phasenschätzung beruht auf dem Phasen-Kickback-Mechanismus der kontrolliert-unitären Operationen sowie auf einer inversen QFT.
• QFT und QPE sind beide weit verbreitete Unterprogramme in zahlreichen Quantenalgorithmen.

Fragen

True/False

1. T/F Die Quanten-Fourier-Transformation ist das Quanten-Analogon der klassischen diskreten Fourier-Transformation (DFT).
2. T/F QFT kann nur mit Hadamard- und CNOT-Gattern implementiert werden.
3. T/F QFT ist eine Schlüsselkomponente des Shor-Algorithmus.
4. T/F Das Ergebnis der Quantenphasenschätzung ist ein Quantenzustand, der den Eigenvektor des Operators darstellt.
5. T/F QPE erfordert die Verwendung der inversen Quanten-Fourier-Transformation (QFT $^\dag$ ).
6. T/F Wenn bei QPE die Phase $\phi$ mit $n$ Bits exakt darstellbar ist, liefert der Algorithmus mit Wahrscheinlichkeit 1 das richtige Ergebnis.

Kurze Antworten

1. Wie viele Qubits werden benötigt, um eine QFT für ein System mit $2^n$ Datenpunkten durchzuführen?
2. Kann die QFT auf einen Zustand angewendet werden, der keine Berechnungsgrundlage ist? Wenn ja, was passiert dann?
3. Wie wirkt sich die Anzahl der in QPE verwendeten Kontrollqubits auf die Auflösung der resultierenden Phasenschätzung aus?

Fehler

1. Verwenden Sie die Matrixmultiplikation, um zu überprüfen, ob die Schritte des QFT-Algorithmus tatsächlich die Matrix $\text{QFT}_4$ ergeben:

(Sie müssen das nicht von Hand machen!)

Herausfordernde Probleme

1. Erzeugen Sie einen Vier-Qubit-Zustand, der eine gleichwertige Superposition aller ungeraden Berechnungsbasen ist: $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. Führen Sie dann eine QFT für diesen Zustand durch. Wie sieht der daraus resultierende Zustand aus? Erläutern Sie, warum Ihr Ergebnis sinnvoll ist, und nutzen Sie dabei Ihre Kenntnisse über Fourier-Transformationen.