Jelmaan Fourier kuantum

Untuk modul Qiskit in Classrooms ini, pelajar perlu mempunyai persekitaran Python yang berfungsi dengan pakej-pakej berikut dipasang:

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

Untuk menyediakan dan memasang pakej-pakej di atas, lihat panduan Pasang Qiskit. Untuk menjalankan kerja pada komputer kuantum sebenar, pelajar perlu menyediakan akaun dengan IBM Quantum® dengan mengikuti langkah-langkah dalam panduan Sediakan akaun IBM Cloud anda.

Modul ini telah diuji dan menggunakan 13 saat masa QPU. Ini adalah anggaran semaksimum mungkin; penggunaan sebenar anda mungkin berbeza.

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

Pengenalan

Jelmaan Fourier ialah alat yang sangat meluas digunakan dalam matematik, fizik, pemprosesan isyarat, pemampatan data, dan banyak bidang lain. Versi kuantum jelmaan Fourier, yang tepat dinamakan jelmaan Fourier kuantum, menjadi asas kepada beberapa algoritma kuantum yang paling penting.

Hari ini, selepas mengimbas kembali jelmaan Fourier klasik, kita akan bincang bagaimana kita melaksanakan jelmaan Fourier kuantum pada komputer kuantum. Kemudian, kita akan bincang salah satu aplikasi jelmaan Fourier kuantum kepada algoritma yang dipanggil algoritma anggaran fasa. Anggaran fasa kuantum adalah subrutin dalam algoritma pemfaktoran Shor yang terkenal, yang kadangkala dirujuk sebagai "permata mahkota" pengkomputeran kuantum. Modul ini membina ke arah modul lain tentang algoritma Shor, tetapi ia juga dimaksudkan untuk berdiri sendiri. Jelmaan Fourier kuantum ialah algoritma yang menakjubkan dan berguna dengan sendirinya!

Jelmaan Fourier klasik

Sebelum kita terjun ke jelmaan Fourier kuantum, mari kita imbas kembali versi klasiknya. Jelmaan Fourier ialah kaedah mengubah dari satu yang dipanggil "asas" ke asas yang lain. Anda boleh fikir dua asas sebagai perspektif berbeza untuk masalah yang sama — keduanya adalah cara yang sah untuk menyatakan sesuatu fungsi, tetapi salah satunya mungkin lebih menerangkan bergantung pada masalah yang ada. Beberapa contoh pasangan asas yang dihubungkan oleh jelmaan Fourier ialah kedudukan dan momentum, serta masa dan frekuensi.

Mari lihat contoh bagaimana jelmaan Fourier boleh membantu kita mengetahui nota yang dimainkan oleh sebuah alat muzik berdasarkan bentuk gelombang audionya. Biasanya, kita melihat bentuk gelombang diwakili dalam asas masa — iaitu, amplitud gelombang dinyatakan sebagai fungsi masa.

Kita boleh jelmakan bentuk gelombang ini untuk bergerak dari asas masa ke asas frekuensi:

Dalam asas frekuensi, kita mudah nampak puncak yang jelas pada kira-kira 260 Hz. Itu adalah C tengah!

Mungkin anda boleh tentukan bahawa C tengah sedang dimainkan tanpa menggunakan jelmaan Fourier, tetapi bagaimana jika beberapa nota dimainkan serentak? Maka bentuk gelombang menjadi lebih rumit apabila kita plot dalam asas masa:

Tetapi spektrum frekuensi jelas mengenal pasti tiga puncak:

Ini ialah akor C-major, memainkan nota C, E, dan G.

Jenis analisis Fourier ini boleh membantu kita mengekstrak komponen frekuensi bagi mana-mana isyarat yang rumit.

Jelmaan Fourier diskret

