Quantenalgorithmen: Phasenschätzung

hinweis

Kento Ueda (15. Mai 2024)

Dieses Notebook vermittelt die grundlegenden Konzepte und die Implementierung der Quanten-Fourier-Transformation (QFT) und der Quantenphasenschätzung (QPE).

PDF der Originalvorlesung herunterladen. Beachte, dass manche Code-Schnipsel veraltet sein können, da es sich um statische Bilder handelt.

Ungefähre QPU-Zeit für dieses Experiment: 7 Sekunden.

1. Einführung

Quanten-Fourier-Transformation (QFT)

Die Quanten-Fourier-Transformation ist das quantenmechanische Pendant zur klassischen diskreten Fourier-Transformation. Es handelt sich um eine lineare Transformation, die auf Quantenzustände angewendet wird und Rechenbasisdarstellungen in ihre Fourier-Basis-Darstellungen überführt. Die QFT spielt eine zentrale Rolle in vielen Quantenalgorithmen und bietet eine effiziente Methode, Periodizitätsinformationen aus Quantenzuständen zu extrahieren. Die QFT kann mit $O(N^2)$ Operationen durch Quantengates wie Hadamard-Gates und Control-Phase-Gates für $N$ Qubits implementiert werden, was einen exponentiellen Speedup gegenüber der klassischen Fourier-Transformation ermöglicht.

• Anwendungen: Sie ist ein grundlegender Baustein in Quantenalgorithmen wie Shors Algorithmus zur Faktorisierung großer ganzer Zahlen und zum diskreten Logarithmus.

Quantenphasenschätzung (QPE)

Die Quantenphasenschätzung ist ein Quantenalgorithmus, der die Phase eines Eigenvektors eines unitären Operators schätzt. Dieser Algorithmus bildet eine Brücke zwischen den abstrakten mathematischen Eigenschaften von Quantenzuständen und ihren rechnerischen Anwendungen.

• Anwendungen: Er kann Probleme lösen wie das Finden von Eigenwerten unitärer Matrizen und die Simulation von Quantensystemen.

Zusammen bilden QFT und QPE das wesentliche Rückgrat vieler Quantenalgorithmen, die Probleme lösen, die für klassische Computer nicht handhabbar sind. Am Ende dieses Notebooks wirst du verstehen, wie diese Techniken implementiert werden.

2. Grundlagen der Quanten-Fourier-Transformation (QFT)

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

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
from qiskit.visualization import plot_histogram, plot_bloch_multivector
from qiskit.quantum_info import Statevector
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit_ibm_runtime import Sampler

from numpy import pi

In Analogie zur diskreten Fourier-Transformation wirkt die QFT auf einen Quantenzustand $\vert X\rangle = \sum_{j=0}^{N-1} x_j \vert j \rangle$ für $N$ Qubits und bildet ihn auf den Quantenzustand $\vert Y\rangle = \sum_{k=0}^{N-1} y_k \vert k \rangle$ ab.

$$QFT_{N}: \vert j \rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_N^{jk} \vert k \rangle$$

wobei $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$.

Oder als unitäre Matrix dargestellt:

$$U_{QFT} = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} \sum_{k=0}^{N-1} \omega_N^{jk} \vert k \rangle \langle j \vert$$

2.1. Intuition

Die Quanten-Fourier-Transformation (QFT) transformiert zwischen zwei Basen: der Rechenbasis (Z-Basis) und der Fourier-Basis. Was bedeutet die Fourier-Basis in diesem Kontext? Du erinnerst dich wahrscheinlich, dass die Fourier-Transformation $F(\omega)$ einer Funktion $f(x)$ die Faltung von $f(x)$ mit einer Sinusfunktion der Frequenz $\omega$ beschreibt. Vereinfacht gesagt: Die Fourier-Transformation ist eine Funktion, die beschreibt, wie viel von jeder Frequenz $\omega$ nötig wäre, um $f(x)$ aus Sinusfunktionen (oder Kosinusfunktionen) aufzubauen. Um ein besseres Gefühl dafür zu bekommen, was die QFT in diesem Kontext bedeutet, betrachte die folgenden Einzelbilder, die eine mit vier Qubits binär kodierte Zahl zeigen:

In der Rechenbasis speichern wir Zahlen in Binärform mithilfe der Zustände $|0\rangle$ und $|1\rangle$.

Beachte die Frequenz, mit der die verschiedenen Qubits wechseln: Das am weitesten links stehende Qubit wechselt bei jeder Erhöhung der Zahl, das nächste bei jeder zweiten, das dritte bei jeder vierten Erhöhung usw.

Wenn wir eine Quanten-Fourier-Transformation auf diese Zustände anwenden, bilden wir ab:

