มาทำความรู้จักกับ Deutsch — Jozsa Algorithm กัน

7 min readMar 23, 2022

Deutsch — Jozsa Algorithm คืออะไร เรามาทำความรู้จักกัน . . .

ความเป็นมา

Deutsch — Jozsa Algorithm ถูกพัฒนาและคิดค้นโดย David Deutsch และ Richard Jozsa ในปี 1992 ซึ่งเป็นอัลกอริทึมแรกของควอนตัมที่สามารถนำไปใช้ในการต่อยอดและใช้ในการเรียนรู้อัลกอริทึมที่ซับซ้อนของควอนตัมอัลกอริทึม (Quantum Algortihm) อื่น ๆ ได้ ที่อาจจะนำไปใช้ประยุกต์กับชีวิตประจำวันได้ยากไม่เหมือนกับอัลกอรึทึมชนิดอื่น ๆ

จุดประสงค์ของอัลกอริทึม

Deutsch — Jozsa Algorithm ใช้ในการแก้ไขปัญหาว่าฟังก์ชันที่เราตรวจสอบนั้น อยู่ในสถานะสมดุล (balanced) หรือ สถานะคงที่ (constant) หรือสามารถอธิบายในอีกความหมายนึงได้ว่าถ้าเรามีฟังก์ชันที่เป็นตัวเลขอยู่ที่มี n-bit เป็น input ที่หลังจากผ่านกระบวนการประมวลผลแล้วผลลัพธ์ที่ได้จะต้องออกมาไม่เป็น 0 หรือ 1 เท่านั้น

f : {0, 1}^n -> 0 or 1 หรือ f({x0, x1, x2, . . . , xn}) ->0 or 1 ที่ xn เป็น 0 หรือ 1

โดยที่สามารถเทียบจากตารางได้ดังนี้

วิธีการแก้ปัญหาแบบ Classical Computing

ในวิธีการแก้ไขปัญหาของฟังก์ชันดังกล่าวในรูปแบบของ Classical Computing หรือการประมวลผลทั่วไปในคอมพิวเตอร์ปัจจุบัน

สามารถเขียนเป็นโค้ดเบื้องต้นได้ดังนี้ :

if f(0) == 0:
  if f(1) == 0:   
     print("Constant")  
  else:    
     print("Balanced") 
else:  
  if f(1) == 0:   
     print("Balanced")  
  else:    
     print("Constant")

ซึ่งจะเห็นได้ว่าหากใช้วิธีการประมวลผลทั่วไปบน Classical Computing จะต้องใช้จำนวนรอบของการ evaluate ของ input หรือที่เรียกว่า query ทั้งหมด 2 ครั้ง ในกรณีที่ดีที่สุด (best case) และ 2^n-1 + 1 ครั้งในกรณีที่แย่ที่สุด (worst case) โดยที่ n คือจำนวนบิท

ที่ใน Quantum Computer จะใช้การ evaluate หรือ query เพียงแค่ 1 ครั้งเท่านั้น

วิธีการแก้ไขปัญหาแบบ Quantum Computing

จากที่กล่าวไปข้างต้น เราจะทำการแก้ไขปัญหาดังกล่าวโดยใช้วิธีการของ Deutsch-Jozsa Algorithm ซึ่งจะมีการนำ Quantum Circuit และความรู้เรื่อง Matrix มาใช้

FYI: Deutsch Algorithm จะแตกต่างจาก Deutsch — Jozsa Algorithm ตรงที่จะใช้การ evaluate 2 ครั้งใน n-bit แทนที่จะเป็นครั้งเดียว จึงทำให้ในปี 1992 Jozsa ได้เข้ามาช่วยพัฒนาอัลกอริทึมนี้ให้เป็นฟังก์ชันทั่วไปและสามารถรองรับ input ได้ n-bit

แก้ไขปัญหาโดยใช้ Linear Transformation

ก่อนอื่นจะทำการยกตัวอย่างให้อยู่ในรูปของการคำนวณโดยใช้ matrix ซึ่งกำหนดว่า ให้ใช้ f4 จากตารางที่เป็นสถานะคงที่ (constant) และมี |0>, |1> โดยจะให้เราหาค่า Nf ตามภาพ

จากตัวอย่างเราสามารถใช้ Linear transformation ในการแก้ไขปัญหาได้ ที่สุดท้ายแล้วเราจะได้คำตอบของ Nf อยู่ในรูปแบบของ matrix 4x4 ดังนี้

