Shor’s Algorithm [Part 2]

5 min readJun 29, 2022

มาดูกันดีกว่าว่าเราสามารถนำ Quantum Computing มาปรับใช้ยังไงได้บ้าง …

จากบทความที่ผ่านมา [Part 1] นั้นในบทความนี้จะเป็นการนำความรู้จากบทความก่อนมาปรับใช้ ดังนั้นถ้าใครยังไม่เคยอ่านบทความก่อนสามารถอ่านได้เลยครับ 😄

Shor’s Algorithm [Part 1]

มาทำความรู้จักกับหนึ่งในอัลกอริทึมที่คนที่ศึกษาควอนตัมคอมพิวเตอร์ต้องรู้จัก . . .

ksupasate.medium.com

เกริ่นนำ

จากบทความที่ผ่านมา ถ้าจะให้สรุปสั้น ๆ ของเป้าหมายของ Shor’s Algorithm คือ ขั้นตอนในการแยกตัวประกอบของจำนวนเต็ม ที่มีประสิทธิภาพและมีความเร็วอย่างมากบน Quantum Computer นั่นเอง

โดยที่ในบทความนี้จะนำหลักการของบทความที่แล้วมาประยุกต์เข้ากับความรู้ในเรื่องของ Quantum Fourier Transform (QFT) นั่นเอง

Quantum Fourier Transform

Fourier Transform นั้นหลายคนอาจจะเคยได้ยินจากวิชา Calculus หรือคณิตศาสตร์ขั้นสูงมากมายในระดับมหาวิทยาลัย โดยที่ Fourier Transform นั้นเกิดขึ้นมากมายกับการประมวลผลต่าง ๆ บน classical computer ตั้งแต่การประมวลผลของ signals ไปจนถึงการบีบอัดข้อมูล (data compression) หรือแม้แต่ในทฤษฎีที่มีความซับซ้อน

ซึ่ง Quantum Fourier Transform หรือ QTF นั้นจะใช้การ implement ของ quantum ในการแปลง discreate Fourier หรือฟูริเยร์แบบไม่ต่อเนื่อง อยู่เหนือ amplitude ของฟังก์ชันคลื่นนั่นเอง โดยที่หลักการนี้นั้นนิยมนำไปใช้อย่างมากบนควอนตัมอัลกอริทึม โดยเฉพาะ Shor’s Algorithm ที่มีการนำส่วนนี้มาประยุกต์ใช้เพื่อเพิ่มประสิทธิภาพ

โดยที่ QTF นั้นสามารถใช้ในการแปลงจำนวน N ที่มีขนาดใหญ่มาก ๆ ให้เหลือขนาด 2^n ได้ ตามสมการด้านล่าง

สมการของการแปลงค่า N ให้มีขนาดเท่ากับ 2^n โดยใช้ QTF

ซึ่งเราสามารถ implement หลักการของ Quantum Fourier Transform นี้ให้อยู่ในรูปแบบของ Quantum Circuit ได้ดังนี้

โดยที่ทุกคนสามารถศึกษารายละเอียดเพิ่มเติมและเชิงลึกเกี่ยวกับ QTF ได้ที่นี่:
Quantum Fourier Transform (qiskit.org)

การนำความรู้ทั้งหมดมาประยุกต์ใช้ด้วยกัน

จากบทความที่แล้วนั้นจะเห็นได้ว่าหนึ่งในปัญหาของ Shor’s Algorithm นั่นก็คือการหาคาบที่เกิดจากฟังก์ชัน (period) หรือจะสามารถบอกได้ว่าปัญหาของการหาตัวประกอบ (factoring problem) นั้นสามารถเปลี่ยนเป็นการหาคาบที่เกิดจากฟังก์ชัน (period problem) แทนได้ใน polynomial time

ดังนั้นหากอัลกอริทึมที่ใช้ใน การหาคาบที่เกิดจากฟังก์ชันนั้นมีประสิทธิภาพ จะสามารถนำไปใช้ใน การหาตัวประกอบของจำนวนเต็มได้อย่างมีประสิทธิภาพ เช่นกัน หรือหากพูดในเชิงคณิตศาสตร์ก็จะได้ว่า หากเราสามารถหาคาบของ a^x mod N ได้อย่างมีประสิทธิภาพก็จะสามารถนำไปใช้ในการหาตัวประกอบได้อย่างมีประสิทธิภาพได้เช่นกัน

