Algoritma kuantum: Estimasi fase

catatan

Kento Ueda (15 May 2024)

Notebook ini membahas konsep dasar dan implementasi Transformasi Fourier Kuantum (QFT) dan Estimasi Fase Kuantum (QPE).

Unduh pdf dari kuliah aslinya. Perlu diperhatikan bahwa beberapa potongan kode mungkin sudah tidak berlaku karena ini adalah gambar statis.

Perkiraan waktu QPU untuk menjalankan eksperimen ini adalah 7 detik.

1. Pendahuluan

Quantum Fourier Transformation (QFT)

Quantum Fourier Transformation adalah padanan kuantum dari transformasi Fourier diskrit klasik. Ini adalah transformasi linear yang diterapkan pada keadaan kuantum, memetakan basis komputasional ke representasi basis Fourier-nya. QFT memainkan peran kunci dalam banyak algoritma kuantum, menawarkan metode efisien untuk mengekstrak informasi periodisitas dari keadaan kuantum. QFT dapat diimplementasikan dengan $O(N^2)$ operasi menggunakan gate kuantum seperti Hadamard gate dan Control-Phase gate untuk $N$ qubit, memungkinkan percepatan eksponensial dibandingkan transformasi Fourier klasik.

• Aplikasi: Ini adalah bagian fundamental dalam algoritma kuantum seperti algoritma Shor untuk memfaktorkan bilangan bulat besar dan logaritma diskrit.

Quantum Phase Estimation (QPE)

Quantum Phase Estimation adalah algoritma kuantum yang digunakan untuk mengestimasi fase yang terkait dengan eigenvector dari operator uniter. Algoritma ini memberikan jembatan antara sifat matematis abstrak dari keadaan kuantum dan aplikasi komputasionalnya.

• Aplikasi: Algoritma ini dapat menyelesaikan masalah seperti menemukan nilai eigen dari matriks uniter dan mensimulasikan sistem kuantum.

Bersama-sama, QFT dan QPE membentuk tulang punggung dari banyak algoritma kuantum yang memecahkan masalah yang tidak mungkin diselesaikan oleh komputer klasik. Di akhir notebook ini, kamu akan mendapatkan pemahaman tentang bagaimana teknik-teknik ini diimplementasikan.

2. Dasar-dasar Quantum 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

Dari analogi dengan transformasi Fourier diskrit, QFT bekerja pada keadaan kuantum $\vert X\rangle = \sum_{j=0}^{N-1} x_j \vert j \rangle$ untuk $N$ qubit dan memetakannya ke keadaan kuantum $\vert Y\rangle = \sum_{k=0}^{N-1} y_k \vert k \rangle$.

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

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

Atau representasi matriks uniter:

$$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. Intuisi

Quantum Fourier transform (QFT) melakukan transformasi antara dua basis: basis komputasional (Z) dan basis Fourier. Tapi apa arti basis Fourier dalam konteks ini? Kamu mungkin ingat bahwa transformasi Fourier $F(\omega)$ dari fungsi $f(x)$ menggambarkan konvolusi $f(x)$ ke fungsi sinusoidal dengan frekuensi $\omega$. Secara sederhana: transformasi Fourier adalah fungsi yang menggambarkan seberapa banyak dari setiap frekuensi $\omega$ yang kita perlukan untuk membangun fungsi $f(x)$ dari fungsi sinus (atau kosinus). Untuk lebih memahami apa yang dimaksud QFT dalam konteks ini, perhatikan gambar bertahap di bawah yang menunjukkan angka yang dikodekan dalam biner menggunakan empat qubit:

Dalam basis komputasional, kita menyimpan angka dalam biner menggunakan keadaan $|0\rangle$ dan $|1\rangle$.

Perhatikan frekuensi perubahan qubit yang berbeda; qubit paling kiri berubah setiap kenaikan angka, qubit berikutnya setiap 2 kenaikan, yang ketiga setiap 4 kenaikan, dan seterusnya.