วิธีคำตอบของ Nf โดยใช้ Linear Transformation

แก้ไขปัญหาโดยใช้ Quantum Circuit

Quantum Circuit โดยใช้ Unitary Matrix ในการอธิบายฟังก์ชัน

ซึ่งสามารถใช้ Uf ในการย้อนค่าจาก |x, y⊗f(x)> ให้กลับมาเป็น |x, y> ได้ดังนี้

Quantum Circuit โดยใช้ Unitary Matrix 2 ครั้งในการย้อนค่าให้กลับมาเป็นค่าเดิม

คำถามคือ เราจะสามารถหา Uf ได้ยังไงละ 🤔

ซึ่งจะทำการหาค่าโดยใช้ Deutsch Algorithm อย่างเดียวก่อน

Quantum Oracle

ก่อนที่เราจะไปหาค่า Uf เรามาทำการรู้จักกับสิ่งที่เรียกว่า “Quantum Oracles” หรือ ผู้พยากรณ์(หมอดู)ควอนตัมกันดีกว่า

โดยที่ทุกคนรู้อยู่แล้วว่า Uf นั้นถูกสร้างขึ้นมาเรียบร้อยแล้ว และ เราทำการตั้งชื่อมันว่า “black-box” โดยที่สิ่งนี้นั้นสามารถเรียกอีกอย่างนึงได้ว่า “Quantum Oracles” ซึ่งจะมีคุณสมบัติต่าง ๆ ดังนี้

ถ้าเรากำหนดให้ x ถูกอัลกอริทึมวัดผลโดยใช้ f(x) ที่อยู่ใน black-box แต่เราไม่สามารถเห็นค่าข้างในของ black-box ได้และไม่รู้ว่า x จะแสดงค่าออกมาได้อย่างไร
จากข้อ 1) จึงทำให้เราไม่มีวิธีในการดูการทำงานของ Oracle function ได้เลย
ทำได้แค่ใส่ค่าบางค่าและถามคำตอบที่ได้จาก f(x) เท่านั้น

จากคุณสมบัติของ Quantum Oracles อาจจะทำให้บางคนยังงงอยู่ว่าคืออะไร งั้นเราไปดูวิธีการแก้ปัญหากันต่อดีกว่า 🚀

Deutsch’s Algorithm Solution

ก่อนทำการแก้ไขปัญหา เรามาย้อนเป้าหมายของอัลกอรึทึมนี้กันอีกรอบดีกว่า โดยที่เป้าหมายของอัลกอริทึมนี้คือ เมื่อเรากำหนดให้ f:{0,1} -> {0,1} ให้เราหาว่าฟังก์ชันนี้เป็นฟังก์ชันสมดุล (balanced) หรือ ฟังก์ชันคงที่ (constant) ซึ่งจะมี quantum oracle ใช้ในการแก้ไขปัญหานี้แต่เราไม่รู้เลยว่าการทำงานข้างในของอัลกอริทึมเป็นยังไง

ที่จะทำการยกตัวอย่างให้ input มีค่าเป็น |0> และ |1> โดยที่จะมี quantum circuit ดังนี้

1)เริ่มจาก |φ0⟩ จะได้ว่า

2)ต่อไป |φ1⟩ ทำการผ่าน Hadamard gate ทั้งสองคิวบิท จะได้ว่า

3)และ |φ2⟩ จะเป็นการผ่าน Uf ที่จะได้ว่า

เมื่อแทน f(x) แล้วสามารถแยกออกมาได้สองกรณีตามค่า f(x) ดังนี้

ที่จะเห็นว่าจากสองกรณีสามารถแยกออกมาให้เป็นรูปเดียวกันได้โดยทำการดึงตัวประกอบร่วมอย่าง (-1)^f(x) ออกมา

ทำการคูณ (-1)^f(x) กับ |x> จะได้ดังนี้

สุดท้ายสามารถเขียนออกมาให้เป็นสองกรณีอย่าง f เป็น constanst หรือ balanced ได้ดังนี้

4)สุดท้าย |φ3⟩ จะทำการใช้ Hadamard gate กับคิวบิทแรก จะได้ค่าดังนี้

ที่จะเห็นแค่ทำการวัดคิวบิทแรก เราก็สามารถแยกแยะได้ว่าฟังก์ชันนั้นสมดุลหรือคงที่ และเราทำได้ เพียงแค่ evaluate ฟังก์ชันเพียงครั้งเดียว