ทบทวนปัญหากันอีกสักรอบ

จากฟังก์ชันคาบ: f(x) = a^x mod N ที่ a และ N นั้นเป็นจำนวนบวก และ a<N และไม่มีตัวประกอบร่วม ซึ่งคาบหรือ r นั้นจะมีค่าน้อยที่สุด (ไม่เท่ากับ 0) เช่น a^r mod N = 1

โดยสามารถดูตัวอย่างด้วยการพล็อตกราฟได้ที่ด้านล่างนี้ (เส้นที่ลากนั้นใช้ในการดูคาบไม่ได้แสดงถึงค่ากลางระหว่างจุด x)

ตัวอย่างของฟังก์ชันคาบใน Shor’s Algorithm

Solution

วิธีการแก้ปัญหานั้นจะทำการใช้หลักการของ Quantum Phase Estimation (QPE) ที่มีการนำ QTF เข้ามาเกี่ยวข้องด้วย

โดยสามารถเขียน unitary operator ได้ดังนี้ : U|y> = |ay mod N>ที่หากเรามาดูที่ค่า U โดยทำการเริ่มที่ state |1> จะเห็นได้ว่าจำนวนของ successive application ของ U จะถูกคูณด้วย state ของ register ด้วย a(mod N) เสมอ และเมื่อผ่านไป r รอบ จะเห็นได้ว่าจะกลับมาที่ state |1> อีกครั้ง

ยกตัวอย่าง: a = 3 และ N = 35

หรือสามารถพล็อตกราฟให้เห็นภาพชัดมากยิ่งขึ้นได้ดังนี้

นำสมการข้างต้นของตัวอย่างมาพล็อตเป็นกราฟเพื่อทำให้มองง่ายมากยิ่งขึ้น

ขั้นตอนต่อไปจะเป็นการทำ superposition ของ state นี้ใน cycle ของ (|u0>) ที่จะทำให้เป็น eigenstate ของ U ดังนี้

เมื่อทำการยกตัวอย่างเดิมและแทนค่าไปจะได้ดังนี้

โดยที่เมื่อ eigenstate นั้นมีค่าของ eigenvalue ของ 1 นั้นเป็นค่าที่น่าสนใจและไม่ต้องการ ดังนั้น eigenstate ที่น่าสนใจกว่านั้นอาจจะเป็นช่วงที่ เฟส (phase) แตกต่างกันในแต่ละ computational basis states โดยเฉพาะอย่างยิ่ง เมื่อมาดู phase ของลำดับที่ k state จะได้ค่าดังนี้

และเมื่อทำการแทนค่าด้วยตัวอย่างเดิมจะได้ว่า

ที่จะเห็นได้ว่า r = 12 จะโผล่ในตัวส่วนของ phase

จึงทำให้นี่มีค่าของ eigenvalue ที่น่าสนใจเพราะประกอบด้วยค่า r ด้วย ซึ่งในความเป็นจริงจะต้องทำการรวม r ไว้ด้วยเพื่อทำให้มั่นใจว่าความแตกต่างของ เฟส (phase) ระหว่าง computational basis state นั้นจะมีค่าเท่ากัน

นี่ไม่ใช่เฉพาะ eigenstate ที่มีพฤติกรรมเหล่านี้ โดยที่เราสามารถคูณด้วยจำนวนเต็ม s สำหรับความแตกต่างของเฟสนี้ ซึ่งจะทำการแสดง eigenvalue ของเราออกมา ดังนี้

สามารถแทนค่าจากตัวอย่างเก่าได้อีกเช่นเคยจะได้

โดยที่ตอนนี้เราจะได้ค่า eigenstate เฉพาะสำหรับแต่ละค่าของจำนวนเต็มแล้ว โดยที่: 0 ≤ s ≤ r-1 ซึ่งหากเราทำการหาผลรวมของ eigenstate เหล่านี้ ความแตกต่างของ เฟส (phase) จะทำการยกเลิก computational basis state ยกเว้น |1> ดังนี้

