อัลกอริทึมควอนตัม: การประมาณเฟส

หมายเหตุ

Kento Ueda (15 พฤษภาคม 2024)

Notebook นี้อธิบายแนวคิดพื้นฐานและการนำไปใช้งานของ Quantum Fourier Transformation (QFT) และ Quantum Phase Estimation (QPE)

ดาวน์โหลด pdf ของเลคเชอร์ต้นฉบับ โปรดทราบว่าโค้ดบางส่วนอาจล้าสมัย เนื่องจากเป็นภาพนิ่ง

เวลา QPU โดยประมาณสำหรับการทดลองนี้คือ 7 วินาที

1. บทนำ

Quantum Fourier Transformation (QFT)

Quantum Fourier Transformation คือคู่เทียบเชิงควอนตัมของ discrete Fourier transform แบบคลาสสิก เป็นการแปลงเชิงเส้นที่กระทำกับสถานะควอนตัม โดยแมปฐาน computational ไปยังการแทนในฐาน Fourier QFT มีบทบาทสำคัญในอัลกอริทึมควอนตัมหลายตัว ด้วยการเป็นวิธีที่มีประสิทธิภาพในการดึงข้อมูลเกี่ยวกับความเป็นคาบจากสถานะควอนตัม QFT สามารถสร้างได้ด้วยการดำเนินการ $O(N^2)$ โดยใช้ Gate ควอนตัม เช่น Hadamard Gate และ Control-Phase Gate สำหรับ $N$ Qubit ซึ่งทำให้เร็วขึ้นแบบเลขชี้กำลังเมื่อเทียบกับ Fourier Transform แบบคลาสสิก

• การประยุกต์ใช้: เป็นส่วนพื้นฐานในอัลกอริทึมควอนตัมอย่างอัลกอริทึมของ Shor สำหรับการแยกตัวประกอบจำนวนเต็มขนาดใหญ่ และ discrete logarithm

Quantum Phase Estimation (QPE)

Quantum Phase Estimation คืออัลกอริทึมควอนตัมที่ใช้ประมาณค่าเฟสที่เชื่อมโยงกับ eigenvector ของ unitary operator อัลกอริทึมนี้เป็นสะพานเชื่อมระหว่างคุณสมบัติทางคณิตศาสตร์เชิงนามธรรมของสถานะควอนตัมกับการประยุกต์ใช้เชิงการคำนวณ

• การประยุกต์ใช้: สามารถแก้ปัญหาต่าง ๆ เช่น การหา eigenvalue ของเมทริกซ์ unitary และการจำลองระบบควอนตัม

QFT และ QPE ด้วยกันเป็นกระดูกสันหลังที่สำคัญของอัลกอริทึมควอนตัมหลายตัวที่แก้ปัญหาซึ่งคอมพิวเตอร์คลาสสิกทำไม่ได้ เมื่อจบ notebook นี้ คุณจะเข้าใจวิธีการนำเทคนิคเหล่านี้ไปใช้งาน