Jelmaan Fourier berguna untuk pelbagai aplikasi pemprosesan isyarat. Tetapi dalam kebanyakan aplikasi dunia sebenar ini (termasuk contoh muzik yang kita gunakan di atas), kita ingin mengubah set data diskret sebanyak $N$ titik — bukan fungsi berterusan. Dalam kes ini, kita menggunakan jelmaan Fourier diskret. Jelmaan Fourier diskret (DFT) bertindak ke atas vektor $(x_0, ..., x_{N-1})$ dan memetakannya ke vektor $(y_0, ..., y_{N-1})$ mengikut formula:

$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 bahawa terdapat konvensyen lain yang mempunyai tanda negatif dalam eksponen, jadi berhati-hati apabila anda melihat DFT di luar sana.) Ingat bahawa $e^{2\pi i \frac{jk}{N}}$ ialah fungsi berkala, dengan tempoh $\frac{N}{k}$. Jadi, dengan mendarab dengan fungsi ini, jelmaan Fourier pada dasarnya adalah cara untuk memecahkan fungsi (diskret) $\{x_{j}\}$ kepada kombinasi linear fungsi-fungsi berkala yang membentuknya, masing-masing dengan tempoh $\frac{N}{k}$.

Jelmaan Fourier kuantum

Jadi kini, kita telah melihat bagaimana jelmaan Fourier digunakan untuk mewakili fungsi sebagai kombinasi linear set baharu yang dipanggil "fungsi asas." Transformasi asas juga kerap dilakukan ke atas keadaan Qubit. Sebagai contoh, keadaan satu Qubit $|\psi\rangle$ boleh dinyatakan dalam asas komputasi $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$, dengan keadaan asas $|0\rangle$ dan $|1\rangle$, atau dalam asas $X$ $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ dengan keadaan asas $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$ dan $|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$. Kedua-duanya sama sah, tetapi salah satunya mungkin lebih semula jadi bergantung pada jenis masalah yang cuba anda selesaikan.

Keadaan Qubit juga boleh dinyatakan dalam asas Fourier di mana keadaan dinyatakan dalam sebutan kombinasi linear keadaan asas Fourier $|\phi_y\rangle$, bukannya keadaan asas komputasi biasa, $|x\rangle$. Untuk melakukan ini, anda perlu menerapkan jelmaan 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$ ialah bilangan keadaan asas dalam sistem kuantum anda. Perhatikan bahawa, memandangkan kita kini bekerja dengan Qubit, $m$ Qubit memberi anda $2^m$ keadaan asas, jadi $N=2^m$. Di sini, keadaan asas ditulis sebagai satu nombor $|x\rangle$ di mana $x$ berkisar dari $0$ hingga $N-1$, tetapi anda mungkin lebih kerap melihat keadaan asas dinyatakan sebagai $|00...00\rangle$, $|00...01\rangle$, $|00...11\rangle$, ..., $|11...11\rangle$, di mana setiap digit binari mewakili keadaan Qubit 0 hingga $m-1$, dari kanan ke kiri. Terdapat cara mudah untuk menukar keadaan binari ini kepada satu nombor: layani sahaja ia seperti nombor binari! Jadi, $|00...00\rangle = |0\rangle$, $|00...01\rangle = |1\rangle$, $|00...10\rangle = |2\rangle$, $|00...11\rangle = |3\rangle$, dan seterusnya, sehinggalah $|11...11\rangle = |2^m -1\rangle = |N-1\rangle$.

Bina intuisi untuk keadaan asas Fourier

Jadi, kita baru sahaja bincangkan apakah keadaan asas komputasi dan bagaimana ia dipesan: ia adalah set keadaan di mana setiap Qubit sama ada berada dalam $0$ atau $1$, dan kita pesan dari keadaan di mana semua Qubit adalah $0$, $|00...00\rangle$, hingga keadaan di mana semuanya $1$, $|11...11\rangle$.

