Transformasi Fourier Kuantum

Untuk modul Qiskit in Classrooms ini, mahasiswa harus memiliki lingkungan Python yang berjalan dengan paket-paket berikut terinstal:

• qiskit v2.1.0 atau lebih baru
• qiskit-ibm-runtime v0.40.1 atau lebih baru
• qiskit-aer v0.17.0 atau lebih baru
• qiskit.visualization
• numpy
• pylatexenc

Untuk menyiapkan dan menginstal paket-paket di atas, lihat panduan Install Qiskit. Agar bisa menjalankan job di komputer kuantum nyata, mahasiswa perlu membuat akun di IBM Quantum® dengan mengikuti langkah-langkah di panduan Set up your IBM Cloud account.

Modul ini telah diuji dan menggunakan 13 detik waktu QPU. Ini adalah estimasi dengan itikad baik; penggunaan aktualmu mungkin berbeda.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer qiskit-ibm-runtime

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

Pendahuluan

Transformasi Fourier adalah alat yang sangat umum digunakan dalam matematika, fisika, pemrosesan sinyal, kompresi data, dan banyak bidang lainnya. Versi kuantum dari transformasi Fourier, yang tepat dinamai transformasi Fourier kuantum, menjadi dasar dari beberapa algoritma kuantum yang paling penting.

Hari ini, setelah mengingat kembali transformasi Fourier klasik, kita akan membahas cara mengimplementasikan transformasi Fourier kuantum di komputer kuantum. Kemudian, kita akan mendiskusikan salah satu aplikasi transformasi Fourier kuantum pada algoritma yang disebut algoritma estimasi fase. Estimasi fase kuantum adalah subrutin dalam algoritma faktorisasi terkenal milik Shor, yang terkadang disebut sebagai "mahkota permata" komputasi kuantum. Modul ini mengarah ke modul lain yang membahas algoritma Shor secara mendalam, tapi juga dirancang untuk bisa berdiri sendiri. Transformasi Fourier kuantum adalah algoritma yang menarik dan berguna dengan sendirinya!

Transformasi Fourier klasik

Sebelum kita masuk ke transformasi Fourier kuantum, mari kita ingat dulu versi klasiknya. Transformasi Fourier adalah metode untuk berpindah dari satu "basis" ke basis lainnya. Kamu bisa menganggap dua basis sebagai perspektif berbeda dari masalah yang sama — keduanya adalah cara yang valid untuk mengekspresikan sebuah fungsi, tapi salah satunya mungkin lebih informatif, tergantung pada masalah yang dihadapi. Beberapa contoh pasangan basis yang dihubungkan oleh transformasi Fourier adalah posisi dan momentum, serta waktu dan frekuensi.

Mari kita lihat contoh bagaimana transformasi Fourier bisa membantu kita mengetahui nada apa yang dimainkan sebuah instrumen berdasarkan bentuk gelombang audionya. Biasanya, kita melihat bentuk gelombang yang direpresentasikan dalam basis waktu — yaitu, amplitudo gelombang diekspresikan sebagai fungsi dari waktu.

Kita bisa melakukan transformasi Fourier pada bentuk gelombang ini untuk berpindah dari basis waktu ke basis frekuensi:

Dalam basis frekuensi, kita bisa dengan mudah melihat puncak yang jelas sekitar 260 Hz. Itu adalah C tengah!

Sekarang, mungkin kamu bisa menentukan bahwa nada C tengah sedang dimainkan tanpa menggunakan transformasi Fourier, tapi bagaimana jika beberapa nada dimainkan sekaligus? Maka bentuk gelombangnya menjadi lebih rumit ketika kita memplotnya dalam basis waktu:

Tapi spektrum frekuensi dengan jelas mengidentifikasi tiga puncak:

Ini adalah akord C-mayor, memainkan nada C, E, dan G.

Analisis Fourier semacam ini bisa membantu kita mengekstrak komponen frekuensi dari sinyal yang rumit sekalipun.

Transformasi Fourier diskrit