Deutsch — Jozsa’s Algorithm Solution

จากวิธีการแก้ไขปัญหาของ Deutsch Algorithm นั้นจะสามารถทำได้ในคิวบิทแค่ 2 ตัว แต่ใน Deutsch — Jozsa’s Algorithm สามารถทำได้ในคิวบิท n ตัว ที่จะมี Quantum Circuit ดังนี้

โดยที่จะมีวิธีการคำนวณดังนี้

1)ทำการเตรียม quantum register 2 ตัว โดยที่ตัวแรกจะเป็น n-qubit register ที่จะทำการกำหนดเป็น |0> และตัวที่สองเป็น one-qubit register ที่จะกำหนดเป็น |1>

2)ทำการใช้ Hadamard gate ในแต่ละคิวบิท

3)ทำการใช้ Uf หรือ Quantum Oracle |x⟩|y⟩ to |x⟩|y⊕f(x)⟩ ที่ x และ f(x) จะมีค่าได้แค่ 0 หรือ 1

4)ทำการใช้ Hadamard gate กับ first qubit register จะได้

ที่ x⋅y=x0y0 ⊕ x1y1 ⊕ … ⊕ xn−1 yn−1 คือผลรวมของ bitwise product

5)สุดท้ายทำการวัด (measure) ผลลัพธ์ ที่จะได้ความน่าจะเป็นของการวัดดังนี้

ที่หากได้ผลลัพธ์เป็น 0 แสดงว่า f(x) เป็นฟังก์ชันคงที่ (constant) และหากได้ผลลัพธ์เป็น 1แสดงว่า f(x) เป็นฟังก์ชันสมดุล (balanced)

การคำนวณหา Uf

ดังนั้นจากการคำนวณเบื้องต้นเราสามารถใช้เทคนิคนี้ในการหาค่า Uf ได้

ที่เราจะทำการยกตัวอย่างจาก f4 เช่นเดิม ซึ่งเมื่อทำการคำนวณแล้วจะได้ดังนี้ โดยจะแบ่งออกเป็น 2 รูปแบบ คือ big endian และ little endian

big endian เป็นการเก็บข้อมูลที่มากก่อน จะเป็นการเรียงจากซ้ายไปขวาหรือเป็นระบบทั่วไปที่เราใช้ในปัจจุบัน เช่น |01> จะได้ว่า x = 0, y = 1 หรือเรียงเป็นคำแบบ LOVE
little endian เป็นการเก็บข้อมูลที่น้อยก่อน จะเป็นการเรียงจากขวาไปซ้ายหรือเป็นระบบตรงข้ามที่เราใช้ในปัจจุบัน เช่น |01> จะได้ว่า x=1, y=0 หรือเรียงเป็นคำแบบ EVOL

ที่จะสามารถแสดงวิธีทำได้ดังนี้

FYI: ⊕ คือเครื่องหมายของ XOR Operator ถ้า bit มีค่าเหมือนกันผลลัพธ์จะได้ 0 และถ้า bit มีค่าต่างกันผลลัพธ์จะได้ 1 เช่น 0⊕1 = 1 และ 0⊕0 = 0

จะเห็นได้ว่าเท่านี้เราก็สามารถหาค่า matrix ของ black-box หรือ quantum oracle ได้แล้ว โดยทำการหาค่า Uf จากสมการคณิตศาสตร์ข้างต้นเท่านั้นเอง

โดยที่ต่อไปเราจะทำการนำสมการเหล่านี้มา implement ให้อยู่ในรูปแบบของ quantum circuit เพื่อที่จะทำให้เห็นภาพได้ชัดมากยิ่งขึ้นและไม่ต้องเสียเวลาในการคำนวณผลลัพธ์ 🥸

Qiskit Implementation

หลังจากที่เราทำการคำนวณหาค่า Uf มาได้แล้วทีนี้ วิธีการที่เราจะสร้าง Quantum Circuit ในการหาว่าฟังก์ชันนั้นเป็นฟังก์ชันคงที่ (constant) หรือ ฟังก์ชันสมดุล (balanced) มีอยู่ด้วยกันสองวิธี ดังนี้

