Grover’s algorithm
วันก่อนนินชวนมาฟังงาน quantum computing แล้วไปสะดุดกับการทดลองเรื่อง Grover’s algorithm ที่น้อง ๆ ทำมา หลัก ๆ Grover เป็น iterative algorithm ในการหาของ ตอนแรกผมเข้าใจว่าทำวนแต่ละรอบความน่าจะเป็นของตัวที่ต้องการหาจะสูงขึ้นไปเรื่อย ๆ แต่จากที่น้องทำมากลายเป็นว่าพอวนมากรอบความน่าจะเป็นกลับต่ำลงแทน ทำให้งง ๆ เลยหามาอ่านหน่อย
โจทย์: การค้นหาของ
โจทย์หลัก ๆ ของ Grover คือการค้นหาของ สมมติว่า
- เรามีของอยู่ N อย่าง เราสามารถเขียน “index” ของของเหล่านี้ในรูปของ n-bit โดยที่ N = 2^n
- มีของอย่างเดียวที่เราต้องการ นั่นคือ สมมติว่าเรามีฟังก์ชัน f ที่ มีตัวแปร n-bit ω ตัวเดียวที่ f(ω)=1 และสำหรับตัวแปร n-bit x อื่น ๆ f(x)=0
หากเป็นคอมพิวเตอร์ทั่วไปเราสามารถหา ω ได้โดยการ generate ตัวแปร n-bit และทดสอบทีละตัวดังนั้น complexity ก็จะ O(N)
ในกรณีของควอนตัม เราจะทำงานกับ “qubit” และใช้ประโยชน์จาก “super-position” ในการเร่งการคำนวณ
เท่าที่เข้าใจพวกอัลกอริทึมควอนตัมเริ่มจากการ initialize qubit ต่าง ๆ ให้ระบบโดยรวมอยู่ในสถานะ uniform superposition โดยใช้ Hadamard gate
สถานะของระบบโดยรวมคือ
หลัก ๆ แล้ว Grover’s algorithm จะทำให้ amplitude ของคำตอบ ω เด่นขึ้นจากตัวแปร n-bit อื่น ๆ จนเมื่อเราทำการวัดหลาย ๆ ครั้ง จำนวนครั้งที่ state “ฟุบ (collapse)” ลงมาที่ ω มากกว่าคำตอบอื่น
Steps ของ Grover’s
- สมมติว่าเรามีวงจรควอนตัม F (ทดไว้ก่อน วันหลังค่อยดูว่าทำไง) ที่สามารถ “flip” amplitude ของ ω ได้ นั่นคือ
จะเห็นว่ามีเพียง amplitude ของคำตอบที่ถูก flip ตัวแปรอื่น ๆ ยังคงที่
- จากนั้นสมมติว่าเรามีวงจรควอนตัม D (ทดไว้ก่อนเช่นกัน) ที่หาก α(x) เป็น alplitude ของ x ใด ๆ แล้ว D ทำการ “diffuse” amplitude โดย
โดยที่ μ คือค่าเฉลี่ยของ amplitude นั่นคือ
- อัลกอริทึมของ Grover จะทำการ flip และ diffuse สลับกันไปเรื่อย ๆ
- ลองทำรอบแรก
ดังนั้นเมื่อนำ initial state |s> ไปผ่าน D แล้ว amplitude ของ x ใด ๆ จะค่อนข้างคงที่ ส่วน alplitude ของ ω จะกลายเป็น ~3/sqrt(N) ซึ่งใหญ่ขึ้น (แบบฝึกหัด)
หากเราทำซ้ำรอบ 2 alplitude ของ ω จะกลายเป็น ~5/sqrt(N) ซึ่งใหญ่ขึ้นอีก
นั้นคือการทำ flip+diffuse ซ้ำไปเรื่อย ๆ จะทำให้ alplitude ของตัวแปร n-bit ω ที่เราสนใจนั้นใหญ่ขึ้นเรื่อย ๆ จนสุดท้านหากเราทำการวัด (measurement) ค่าที่วัดได้สูงสุดก็น่าจะตรงกับ ω นั่นเอง
ปัญหาที่เจอและจำนวน Grover’s steps
การที่เราทำ flip+diffuse ไปเรื่อย ๆ แล้วผลแย่ลงอาจจะมาจากการที่เมื่อ amplitude ของ ω ใหญ่มากๆๆๆเมื่อเทียบกับ x อื่น ๆ อาจทำให้ค่า μ นั้นติดลบได้ ซึ่งในกรณีนี้จะทำให้ amplitude ของ ω หลังจาก diffusion นั้นลดลงแทน ผลเลยแย่ลง จริง ๆ มีคนบอกอีกว่า Grover’s algorithm มีพฤติกรรมแบบ periodic คือจะกลับมาดีได้อีก คงต้องไปอ่านเพิ่มวันหลัง
ถ้าตามบทความใน [1] จริงๆ แล้วเราพอจะคำนวณ bound การเปลี่ยนแปลงของ amplitude ของ ω ในแต่ละรอบได้ เช่น หากให้ α(ω,t) แทน amplitude ของคำตอบ ω ในรอบ t เราจะได้ว่า
- α(ω,t+1) ≥ α(ω,t) + 1/√N หรือ α(ω,t+1) ≥ α(ω,0) + t/√N เมื่อ α(ω,t) < 1/2
- α(ω,t+1) ≤ α(ω,t) + 2/√N หรือ α(ω,t+1) ≤ α(ω,0) + 2t/√N
จาก bound นี้เราพอจะคำนวณจำนวนครั้งของ Grover’s step ได้ เช่น หากเรามีของมากกว่า 16 ชิ้น (N>16) หาก t<√N/8 จะได้ว่า α(ω,t+1) ≤ α(ω,0) + 2/8 ≤ 1/√N + 1/4 <1/2 ทำให้เราสามารถใช้ bound แรกได้
นั่นคือ หากเราทำ Grover’s step ทั้งหมด √N/8 ครั้งจะได้ว่า α(ω,t+1) ≥ α(ω,0) + 1/8 ≥ 1/8 >0.1
นั่นแปลว่าความน่าจะเป็นที่การวัดจะนำไปสู่การฟุบ (collapse) ลงสู่ state ω (ซึ่งคือกำลังสองของ amplitude) ก็จะ >0.01
ดังนั้นความน่าจะเป็นที่การวัดแต่ละครั้งจะได้ผลไม่เท่ากับ ω นั้นจะไม่เกิน 0.99
หากเราทำการส่ง qubits ทั้งหลายผ่าน Grover’s step ทั้ง √N/8 และทำการวัดหลาย ๆ ครั้ง ความน่าจะเป็นที่เราจะวัดได้ ω ก็จะสูงขึ้นมานั่นเอง
ดูเหมือนว่าจำนวน Grover’s step มาตรฐานที่ต้องใช้คือ π√N/4 [2] แต่ยังไม่ค่อยเข้าใจว่ามาไง กับดูเหมือนจะยังสามารถลดจำนวน steps ลงได้อีก [3] ไว้ว่าง ๆ ค่อยอ่านเพิ่มละกัน
เอกสารอ้างอิง
[1] “Lecture 4: Grover’s Algorithm”, Lecturer: John Wright, Scribe: Tom Tseng
[2] Grover’s algorithm
[3] N. Nahimovs and A. Rovosh. “A Note on the Optimality of the Grover’s Algorithm”