Transformasi Fourier berguna untuk berbagai aplikasi pemrosesan sinyal. Tapi dalam sebagian besar aplikasi dunia nyata ini (termasuk contoh musik yang kita gunakan di atas), kita ingin mentransformasi sekumpulan diskrit dari $N$ titik data — bukan fungsi kontinu. Dalam hal ini, kita menggunakan transformasi Fourier diskrit. Transformasi Fourier diskrit (DFT) bekerja pada vektor $(x_0, ..., x_{N-1})$ dan memetakannya ke vektor $(y_0, ..., y_{N-1})$ menurut rumus:

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

di mana kita ambil $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$. (Perhatikan bahwa ada konvensi lain yang memiliki tanda minus dalam eksponensial, jadi hati-hati ketika kamu menemukan DFT di tempat lain.) Ingat bahwa $e^{2\pi i \frac{jk}{N}}$ adalah fungsi periodik, dengan periode $\frac{N}{k}$. Jadi, dengan mengalikan fungsi ini, transformasi Fourier pada dasarnya adalah cara untuk memecah fungsi (diskrit) $\{x_{j}\}$ menjadi kombinasi linier dari fungsi-fungsi periodik penyusunnya, masing-masing dengan periode $\frac{N}{k}$.

Transformasi Fourier kuantum

Jadi sekarang, kita telah melihat bagaimana transformasi Fourier digunakan untuk merepresentasikan sebuah fungsi sebagai kombinasi linier dari sekumpulan "fungsi basis" baru. Transformasi basis juga secara rutin dilakukan pada keadaan qubit. Misalnya, keadaan sebuah qubit tunggal $|\psi\rangle$ bisa diekspresikan dalam basis komputasi $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$, dengan keadaan basis $|0\rangle$ dan $|1\rangle$, atau dalam basis $X$ yaitu $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ dengan keadaan basis $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$ dan $|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$. Keduanya sama-sama valid, tapi salah satunya mungkin lebih alami dari yang lain, tergantung jenis masalah yang coba kamu selesaikan.

Keadaan qubit juga bisa diekspresikan dalam basis Fourier di mana sebuah keadaan diekspresikan dalam bentuk kombinasi linier dari keadaan basis Fourier $|\phi_y\rangle$, bukan keadaan basis komputasi biasa $|x\rangle$. Untuk melakukan ini, kamu perlu menerapkan transformasi Fourier kuantum (QFT):

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

dengan $\omega_N^{yx} = e^{\frac{2\pi i y x}{N}}$ seperti di atas, dan $N$ adalah jumlah keadaan basis dalam sistem kuantummu. Perhatikan bahwa, karena kita sekarang bekerja dengan qubit, $m$ qubit memberikan $2^m$ keadaan basis, sehingga $N=2^m$. Di sini, keadaan basis ditulis sebagai satu angka $|x\rangle$ di mana $x$ berkisar dari $0$ hingga $N-1$, tapi kamu mungkin lebih sering melihat keadaan basis diekspresikan sebagai $|00...00\rangle$, $|00...01\rangle$, $|00...11\rangle$, ..., $|11...11\rangle$, di mana setiap digit biner merepresentasikan keadaan qubit 0 hingga $m-1$, dari kanan ke kiri. Ada cara mudah untuk mengkonversi keadaan biner ini menjadi satu angka: cukup perlakukan mereka seperti bilangan biner! Jadi, $|00...00\rangle = |0\rangle$, $|00...01\rangle = |1\rangle$, $|00...10\rangle = |2\rangle$, $|00...11\rangle = |3\rangle$, dan seterusnya, sampai $|11...11\rangle = |2^m -1\rangle = |N-1\rangle$.

Bangun intuisi untuk keadaan basis Fourier

Jadi, kita baru saja membahas apa itu keadaan basis komputasi dan bagaimana urutan mereka: keadaan-keadaan itu adalah sekumpulan keadaan di mana setiap qubit berada dalam $0$ atau $1$, dan kita mengurutkan mereka dari keadaan di mana semua qubit adalah $0$, $|00...00\rangle$, ke keadaan di mana semuanya adalah $1$, $|11...11\rangle$.