Tetapi bagaimana kita memahami keadaan asas Fourier? Semua keadaan asas Fourier adalah superposisi sama rata bagi semua keadaan asas komputasi, tetapi setiap keadaan berbeza dari yang lain dalam kekerapan fasa komponen-komponennya. Untuk memahami ini dengan lebih konkret, mari lihat empat keadaan asas Fourier bagi sistem dua Qubit. Keadaan Fourier terendah adalah satu yang fasanya tidak berubah sama sekali:

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

Kita boleh gambarkan keadaan ini dengan memplot amplitud kompleks bagi setiap sebutan. Garis merah membimbing pandangan untuk menunjukkan bagaimana fasa amplitud ini berlegar-legar di satah kompleks sebagai fungsi keadaan asas komputasi. Untuk $|\phi_0\rangle$, fasa kekal malar:

Keadaan asas Fourier seterusnya ialah satu yang fasa komponennya berlegar dari $0$ hingga $2\pi$ hanya sekali:

$|\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 boleh lihat perlegaraan ini dalam plot amplitud kompleks berbanding keadaan asas komputasi:

Jadi, setiap keadaan mempunyai fasa yang $2\pi/4$ radian lebih tinggi daripada keadaan sebelumnya apabila dipesan dengan cara standard, kerana dalam contoh ini kita mempunyai empat keadaan asas ($N=4$). Keadaan asas seterusnya berlegar 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)$

Akhir sekali, komponen Fourier tertinggi ialah yang fasanya paling cepat berubah. Untuk contoh kita dengan dua Qubit, ia adalah satu yang fasanya berlegar 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, terdapat $2^m$ keadaan asas Fourier, yang frekuensi variasi fasanya berkisar dari malar, untuk $|\phi_0\rangle$, hingga berubah dengan pantas untuk $|\phi_{2^m-1}\rangle$, melengkapkan $2^m-1$ perlegaraan sekitar $2\pi$ melalui superposisi keadaan. Jadi, apabila kita mengambil QFT bagi keadaan kuantum, kita pada asasnya melakukan analisis asas yang sama seperti yang kita buat untuk bentuk gelombang muzik dalam Pengenalan. Kita menentukan komponen frekuensi Fourier yang menyumbang kepada mencipta keadaan kuantum yang diminati.

Cuba beberapa contoh QFT

Mari cuba terus membina intuisi kita untuk jelmaan Fourier kuantum dengan membuat keadaan dalam asas komputasi, kemudian melihat apa yang berlaku apabila kita menerapkan QFT padanya. Buat masa ini, kita akan anggap QFT sebagai kotak hitam yang kita terapkan menggunakan QFTGate daripada pustaka Circuit Qiskit. Kemudian, kita akan intip di bawah hood untuk melihat bagaimana ia dilaksanakan.

Kita mulakan dengan memuatkan pakej yang diperlukan dan memilih peranti 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 anda tidak mempunyai masa yang tersedia pada akaun anda atau ingin menggunakan simulator atas sebab apa pun, anda boleh jalankan sel di bawah untuk menyediakan simulator yang akan meniru peranti 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 asas komputasi tunggal

Pertama, mari cuba mengubah keadaan asas komputasi tunggal. Kita mulakan dengan membuat keadaan komputasi rawak:

# 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 jelmakan 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 anda lihat, kita mengukur populasi setiap keadaan lebih kurang sama, tambah tolak beberapa bunyi eksperimental dan statistik. Jadi, jika anda mengambil QFT bagi keadaan asas komputasi tunggal, hasilnya ialah superposisi sama rata bagi semua keadaan. Jika anda biasa dengan jelmaan Fourier, ini mungkin tidak mengejutkan anda. Satu prinsip asas yang boleh membantu kita membina hubungan intuitif antara fungsi dan jelmaan Fouriernya ialah lebar fungsi berbanding songsang dengan lebar jelmaan Fouriernya. Jadi, sesuatu yang sangat terpusat dalam masa, contohnya, seperti denyutan yang sangat singkat, akan memerlukan julat frekuensi yang luas untuk menjana denyutan itu. Isyarat itu akan sangat luas dalam ruang Fourier.