$$|\text{Zustand in Rechenbasis}\rangle \quad \xrightarrow[]{\text{QFT}} \quad |\text{Zustand in Fourier-Basis}\rangle$$ $$\text{QFT}|x\rangle = |\widetilde{x}\rangle$$

(Zustände in der Fourier-Basis werden oft mit einer Tilde (~) bezeichnet.)

In der Fourier-Basis speichern wir Zahlen durch verschiedene Rotationen um die Z-Achse:

IFRAME

Die zu speichernde Zahl bestimmt den Winkel, um den jedes Qubit um die Z-Achse gedreht wird. Im Zustand $|\widetilde{0}\rangle$ befinden sich alle Qubits im Zustand $|{+}\rangle$. Wie im obigen Beispiel zu sehen, wurde zur Kodierung des Zustands $|\widetilde{5}\rangle$ auf 4 Qubits das am weitesten links stehende Qubit um $\tfrac{5}{2^n} = \tfrac{5}{16}$ volle Umdrehungen ($\tfrac{5}{16}\times 2\pi$ Radiant) gedreht. Das nächste Qubit wird doppelt so weit gedreht ($\tfrac{10}{16}\times 2\pi$ Radiant bzw. $10/16$ volle Umdrehungen), dieser Winkel wird für das nächste Qubit wieder verdoppelt usw.

Beachte erneut die Frequenz, mit der jedes Qubit wechselt. Das am weitesten links stehende Qubit (qubit 0) hat in diesem Fall die niedrigste Frequenz, das am weitesten rechts stehende die höchste.

2.2 Beispiel: 1-Qubit-QFT

Betrachten wir den Fall $N = 2^1 = 2$.

Die unitäre Matrix lässt sich schreiben als:

$$\begin{aligned} U_{QFT} & = \frac{1}{\sqrt{2}} \sum_{j=0}^{1} \sum_{k=0}^{1} \omega_2^{jk} \vert k \rangle \langle j \vert \\ & = \frac{1}{\sqrt{2}} (\omega_2^{0} \vert 0 \rangle \langle 0 \vert + \omega_2^{0} \vert 0 \rangle \langle 1 \vert + \omega_2^{0} \vert 1 \rangle \langle 0 \vert + \omega_2^{1} \vert 1 \rangle \langle 1 \vert) \\ & = \frac{1}{\sqrt{2}} (\vert 0 \rangle \langle 0 \vert + \vert 0 \rangle \langle 1 \vert + \vert 1 \rangle \langle 0 \vert - \vert 1 \rangle \langle 1 \vert) \\ & = H \end{aligned}$$

Diese Operation entspricht dem Ergebnis der Anwendung des Hadamard-Gates ($H$).

2.3 Produktdarstellung der QFT

Verallgemeinern wir die Transformation für $N = 2^n$, $QFT_{N}$ angewendet auf den Zustand $\vert x \rangle = \vert x_1\ldots x_n \rangle$.

$$\begin{aligned} QFT_N\vert x \rangle & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1}\omega_N^{xy} \vert y \rangle \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i xy / 2^n} \vert y \rangle ~\text{da}\: \omega_N^{xy} = e^{2\pi i \frac{xy}{N}} \:\text{und}\: N = 2^n \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i \left(\sum_{k=1}^n y_k/2^k\right) x} \vert y_1 \ldots y_n \rangle \:\text{umgeschrieben in gebrochener Binärnotation}\: y = y_1\ldots y_n, y/2^n = \sum_{k=1}^n y_k/2^k \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} \prod_{k=1}^n e^{2 \pi i x y_k/2^k } \vert y_1 \ldots y_n \rangle \:\text{nach Entwicklung des Exponentials einer Summe als Produkt von Exponentialen,} \\ & = \frac{1}{\sqrt{N}} \bigotimes_{k=1}^n \left(\vert0\rangle + e^{2 \pi i x /2^k } \vert1\rangle \right) \:\text{nach Umordnung der Summen und Produkte sowie Entwicklung} \sum_{y=0}^{N-1} = \sum_{y_1=0}^{1}\sum_{y_2=0}^{1}\ldots\sum_{y_n=0}^{1} \\ & = \frac{1}{\sqrt{N}} \left(\vert0\rangle + e^{\frac{2\pi i}{2}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^2}x} \vert1\rangle\right) \otimes \ldots \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^{n-1}}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^n}x} \vert1\rangle\right) \end{aligned}$$

2.4 Beispiel: Circuit-Konstruktion der 3-Qubit-QFT

Aus der obigen Beschreibung ist möglicherweise nicht sofort klar, wie ein QFT-Circuit konstruiert werden soll. Beachte zunächst, dass wir bei drei Qubits Phasen erwarten, die sich mit unterschiedlichen „Raten" entwickeln. Wie das genau in einen Circuit übersetzt wird, bleibt als Übung dem Leser überlassen. Es gibt mehrere Diagramme und Beispiele im Vorlesungs-PDF. Weitere Ressourcen findest du in dieser Lektion des Kurses „Grundlagen der Quantenalgorithmen".

