Algoritma kuantum: Anggaran fasa

nota

Kento Ueda (15 Mei 2024)

Buku nota ini menyediakan konsep asas dan pelaksanaan Transformasi Fourier Kuantum (QFT) dan Anggaran Fasa Kuantum (QPE).

Muat turun pdf syarahan asal. Perlu diingat bahawa beberapa coretan kod mungkin sudah lapuk kerana ia adalah imej statik.

Anggaran masa QPU untuk menjalankan eksperimen ini ialah 7 saat.

1. Pengenalan

Transformasi Fourier Kuantum (QFT)

Transformasi Fourier Kuantum ialah rakan sejawat kuantum bagi transformasi Fourier diskret klasik. Ia adalah transformasi linear yang digunakan pada keadaan kuantum, memetakan asas pengiraan kepada perwakilan asas Fourier. QFT memainkan peranan penting dalam banyak algoritma kuantum, menawarkan kaedah cekap untuk mengekstrak maklumat kala dari keadaan kuantum. QFT boleh dilaksanakan dengan operasi $O(N^2)$ menggunakan Gate kuantum seperti Gate Hadamard dan Gate Kawalan-Fasa untuk $N$ Qubit, membolehkan pecutan eksponen berbanding transformasi Fourier klasik.

• Aplikasi: Ia adalah bahagian asas dalam algoritma kuantum seperti algoritma Shor untuk pemfaktoran integer besar dan logaritma diskret.

Anggaran Fasa Kuantum (QPE)

Anggaran Fasa Kuantum ialah algoritma kuantum yang digunakan untuk menganggar fasa yang berkaitan dengan vektor eigen bagi pengendali unitary. Algoritma ini menyediakan jambatan antara sifat matematik abstrak keadaan kuantum dan aplikasi pengiraannya.

• Aplikasi: Ia boleh menyelesaikan masalah seperti mencari nilai eigen matriks unitary dan mensimulasikan sistem kuantum.

Bersama-sama, QFT dan QPE membentuk tulang belakang penting bagi banyak algoritma kuantum yang menyelesaikan masalah yang tidak dapat dilakukan oleh komputer klasik. Menjelang akhir buku nota ini, kamu akan memahami bagaimana teknik-teknik ini dilaksanakan.

2. Asas Transformasi Fourier Kuantum (QFT)

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

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

Berdasarkan analogi dengan transformasi Fourier diskret, QFT bertindak pada keadaan kuantum $\vert X\rangle = \sum_{j=0}^{N-1} x_j \vert j \rangle$ untuk $N$ Qubit dan memetakannya kepada 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 perwakilan matriks unitary:

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

Transformasi Fourier kuantum (QFT) mengubah antara dua asas, iaitu asas pengiraan (Z) dan asas Fourier. Tapi apa yang dimaksudkan dengan asas Fourier dalam konteks ini? Kamu mungkin ingat bahawa transformasi Fourier $F(\omega)$ bagi fungsi $f(x)$ menggambarkan konvolusi $f(x)$ pada fungsi sinusoidal dengan frekuensi $\omega$. Dalam bahasa mudah: transformasi Fourier ialah fungsi yang menggambarkan berapa banyak setiap frekuensi $\omega$ yang diperlukan untuk membina fungsi $f(x)$ daripada fungsi sinus (atau kosinus). Untuk memahami maksud QFT dalam konteks ini dengan lebih baik, pertimbangkan imej berperingkat di bawah yang menunjukkan nombor yang dikodkan dalam binari menggunakan empat Qubit:

Dalam asas pengiraan, kita menyimpan nombor dalam binari menggunakan keadaan $|0\rangle$ dan $|1\rangle$.

Perhatikan frekuensi Qubit yang berbeza berubah; Qubit paling kiri bertukar setiap kenaikan nombor, yang seterusnya setiap 2 kenaikan, yang ketiga setiap 4 kenaikan, dan seterusnya.

Jika kita menggunakan transformasi Fourier kuantum pada keadaan-keadaan ini, kita memetakan

$$|\text{Keadaan dalam Asas Pengiraan}\rangle \quad \xrightarrow[]{\text{QFT}} \quad |\text{Keadaan dalam Asas Fourier}\rangle$$ $$\text{QFT}|x\rangle = |\widetilde{x}\rangle$$

(Kita sering menandakan keadaan dalam asas Fourier menggunakan tilde (~)).

Dalam asas Fourier, kita menyimpan nombor menggunakan putaran berbeza di sekitar paksi Z:

IFRAME

Nombor yang ingin kita simpan menentukan sudut setiap Qubit diputar di sekitar paksi Z. Dalam keadaan $|\widetilde{0}\rangle$, semua Qubit berada dalam keadaan $|{+}\rangle$. Seperti yang dilihat dalam contoh di atas, untuk mengekod keadaan $|\widetilde{5}\rangle$ pada 4 Qubit, kita memutar Qubit paling kiri sebanyak $\tfrac{5}{2^n} = \tfrac{5}{16}$ pusingan penuh ($\tfrac{5}{16}\times 2\pi$ radian). Qubit seterusnya diputar dua kali ganda ini ($\tfrac{10}{16}\times 2\pi$ radian, atau $10/16$ pusingan penuh), sudut ini kemudian digandakan untuk Qubit berikutnya, dan seterusnya.