Fakta ini sebenarnya berkaitan dengan ketakpastian kuantum! Prinsip ketakpastian Heisenberg biasanya dinyatakan sebagai $\Delta x \Delta p \ge \hbar / 2$. Jadi jika ketakpastian dalam $x$ ($\Delta x$) adalah kecil, ketakpastian dalam momentum ($\Delta p$) mesti besar, dan sebaliknya. Ternyata, mengubah dari asas kedudukan $x$ ke asas momentum $p$ dicapai melalui jelmaan Fourier.

Nota: Ingat, kita mengukur populasi dalam setiap keadaan asas, jadi kita kehilangan maklumat tentang fasa relatif antara pelbagai bahagian superposisi. Jadi, walaupun QFT bagi mana-mana keadaan asas komputasi tunggal akan menghasilkan sebaran rata dalam populasi merentasi semua keadaan asas, fasa tidak semestinya sama.

Dua keadaan asas komputasi

Sekarang, mari lihat apa yang berlaku apabila kita menyediakan superposisi keadaan asas komputasi. Apa agaknya rupa jelmaan Fourier dalam kes ini?

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

Yang ini mungkin sedikit mengejutkan. Nampaknya QFT bagi keadaan $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ adalah superposisi semua keadaan asas genap. Tetapi jika kita fikir kembali tentang visualisasi kita bagi setiap keadaan asas $|\phi_y\rangle$, dan bagaimana fasa setiap komponen berlegar sekitar $2\pi$ sebanyak $y$ kali, maka sebab kita mendapat hasil ini mungkin menjadi jelas.

Periksa kefahaman anda

Baca soalan di bawah, fikirkan jawapan anda, kemudian klik segitiga untuk mendedahkan penyelesaian.

Menggunakan petunjuk di atas, terangkan mengapa hasil yang kita perolehi untuk QFT bagi $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ adalah dijangka.

Jawapan:

Keadaan asal mempunyai fasa relatif 0 (atau gandaan integer $2\pi$) antara dua bahagian superposisi. Jadi, kita tahu keadaan ini mempunyai komponen Fourier yang fasanya juga sepadan dengan cara itu: yang mempunyai anjakan fasa 0 antara sebutan |0000> dan sebutan |1000>. Setiap keadaan asas Fourier $|\phi_y\rangle$ terdiri daripada sebutan yang fasanya terkumpul pada kadar $2\pi y/N$, ertinya, apabila dipesan dengan cara biasa, setiap sebutan dalam superposisi mempunyai fasa $2\pi y/N$ lebih tinggi daripada sebutan yang mendahuluinya. Jadi, pada titik tengah $N/2$, kita mahu fasa $2\pi y/N * N/2$ menjadi gandaan integer $2\pi$. Ini berlaku apabila $y$ adalah genap.

Superposisi keadaan komputasi apakah yang akan sepadan dengan QFT yang mempunyai puncak pada setiap nombor binari ganjil?

Jawapan:

Jika anda mengambil QFT bagi keadaan $\psi = |0\rangle - |N/2\rangle$, maka anda akan melihat puncak pada setiap keadaan bernombor binari ganjil.

Urai algoritma QFT

Kini kita telah mendapat lebih banyak intuisi tentang hubungan antara keadaan Qubit dalam asas komputasi dan asas Fourier, mari kita selami algoritma QFT itu sendiri. Dengan kata lain, Gate apa yang sebenarnya kita laksanakan pada komputer kuantum untuk mencapai jelmaan ini?

Mari mulakan dengan kecil, dengan satu Qubit. Jadi, itu bermakna kita akan mempunyai dua keadaan asas. QFT$_2$ mengubah keadaan asas komputasi $|0\rangle$ dan $|1\rangle$ menjadi keadaan asas 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)$

Periksa kefahaman anda

Baca soalan di bawah, fikirkan jawapan anda, kemudian klik segitiga untuk mendedahkan penyelesaian.