Tapi bagaimana kita bisa memahami keadaan basis Fourier? Semua keadaan basis Fourier adalah superposisi yang setara dari semua keadaan basis komputasi, tapi setiap keadaan berbeda satu sama lain dalam periodisitas fase komponennya. Untuk memahami ini lebih konkret, mari kita lihat empat keadaan basis Fourier dari sistem dua qubit. Keadaan Fourier terendah adalah keadaan yang fasenya tidak bervariasi sama sekali:

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

Kita bisa memvisualisasikan keadaan ini dengan memplot amplitudo kompleks dari masing-masing suku. Garis merah memandu mata untuk menunjukkan bagaimana fase amplitudo ini berputar mengelilingi bidang kompleks sebagai fungsi dari keadaan basis komputasi. Untuk $|\phi_0\rangle$, fasenya tetap konstan:

Keadaan basis Fourier berikutnya adalah keadaan yang fase komponennya berputar dari $0$ hingga $2\pi$ tepat satu kali:

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

Dan kita bisa melihat putaran ini dalam plot amplitudo kompleks versus keadaan basis komputasi:

Jadi, setiap keadaan memiliki fase yang $2\pi/4$ radian lebih tinggi dari keadaan sebelumnya ketika diurutkan dengan cara standar, karena dalam contoh ini kita memiliki empat keadaan basis ($N=4$). Keadaan basis berikutnya berputar dari 0 hingga $2\pi$ dua kali:

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

Terakhir, komponen Fourier tertinggi adalah yang memiliki variasi fase tercepat. Untuk contoh kita dengan dua qubit, itu adalah keadaan yang fasenya berputar dari 0 hingga $2\pi$ tiga kali:

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

Secara umum, untuk keadaan $m$ qubit, akan ada $2^m$ keadaan basis Fourier, yang frekuensi variasi fasenya berkisar dari konstan, untuk $|\phi_0\rangle$, hingga bervariasi cepat untuk $|\phi_{2^m-1}\rangle$, menyelesaikan $2^m-1$ putaran mengelilingi $2\pi$ di atas superposisi keadaan. Jadi, ketika kita mengambil QFT dari sebuah keadaan kuantum, kita pada dasarnya melakukan analisis dasar yang sama yang kita lakukan untuk gelombang musik di bagian Pendahuluan. Kita menentukan komponen frekuensi Fourier yang berkontribusi dalam menciptakan keadaan kuantum yang menarik.

Coba beberapa contoh QFT

Mari kita terus membangun intuisi untuk transformasi Fourier kuantum dengan membuat sebuah keadaan dalam basis komputasi, lalu melihat apa yang terjadi ketika kita menerapkan QFT padanya. Untuk saat ini, kita akan memperlakukan QFT sebagai kotak hitam yang kita terapkan menggunakan QFTGate dari pustaka Circuit Qiskit. Nanti, kita akan mengintip ke dalamnya untuk melihat bagaimana ia diimplementasikan.

Kita mulai dengan memuat paket yang diperlukan dan memilih perangkat untuk menjalankan Circuit kita:

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

# Load the Qiskit Runtime 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

Jika kamu tidak memiliki waktu yang tersedia di akunmu atau ingin menggunakan simulator karena alasan apapun, kamu bisa menjalankan sel di bawah ini untuk menyiapkan simulator yang akan meniru perangkat kuantum yang kita pilih di atas:

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

Keadaan basis komputasi tunggal

Pertama, mari kita coba mentransformasi sebuah keadaan basis komputasi tunggal. Kita mulai dengan membuat keadaan komputasi acak:

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

Sekarang, mari kita lakukan transformasi Fourier pada keadaan ini dengan QFTGate:

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