Wir demonstrieren die QFT nur mit Simulatoren und verwenden das Qiskit-Patterns-Framework erst, wenn wir zur Quantenphasenschätzung übergehen.

# Prepare for 3 qubits circuit
qr = QuantumRegister(3)
cr = ClassicalRegister(3)
qc = QuantumCircuit(qr, cr)

qc.h(2)
qc.cp(pi / 2, 1, 2)  # Controlled-phase gate from qubit 1 to qubit 2
qc.cp(pi / 4, 0, 2)  # Controlled-phase gate from qubit 0 to qubit 2
qc.draw(output="mpl")

qc.h(1)
qc.cp(pi / 2, 0, 1)  # Controlled-phase gate from qubit 0 to qubit 1

qc.draw(output="mpl")

qc.h(0)

qc.draw(output="mpl")

qc.swap(0, 2)

qc.draw(output="mpl")

Als Beispiel wenden wir die QFT auf $|5\rangle$ an.

Zunächst bestätigen wir die Binärdarstellung der Ganzzahl 5 und erstellen den Circuit, der den Zustand 5 kodiert:

bin(5)

'0b101'

qc = QuantumCircuit(3)

qc.x(0)
qc.x(2)
qc.draw(output="mpl")

Wir überprüfen die Quantenzustände mit dem Aer-Simulator:

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

Schließlich fügen wir die QFT hinzu und sehen den Endzustand unserer Qubits:

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

Wir sehen, dass die QFT-Funktion korrekt funktioniert hat. Qubit 0 wurde um $\tfrac{5}{8}$ einer vollen Umdrehung gedreht, Qubit 1 um $\tfrac{10}{8}$ volle Umdrehungen (entspricht $\tfrac{1}{4}$ einer vollen Umdrehung) und Qubit 2 um $\tfrac{20}{8}$ volle Umdrehungen (entspricht $\tfrac{1}{2}$ einer vollen Umdrehung).

2.5 Übung: QFT

(1) Implementiere die QFT für 4 Qubits.

##your code goes here##

(2) Wende die QFT auf $|14\rangle$ an, simuliere und zeichne den Zustandsvektor auf der Bloch-Sphäre.

##your code goes here##

Lösung der Übung: QFT

(1)

qr = QuantumRegister(4)
cr = ClassicalRegister(4)
qc = QuantumCircuit(qr, cr)

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

(2)

bin(14)

'0b1110'

qc = QuantumCircuit(4)

qc.x(1)
qc.x(2)
qc.x(3)
qc.draw("mpl")

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)
qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

3. Grundlagen der Quantenphasenschätzung (QPE)

Gegeben eine unitäre Operation $U$, schätzt die QPE $\theta$ in $U\vert\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$; da $U$ unitär ist, haben alle Eigenwerte den Betrag 1.

3.1 Vorgehen

1. Aufbau

$\vert\psi\rangle$ befindet sich in einem Qubit-Register. Ein weiteres Register aus $n$ Qubits bildet das Zählregister, in dem wir den Wert $2^n\theta$ speichern:

$$|\psi_0\rangle = \lvert 0 \rangle^{\otimes n} \lvert \psi \rangle$$

2. Superposition

Wende eine $n$-Bit-Hadamard-Gate-Operation $H^{\otimes n}$ auf das Zählregister an:

$$|\psi_1\rangle = {\frac {1}{2^{\frac {n}{2}}}}\left(|0\rangle +|1\rangle \right)^{\otimes n} \lvert \psi \rangle$$

3. Gesteuerte unitäre Operationen

Wir führen die kontrollierte unitäre Operation $CU$ ein, die den unitären Operator $U$ nur dann auf das Zielregister anwendet, wenn das zugehörige Kontrollbit $|1\rangle$ ist. Da $U$ ein unitärer Operator mit Eigenvektor $|\psi\rangle$ ist, sodass $U|\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$, gilt:

$$U^{2^{j}}|\psi \rangle =U^{2^{j}-1}U|\psi \rangle =U^{2^{j}-1}e^{2\pi i\theta }|\psi \rangle =\cdots =e^{2\pi i2^{j}\theta }|\psi \rangle$$

3.2 Beispiel: T-Gate-QPE

Verwenden wir das $T$-Gate als Beispiel für die QPE und schätzen wir seine Phase $\theta$.

$$T|1\rangle = \begin{pmatrix} 1 & 0\\ 0 & e^\frac{i\pi}{4}\\ \end{pmatrix} \begin{pmatrix} 0\\ 1\\ \end{pmatrix} = e^\frac{i\pi}{4}|1\rangle$$

Wir erwarten:

$$\theta = \frac{1}{8}$$

wobei