สุดท้ายนี้หากเราทำการแทนค่าด้วยตัวอย่างนี้ โดยที่: a=7, N=15 และ r=4 จะได้ค่าดังนี้

ซึ่งจะเห็นได้ว่า computational basis state ของ |1> นั้นจะเป็น superposition ของ eigenstate เหล่านี้ หรือ หมายความว่า หากเราทำการใช้ QPE บน U โดยใช้ state |1> เราจะทำการวัด phase ได้ดังนี้:

โดยที่ s คือตัวเลขสุ่มระหว่าง 0 ถึง r-1 แล้วสุดท้ายเราก็จะสามารถใช้ continued fractions algorithm กับ ϕ ในการหาค่า r ได้

ที่ Quantum Circuit จะมีหน้าตาประมาณนี้:

Code Implementation on QISKIT

โดยที่ตัวอย่างนี้นั้นจะกำหนดค่าต่าง ๆ ดังนี้: a=7 และ N=15 โดย U มีค่าเท่ากับสมการ U|y> = |ay mod 15>

ซึ่งสามารถทำตามโค้ดตัวอย่างได้ดังนี้:

import library ที่ใช้งาน

import matplotlib.pyplot as plt
import numpy as np
from qiskit import QuantumCircuit, Aer, transpile, assemble
from qiskit.visualization import plot_histogram
from math import gcd
from numpy.random import randint
import pandas as pd
from fractions import Fraction
print(“Imports Successful”)

2. สร้างฟังก์ชัน c_amod15 สำหรับการคืนค่าเกท U ที่ควบคุมด้วยเวลา a

def c_amod15(a, power):
 “””Controlled multiplication by a mod 15"””
 if a not in [2,4,7,8,11,13]:
 raise ValueError(“‘a’ must be 2,4,7,8,11 or 13”)
 U = QuantumCircuit(4) 
 for iteration in range(power):
 if a in [2,13]:
 U.swap(0,1)
 U.swap(1,2)
 U.swap(2,3)
 if a in [7,8]:
 U.swap(2,3)
 U.swap(1,2)
 U.swap(0,1)
 if a in [4, 11]:
 U.swap(1,3)
 U.swap(0,2)
 if a in [7,11,13]:
 for q in range(4):
 U.x(q)
 U = U.to_gate()
 U.name = “%i^%i mod 15” % (a, power)
 c_U = U.control()
 return c_U

3. ทำการกำหนด counting qubits ในที่นี่จะทำการกำหนดให้เท่ากับ 8

# Specify variables
n_count = 8 # number of counting qubits
a = 7

4. ทำการสร้าง circuit สำหรับ QTF