Seperti yang kamu lihat, kita mengukur populasi dari setiap keadaan menjadi lebih kurang sama, dengan mempertimbangkan beberapa noise eksperimental dan statistik. Jadi, jika kamu mengambil QFT dari sebuah keadaan basis komputasi tunggal, hasilnya adalah superposisi yang setara dari semua keadaan. Jika kamu familiar dengan transformasi Fourier, ini mungkin tidak mengejutkanmu. Satu prinsip dasar yang bisa membantu kita membangun koneksi intuitif antara sebuah fungsi dan transformasi Fouriernya adalah bahwa lebar sebuah fungsi berbanding terbalik dengan lebar transformasi Fouriernya. Jadi, sesuatu yang sangat terlokalisasi dalam waktu, misalnya, seperti pulsa yang sangat pendek, akan memerlukan rentang frekuensi yang luas untuk menghasilkan pulsa itu. Sinyal itu akan sangat lebar dalam ruang Fourier.

Fakta ini sebenarnya berkaitan dengan ketidakpastian kuantum! Prinsip ketidakpastian Heisenberg biasanya dinyatakan sebagai $\Delta x \Delta p \ge \hbar / 2$. Jadi jika ketidakpastian dalam $x$ ($\Delta x$) kecil, ketidakpastian dalam momentum ($\Delta p$) harus besar, dan sebaliknya. Ternyata, berpindah dari basis posisi $x$ ke basis momentum $p$ dilakukan melalui transformasi Fourier.

Catatan: Ingatlah, kita mengukur populasi dalam setiap keadaan basis, jadi kita kehilangan informasi tentang fase relatif antara berbagai bagian superposisi. Jadi, meskipun QFT dari setiap keadaan basis komputasi tunggal akan menghasilkan sebaran yang sama merata dalam populasi di semua keadaan basis, fase-nya belum tentu sama.

Dua keadaan basis komputasi

Sekarang, mari kita lihat apa yang terjadi ketika kita menyiapkan superposisi dari keadaan basis komputasi. Menurutmu, seperti apa hasil transformasi Fourier dalam kasus ini?

Mari kita pilih superposisi:

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

Sekarang, mari kita lakukan transformasi Fourier pada keadaan ini dengan QFTGate:

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

Ini mungkin sedikit lebih mengejutkan. Terlihat bahwa QFT dari keadaan $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ adalah superposisi dari semua keadaan basis genap. Tapi jika kita kembali ke visualisasi kita tentang setiap keadaan basis $|\phi_y\rangle$, dan bagaimana fase setiap komponen berputar mengelilingi $2\pi$ sebanyak $y$ kali, maka alasan kita mendapatkan hasil ini mungkin menjadi jelas.

Uji pemahamanmu

Baca pertanyaan di bawah ini, pikirkan jawabanmu, lalu klik segitiga untuk melihat solusinya.

Menggunakan petunjuk di atas, jelaskan mengapa hasil yang kita dapatkan untuk QFT dari $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ sudah diperkirakan.

Jawaban:

Keadaan awal memiliki fase relatif 0 (atau kelipatan bilangan bulat dari $2\pi$) antara dua bagian superposisi. Jadi, kita tahu keadaan ini memiliki komponen Fourier yang fasenya juga cocok dengan cara itu: keadaan yang memiliki pergeseran fase 0 antara suku |0000> dan suku |1000>. Setiap keadaan basis Fourier $|\phi_y\rangle$ tersusun dari suku-suku yang fasenya terakumulasi pada laju $2\pi y/N$, artinya, ketika diurutkan dengan cara biasa, setiap suku dalam superposisi memiliki fase $2\pi y/N$ lebih besar dari suku sebelumnya. Jadi, pada titik tengah $N/2$, kita ingin fase $2\pi y/N * N/2$ menjadi kelipatan bilangan bulat dari $2\pi$. Ini terjadi ketika $y$ genap.

Superposisi keadaan komputasi seperti apa yang akan berkorespondensi dengan QFT yang memiliki puncak pada setiap bilangan biner ganjil?

Jawaban:

Jika kamu mengambil QFT dari keadaan $\psi = |0\rangle - |N/2\rangle$, maka kamu akan melihat puncak pada setiap keadaan bernomor biner ganjil.

Uraikan algoritma QFT