Gunakan persamaan untuk QFT dalam bahagian sebelumnya untuk mengesahkan dua keadaan asas Fourier di atas.

Jawapan:

Formula QFT umum ialah:

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

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

Lihat dua persamaan tersebut. Anda mungkin sudah tahu Gate kuantum yang boleh digunakan untuk melaksanakan jelmaan ini. Iaitu, terdapat Gate yang mengubah keadaan asas komputasi $|0\rangle$ dan $|1\rangle$ kepada keadaan asas Fourier masing-masing $|\phi_0\rangle$ dan $|\phi_1\rangle$. Ia adalah Gate Hadamard! Ini menjadi lebih jelas jika kita memperkenalkan perwakilan matriks 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$

Jika anda tidak biasa dengan notasi ini untuk menyatakan pengoperasi kuantum, tidak mengapa! Ia adalah cara untuk mewakili matriks $N \times N$, di mana $x$ dan $y$ mengindeks lajur dan baris matriks, dari $0$ hingga $N-1$, dan $\omega_N^{xy}$ adalah nilai entri tertentu itu. Jadi, entri dalam lajur ke-0 dan baris ke-2, contohnya, hanyalah $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$.

Dalam perwakilan ini, setiap keadaan asas komputasi dikaitkan dengan salah satu vektor asas:

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

Jika anda ingin belajar lebih mendalam tentang perwakilan ini, lihat pelajaran John Watrous tentang sistem berbilang dalam kursus Asas maklumat kuantum.

Mari cuba bina matriks untuk QFT$_4$. Menggunakan formula di atas, kita dapati bahawa

\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 melaksanakan matriks ini pada komputer kuantum, kita perlu mengetahui kombinasi Gate mana yang diterapkan pada Qubit mana yang akan memberikan transformasi uniter yang sepadan dengan matriks di atas. Kita sudah tahu salah satu Gate yang diperlukan: Hadamard. Gate lain yang kita perlukan ialah Gate fasa terkawal, yang menerapkan fasa relatif $\alpha$ pada keadaan Qubit sasaran, selagi Qubit kawalan berada dalam keadaan $|1\rangle$. Dalam bentuk matriks ini kelihatan 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\}

Memandangkan hanya keadaan $|11\rangle$ yang diubah, sebenarnya tidak penting Qubit mana yang dianggap "kawalan" dan mana yang "sasaran." Hasilnya akan sama dalam kedua-dua cara.

Akhir sekali, kita juga memerlukan beberapa Gate SWAP. Gate SWAP menukar keadaan dua Qubit. Ia kelihatan seperti:

\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 membina Circuit QFT$_{2^m}$ pada $m$ Qubit adalah berulang — anda pertama menerapkan QFT$_{2^{m-1}}$ pada Qubit $1$ hingga $m-1$, kemudian menambah beberapa Gate antara Qubit $0$ dan $m-1$ Qubit yang lain. Tetapi untuk menerapkan QFT$_{2^{m-1}}$, anda perlu menerapkan QFT$_{2^{m-2}}$ pada Qubit 2 hingga $m-1$ terlebih dahulu, kemudian menambah beberapa Gate antara Qubit 1 dan Qubit yang tinggal $2$ hingga $m-1$. Ia seperti anak patung bersarang Rusia: setiap anak patung menambah faktor dua dalam dimensi Circuit QFT, dengan anak patung terkecil di tengah-tengah, iaitu QFT$_2$, atau Gate Hadamard.

Untuk meletakkan anak patung di dalam anak patung yang lebih besar seterusnya, seterusnya meningkatkan dimensi QFT sebanyak faktor dua, anda sentiasa mengikuti prosedur yang sama:

1. Pertama, terapkan QFT$_{2^{m-1}}$ pada $m-1$ Qubit paling bawah. Ini adalah "anak patung yang lebih kecil" daripada set anak patung bersarang Rusia yang akan anda masukkan ke dalam anak patung yang lebih besar seterusnya.
2. Gunakan Qubit seterusnya di atas sebagai kawalan, dan terapkan Gate fasa terkawal kepada setiap $m-1$ Qubit bawah, dengan fasa kepada keadaan asas standard bagi setiap $m-1$ Qubit yang tinggal.
3. Lakukan Hadamard pada Qubit paling atas yang sama yang digunakan sebagai kawalan dalam Gate fasa.
4. Gunakan Gate SWAP untuk mengatur semula susunan Qubit supaya bit paling tidak signifikan (atas) menjadi bit paling signifikan (bawah), dan semua yang lain beralih ke atas satu.

Kita sudah menggunakan fungsi QFTGate daripada pustaka Circuit Qiskit, tetapi sekarang mari lihat di dalam beberapa Gate QFT ini untuk mengesahkan prosedur di atas. Kita boleh 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 anda mula nampak bagaimana setiap satu bersarang di dalam yang terbesar seterusnya. Anda mungkin perasan, bagaimanapun, bahawa beberapa Gate fasa tidak tepat seperti yang ditetapkan dalam prosedur yang kita gariskan di atas, dan SWAP tidak muncul selepas setiap subrutin, tetapi sebaliknya hanya di hujung QFT penuh sahaja. Ini menjimatkan Gate yang tidak perlu, yang akan menyebabkan Circuit mengambil masa lebih lama dan lebih mudah tersalah. Daripada melaksanakan SWAP selepas setiap anak patung bersarang, Circuit menjejaki di mana setiap keadaan Qubit sepatutnya berada dan menyesuaikan Qubit yang diterapkan Gate fasa padanya dengan sewajarnya. Kemudian, satu set SWAP akhir di penghujung meletakkan segalanya pada tempat yang betul.

Gunakan QFT: Anggaran fasa

Mari kita lihat bagaimana QFT boleh digunakan untuk menyelesaikan masalah yang berguna dalam pengkomputeran kuantum. Mengira songsang jelmaan Fourier kuantum adalah langkah yang diperlukan dalam algoritma yang dikenali sebagai Anggaran Fasa Kuantum (QPE), yang merupakan subrutin dalam banyak algoritma lain, termasuk "permata mahkota" algoritma kuantum, algoritma pemfaktoran Shor.

Matlamat QPE adalah untuk menganggar nilai eigen bagi pengoperasi unitar. Pengoperasi unitar sangat meluas dalam pengkomputeran kuantum, dan sering kali, mencari nilai eigen bagi vektor eigen yang berkaitan adalah langkah yang diperlukan dalam algoritma yang lebih besar. Bergantung pada masalah, nilai eigen boleh mewakili tenaga Hamiltonian dalam masalah simulasi, boleh membantu kita mencari faktor perdana sesuatu nombor dalam algoritma Shor, atau boleh mengandungi maklumat penting yang lain. QPE adalah salah satu subrutin yang paling penting dan banyak digunakan dalam pengkomputeran kuantum.

Jadi, apakah kaitannya dengan jelmaan Fourier kuantum? Seperti yang mungkin kamu ingat, mana-mana nilai eigen $\lambda$ bagi pengoperasi unitar mempunyai magnitud $|\lambda| = 1$. Jadi kita boleh tulis setiap nilai eigen sebagai nombor kompleks dengan magnitud satu:

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

di mana $\theta$ adalah nombor nyata antara 0 dan 1. Jika kamu ingin maklumat lanjut tentang matriks unitar, lihat pelajaran John Watrous mengenai subjek ini dalam Asas maklumat kuantum.

Perhatikan bahawa $\lambda$ adalah berkala dalam $\theta$. Ini mungkin sudah mencadangkan kepada kamu bahawa QFT mungkin terlibat, kerana kita telah melihat betapa bergunanya QFT dalam menganalisis fungsi berkala. Di bawah, kita akan menelusuri algoritma dan melihat dengan tepat bagaimana QFT memainkan peranannya.