Jika kita menerapkan quantum Fourier transform pada keadaan-keadaan ini, kita memetakan

$$|\text{State in Computational Basis}\rangle \quad \xrightarrow[]{\text{QFT}} \quad |\text{State in Fourier Basis}\rangle$$ $$\text{QFT}|x\rangle = |\widetilde{x}\rangle$$

(Kita sering menandai keadaan dalam basis Fourier menggunakan tilde (~)).

Dalam basis Fourier, kita menyimpan angka menggunakan rotasi yang berbeda di sekitar sumbu Z:

IFRAME

Angka yang ingin kita simpan menentukan sudut rotasi setiap qubit di sekitar sumbu Z. Dalam keadaan $|\widetilde{0}\rangle$, semua qubit berada dalam keadaan $|{+}\rangle$. Seperti yang terlihat pada contoh di atas, untuk mengkodekan keadaan $|\widetilde{5}\rangle$ pada 4 qubit, kita memutar qubit paling kiri sebesar $\tfrac{5}{2^n} = \tfrac{5}{16}$ putaran penuh ($\tfrac{5}{16}\times 2\pi$ radian). Qubit berikutnya diputar dua kali lipat ($\tfrac{10}{16}\times 2\pi$ radian, atau $10/16$ putaran penuh), sudut ini kemudian digandakan untuk qubit berikutnya, dan seterusnya.

Sekali lagi, perhatikan frekuensi perubahan setiap qubit. Qubit paling kiri (qubit 0) dalam kasus ini memiliki frekuensi terendah, dan yang paling kanan memiliki frekuensi tertinggi.

2.2 Contoh: QFT 1-qubit

Mari kita pertimbangkan kasus $N = 2^1 = 2$.

Matriks uniter dapat ditulis:

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

Operasi ini adalah hasil dari penerapan Hadamard gate ($H$).

2.3 Representasi produk dari QFT

Mari kita generalisasi transformasi untuk $N = 2^n$, $QFT_{N}$ yang bekerja pada keadaan $\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{since}\: \omega_N^{xy} = e^{2\pi i \frac{xy}{N}} \:\text{and}\: 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{rewriting in fractional binary notation}\: 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{after expanding the exponential of a sum to a product of exponentials,} \\ & = \frac{1}{\sqrt{N}} \bigotimes_{k=1}^n \left(\vert0\rangle + e^{2 \pi i x /2^k } \vert1\rangle \right) \:\text{after rearranging the sum and products, and expanding} \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 Contoh: Konstruksi Circuit QFT 3 qubit

Dari deskripsi di atas, mungkin belum jelas bagaimana membangun Circuit QFT. Untuk saat ini, cukup catat bahwa kita mengharapkan tiga qubit memiliki fase yang berevolusi dengan "kecepatan" yang berbeda. Memahami bagaimana tepatnya ini diterjemahkan ke dalam Circuit diserahkan sebagai latihan bagi pembaca. Ada beberapa diagram dan contoh dalam pdf kuliah. Sumber tambahan termasuk pelajaran ini dari kursus Fundamentals of quantum algorithms.

Kita akan mendemonstrasikan QFT hanya menggunakan simulator, sehingga kita tidak akan menggunakan kerangka kerja pola Qiskit sampai kita beralih ke estimasi fase kuantum.

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

Kita coba menerapkan QFT pada $|5\rangle$ sebagai contoh.

Pertama, kita konfirmasi notasi biner dari bilangan bulat 5 dan buat Circuit yang mengkodekan keadaan 5:

bin(5)

'0b101'

qc = QuantumCircuit(3)

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

Kita periksa keadaan kuantum menggunakan simulator Aer:

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

Terakhir, kita tambahkan QFT dan lihat keadaan akhir qubit kita:

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)