Sekarang setelah kita punya intuisi yang lebih baik tentang hubungan antara state qubit dalam basis komputasi dan basis Fourier, mari kita gali algoritma QFT itu sendiri. Dengan kata lain, gate apa saja yang sebenarnya kita implementasikan di komputer kuantum untuk mencapai transformasi ini?

Mari kita mulai dari yang kecil, dengan satu qubit saja. Jadi, kita punya dua state basis. QFT$_2$ mengubah state basis komputasi $|0\rangle$ dan $|1\rangle$ menjadi state basis Fourier $\phi_0$ dan $\phi_1$:

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

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

Cek pemahamanmu

Baca pertanyaan di bawah ini, pikirkan jawabanmu, lalu klik segitiga untuk melihat solusinya.

Gunakan persamaan QFT di bagian sebelumnya untuk memverifikasi dua state basis Fourier di atas.

Jawaban:

Formula QFT umum adalah:

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

Untuk satu qubit ($n=1$), $N=2^n=2$, dan $\omega_N^{xy} = e^{2\pi i \frac {y x}{2}}$. Jadi, kita punya

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

Perhatikan kedua persamaan itu. Mungkin kamu sudah tahu gate kuantum yang bisa digunakan untuk mengimplementasikan transformasi ini. Artinya, ada gate yang mengubah state basis komputasi $|0\rangle$ dan $|1\rangle$ menjadi state basis Fourier $|\phi_0\rangle$ dan $|\phi_1\rangle$ masing-masing. Itu adalah Hadamard gate! Ini menjadi lebih jelas kalau kita perkenalkan representasi matriks dari operasi QFT$_N$:

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

Kalau kamu belum familiar dengan notasi ini untuk mengekspresikan operator kuantum, tidak apa-apa! Ini adalah cara untuk merepresentasikan matriks $N \times N$, di mana $x$ dan $y$ mengindeks kolom dan baris matriks, dari $0$ sampai $N-1$, dan $\omega_N^{xy}$ adalah nilai entri tertentu tersebut. Jadi, entri di kolom ke-0 dan baris ke-2, misalnya, hanyalah $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$.

Dalam representasi ini, setiap state basis komputasi dikaitkan dengan salah satu vektor basis:

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

Kalau kamu ingin mempelajari representasi ini lebih dalam, lihat pelajaran John Watrous tentang multiple systems di kursus Basics of quantum information.

Mari kita coba membuat matriks untuk QFT$_4$. Menggunakan formula di atas, kita temukan bahwa

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

Untuk mengimplementasikan matriks ini di komputer kuantum, kita perlu mencari tahu kombinasi gate apa yang diterapkan ke qubit mana yang akan menghasilkan transformasi uniter yang cocok dengan matriks di atas. Kita sudah tahu salah satu gate yang diperlukan: Hadamard. Gate lain yang kita butuhkan adalah controlled-phase gate, yang menerapkan fase relatif $\alpha$ ke state qubit target, selama qubit kontrol berada dalam state $|1\rangle$. Dalam bentuk matriks ini terlihat seperti:

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

Karena hanya state $|11\rangle$ yang berubah, sebenarnya tidak masalah qubit mana yang dianggap "kontrol" dan mana yang "target." Hasilnya akan sama dalam kedua kasus.

Terakhir, kita juga butuh beberapa SWAP gate. SWAP gate menukar state dua qubit. Bentuknya seperti ini:

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

Prosedur untuk membuat Circuit QFT$_{2^m}$ pada $m$ qubit bersifat iteratif — kamu pertama-tama menerapkan QFT$_{2^{m-1}}$ ke qubit $1$ hingga $m-1$, lalu menambahkan beberapa gate antara qubit $0$ dan $m-1$ qubit lainnya. Tapi untuk menerapkan QFT$_{2^{m-1}}$, kamu pertama-tama perlu menerapkan QFT$_{2^{m-2}}$ ke qubit 2 hingga $m-1$, lalu menambahkan beberapa gate antara qubit 1 dan qubit yang tersisa $2$ hingga $m-1$. Ini seperti boneka Rusia bersarang: setiap boneka menambahkan faktor dua dalam dimensi Circuit QFT, dengan boneka terkecil di tengah-tengah, yaitu QFT$_2$, atau Hadamard gate.