2. พื้นฐานของ Quantum Fourier Transformation (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

จากการเทียบเคียงกับ discrete Fourier transform QFT กระทำกับสถานะควอนตัม $\vert X\rangle = \sum_{j=0}^{N-1} x_j \vert j \rangle$ สำหรับ $N$ Qubit และแมปไปยังสถานะควอนตัม $\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$$

โดยที่ $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$

หรือในรูปแบบเมทริกซ์ 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. ความเข้าใจเชิงสัญชาตญาณ

Quantum Fourier Transform (QFT) แปลงระหว่างสองฐาน ได้แก่ ฐาน computational (Z) และฐาน Fourier แต่ฐาน Fourier หมายความว่าอะไรในบริบทนี้? คุณอาจจำได้ว่า Fourier transform $F(\omega)$ ของฟังก์ชัน $f(x)$ อธิบาย convolution ของ $f(x)$ กับฟังก์ชัน sinusoidal ที่มีความถี่ $\omega$ พูดง่าย ๆ คือ Fourier transform คือฟังก์ชันที่บอกว่าเราต้องการความถี่ $\omega$ แต่ละค่ามากเท่าใดในการสร้างฟังก์ชัน $f(x)$ จากฟังก์ชัน sine (หรือ cosine) เพื่อให้เข้าใจ QFT ในบริบทนี้ดียิ่งขึ้น ลองดูภาพด้านล่างที่แสดงตัวเลขที่เข้ารหัสในระบบไบนารีโดยใช้สี่ Qubit:

ในฐาน computational เราเก็บตัวเลขในรูปแบบไบนารีโดยใช้สถานะ $|0\rangle$ และ $|1\rangle$

สังเกตความถี่ที่ Qubit แต่ละตัวเปลี่ยนแปลง: Qubit ซ้ายสุดจะพลิกทุกครั้งที่ตัวเลขเพิ่มขึ้น ตัวถัดไปพลิกทุก 2 ครั้ง ตัวที่สามทุก 4 ครั้ง และต่อไปเรื่อย ๆ

ถ้าเราใช้ quantum Fourier transform กับสถานะเหล่านี้ เราจะแมป

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

(เรามักแทนสถานะในฐาน Fourier ด้วยเครื่องหมายทิลดา (~))

ในฐาน Fourier เราเก็บตัวเลขโดยใช้มุมหมุนรอบแกน Z ที่ต่างกัน:

IFRAME

ตัวเลขที่ต้องการเก็บจะกำหนดมุมที่ Qubit แต่ละตัวหมุนรอบแกน Z ในสถานะ $|\widetilde{0}\rangle$ Qubit ทุกตัวอยู่ในสถานะ $|{+}\rangle$ ดังที่เห็นในตัวอย่างข้างต้น เมื่อเข้ารหัสสถานะ $|\widetilde{5}\rangle$ บน 4 Qubit เราหมุน Qubit ซ้ายสุดด้วยมุม $\tfrac{5}{2^n} = \tfrac{5}{16}$ รอบเต็ม ($\tfrac{5}{16}\times 2\pi$ เรเดียน) Qubit ถัดไปหมุนเป็นสองเท่า ($\tfrac{10}{16}\times 2\pi$ เรเดียน หรือ $10/16$ รอบเต็ม) และมุมนี้ก็ถูกเพิ่มเป็นสองเท่าสำหรับ Qubit ถัดไปเรื่อย ๆ

อีกครั้ง สังเกตความถี่ที่ Qubit แต่ละตัวเปลี่ยนแปลง Qubit ซ้ายสุด (qubit 0) ในกรณีนี้มีความถี่ต่ำสุด และขวาสุดมีความถี่สูงสุด

2.2 ตัวอย่าง: QFT แบบ 1 Qubit

ลองพิจารณากรณี $N = 2^1 = 2$

เมทริกซ์ unitary เขียนได้เป็น:

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

การดำเนินการนี้เป็นผลจากการใช้ Hadamard Gate ($H$)

2.3 การแทนแบบผลคูณของ QFT

ลองสรุปการแปลงสำหรับ $N = 2^n$, $QFT_{N}$ ที่กระทำกับสถานะ $\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 ตัวอย่าง: การสร้าง Circuit QFT สำหรับ 3 Qubit

จากคำอธิบายข้างต้น อาจยังไม่ชัดเจนว่าจะสร้าง QFT Circuit ได้อย่างไร ขอให้สังเกตแค่ว่าเราคาดหวังให้สาม Qubit มีเฟสที่วิวัฒนาการในอัตรา "ต่างกัน" การทำความเข้าใจว่าสิ่งนี้แปลเป็น Circuit ได้อย่างไรนั้นเป็นแบบฝึกหัดสำหรับผู้อ่าน มีหลายไดอะแกรมและตัวอย่างใน pdf ของเลคเชอร์ แหล่งข้อมูลเพิ่มเติมได้แก่ บทเรียนนี้ จากคอร์ส Fundamentals of quantum algorithms

เราจะสาธิต QFT โดยใช้ simulator เท่านั้น จึงยังไม่ใช้ Qiskit patterns framework จนกว่าจะเข้าสู่ส่วน quantum phase estimation

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

ลองใช้ QFT กับ $|5\rangle$ เป็นตัวอย่าง

ก่อนอื่น เราตรวจสอบรูปแบบไบนารีของจำนวนเต็ม 5 และสร้าง Circuit ที่เข้ารหัสสถานะ 5:

bin(5)

'0b101'

qc = QuantumCircuit(3)

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

เราตรวจสอบสถานะควอนตัมโดยใช้ Aer simulator:

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

สุดท้าย เราเพิ่ม QFT และดูสถานะสุดท้ายของ Qubit:

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)

เราเห็นว่าฟังก์ชัน QFT ทำงานถูกต้อง Qubit 0 ถูกหมุน $\tfrac{5}{8}$ รอบเต็ม Qubit 1 หมุน $\tfrac{10}{8}$ รอบเต็ม (เทียบเท่า $\tfrac{1}{4}$ รอบ) และ Qubit 2 หมุน $\tfrac{20}{8}$ รอบเต็ม (เทียบเท่า $\tfrac{1}{2}$ รอบ)