$$T|1\rangle = e^{2i\pi\theta}|1\rangle$$

Wir initialisieren $\vert\psi\rangle = \vert1\rangle$ als Eigenvektor des $T$-Gates durch Anwendung eines $X$-Gates:

qpe = QuantumCircuit(4, 3)
qpe.x(3)
qpe.draw(output="mpl")

Als nächstes wenden wir Hadamard-Gates auf die Zähl-Qubits an:

for qubit in range(3):
    qpe.h(qubit)
qpe.draw(output="mpl")

Wir führen die gesteuerten unitären Operationen durch:

repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.draw(output="mpl")

Wir wenden die inverse Quanten-Fourier-Transformation an, um den Zustand des Zählregisters zu konvertieren, und messen dann das Zählregister:

from qiskit.circuit.library import QFT

# Apply inverse QFT
qpe.append(QFT(3, inverse=True), [0, 1, 2])
qpe.draw(output="mpl")

for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

Wir können mit dem Aer-Simulator simulieren:

aer_sim = AerSimulator()
shots = 2048

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

Wir erhalten mit Sicherheit genau ein Ergebnis (001), was der Dezimalzahl 1 entspricht. Nun müssen wir unser Ergebnis (1) durch $2^n$ teilen, um $\theta$ zu erhalten:

$$\theta = \frac{1}{2^3} = \frac{1}{8}$$

Shors Algorithmus ermöglicht es uns, eine Zahl zu faktorisieren, indem wir einen Circuit mit unbekanntem $\theta$ konstruieren und $\theta$ bestimmen.

3.3 Übung

Schätze $\theta = 1/3$ mit 3 Qubits zum Zählen und einem Qubit für einen Eigenvektor.

$P|1\rangle = e^{i\lambda}|1\rangle$. Da wir $U|1\rangle = e^{2\pi i \tfrac{1}{3}}|1\rangle$ implementieren wollen, müssen wir $\lambda = \tfrac{2 \pi}{3}$ setzen.

##your code goes here##

Lösung der Übung: $\theta = 1/3$

# Create and set up circuit
qpe = QuantumCircuit(4, 3)

# Apply H-Gates to counting qubits:
for qubit in range(3):
    qpe.h(qubit)

# Prepare our eigenstate |psi>:
qpe.x(3)

# Do the controlled-U operations:
angle = 2 * pi / 3
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(angle, counting_qubit, 3)
    repetitions *= 2

# Do the inverse QFT:
qpe.append(QFT(3, inverse=True), [0, 1, 2])

for n in range(3):
    qpe.measure(n, n)

qpe.draw(output="mpl")

aer_sim = AerSimulator()
shots = 4096

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

4. Ausführung mit dem IBM Quantum Sampler Primitive

Wir werden QPE auf einem echten Quantengerät durchführen und dabei den 4 Schritten der Qiskit-Patterns folgen.

1. Problem in ein quantennatives Format überführen

2. Die Circuits optimieren

3. Den Ziel-Circuit ausführen

4. Die Ergebnisse nachbearbeiten

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Sampler

# Loading your IBM Quantum® account(s)

service = QiskitRuntimeService()

4.1 Schritt 1: Problem auf Quantencircuits und Operatoren abbilden

qpe = QuantumCircuit(4, 3)
qpe.x(3)
for qubit in range(3):
    qpe.h(qubit)
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.append(QFT(3, inverse=True), [0, 1, 2])
for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

backend = service.least_busy(simulator=False, operational=True, min_num_qubits=4)

print(backend)

<IBMBackend('ibm_strasbourg')>

4.2 Schritt 2: Für Zielhardware optimieren

# Transpile the circuit into basis gates executable on the hardware
pm = generate_preset_pass_manager(backend=backend, optimization_level=2)
qc_compiled = pm.run(qpe)

qc_compiled.draw("mpl", idle_wires=False)

4.3 Schritt 3: Auf Zielhardware ausführen

real_sampler = Sampler(mode=backend)
job = real_sampler.run([qc_compiled], shots=1024)
job_id = job.job_id()
print("job id:", job_id)

job id: d13p4zb5z6q00087ag00

job = service.job(job_id)  # Input your job-id between the quotations
job.status()

'DONE'

result_real = job.result()
print(result_real)

PrimitiveResult([SamplerPubResult(data=DataBin(c=BitArray(<shape=(), num_shots=1024, num_bits=3>)), metadata={'circuit_metadata': {}})], metadata={'execution': {'execution_spans': ExecutionSpans([DoubleSliceSpan(<start='2025-06-09 22:39:00', stop='2025-06-09 22:39:00', size=1024>)])}, 'version': 2})

4.4 Schritt 4: Ergebnisse nachbearbeiten

from qiskit.visualization import plot_histogram

plot_histogram(result_real[0].data.c.get_counts())

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'