Sekali lagi, perhatikan frekuensi setiap Qubit berubah. Qubit paling kiri (qubit 0) dalam kes ini mempunyai frekuensi terendah, dan yang paling kanan mempunyai frekuensi tertinggi.

2.2 Contoh: QFT 1-Qubit

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

Matriks unitary boleh 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 daripada menggunakan Gate Hadamard ($H$).

2.3 Perwakilan hasil darab QFT

Mari kita umumkan transformasi untuk $N = 2^n$, $QFT_{N}$ yang bertindak 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: Pembinaan Circuit QFT 3 Qubit

Daripada penerangan di atas, mungkin tidak jelas bagaimana membina Circuit QFT. Buat masa ini, cukuplah untuk diperhatikan bahawa kita menjangkakan tiga Qubit mempunyai fasa yang berevolusi pada "kadar" yang berbeza. Memahami bagaimana ini diterjemahkan ke dalam Circuit diserahkan sebagai latihan kepada pembaca. Terdapat pelbagai gambar rajah dan contoh dalam pdf syarahan. Sumber tambahan termasuk pelajaran ini daripada kursus Asas algoritma kuantum.

Kita akan menunjukkan QFT menggunakan simulator sahaja, oleh itu kita tidak akan menggunakan rangka kerja corak Qiskit sehingga kita beralih kepada anggaran fasa 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 cuba menggunakan QFT pada $|5\rangle$ sebagai contoh.

Pertama, kita sahkan notasi binari bagi integer 5 dan cipta Circuit yang mengekod keadaan 5:

bin(5)

'0b101'

qc = QuantumCircuit(3)

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

Kita semak keadaan kuantum menggunakan simulator Aer:

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

Akhirnya, kita tambah 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 dapat lihat fungsi QFT kita telah berfungsi dengan betul. Qubit 0 telah diputar sebanyak $\tfrac{5}{8}$ pusingan penuh, Qubit 1 sebanyak $\tfrac{10}{8}$ pusingan penuh (bersamaan dengan $\tfrac{1}{4}$ pusingan penuh), dan Qubit 2 sebanyak $\tfrac{20}{8}$ pusingan penuh (bersamaan dengan $\tfrac{1}{2}$ pusingan penuh).

2.5 Latihan: QFT

(1) Laksanakan QFT untuk 4 Qubit.

##your code goes here##

(2) Gunakan QFT pada $|14\rangle$, simulasikan dan plot vektor keadaan menggunakan sfera Bloch.

##your code goes here##

Penyelesaian 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. Asas Anggaran Fasa Kuantum (QPE)

Diberi operasi unitary $U$, QPE menganggar $\theta$ dalam $U\vert\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$ memandangkan $U$ adalah unitary, semua nilai eigennya mempunyai norma 1.

3.1 Prosedur

1. Persediaan

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

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

2. Superposisi

Guna operasi Gate Hadamard $n$-bit $H^{\otimes n}$ pada daftar pengiraan:

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

3. Operasi Unitary Terkawal

Kita perlu memperkenalkan unitary terkawal $CU$ yang menggunakan operator unitary $U$ pada daftar sasaran hanya jika bit kawalan yang sepadan adalah $|1\rangle$. Memandangkan $U$ adalah operator unitary dengan eigenvector $|\psi\rangle$ supaya $U|\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$, ini bermakna:

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

Mari kita gunakan Gate $T$ sebagai contoh QPE dan anggar fasa $\theta$ nya.

$$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 jangka untuk mendapat:

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

di mana

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

Kita mulakan $\vert\psi\rangle = \vert1\rangle$ bagi eigenvector Gate $T$ dengan menggunakan Gate $X$:

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

Seterusnya, kita guna Gate Hadamard pada Qubit pengiraan:

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

Kita lakukan operasi unitary terkawal:

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 guna transformasi Fourier kuantum songsang untuk menukar keadaan daftar pengiraan, kemudian ukur daftar pengiraan:

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 boleh 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 nampak kita dapat satu keputusan (001) dengan kepastian, yang diterjemahkan ke dalam perpuluhan: 1. Kita kini perlu bahagi keputusan kita (1) dengan $2^n$ untuk mendapat $\theta$:

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

Algoritma Shor membolehkan kita memfaktorkan nombor dengan membina Circuit di mana $\theta$ tidak diketahui dan mendapatkan $\theta$.

3.3 Latihan

Anggar $\theta = 1/3$ menggunakan 3 Qubit untuk pengiraan dan satu Qubit untuk eigenvector.

$P|1\rangle = e^{i\lambda}|1\rangle$. Memandangkan kita mahu melaksanakan $U|1\rangle = e^{2\pi i \tfrac{1}{3}}|1\rangle$, kita perlu tetapkan $\lambda = \tfrac{2 \pi}{3}$.

##your code goes here##

Penyelesaian 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. Pelaksanaan menggunakan primitif Sampler Qiskit Runtime

Kita akan melakukan QPE menggunakan peranti kuantum sebenar dan ikut 4 langkah corak Qiskit.

1. Petakan masalah ke format natif kuantum
2. Optimumkan Circuit
3. Laksanakan Circuit sasaran
4. Proses keputusan

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: Optimumkan untuk perkakasan sasaran

# 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: Laksanakan pada perkakasan sasaran

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 keputusan

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'