Untuk memasukkan satu boneka ke dalam boneka berikutnya yang lebih besar, sehingga meningkatkan dimensi QFT sebesar faktor dua, kamu selalu mengikuti prosedur yang sama:

1. Pertama, terapkan QFT$_{2^{m-1}}$ ke $m-1$ qubit paling bawah. Ini adalah "boneka kecil" dari set boneka Rusia bersarang yang akan segera kamu masukkan ke dalam boneka yang lebih besar.
2. Gunakan qubit berikutnya di atas sebagai kontrol, dan terapkan controlled phase gate ke masing-masing dari $m-1$ qubit bawah, dengan fase ke state basis standar dari masing-masing $m-1$ qubit yang tersisa.
3. Lakukan Hadamard pada qubit paling atas yang sama yang digunakan sebagai kontrol dalam phase gate.
4. Gunakan SWAP gate untuk mengatur ulang urutan qubit sehingga bit paling tidak signifikan (atas) menjadi bit paling signifikan (bawah), dan semua yang lain bergeser ke atas satu langkah.

Kita sudah menggunakan fungsi QFTGate dari Qiskit circuit library, tapi sekarang mari kita lihat isi beberapa QFT gate ini untuk memverifikasi prosedur di atas. Kita bisa melakukan ini dengan decompose().

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

Jadi, semoga dari empat QFT pertama kamu mulai bisa melihat bagaimana masing-masing bersarang di dalam yang berikutnya yang lebih besar. Kamu mungkin menyadari, bahwa beberapa phase gate tidak persis seperti yang ditentukan dalam prosedur yang kita uraikan di atas, dan SWAP tidak muncul setelah setiap subrutin, melainkan hanya di akhir QFT penuh. Ini menghemat gate yang tidak perlu, yang akan membuat Circuit lebih lama dan lebih rentan terhadap kesalahan. Alih-alih mengimplementasikan SWAP setelah setiap boneka bersarang, Circuit melacak di mana setiap state qubit seharusnya berada dan menyesuaikan qubit yang diterapkan phase gate-nya sesuai dengan itu. Kemudian, sekumpulan SWAP terakhir di bagian akhir menempatkan semuanya di tempat yang tepat.

Terapkan QFT: Phase estimation

Mari kita lihat bagaimana QFT bisa digunakan untuk memecahkan masalah yang berguna dalam komputasi kuantum. Menghitung inverse quantum Fourier transform adalah langkah yang diperlukan dalam algoritma yang dikenal sebagai Quantum Phase Estimation (QPE), yang sendirinya merupakan subrutin dalam banyak algoritma lain, termasuk "mahkota permata" algoritma kuantum, algoritma faktorisasi Shor.

Tujuan QPE adalah memperkirakan nilai eigen dari operator uniter. Operator uniter ada di mana-mana dalam komputasi kuantum, dan seringkali, menemukan nilai eigen dari vektor eigen yang terkait adalah langkah yang diperlukan dalam algoritma yang lebih besar. Tergantung pada masalahnya, nilai eigen bisa merepresentasikan energi dari Hamiltonian dalam masalah tipe simulasi, bisa membantu kita menemukan faktor prima dari sebuah angka dalam algoritma Shor, atau bisa mengandung informasi penting lainnya. QPE adalah salah satu subrutin yang paling penting dan banyak digunakan dalam komputasi kuantum.

Jadi, apa hubungannya dengan quantum Fourier transform? Nah, seperti yang mungkin kamu ingat, setiap nilai eigen $\lambda$ dari operator uniter memiliki magnitude $|\lambda| = 1$. Jadi kita bisa menulis setiap nilai eigen sebagai bilangan kompleks dengan magnitude satu:

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

di mana $\theta$ adalah bilangan real antara 0 dan 1. Kalau kamu ingin informasi lebih lanjut tentang matriks uniter, lihat pelajaran John Watrous tentang subjek tersebut dalam Basics of quantum information.