ถ้าหากสุดท้ายแล้ว f(0) = f(1) หรือได้ผลลัพธ์เป็น 0 แสดงว่าเป็นฟังก์ชันคงที่
แต่ถ้า f(0) ≠ f(1) หรือได้ผลลัพธ์เป็น 1แสดงว่าเป็นฟังก์ชันสมดุล

วิธีที่ 1: ทำการแทนค่า Uf ที่หาค่าได้จากการคำนวณลงในโค้ดในการสร้างเป็น black-box ได้เลย

ใน qiskit นั้นเราสามารถสร้าง black-box หรือ quantum oracle ได้เองเลยถ้าหากเราไม่รู้ว่าจะทำการสร้าง quantum gate ยังไง

โดยที่จะทำการใช้คำสั่ง Operator([]) แล้วทำการใส่ค่า matrix ที่เราได้จากการคำนวณลงไปในคำสั่งได้เลย ตัวอย่างเช่น

uf4_little = Operator([
    [0, 0, 1, 0],
    [0, 0, 0, 1],
    [1, 0, 0, 0],
    [0, 1, 0, 0]])

ที่ต่อไปนั้นเราจะทำการสร้าง Quantum Circuit ขึ้นมา

เริ่มจากทำการ import library ต่าง ๆ :

#initialization
import matplotlib.pyplot as plt
%matplotlib inline
import numpy as np# importing Qiskit
from qiskit import IBMQ, BasicAer
from qiskit.providers.ibmq import least_busy
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister, execute
from qiskit.quantum_info.operators import Operator# import basic plot tools
from qiskit.tools.visualization import plot_histogram

ทำการสร้าง Quantum Circuit :

# Creating registers
qr = QuantumRegister(2)
# classical registers for recording the measurement on qr
cr = ClassicalRegister(2)deuCircuit = QuantumCircuit(qr, cr)
barriers = True# initialize the ancilla qubit in the |1> state
deuCircuit.x(qr[1])# Apply barrier 
if barriers:
 deuCircuit.barrier()# Apply Hadamard gates before querying the oracle
deuCircuit.h(qr[0]) 
deuCircuit.h(qr[1])# Apply barrier 
if barriers:
 deuCircuit.barrier()#Apply quantum oracle
# Build your gate with Operator and unitary function# ===== f4 =====
uf4_little = Operator([
 [0, 0, 1, 0],
 [0, 0, 0, 1],
 [1, 0, 0, 0],
 [0, 1, 0, 0]])# ===== little endian =====
deuCircuit.unitary(uf4_little, [qr[0], qr[1]], label='Uf4_little') 

# Apply barrier 
if barriers:
    deuCircuit.barrier()# Apply Hadamard gates after querying the oracle
deuCircuit.h(qr[0])# Measure the input qubit
deuCircuit.measure(qr[0], cr[0])deuCircuit.draw(output='mpl')

เราสามารถสลับ qubit ได้โดยการใช้
deuCircuit.unitary(uf4_little, [qr[0], qr[1]], label=’Uf4_little’)

ต่อไปจะทำการนำ Quantum Circuit ที่เราสร้างมาใช้ในการหาว่า function ที่เราใช้อยู่นั้นเป็น ฟังก์ชันคงที่ (constant) หรือ ฟังก์ชันสมดุล (balanced)

โดยสามารถใช้คำสั่งตามนี้ได้ :

# use local simulator
backend = BasicAer.get_backend('qasm_simulator')
shots = 1024
results = execute(deuCircuit, backend=backend, shots=shots).result()
answer = results.get_counts()# categorize answers to c0 = 0 and c0 = 1
answer_c0 = {}
for c1c0 in answer:
    print('c0 = {} ({} shots)'.format(c1c0[1], answer[c1c0]))if c1c0[1] in answer_c0:
        answer_c0[c1c0[1]] += answer[c1c0]
    else:
        answer_c0[c1c0[1]] = answer[c1c0]plot_histogram(answer_c0)

ผลลัพธ์ทีได้จาก Quantum Circuit โดยทำการทดสอบทั้งหมด 1024 รอบ

จะเห็นได้ว่าคำตอบที่ออกมานั้นจะได้ค่า = 0 จึงทำให้แสดงว่า f4 นั้นเป็นฟังก์ชันคงที่เพราะ f(0) = f(1) นั่นเอง ซึ่งก็จะตรงกับตารางที่อธิบายไปข้างต้น 👏🏻

วิธีที่ 2: ทำการสร้าง black-block หรือ quantum oracle ให้ออกมาอยู่ในรูปแบบของ quantum gate