Kita bisa melihat fungsi QFT kita bekerja dengan benar. Qubit 0 telah diputar sebesar $\tfrac{5}{8}$ putaran penuh, qubit 1 sebesar $\tfrac{10}{8}$ putaran penuh (setara dengan $\tfrac{1}{4}$ putaran penuh), dan qubit 2 sebesar $\tfrac{20}{8}$ putaran penuh (setara dengan $\tfrac{1}{2}$ putaran penuh).

2.5 Latihan: QFT

(1) Implementasikan QFT dengan 4 qubit.

##your code goes here##

(2) Terapkan QFT pada $|14\rangle$, simulasikan dan plot statevector menggunakan Bloch sphere.

##your code goes here##

Solusi latihan: 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. Dasar-dasar Quantum Phase Estimation (QPE)

Diberikan operasi uniter $U$, QPE mengestimasi $\theta$ dalam $U\vert\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$ karena $U$ bersifat uniter, semua nilai eigennya memiliki norma 1.

3.1 Prosedur

1. Persiapan

$\vert\psi\rangle$ berada dalam satu set register qubit. Satu set tambahan $n$ qubit membentuk register pencacah di mana kita akan menyimpan nilai $2^n\theta$:

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

2. Superposisi

Terapkan operasi Hadamard gate $n$-bit $H^{\otimes n}$ pada register pencacah:

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

3. Operasi Controlled Unitary

Kita perlu memperkenalkan controlled unitary $CU$ yang menerapkan operator uniter $U$ pada register target hanya jika bit kontrolnya adalah $|1\rangle$. Karena $U$ adalah operator uniter dengan eigenvector $|\psi\rangle$ sedemikian sehingga $U|\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$, maka:

$$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 Contoh: T-gate QPE

Mari kita gunakan gate $T$ sebagai contoh QPE dan estimasi fasenya $\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$$

Kita harapkan menemukan:

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

di mana

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

Kita menginisialisasi $\vert\psi\rangle = \vert1\rangle$ dari eigenvector gate $T$ dengan menerapkan gate $X$:

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

Selanjutnya, kita menerapkan gate Hadamard pada qubit pencacah:

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

Kita melakukan operasi uniter terkontrol:

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

Kita menerapkan transformasi Fourier kuantum invers untuk mengubah keadaan register pencacah, kemudian mengukur register pencacah:

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

Kita bisa mensimulasikan menggunakan simulator Aer:

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)

Kita mendapatkan satu hasil (001) dengan pasti, yang setara dengan desimal 1. Kita sekarang perlu membagi hasil kita (1) dengan $2^n$ untuk mendapatkan $\theta$:

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

Algoritma Shor memungkinkan kita untuk memfaktorkan sebuah angka dengan membangun circuit dengan $\theta$ tidak diketahui dan memperoleh $\theta$.

3.3 Latihan

Estimasikan $\theta = 1/3$ menggunakan 3 qubit untuk pencacahan dan sebuah qubit untuk eigenvector.

$P|1\rangle = e^{i\lambda}|1\rangle$. Karena kita ingin mengimplementasikan $U|1\rangle = e^{2\pi i \tfrac{1}{3}}|1\rangle$, kita perlu menetapkan $\lambda = \tfrac{2 \pi}{3}$.

##your code goes here##

Solusi latihan: $\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. Eksekusi menggunakan primitif Sampler IBM Quantum

Kita akan menjalankan QPE menggunakan perangkat kuantum nyata dan mengikuti 4 langkah pola Qiskit.

1. Petakan masalah ke format quantum-native

2. Optimalkan Circuit

3. Jalankan Circuit target

4. Proses hasil

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Sampler

# Loading your IBM Quantum® account(s)

service = QiskitRuntimeService()

4.1 Langkah 1: Petakan masalah ke Circuit dan operator kuantum

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 Langkah 2: Optimalkan untuk hardware target

# 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 Langkah 3: Jalankan di hardware target

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 Langkah 4: Proses hasil

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'