คำอธิบายอัลกอริทึม Grover

ในส่วนนี้เราจะอธิบายอัลกอริทึม Grover เริ่มจากการพูดถึง phase query gates และวิธีสร้างมัน ตามด้วยคำอธิบายของตัวอัลกอริทึม Grover เอง สุดท้ายจะพูดสั้น ๆ ถึงวิธีที่อัลกอริทึมนี้ถูกนำไปใช้กับการค้นหาโดยธรรมชาติ

Phase query gates

อัลกอริทึม Grover ใช้การดำเนินการที่รู้จักในชื่อ phase query gates ต่างจาก query gate ธรรมดา $U_f$ ที่กำหนดสำหรับฟังก์ชัน $f$ ที่กำหนดในแบบปกติที่อธิบายไว้ก่อนหน้า phase query gate สำหรับฟังก์ชัน $f$ ถูกกำหนดเป็น

$$Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle$$

สำหรับทุก string $x\in\Sigma^n$

การดำเนินการ $Z_f$ สามารถ implement ได้โดยใช้ query gate $U_f$ หนึ่งตัว ดังที่ diagram นี้แนะนำ:

การ implement นี้ใช้ประโยชน์จากปรากฏการณ์ phase kickback และต้องการ workspace qubit หนึ่งตัวที่ initialize ในสถานะ $\vert -\rangle$ Qubit นี้ยังคงอยู่ในสถานะ $\vert - \rangle$ หลังจากการ implement เสร็จสิ้น และสามารถนำกลับมาใช้ใหม่ (เพื่อ implement $Z_f$ gates ต่อ ๆ ไป เป็นต้น) หรือจะละทิ้งก็ได้

นอกจากการดำเนินการ $Z_f$ แล้ว เราจะใช้ phase query gate สำหรับฟังก์ชัน OR แบบ $n$ บิต ซึ่งกำหนดดังต่อไปนี้สำหรับแต่ละ string $x\in\Sigma^n$

$$\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}$$

โดยชัดเจน phase query gate สำหรับฟังก์ชัน OR แบบ $n$ บิตทำงานดังนี้:

$$Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[0.5mm] - \vert x\rangle & x \neq 0^n. \end{cases}$$

เพื่อให้ชัดเจน นี่คือวิธีที่ $Z_{\mathrm{OR}}$ ทำงานกับ standard basis states; พฤติกรรมบน states ทั่วไปถูกกำหนดจากนิพจน์นี้โดยความเป็นเชิงเส้น

การดำเนินการ $Z_{\mathrm{OR}}$ สามารถ implement ได้ในรูป quantum circuit โดยเริ่มจาก Boolean circuit สำหรับฟังก์ชัน OR จากนั้นสร้างการดำเนินการ $U_{\mathrm{OR}}$ (นั่นคือ standard query gate สำหรับฟังก์ชัน OR แบบ $n$ บิต) โดยใช้ขั้นตอนที่อธิบายในบทเรียน พื้นฐานอัลกอริทึมควอนตัม และสุดท้ายสร้างการดำเนินการ $Z_{\mathrm{OR}}$ โดยใช้ปรากฏการณ์ phase kickback ดังที่อธิบายข้างต้น ควรสังเกตว่าการดำเนินการ $Z_{\mathrm{OR}}$ ไม่มีการพึ่งพาฟังก์ชัน $f$ และสามารถ implement ได้ด้วย quantum circuit ที่ไม่มี query gates เลย

คำอธิบายอัลกอริทึม

เมื่อมีการดำเนินการสองอย่างคือ $Z_f$ และ $Z_{\mathrm{OR}}$ แล้ว เราสามารถอธิบายอัลกอริทึม Grover ได้

อัลกอริทึมอ้างถึงตัวเลข $t$ ซึ่งคือจำนวน iteration ที่มันทำ (และด้วยเหตุนี้คือจำนวน queries ต่อฟังก์ชัน $f$ ที่ต้องการ) ตัวเลข $t$ นี้ไม่ถูกระบุโดยอัลกอริทึม Grover ที่เราอธิบายอยู่ และจะพูดถึงภายหลังในบทเรียนว่าจะเลือกอย่างไร

อัลกอริทึม Grover

1. Initialize register ของ $n$ qubit $\mathsf{Q}$ เป็น all-zero state $\vert 0^n \rangle$ จากนั้นใช้การดำเนินการ Hadamard กับแต่ละ qubit ของ $\mathsf{Q}$
2. ใช้การดำเนินการ unitary $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ กับ register $\mathsf{Q}$ เป็นจำนวน $t$ ครั้ง
3. วัด qubits ของ $\mathsf{Q}$ ด้วย standard basis measurements และ output string ที่ได้

การดำเนินการ $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ ที่วนซ้ำในขั้นตอน 2 จะเรียกว่า Grover operation ตลอดส่วนที่เหลือของบทเรียนนี้ นี่คือ quantum circuit ที่แทน Grover operation เมื่อ $n=7\!:$

ใน diagram นี้ การดำเนินการ $Z_f$ ถูกวาดให้ใหญ่กว่า $Z_{\mathrm{OR}}$ เป็นสัญลักษณ์บอกใบ้ว่ามันน่าจะเป็นการดำเนินการที่มีต้นทุนสูงกว่า โดยเฉพาะในแบบจำลอง query นั้น $Z_f$ ต้องการ query หนึ่งครั้งในขณะที่ $Z_{\mathrm{OR}}$ ไม่ต้องการ query เลย ถ้าเรามี Boolean circuit สำหรับฟังก์ชัน $f$ และแปลงเป็น quantum circuit สำหรับ $Z_f$ เราพอคาดได้ว่า quantum circuit ที่ได้จะใหญ่และซับซ้อนกว่า circuit สำหรับ $Z_{\mathrm{OR}}$

นี่คือ diagram ของ quantum circuit สำหรับอัลกอริทึมทั้งหมดเมื่อ $n=7$ และ $t=3$ สำหรับค่า $t$ ที่ใหญ่กว่า เราสามารถแทรก Grover operation เพิ่มเติมได้ก่อนการวัด

การนำไปใช้กับการค้นหา

อัลกอริทึม Grover สามารถนำไปใช้กับปัญหา Search ดังนี้:

• เลือกตัวเลข $t$ ในขั้นตอน 2 (ซึ่งจะพูดถึงภายหลังในบทเรียน)
• รันอัลกอริทึม Grover บนฟังก์ชัน $f$ โดยใช้ค่า $t$ ที่เลือก เพื่อได้ string $x\in\Sigma^n$
• Query ฟังก์ชัน $f$ บน string $x$ เพื่อดูว่ามันเป็น solution ที่ถูกต้องหรือไม่:
  • ถ้า $f(x) = 1$ แปลว่าเราพบ solution แล้ว จึงหยุดและ output $x$
  • มิฉะนั้น ถ้า $f(x) = 0$ เราสามารถรันกระบวนการอีกครั้งโดยอาจเลือก $t$ ต่างกัน หรือตัดสินใจยอมแพ้และ output "ไม่มี solution"

เมื่อวิเคราะห์วิธีทำงานของอัลกอริทึม Grover แล้ว เราจะเห็นว่าการเลือก $t = O(\sqrt{N})$ ทำให้ได้ solution ของปัญหาการค้นหา (ถ้ามี) ด้วยความน่าจะเป็นสูง