2.5 แบบฝึกหัด: QFT

(1) นำ QFT ของ 4 Qubit ไปใช้งาน

##your code goes here##

(2) ใช้ QFT กับ $|14\rangle$ จำลองและพล็อต statevector โดยใช้ Bloch sphere

##your code goes here##

เฉลยแบบฝึกหัด: 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. พื้นฐานของ Quantum Phase Estimation (QPE)

กำหนดให้มี unitary operation $U$, QPE ประมาณ $\theta$ ใน $U\vert\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$ เนื่องจาก $U$ เป็น unitary eigenvalue ทุกตัวจึงมีขนาด 1

3.1 ขั้นตอน

1. การตั้งค่า

$\vert\psi\rangle$ อยู่ใน register ของ Qubit ชุดหนึ่ง มี Qubit เพิ่มเติม $n$ ตัวเป็น counting register สำหรับเก็บค่า $2^n\theta$:

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

2. Superposition

ใช้ $n$-bit Hadamard Gate $H^{\otimes n}$ กับ counting register:

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

3. การดำเนินการ Controlled Unitary

เราต้องนำ controlled unitary $CU$ มาใช้ ซึ่งจะใช้ unitary operator $U$ กับ target register เฉพาะเมื่อ control bit ที่สอดคล้องกันเป็น $|1\rangle$ เนื่องจาก $U$ เป็น unitary operator ที่มี eigenvector $|\psi\rangle$ โดยที่ $U|\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$ ดังนั้น:

$$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 ตัวอย่าง: QPE ของ T-gate

ลองใช้ $T$ gate เป็นตัวอย่างของ QPE และประมาณค่าเฟส $\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$$

เราคาดว่าจะพบ:

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

โดยที่

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

เราเริ่มต้น $\vert\psi\rangle = \vert1\rangle$ ของ eigenvector ของ $T$ gate โดยใช้ $X$ gate:

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

ถัดไป เราใช้ Hadamard Gate กับ counting Qubit:

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

เราดำเนินการ controlled unitary:

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

เราใช้ inverse quantum Fourier transformation เพื่อแปลงสถานะของ counting register จากนั้นวัดค่า counting register:

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

เราจำลองโดยใช้ Aer simulator:

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)

เราเห็นว่าได้ผลลัพธ์หนึ่งค่า (001) อย่างแน่นอน ซึ่งแปลงเป็นเลขฐานสิบได้: 1 ตอนนี้เราต้องหาร (1) ด้วย $2^n$ เพื่อให้ได้ $\theta$:

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

อัลกอริทึมของ Shor ช่วยให้เราแยกตัวประกอบตัวเลขได้โดยสร้าง Circuit ที่ $\theta$ ยังไม่ทราบค่าและหาค่า $\theta$ ออกมา

3.3 แบบฝึกหัด

ประมาณ $\theta = 1/3$ โดยใช้ 3 Qubit สำหรับการนับและ 1 Qubit สำหรับ eigenvector

$P|1\rangle = e^{i\lambda}|1\rangle$ เนื่องจากเราต้องการสร้าง $U|1\rangle = e^{2\pi i \tfrac{1}{3}}|1\rangle$ เราต้องตั้งค่า $\lambda = \tfrac{2 \pi}{3}$

##your code goes here##

เฉลยแบบฝึกหัด: $\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. การรันด้วย Qiskit Runtime Sampler Primitive

เราจะทำ QPE โดยใช้อุปกรณ์ควอนตัมจริงและทำตาม 4 ขั้นตอนของ Qiskit patterns

1. แมปปัญหาให้อยู่ในรูปแบบที่เหมาะกับควอนตัม
2. ปรับปรุง Circuit
3. รัน Circuit เป้าหมาย
4. ประมวลผลผลลัพธ์

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Sampler

# Loading your IBM Quantum® account(s)

service = QiskitRuntimeService()

4.1 ขั้นตอนที่ 1: แมปปัญหาไปยัง Circuit และ Operator ควอนตัม

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 ขั้นตอนที่ 2: ปรับปรุงสำหรับฮาร์ดแวร์เป้าหมาย

# 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 ขั้นตอนที่ 3: รันบนฮาร์ดแวร์เป้าหมาย

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 ขั้นตอนที่ 4: ประมวลผลผลลัพธ์

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'