ต่อไปเราจะทำการใช้ Quantum Gate ในการสร้าง Quantum Oracle หรือ black-box แทน ซึ่งจากที่เราทราบจากการคำนวณข้างต้นจะเห็นว่าทำการใช้ ⊕ หรือก็คือ XOR ที่ใน qiskit หรือ quantum circuit จะมี gate นึงที่ทำหน้าที่คล้าย XOR นั่นก็คือ “CNOT Gate”

โดยที่ในเราจะทำการดูจากตาราง f2 จะเห็นว่าความสัมพันธ์นั้นเหมือนกับ XOR เลยจากภาพ

ดังนั้นเราจะทำการใช้ CNOT gate กับตาราง f2 ดังนี้ :

# Creating registers
qr = QuantumRegister(2)
# classical registers for recording the measurement on qr
cr = ClassicalRegister(2)deuCircuit = QuantumCircuit(qr, cr)
barriers = True# initialize the ancilla qubit in the |1> state
deuCircuit.x(qr[1])# Apply barrier 
if barriers:
    deuCircuit.barrier()# Apply Hadamard gates before querying the oracle
deuCircuit.h(qr[0])    
deuCircuit.h(qr[1])# Apply barrier 
if barriers:
    deuCircuit.barrier()#Apply quantum oracle
# Build your gate with Quantum Gate
deuCircuit.cx(qr[0], qr[1])# Apply barrier 
if barriers:
    deuCircuit.barrier()# Apply Hadamard gates after querying the oracle
deuCircuit.h(qr[0])# Measure the input qubit
deuCircuit.measure(qr[0], cr[0])deuCircuit.draw(output='mpl')

และทำการวัดค่าที่ได้ออกมาจะได้ดังนี้ :

ที่จะเห็นว่าสุดท้ายแล้วจะสามารถวัดได้มีค่าเท่ากับ 1 หรือหมายความว่า f2 นั้นเป็นฟังก์ชันสมดุล (balanced) นั่นเอง

ส่วนฟังก์ชันคงที่ (constant) นั้นสามารถทำได้ดังนี้
หาก f(x) = 0 ให้ใช้ I gate ลงบน quantum register ตัวที่ 2
หาก f(x) = 1 ให้ใช้ X gate ลงบน quantum register ตัวที่ 2

เท่านี้เราก็สามารถใช้ Quantum Circuit ในการหาว่าฟังก์ชันนี้อยู่ในสถานะใดได้แล้ว 🥳 ส่วนใน Deutsch — Jozsa Algorithm นั้นก็อยู่ในรูปแบบใกล้เคียงกันเพียงแค่ทำการเพิ่ม qubit นั่นเอง

สรุป

สุดท้ายนี้จะขอทำการสรุปอีกรอบนึง โดยที่ Deutsch — Jozsa Algorithm คือการหาว่า ฟังก์ชันที่เราตรวจสอบนั้น อยู่ในสถานะสมดุล (balanced) หรือ สถานะคงที่ (constant) โดยสามารถใช้วิธีการได้หลายวิธี ไม่ว่าจะเป็นวิธีการทางคณิตศาสตร์ในการพิสูจน์จากสมการข้างต้น หรือ จะใช้ Quantum Circuit ในการประมวลผลหรือคิดแทนนั่นเอง

โดยที่บางคนอาจจะสงสัยว่าอัลกอริทึมนี้นั้นเรียนไปเพื่ออะไร สาเหตุที่เราควรศึกษาอัลกอริทึมนี้เพราะว่าอัลกอริทึมนี้จะเป็นวิธีพื้นฐานในการคิดค้นอัลกอริทึมอื่น ๆ ทางควอนตัมที่มีความซับซ้อนได้ หรือแม้แต่จะเห็นว่าหากเรานำอัลกอริทึมนี้ไปคิดใน classical computer นั้นจะใช้การประมวลผล 2 query แต่ใน quantum computer นั้นใช้เพียง 1 query เท่านั้น นี่ก็อาจจะเป็นอีกหนึ่งอัลกอริทึมที่สามารถพิสูจน์เบื้องต้นได้ว่า quantum computer นั้นมีการประมวลผลที่รวดเร็วกว่า classical computer โดยอาศัยหลักการของ superposition นั่นเอง 🚀🤓

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

Happy Coding & Learning Quantum 😁