Cara QPE berfungsi

Pertama, kita akan mulakan dengan algoritma QPE yang paling mudah, yang secara kasar menganggar fasa kepada satu digit perduaan ketepatan. Dalam erti kata lain, algoritma ini boleh membezakan antara $\theta = 0$ dan $\theta = 1/2$, tetapi tidak lebih baik daripada itu. Berikut adalah rajah litar:

Qubit-Qubit disediakan dalam keadaan $|\pi_0\rangle = |\psi\rangle|0\rangle$, di mana Qubit $0$ berada dalam keadaan $|0\rangle$ dan Qubit-Qubit yang lain berada dalam keadaan $|\psi\rangle$, yang merupakan keadaan eigen bagi $U$. Selepas Hadamard pertama, keadaan Qubit menjadi:

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

Gate seterusnya adalah Gate "controlled-$U$". Ini mengenakan operasi unitar $U$ pada Qubit-Qubit bawah yang berada dalam keadaan $|\psi\rangle$ jika Qubit 0 berada dalam keadaan $|1\rangle$, tetapi tidak melakukan apa-apa pada $|\psi\rangle$ jika Qubit 0 berada dalam keadaan $|0\rangle$. Ini mengubah Qubit-Qubit kepada keadaan:

$|\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 pelik baru sahaja berlaku: Gate controlled-$U$ hanya menggunakan Qubit $0$ sebagai Qubit kawalan, jadi seseorang mungkin fikir bahawa Gate ini tidak akan mengubah keadaan Qubit 0 sama sekali. Tetapi entah bagaimana, ia berubah! Walaupun operasi dikenakan pada Qubit-Qubit bawah, kesan keseluruhan Gate adalah mengubah fasa Qubit $0$. Ini dikenali sebagai "mekanisme tendangan balik fasa," dan digunakan dalam banyak algoritma kuantum, termasuk algoritma Deutsch-Josza dan Grover. Jika kamu ingin mengetahui lebih lanjut tentang mekanisme tendangan balik fasa, lihat pelajaran John Watrous tentang Algoritma pertanyaan kuantum dalam Asas algoritma kuantum.

Selepas tendangan balik fasa, kita kenakan satu lagi Hadamard pada Qubit $0$, yang menghasilkan keadaan:

$|\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, apabila kita mengukur Qubit $0$ pada akhirnya, 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 hingar). Jika $\theta$ adalah sesuatu yang lain daripada ini, pengukuran akhir hanya bersifat kebarangkalian dan hanya memberitahu kita sekadar itu.

QPE dengan lebih ketepatan: lebih banyak Qubit

Kita boleh memperluaskan konsep mudah ini kepada algoritma yang lebih kompleks dengan ketepatan sewenang-wenangnya. Jika bukannya hanya menggunakan Qubit $0$ untuk mengukur fasa, kita menggunakan $m$ Qubit dari $0$ hingga $m-1$, maka kita akan dapat menganggar fasa dengan $m$ bit ketepatan. Mari kita lihat bagaimana ini berfungsi:

Litar QPE yang lebih tepat ini bermula sama seperti versi satu-bit: Hadamard dikenakan pada $m$ Qubit pertama, dan Qubit-Qubit yang lain disediakan dalam keadaan $|\psi\rangle$, mewujudkan keadaan:

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

Sekarang, unitar-unitar terkawal dikenakan. Qubit $0$ adalah kawalan untuk unitar $U$ yang sama seperti sebelumnya. Tetapi sekarang, Qubit $1$ adalah kawalan untuk unitar $U^2$, yang hanyalah $U$ dikenakan dua kali. Jadi, nilai eigen $U^2$ adalah $e^{2*2\pi i \theta}$. Secara umumnya, setiap Qubit $k$ dari 0 hingga $m-1$ akan menjadi kawalan untuk unitar $U^{2^k}$. Ini bermakna setiap Qubit ini akan mengalami tendangan balik fasa sebesar $e^{2^k*2\pi i \theta}$. Ini menghasilkan keadaan:

$|\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 boleh ditulis semula sebagai jumlah atas keadaan asas pengkomputeran:

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

Adakah jumlah itu kelihatan biasa? Ia adalah QFT! Ingat persamaan untuk jelmaan Fourier kuantum:

$\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 fasa $\theta = y/2^m$ untuk suatu integer $y$ antara $0$ dan $2^m-1$, maka mengambil songsang QFT bagi keadaan ini akan menghasilkan keadaan:

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

dan daripada $|y\rangle$, kita boleh menentukan $\theta$.

Jika $\theta/2^m$ bukan gandaan integer, bagaimanapun, maka mengambil songsang QFT hanya akan menganggar $\theta$. Seberapa baik ia menganggar $\theta$ akan bersifat kebarangkalian, bermakna kita tidak selalu mendapat anggaran terbaik, tetapi ia akan cukup hampir, dan semakin banyak Qubit $m$ yang kamu gunakan, semakin baik anggaran yang kamu akan dapat. Untuk mengetahui cara mengukur anggaran $\theta$ ini, lihat pelajaran John Watrous tentang Anggaran fasa dan pemfaktoran dalam Asas algoritma kuantum.

Kesimpulan

Modul ini memberikan gambaran keseluruhan tentang apa itu QFT, bagaimana ia dilaksanakan pada komputer kuantum, dan betapa bergunanya ia dalam menyelesaikan masalah. Kita diberikan sedikit gambaran tentang kegunaannya apabila kita melihat bagaimana ia boleh digunakan dalam anggaran fasa kuantum untuk mengetahui tentang nilai eigen matriks unitar.

Konsep penting

• Jelmaan Fourier Kuantum adalah analog kuantum bagi Jelmaan Fourier Diskret.
• QFT adalah contoh penjelmaan asas.
• Prosedur Anggaran Fasa Kuantum bergantung pada mekanisme tendangan balik fasa daripada operasi unitar terkawal, serta songsang QFT.
• QFT dan QPE keduanya merupakan subrutin yang banyak digunakan dalam pelbagai algoritma kuantum.

Soalan

Benar/Salah

1. B/S Jelmaan Fourier Kuantum adalah analog kuantum bagi jelmaan Fourier diskret klasik (DFT).
2. B/S QFT boleh dilaksanakan menggunakan hanya Gate Hadamard dan CNOT.
3. B/S QFT adalah komponen utama algoritma Shor.
4. B/S Keluaran Anggaran Fasa Kuantum adalah keadaan kuantum yang mewakili vektor eigen bagi pengoperasi.
5. B/S QPE memerlukan penggunaan songsang Jelmaan Fourier Kuantum (QFT$^\dag$).
6. B/S Dalam QPE, jika fasa $\phi$ boleh diwakili dengan tepat menggunakan $n$ bit, algoritma memberikan keputusan yang betul dengan kebarangkalian 1.

Jawapan pendek

1. Berapa banyak Qubit yang diperlukan untuk melaksanakan QFT pada sistem dengan $2^n$ titik data?
2. Bolehkah QFT digunakan pada keadaan yang bukan keadaan asas pengkomputeran? Jika boleh, apakah yang berlaku?
3. Bagaimana bilangan Qubit kawalan yang digunakan dalam QPE mempengaruhi resolusi anggaran fasa yang dihasilkan?

Masalah

1. Gunakan pendaraban matriks untuk mengesahkan bahawa 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 perlu buat ini dengan tangan!)

Masalah cabaran

1. Buat keadaan empat-Qubit yang merupakan superposisi sama rata bagi semua asas pengkomputeran ganjil: $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. Kemudian lakukan QFT pada keadaan tersebut. Apakah keadaan yang dihasilkan? Terangkan mengapa hasilmu masuk akal, menggunakan pengetahuanmu tentang jelmaan Fourier.