Perhatikan bahwa $\lambda$ bersifat periodik dalam $\theta$. Ini sudah mungkin mengingatkanmu bahwa QFT bisa terlibat, karena kita telah melihat betapa bergunanya QFT untuk menganalisis fungsi periodik. Di bawah ini, kita akan menelusuri algoritma dan melihat dengan tepat bagaimana QFT berperan.

Cara kerja QPE

Pertama, kita akan mulai dengan algoritma QPE paling sederhana, yang secara kasar memperkirakan fase ke satu digit biner presisi. Dengan kata lain, algoritma ini bisa membedakan antara $\theta = 0$ dan $\theta = 1/2$, tapi tidak bisa lebih baik dari itu. Berikut diagram Circuit-nya:

Qubit disiapkan dalam state $|\pi_0\rangle = |\psi\rangle|0\rangle$, di mana qubit $0$ berada dalam state $|0\rangle$ dan qubit yang tersisa berada dalam state $|\psi\rangle$, yang merupakan eigenstate dari $U$. Setelah Hadamard pertama, state qubit menjadi:

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

Gate berikutnya adalah "controlled-$U$" gate. Ini menerapkan operasi uniter $U$ ke qubit bawah yang berada dalam state $|\psi\rangle$ jika qubit 0 berada dalam state $|1\rangle$, tapi tidak melakukan apa pun pada $|\psi\rangle$ jika qubit 0 berada dalam state $|0\rangle$. Ini mengubah qubit ke state:

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

Sesuatu yang aneh baru saja terjadi: controlled-$U$ gate hanya menggunakan qubit $0$ sebagai qubit kontrol, jadi orang mungkin berpikir bahwa gate ini sama sekali tidak akan mengubah state qubit 0. Tapi entah bagaimana, itu berubah! Meskipun operasi diterapkan ke qubit bawah, efek keseluruhan dari gate tersebut adalah mengubah fase qubit $0$. Ini dikenal sebagai "mekanisme phase kickback," dan digunakan dalam banyak algoritma kuantum, termasuk algoritma Deutsch-Josza dan Grover. Kalau kamu ingin mempelajari lebih lanjut tentang mekanisme phase-kickback, lihat pelajaran John Watrous tentang Quantum query algorithms dalam Fundamentals of quantum algorithms.

Setelah phase-kickback, kita menerapkan satu Hadamard lagi ke qubit $0$, yang menghasilkan state:

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

Jadi, ketika kita mengukur qubit $0$ di akhir, kita akan mengukur $|0\rangle$ dengan kepastian 100% jika $\theta = 0$ dan kita akan mengukur $|1\rangle$ dengan kepastian 100% jika $\theta = \frac{1}{2}$ (dan jika komputer kuantum kita sempurna, tanpa noise). Jika $\theta$ adalah sesuatu selain ini, pengukuran akhir hanya bersifat probabilistik dan hanya memberitahu kita sejauh itu.

QPE dengan presisi lebih tinggi: lebih banyak qubit

Kita bisa memperluas konsep sederhana ini ke algoritma yang lebih kompleks dengan presisi sembarang. Jika alih-alih hanya menggunakan qubit $0$ untuk mengukur fase, kita menggunakan $m$ qubit $0$ hingga $m-1$, maka kita akan dapat memperkirakan fase dengan $m$ bit presisi. Mari kita lihat cara kerjanya:

Circuit QPE yang lebih presisi ini dimulai sama seperti versi satu-bit: Hadamard diterapkan ke $m$ qubit pertama, dan qubit yang tersisa disiapkan dalam state $|\psi\rangle$, membuat state:

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

Sekarang, controlled-unitary diterapkan. Qubit $0$ adalah kontrol untuk uniter $U$ yang sama seperti sebelumnya. Tapi sekarang, qubit $1$ adalah kontrol untuk uniter $U^2$, yang hanya $U$ diterapkan dua kali. Jadi, nilai eigen dari $U^2$ adalah $e^{2*2\pi i \theta}$. Secara umum, setiap qubit $k$ dari 0 hingga $m-1$ akan menjadi kontrol untuk uniter $U^{2^k}$. Itu berarti setiap qubit ini akan mengalami phase kickback sebesar $e^{2^k*2\pi i \theta}$. Ini menghasilkan state:

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