def qft_dagger(n):
 “””n-qubit QFTdagger the first n qubits in circ”””
 qc = QuantumCircuit(n)
 # Don’t forget the Swaps!
 for qubit in range(n//2):
 qc.swap(qubit, n-qubit-1)
 for j in range(n):
 for m in range(j):
 qc.cp(-np.pi/float(2**(j-m)), m, j)
 qc.h(j)
 qc.name = “QFT†”
 return qc

5. ทำการสร้าง circuit สำหรับ Shor’s Algorithm

# Create QuantumCircuit with n_count counting qubits
# plus 4 qubits for U to act on
qc = QuantumCircuit(n_count + 4, n_count)# Initialize counting qubits
# in state |+>
for q in range(n_count):
 qc.h(q)
 
# And auxiliary register in state |1>
qc.x(3+n_count)# Do controlled-U operations
for q in range(n_count):
 qc.append(c_amod15(a, 2**q), 
 [q] + [i+n_count for i in range(4)])# Do inverse-QFT
qc.append(qft_dagger(n_count), range(n_count))# Measure circuit
qc.measure(range(n_count), range(n_count))
qc.draw(fold=-1) # -1 means ‘do not fold’

6. ทำการวัดผลลัพธ์ออกมา (measure)

aer_sim = Aer.get_backend(‘aer_simulator’)
t_qc = transpile(qc, aer_sim)
qobj = assemble(t_qc)
results = aer_sim.run(qobj).result()
counts = results.get_counts()
plot_histogram(counts)

7. เนื่องจากเรามี 8 คิวบิต ผลลัพธ์เหล่านี้จึงสอดคล้องกับเฟสที่วัดได้จากโค้ดด้านล่าง

rows, measured_phases = [], []
for output in counts:
 decimal = int(output, 2) # Convert (base 2) string to decimal
 phase = decimal/(2**n_count) # Find corresponding eigenvalue
 measured_phases.append(phase)
 # Add these values to the rows in our table:
 rows.append([f”{output}(bin) = {decimal:>3}(dec)”, 
 f”{decimal}/{2**n_count} = {phase:.2f}”])
# Print the rows in a table
headers=[“Register Output”, “Phase”]
df = pd.DataFrame(rows, columns=headers)
print(df)

8. สุดท้ายนี้สามารถใช้ Fractions Algorithm ในการหาค่า s และ r ได้ดังนี้ (Fraction เป็นฟังก์ชัน built-in ของ python)

rows = []
for phase in measured_phases:
 frac = Fraction(phase).limit_denominator(15)
 rows.append([phase, f”{frac.numerator}/{frac.denominator}”, frac.denominator])
# Print as a table
headers=[“Phase”, “Fraction”, “Guess for r”]
df = pd.DataFrame(rows, columns=headers)
print(df)

โดยที่หากทำการรันโค้ดข้างบนทั้งหมด จะเห็นได้ว่า ค่าของ eigenvalues สองค่าที่เราทำการวัด (measure) นั้นจะให้ค่าที่ถูกต้องกับเรา โดยที่ r = 4

แต่จะเห็นได้ว่า Shor’s Algorithm นั้นยังมีโอกาสผิดพลาดเพราะ ยังมีบางครั้งที่ได้ค่า s = 0 หรือเพราะว่า s และ r ไม่ใช่ coprime แทนที่ r ควรจะเป็น

ดังนั้นทางออกที่ง่ายที่สุดคือทำการทำการทดลองซ้ำ ๆ จนกว่าจะได้ผลลัพธ์ที่น่าพอใจสำหรับค่าของ r นั่นเอง 😅

สรุป

จากบทความทั้งหมดนี้จะเห็นได้ว่าเราสามารถนำความรู้ทางด้าน Quantum Fourier Transform (QTF) มาปรับใช้กับ Shor’s Algorithm ได้ ที่จะมีการนำความรู้ของ Quantum Phase Estimation (QPE) มาใช้อีกด้วย

ซึ่งจาก [Part 1] จะเห็นได้ว่าการหาฟังก์ชันคาบนั้นเป็นสิ่งที่หาได้ยากมาก ดังนั้นหากอัลกอริทึมที่ใช้ใน การหาคาบที่เกิดจากฟังก์ชันนั้นมีประสิทธิภาพ จะสามารถนำไปใช้ใน การหาตัวประกอบของจำนวนเต็มได้อย่างมีประสิทธิภาพ เช่นกัน

จึงทำให้บทประยุกต์จากความรู้ทั้งสองเรื่องนี้อย่าง QTF และ QPE สามารถนำมาปรับใช้กับ Shor’s Algorithm ได้เป็นอย่างดี

สุดท้ายนี้นี่เป็นแค่ส่วนหนึ่งของ Shor’s Algorithm ที่ในปัจจุบันมีคนนำแนวคิดนี้ไปปรับใช้มากมายและความรู้ของ QTF และ QPE นั้นก็เป็นส่วนสำคัญเช่นกัน ดังนั้นถ้าใครอยากเรียนรู้เพิ่มเติมสามารถตามลิงก์จาก Reference ข้างล่างได้เลย 🤓

สุดท้ายนี้หากชื่นชอบโพสนี้ก็อย่าลืมแชร์และแบ่งปันความรู้ทางด้านควอนตัมต่อเนื่องให้กับคนอื่น ๆ ด้วยนะครับ ขอบคุณทุกคนที่อ่านถึงจุดนี้ครับ :)

Happy Coding & Learning Quantum 😁