Ini bisa ditulis ulang sebagai jumlah atas state basis komputasi:

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

Apakah jumlahnya terlihat familiar? Itu adalah QFT! Ingat persamaan untuk quantum Fourier transform:

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

Jadi, jika fase $\theta = y/2^m$ untuk beberapa bilangan bulat $y$ antara $0$ dan $2^m-1$, maka mengambil inverse QFT dari state ini akan menghasilkan state:

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

dan dari $|y\rangle$, kita bisa mendeduksi $\theta$.

Jika $\theta/2^m$ bukan kelipatan bilangan bulat, namun, maka mengambil inverse QFT hanya akan memperkirakan $\theta$. Seberapa baik perkiraan $\theta$ akan bersifat probabilistik, artinya kita tidak selalu mendapatkan perkiraan terbaik, tapi akan cukup dekat, dan semakin banyak qubit $m$ yang kamu gunakan, semakin baik perkiraan yang akan kamu dapatkan. Untuk mempelajari cara mengkuantifikasi perkiraan $\theta$ ini, lihat pelajaran John Watrous tentang Phase estimation and factoring dalam Fundamentals of quantum algorithms.

Kesimpulan

Modul ini memberikan gambaran umum tentang apa itu QFT, bagaimana diimplementasikan di komputer kuantum, dan betapa bergunanya untuk memecahkan masalah. Kita memberikan gambaran sekilas tentang kegunaannya ketika kita melihat bagaimana QFT bisa digunakan dalam quantum phase estimation untuk mempelajari nilai eigen dari matriks uniter.

Konsep kritis

• Quantum Fourier Transform adalah analog kuantum dari Discrete Fourier Transform.
• QFT adalah contoh dari transformasi basis.
• Prosedur Quantum Phase Estimation bergantung pada mekanisme phase-kickback dari operasi controlled-unitary, serta inverse QFT.
• QFT dan QPE keduanya merupakan subrutin yang banyak digunakan dalam berbagai algoritma kuantum.

Pertanyaan

Benar/Salah

1. B/S Quantum Fourier Transform adalah analog kuantum dari classical discrete Fourier transform (DFT).
2. B/S QFT bisa diimplementasikan hanya menggunakan Hadamard dan CNOT gate.
3. B/S QFT adalah komponen kunci dari algoritma Shor.
4. B/S Output dari Quantum Phase Estimation adalah state kuantum yang merepresentasikan vektor eigen dari operator.
5. B/S QPE memerlukan penggunaan inverse Quantum Fourier Transform (QFT$^\dag$).
6. B/S Dalam QPE, jika fase $\phi$ dapat direpresentasikan secara tepat dengan $n$ bit, algoritma memberikan hasil yang benar dengan probabilitas 1.

Jawaban singkat

1. Berapa banyak qubit yang diperlukan untuk melakukan QFT pada sistem dengan $2^n$ titik data?
2. Bisakah QFT digunakan pada state yang bukan state basis komputasi? Jika ya, apa yang terjadi?
3. Bagaimana jumlah qubit kontrol yang digunakan dalam QPE mempengaruhi resolusi perkiraan fase yang dihasilkan?

Soal

1. Gunakan perkalian matriks untuk memverifikasi bahwa langkah-langkah dalam algoritma QFT memang menghasilkan matriks $\text{QFT}_4$:

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

(Kamu tidak harus melakukan ini dengan tangan!)

Soal tantangan

1. Buat state empat-qubit yang merupakan superposisi merata dari semua basis komputasi ganjil: $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. Kemudian lakukan QFT pada state tersebut. Apa state yang dihasilkan? Jelaskan mengapa hasilmu masuk akal, menggunakan pengetahuanmu tentang transformasi Fourier.