อัลกอริทึมของ Grover

โมดูล Qiskit in Classrooms นี้ต้องการให้นักเรียนมี Python environment ที่ใช้งานได้พร้อมติดตั้งแพ็กเกจต่อไปนี้:

• qiskit v2.1.0 หรือใหม่กว่า
• qiskit-ibm-runtime v0.40.1 หรือใหม่กว่า
• qiskit-aer v0.17.0 หรือใหม่กว่า
• qiskit.visualization
• numpy
• pylatexenc

สำหรับการตั้งค่าและติดตั้งแพ็กเกจข้างต้น ดู คู่มือติดตั้ง Qiskit เพื่อรันงานบนคอมพิวเตอร์ควอนตัมจริง นักเรียนต้องสร้างบัญชี IBM Quantum® โดยทำตามขั้นตอนในคู่มือ ตั้งค่าบัญชี IBM Cloud

โมดูลนี้ผ่านการทดสอบและใช้เวลา QPU ไป 12 วินาที ตัวเลขนี้เป็นค่าประมาณ ปริมาณการใช้งานจริงของคุณอาจแตกต่างกัน

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

บทนำ

อัลกอริทึมของ Grover เป็นอัลกอริทึมควอนตัมพื้นฐานที่แก้ ปัญหาการค้นหาแบบไม่มีโครงสร้าง: เมื่อกำหนดชุดข้อมูล $N$ รายการและวิธีตรวจสอบว่ารายการใดคือสิ่งที่ต้องการ จะค้นหารายการนั้นได้เร็วแค่ไหน? ในการประมวลผลแบบคลาสสิก หากข้อมูลไม่ได้เรียงลำดับและไม่มีโครงสร้างให้ใช้ประโยชน์ วิธีที่ดีที่สุดคือตรวจสอบทีละรายการ ทำให้มีความซับซ้อนในการสอบถาม $O(N)$ — โดยเฉลี่ยต้องตรวจสอบประมาณครึ่งหนึ่งก่อนจะพบเป้าหมาย

อัลกอริทึมของ Grover ที่นำเสนอโดย Lov Grover ในปี 1996 แสดงให้เห็นว่าคอมพิวเตอร์ควอนตัมสามารถแก้ปัญหานี้ได้มีประสิทธิภาพกว่ามาก โดยต้องการเพียง $O(\sqrt{N})$ ขั้นตอนเพื่อค้นหารายการที่ทำเครื่องหมายไว้ด้วยความน่าจะเป็นสูง ซึ่งแสดงถึง การเร่งความเร็วแบบกำลังสอง เหนือวิธีคลาสสิก อันมีนัยสำคัญสำหรับชุดข้อมูลขนาดใหญ่

อัลกอริทึมดำเนินการในบริบทดังต่อไปนี้:

• การตั้งค่าปัญหา: มีฟังก์ชัน $f(x)$ ที่คืนค่า 1 หาก $x$ คือรายการที่ต้องการ และ 0 กรณีอื่น ฟังก์ชันนี้มักเรียกว่า oracle หรือ กล่องดำ เนื่องจากเราเรียนรู้เกี่ยวกับข้อมูลได้จากการสอบถาม $f(x)$ เท่านั้น
• ประโยชน์ของควอนตัม: ขณะที่อัลกอริทึมคลาสสิกสำหรับปัญหานี้ต้องการ $N/2$ การสอบถามโดยเฉลี่ย อัลกอริทึมของ Grover สามารถค้นหาคำตอบได้ในประมาณ $\pi\sqrt{N}/4$ การสอบถาม ซึ่งเร็วกว่ามากสำหรับ $N$ ขนาดใหญ่
• หลักการทำงาน (ภาพรวม):
  • คอมพิวเตอร์ควอนตัมสร้าง ซูเปอร์โพสิชัน ของสถานะที่เป็นไปได้ทั้งหมดก่อน แทนรายการที่เป็นไปได้ทั้งหมดพร้อมกัน
  • จากนั้นนำชุดการดำเนินการควอนตัม (การวนซ้ำของ Grover) มาใช้ซ้ำๆ เพื่อขยายความน่าจะเป็นของคำตอบที่ถูกต้องและลดส่วนที่เหลือลง
  • หลังจากวนซ้ำเพียงพอแล้ว การวัดสถานะควอนตัมจะให้คำตอบที่ถูกต้องด้วยความน่าจะเป็นสูง

ต่อไปนี้เป็นแผนภาพพื้นฐานมากของอัลกอริทึมของ Grover ที่ข้ามรายละเอียดสำคัญหลายส่วน สำหรับแผนภาพที่ละเอียดกว่า ดู บทความนี้

สิ่งที่ควรสังเกตเกี่ยวกับอัลกอริทึมของ Grover:

• เหมาะสมที่สุดสำหรับการค้นหาแบบไม่มีโครงสร้าง: ไม่มีอัลกอริทึมควอนตัมใดที่สามารถแก้ปัญหาด้วยการสอบถามน้อยกว่า $O(\sqrt{N})$
• ให้การเร่งความเร็วแบบกำลังสองเท่านั้น ไม่ใช่เลขยกกำลัง — ต่างจากอัลกอริทึมควอนตัมบางตัว (เช่น อัลกอริทึมของ Shor สำหรับการแยกตัวประกอบ)
• มีผลทางปฏิบัติ เช่น อาจเพิ่มความเร็วการโจมตีแบบ brute-force บนระบบเข้ารหัส แม้ว่าความเร็วที่ได้ยังไม่เพียงพอที่จะทำลายการเข้ารหัสสมัยใหม่ส่วนใหญ่ได้โดยลำพัง

สำหรับนักศึกษาระดับปริญญาตรีที่คุ้นเคยกับแนวคิดการประมวลผลพื้นฐานและโมเดลการสอบถาม อัลกอริทึมของ Grover แสดงให้เห็นอย่างชัดเจนว่าการประมวลผลเชิงควอนตัมสามารถเหนือกว่าแนวทางคลาสสิกในปัญหาบางประเภทได้อย่างไร แม้ว่าการปรับปรุงจะ "เพียงแค่" แบบกำลังสอง และยังเป็นประตูสู่การทำความเข้าใจอัลกอริทึมควอนตัมขั้นสูงและศักยภาพที่กว้างขึ้นของการประมวลผลเชิงควอนตัม

การขยายแอมพลิจูด (Amplitude amplification) เป็นอัลกอริทึมควอนตัมหรือซับรูทีนสำหรับจุดประสงค์ทั่วไป ที่ใช้เพื่อให้ได้การเร่งความเร็วแบบกำลังสองเหนืออัลกอริทึมคลาสสิกหลายตัว อัลกอริทึมของ Grover เป็นตัวแรกที่แสดงให้เห็นการเร่งความเร็วนี้บนปัญหาการค้นหาแบบไม่มีโครงสร้าง การกำหนดปัญหาการค้นหาของ Grover ต้องการฟังก์ชัน oracle ที่ทำเครื่องหมายสถานะฐาน computational หนึ่งสถานะหรือมากกว่าเป็นสถานะที่ต้องการค้นหา และ Circuit การขยายที่เพิ่มแอมพลิจูดของสถานะที่ทำเครื่องหมาย ส่งผลให้กดสถานะที่เหลือลง

ที่นี่ เราแสดงวิธีสร้าง oracle ของ Grover และใช้ GroverOperator จากไลบรารี Circuit ของ Qiskit เพื่อตั้งค่าอินสแตนซ์การค้นหาของ Grover ได้อย่างง่ายดาย Runtime Sampler primitive ช่วยให้รัน Circuit ของ Grover ได้อย่างราบรื่น

คณิตศาสตร์

สมมติว่ามีฟังก์ชัน $f$ ที่แมปสตริงไบนารีไปยังตัวแปรไบนารีเดี่ยว หมายความว่า

$$f: \Sigma^n \rightarrow \Sigma$$

ตัวอย่างหนึ่งที่นิยามบน $\Sigma^6$ คือ

$$f(x)= \begin{cases} 1 \qquad \text{if }x=\{010101\}\\ 0 \qquad \text{otherwise } \end{cases}$$

อีกตัวอย่างหนึ่งที่นิยามบน $\Sigma^{2n}$ คือ

$$f(x)= \begin{cases} 1 \qquad \text{if equal numbers of 1's and 0's in string}\\ 0 \qquad \text{otherwise } \end{cases}$$

งานของคุณคือค้นหาสถานะควอนตัมที่ตรงกับ argument $x$ ของ $f(x)$ ที่ถูกแมปไปยัง 1 กล่าวอีกนัย ค้นหา $\{x_1\}\in \Sigma^n$ ทั้งหมด โดยที่ $f(x_1)=1$ (หรือรายงานว่าไม่มีคำตอบ) เราจะเรียกตัวที่ไม่ใช่คำตอบว่า $x_0$ แน่นอนว่าเราจะทำสิ่งนี้บนคอมพิวเตอร์ควอนตัม โดยใช้สถานะควอนตัม ดังนั้นจึงเป็นประโยชน์ที่จะแสดงสตริงไบนารีเหล่านี้เป็นสถานะ:

$$\{|x_1\rangle\} \in |\Sigma^n\rangle$$

ใช้สัญลักษณ์สถานะควอนตัม (Dirac) เรากำลังมองหาสถานะพิเศษหนึ่งสถานะหรือมากกว่า $\{|x_1\rangle\}$ ในชุดของ $N=2^n$ สถานะที่เป็นไปได้ โดยที่ $n$ คือจำนวน Qubit และตัวที่ไม่ใช่คำตอบแทนด้วย $\{|x_0\rangle\}$

เราสามารถคิดฟังก์ชัน $f$ ว่าถูกจัดหาโดย oracle: กล่องดำที่เราสามารถสอบถามเพื่อกำหนดผลกระทบต่อสถานะ $|x\rangle$ ในทางปฏิบัติ เรามักจะรู้ฟังก์ชัน แต่อาจซับซ้อนมากในการใช้งาน ทำให้การลดจำนวนการสอบถามหรือการนำ $f$ ไปใช้อาจมีความสำคัญ หรืออาจจินตนาการถึงระบบที่บุคคลหนึ่งกำลังสอบถาม oracle ที่ควบคุมโดยอีกคน ดังนั้นเราจึงไม่รู้ฟังก์ชัน oracle เพียงแต่รู้การกระทำต่อสถานะเฉพาะจากการสอบถาม

นี่คือ "ปัญหาการค้นหาแบบไม่มีโครงสร้าง" ในแง่ที่ไม่มีสิ่งพิเศษใดๆ เกี่ยวกับ $f$ ที่ช่วยในการค้นหา ผลลัพธ์ไม่ได้เรียงลำดับและคำตอบไม่ได้ถูกทราบว่ากระจุกตัว และอื่นๆ ลองนึกถึงสมุดโทรศัพท์กระดาษเก่าเป็นตัวเปรียบเทียบ การค้นหาแบบไม่มีโครงสร้างนี้คล้ายกับการไล่ดูเพื่อหา หมายเลข ใดหมายเลขหนึ่ง ไม่ใช่การค้นหาในรายชื่อที่เรียงตามตัวอักษร

ในกรณีที่ต้องการคำตอบเดียว ในแบบคลาสสิก จำเป็นต้องใช้จำนวนการสอบถามที่เป็นเส้นตรงใน $N$ ชัดเจนว่าอาจหาคำตอบได้ตั้งแต่ครั้งแรก หรืออาจไม่พบคำตอบใน $N-1$ การเดาแรก ทำให้ต้องสอบถาม input ที่ $N$ เพื่อดูว่ามีคำตอบหรือไม่ เนื่องจากฟังก์ชันไม่มีโครงสร้างที่ใช้ประโยชน์ได้ คุณต้องใช้ $N/2$ การเดาโดยเฉลี่ย อัลกอริทึมของ Grover ต้องการจำนวนการสอบถามหรือการคำนวณ $f$ ที่ scale เหมือน $\sqrt{N}$

ภาพรวม Circuit ในอัลกอริทึมของ Grover

สามารถหาการอธิบายทางคณิตศาสตร์อย่างสมบูรณ์ของอัลกอริทึมของ Grover ได้ใน พื้นฐานของอัลกอริทึมควอนตัม หลักสูตรโดย John Watrous บน IBM Quantum Learning การอธิบายแบบย่อให้ไว้ในภาคผนวกตอนท้ายของโมดูลนี้ แต่สำหรับตอนนี้ เราจะทบทวนเฉพาะโครงสร้างโดยรวมของ Circuit ควอนตัมที่ใช้งานอัลกอริทึมของ Grover

อัลกอริทึมของ Grover แบ่งออกเป็นขั้นตอนดังต่อไปนี้:

• การเตรียมซูเปอร์โพสิชันเริ่มต้น (การนำ Hadamard Gate ไปใช้กับ Qubit ทั้งหมด)
• "การทำเครื่องหมาย" สถานะเป้าหมายด้วยการพลิกเฟส
• ขั้นตอน "การกระจาย" ที่นำ Hadamard Gate และการพลิกเฟสไปใช้กับ Qubit ทั้งหมด
• การทำซ้ำขั้นตอนการทำเครื่องหมายและการกระจายตามความเหมาะสมเพื่อเพิ่มความน่าจะเป็นในการวัดสถานะเป้าหมายให้สูงสุด
• การวัด

บ่อยครั้ง Gate การทำเครื่องหมาย $Z_f$ และเลเยอร์การกระจายที่ประกอบด้วย $H,$ $Z_{\text{OR}},$ และ $H$ มักเรียกรวมกันว่า "Grover operator" ในแผนภาพนี้ แสดงเพียงการทำซ้ำ Grover operator ครั้งเดียว

Hadamard Gate $H$ เป็นที่รู้จักกันดีและใช้กันอย่างแพร่หลายในการประมวลผลเชิงควอนตัม Hadamard Gate สร้างสถานะซูเปอร์โพสิชัน โดยเฉพาะถูกนิยามด้วย

$$H|0\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)\\ H|1\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)$$

การดำเนินการบนสถานะอื่นๆ ถูกนิยามผ่านความเป็นเชิงเส้น โดยเฉพาะ เลเยอร์ของ Hadamard Gate ช่วยให้เราไปจากสถานะเริ่มต้นที่ Qubit ทั้งหมดอยู่ใน $|0\rangle$ (แทนด้วย $|0\rangle^{\otimes n}$) ไปยังสถานะที่ Qubit แต่ละตัวมีความน่าจะเป็นที่จะถูกวัดใน $|0\rangle$ หรือ $|1\rangle$ ซึ่งทำให้เราสำรวจพื้นที่ของสถานะที่เป็นไปได้ทั้งหมดแตกต่างจากการประมวลผลแบบคลาสสิก

คุณสมบัติผลสืบเนื่องสำคัญของ Hadamard Gate คือการนำมาใช้เป็นครั้งที่สองสามารถยกเลิกสถานะซูเปอร์โพสิชันได้:

$$H\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)=|0\rangle\\ H\frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)=|1\rangle$$

สิ่งนี้จะมีความสำคัญในอีกสักครู่

ทดสอบความเข้าใจ

อ่านคำถามด้านล่าง คิดหาคำตอบ แล้วคลิกสามเหลี่ยมเพื่อดูเฉลย

จากนิยามของ Hadamard Gate แสดงให้เห็นว่าการนำ Hadamard Gate มาใช้เป็นครั้งที่สองสามารถยกเลิกซูเปอร์โพสิชันดังกล่าวได้ตามที่กล่าวอ้าง

คำตอบ:

เมื่อเรานำ X ไปใช้กับสถานะ $|+\rangle$ เราจะได้ค่า +1 และกับสถานะ $|-\rangle$ เราจะได้ -1 ดังนั้นหากมีการกระจายแบบ 50-50 เราจะได้ค่าคาดหวังเป็น 0

Gate $Z_\text{OR}$ พบเห็นได้น้อยกว่า และถูกนิยามตาม

$$\text{Z}_\text{OR}|x\rangle = \begin{cases} |x\rangle & \text{if } x = 0^n \\ -|x\rangle & \text{if } x \neq 0^n \end{cases} \qquad \forall x \in \Sigma^n$$

สุดท้าย Gate $Z_f$ ถูกนิยามด้วย

$$Z_f:|x\rangle \rightarrow (-1)^{f(x)}|x\rangle \qquad \forall x \in \Sigma^n$$

สังเกตว่าผลของสิ่งนี้คือ $Z_f$ พลิกเครื่องหมายบนสถานะเป้าหมายที่ $f(x) = 1$ และปล่อยสถานะอื่นไว้ไม่เปลี่ยนแปลง

ในระดับนามธรรมสูงมาก คุณสามารถคิดเกี่ยวกับขั้นตอนใน Circuit ได้ดังนี้:

• เลเยอร์ Hadamard แรก: นำ Qubit เข้าสู่ซูเปอร์โพสิชันของสถานะที่เป็นไปได้ทั้งหมด
• $Z_f$: ทำเครื่องหมายสถานะเป้าหมายโดยเพิ่มเครื่องหมาย "-" ไว้ข้างหน้า สิ่งนี้ไม่ได้เปลี่ยนความน่าจะเป็นในการวัดทันที แต่เปลี่ยนวิธีที่สถานะเป้าหมายจะทำงานในขั้นตอนถัดไป
• เลเยอร์ Hadamard อีกชั้น: เครื่องหมาย "-" ที่เพิ่มในขั้นตอนก่อนหน้าจะเปลี่ยนเครื่องหมายสัมพัทธ์ระหว่างบางเทอม เนื่องจาก Hadamard Gate เปลี่ยนการผสมของสถานะ computational $(|0\rangle+|1\rangle)/\sqrt{2}$ ไปเป็นสถานะ computational หนึ่ง $|0\rangle,$ และเปลี่ยน $(|0\rangle-|1\rangle)/\sqrt{2}$ ไปเป็น $|1\rangle$ ความแตกต่างของเครื่องหมายสัมพัทธ์นี้จึงเริ่มมีบทบาทในสถานะที่ถูกวัด
• นำเลเยอร์สุดท้ายของ Hadamard Gate ไปใช้ แล้วทำการวัด เราจะเห็นรายละเอียดเพิ่มเติมว่าสิ่งนี้ทำงานอย่างไรในส่วนถัดไป

ตัวอย่าง

เพื่อทำความเข้าใจวิธีการทำงานของอัลกอริทึมของ Grover มากขึ้น มาดูตัวอย่างขนาดเล็กที่มีสอง Qubit กัน ส่วนนี้อาจถือเป็นตัวเลือกสำหรับผู้ที่ไม่ได้มุ่งเน้นด้านกลศาสตร์ควอนตัมและสัญลักษณ์ Dirac แต่สำหรับผู้ที่หวังจะทำงานอย่างจริงจังกับคอมพิวเตอร์ควอนตัม แนะนำให้ศึกษาส่วนนี้อย่างยิ่ง

ต่อไปนี้เป็นแผนภาพ Circuit พร้อมสถานะควอนตัมที่ระบุตำแหน่งต่างๆ ตลอดทั้ง Circuit สังเกตว่าด้วยเพียงสอง Qubit มีเพียงสี่สถานะที่เป็นไปได้ที่อาจวัดได้ในทุกกรณี: $|00\rangle$, $|01\rangle$, $|10\rangle$, และ $|11\rangle$

สมมติว่า oracle ($Z_f$, ที่เราไม่รู้) ทำเครื่องหมายสถานะ $|01\rangle$ เราจะทำงานผ่านการกระทำของชุด Gate ควอนตัมแต่ละชุด รวมถึง oracle และดูการกระจายของสถานะที่เป็นไปได้ที่ออกมาในเวลาของการวัด ในตอนเริ่มต้น เรามี

$$|\psi_0\rangle = |00\rangle$$

ใช้นิยามของ Hadamard Gate เรามี

$$|\psi_1\rangle = \frac{1}{2}\left(|0\rangle+|1\rangle\right)\left(|0\rangle+|1\rangle\right)=\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)$$

ตอนนี้ oracle ทำเครื่องหมายสถานะเป้าหมาย:

$$|\psi_2\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle+|11\rangle\right)$$

สังเกตว่าในสถานะนี้ ผลลัพธ์ที่เป็นไปได้ทั้งสี่มีความน่าจะเป็นในการวัดเท่ากัน ทั้งหมดมีน้ำหนัก $1/2$ หมายความว่าแต่ละตัวมีโอกาส $|1/2|^2=1/4$ ที่จะถูกวัด ดังนั้นแม้ว่าสถานะ $|01\rangle$ จะถูกทำเครื่องหมายผ่านเฟส "-" แต่สิ่งนี้ยังไม่ได้ส่งผลให้ความน่าจะเป็นในการวัดสถานะนั้นเพิ่มขึ้น เราดำเนินต่อโดยนำเลเยอร์ถัดไปของ Hadamard Gate ไปใช้

$$\begin{aligned} |\psi_3\rangle = &\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

รวมเทอมที่คล้ายกัน เราพบว่า

$$|\psi_3\rangle = \frac{1}{2}\left(|00\rangle+|01\rangle-|10\rangle+|11\rangle\right)$$

ตอนนี้ $Z_{\text{OR}}$ พลิกเครื่องหมายบนสถานะทั้งหมดยกเว้น $|00\rangle$:

$$|\psi_4\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)$$

และสุดท้าย เรานำเลเยอร์สุดท้ายของ Hadamard Gate ไปใช้:

$$\begin{aligned} |\psi_5\rangle =&\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

ควรลองรวมเทอมเหล่านี้เพื่อเห็นด้วยตัวเองว่าผลลัพธ์คือ:

$$|\psi_5\rangle =|01\rangle$$

นั่นคือ ความน่าจะเป็นของการวัด $|01\rangle$ อยู่ที่ 100% (ในกรณีที่ไม่มี noise และข้อผิดพลาด) และความน่าจะเป็นในการวัดสถานะอื่นๆ เป็นศูนย์

ตัวอย่างสอง Qubit นี้เป็นกรณีที่สะอาดเป็นพิเศษ อัลกอริทึมของ Grover จะไม่ได้ผลลัพธ์ 100% เสมอไป แต่จะขยายความน่าจะเป็นของการวัดสถานะเป้าหมาย และ Grover operator อาจต้องทำซ้ำมากกว่าหนึ่งครั้ง

ในส่วนถัดไป เราจะนำอัลกอริทึมนี้ไปใช้งานจริงโดยใช้คอมพิวเตอร์ควอนตัม IBM®

ข้อจำกัดที่ชัดเจน

เพื่อนำ Grover operator ไปใช้ เราต้องสร้าง Grover operator ซึ่งหมายความว่าเราต้องสามารถพลิกเฟสบนสถานะที่ตรงกับเกณฑ์คำตอบของเราได้ สิ่งนี้ตั้งคำถามขึ้นมาว่า: ถ้าเรารู้ชุดคำตอบของเราดีพอที่จะออกแบบ Circuit ควอนตัมเพื่อติดป้ายแต่ละตัว แล้วเรากำลังค้นหาอะไรอยู่?! คำตอบมีสามส่วน และเราจะกลับมาดูสิ่งนี้ตลอดบทเรียน:

(1) อัลกอริทึมการสอบถามประเภทนี้มักเกี่ยวข้องกับสองฝ่าย: ฝ่ายหนึ่งมี oracle ที่กำหนดเกณฑ์คำตอบ และอีกฝ่ายพยายามเดา/หาสถานะคำตอบ ข้อเท็จจริงที่ว่าคนหนึ่งสามารถสร้าง oracle ได้ไม่ได้ยกเลิกความจำเป็นในการค้นหา

(2) มีปัญหาที่การระบุเกณฑ์คำตอบทำได้ง่ายกว่าการหาคำตอบ ตัวอย่างที่รู้จักกันดีที่สุดอาจเป็นการระบุตัวประกอบเฉพาะของจำนวนขนาดใหญ่ อัลกอริทึมของ Grover ไม่ค่อยมีประสิทธิภาพในการแก้ปัญหาเฉพาะนั้น เราจะใช้อัลกอริทึมของ Shor สำหรับการแยกตัวประกอบเฉพาะ นี่เป็นเพียงตัวอย่างเพื่อชี้ให้เห็นว่าการรู้เกณฑ์พฤติกรรมของสถานะไม่ได้หมายความว่ารู้สถานะนั้นเสมอไป

(3) อัลกอริทึมของ Grover ไม่ได้ส่งคืนเฉพาะข้อมูลคลาสสิกเท่านั้น จริงอยู่ ถ้าเราวัดสถานะสุดท้ายหลังจาก $t$ การซ้ำของ Grover operator เราน่าจะได้ข้อมูลคลาสสิกที่ระบุสถานะคำตอบ แต่ถ้าเราไม่ต้องการข้อมูลคลาสสิก แต่ต้องการสถานะคำตอบที่เตรียมไว้บนคอมพิวเตอร์ควอนตัมเพื่อใช้ต่อในอัลกอริทึมอื่น? อัลกอริทึมของ Grover จริงๆ แล้วสร้างสถานะควอนตัมที่มีน้ำหนักหนักอยู่ที่คำตอบ ดังนั้นคุณอาจพบ Grover's algorithm เป็นซับรูทีนในอัลกอริทึมควอนตัมที่ซับซ้อนกว่า

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

การ import ทั่วไปและแนวทาง

เราเริ่มต้นด้วยการ import แพ็กเกจที่จำเป็นหลายอย่าง

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

ตลอดบทเรียนนี้และบทเรียนอื่นๆ เราจะใช้กรอบการทำงานสำหรับการประมวลผลเชิงควอนตัมที่เรียกว่า "Qiskit patterns" ซึ่งแบ่ง workflow ออกเป็นขั้นตอนดังต่อไปนี้:

• ขั้นตอนที่ 1: แมป input คลาสสิกไปยังปัญหาควอนตัม
• ขั้นตอนที่ 2: ปรับแต่งปัญหาสำหรับการรันเชิงควอนตัม
• ขั้นตอนที่ 3: รันโดยใช้ Qiskit Runtime Primitives
• ขั้นตอนที่ 4: การประมวลผลหลังและการวิเคราะห์แบบคลาสสิก

โดยทั่วไปเราจะทำตามขั้นตอนเหล่านี้ แม้ว่าเราอาจไม่ได้ระบุชื่อขั้นตอนอย่างชัดเจนเสมอไป

กิจกรรมที่ 1: ค้นหาสถานะเป้าหมายเดี่ยวที่กำหนดไว้

ขั้นตอนที่ 1: แมป input คลาสสิกไปยังปัญหาควอนตัม

เราต้องการ Gate การสอบถามเฟสเพื่อใส่เฟสรวม (-1) บนสถานะคำตอบ และปล่อยสถานะที่ไม่ใช่คำตอบไม่เปลี่ยนแปลง อีกนัยหนึ่งคืออัลกอริทึมของ Grover ต้องการ oracle ที่ระบุสถานะฐาน computational ที่ทำเครื่องหมายหนึ่งสถานะหรือมากกว่า โดย "ทำเครื่องหมาย" หมายถึงสถานะที่มีเฟส -1 สิ่งนี้ทำโดยใช้ controlled-Z gate หรือการขยายแบบ multi-controlled ของมันบน $N$ Qubit เพื่อดูว่าสิ่งนี้ทำงานอย่างไร ให้พิจารณาตัวอย่างเฉพาะของ bitstring {110} เราต้องการ Circuit ที่กระทำกับสถานะ $|\psi\rangle = |q_2,q_1,q_0\rangle$ และใส่เฟสหาก $|\psi\rangle = |011\rangle$ (ซึ่งเราได้พลิกลำดับของสตริงไบนารีเนื่องจากสัญลักษณ์ใน Qiskit ที่วาง Qubit ที่มีนัยสำคัญน้อยที่สุด (มักเป็น 0) ทางขวา)

ดังนั้น เราต้องการ Circuit $Z_f$ ที่ทำ

$$Z_f|\psi\rangle = \begin{cases} -|\psi\rangle \qquad \text{if} \qquad |\psi\rangle = |011\rangle \\ |\psi\rangle \qquad \text{if} \qquad |\psi\rangle \neq |011\rangle\end{cases}$$

เราสามารถใช้ multiple control multiple target gate (MCMTGate) เพื่อนำ Z gate ที่ควบคุมโดย Qubit ทั้งหมดไปใช้ (พลิกเฟสหาก Qubit ทั้งหมดอยู่ในสถานะ $|1\rangle$) แน่นอนว่า Qubit บางตัวในสถานะที่ต้องการอาจเป็น $|0\rangle$ ดังนั้น สำหรับ Qubit เหล่านั้นเราต้องนำ X gate ไปใช้ก่อน จากนั้นทำ multiply-controlled Z gate แล้วนำ X gate อีกครั้งเพื่อยกเลิกการเปลี่ยนแปลง MCMTGate มีลักษณะดังนี้:

mcmt_ex = QuantumCircuit(3)
mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)
mcmt_ex.draw(output="mpl", style="iqp")

สังเกตว่า Qubit จำนวนมากอาจมีส่วนร่วมในกระบวนการ control (ที่นี่มีสาม Qubit) แต่ไม่มี Qubit ตัวใดถูกระบุเป็น target สิ่งนี้เป็นเพราะสถานะทั้งหมดได้รับเครื่องหมาย "-" รวม (การพลิกเฟส) Gate นี้ส่งผลต่อ Qubit ทุกตัวอย่างเท่าเทียมกัน ซึ่งต่างจาก Gate หลาย Qubit อื่นๆ เช่น CX gate ที่มี control qubit เดี่ยวและ target qubit เดี่ยว

ในโค้ดต่อไปนี้ เรานิยาม phase query gate (หรือ oracle) ที่ทำสิ่งที่เพิ่งอธิบาย: ทำเครื่องหมายสถานะฐาน input หนึ่งสถานะหรือมากกว่าที่นิยามผ่านการแสดง bitstring MCMT gate ถูกใช้เพื่อใช้งาน multi-controlled Z-gate

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bitstring to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bitstring
        zero_inds = [
            ind for ind in range(num_qubits) if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bitstring has a '0' entry
        qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        qc.x(zero_inds)
    return qc

ตอนนี้เราเลือกสถานะ "ที่ทำเครื่องหมาย" เฉพาะเป็นเป้าหมาย และนำฟังก์ชันที่เพิ่งนิยามมาใช้ มาดูกันว่า Circuit ที่สร้างขึ้นมีลักษณะอย่างไร

marked_states = ["1110"]
oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

หาก Qubit 1-3 อยู่ในสถานะ $|1\rangle$ และ Qubit 0 เริ่มต้นอยู่ในสถานะ $|0\rangle$ X gate ตัวแรกจะพลิก Qubit 0 ไปเป็น $|1\rangle$ และ Qubit ทั้งหมดจะอยู่ใน $|1\rangle$ ซึ่งหมายความว่า MCMT gate จะนำการเปลี่ยนเครื่องหมายรวมหรือการพลิกเฟสไปใช้ตามต้องการ ในกรณีอื่นๆ Qubit 1-3 อยู่ในสถานะ $|0\rangle$ หรือ Qubit 0 ถูกพลิกไปเป็นสถานะ $|0\rangle$ และจะไม่มีการนำการพลิกเฟสไปใช้ เราเห็นว่า Circuit นี้ทำเครื่องหมายสถานะที่ต้องการ $|0111\rangle$ หรือ bitstring {1110} จริงๆ

Grover operator เต็มรูปแบบประกอบด้วย phase query gate (oracle), เลเยอร์ Hadamard และ operator $Z_\text{OR}$ เราสามารถใช้ grover_operator ที่มีอยู่แล้วเพื่อสร้างสิ่งนี้จาก oracle ที่เรานิยามด้านบน

grover_op = grover_operator(oracle)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

ตามที่เราเถียงด้านบน เราอาจต้องนำ Grover operator ไปใช้หลายครั้ง จำนวนการวนซ้ำที่เหมาะสม $t$ เพื่อเพิ่มแอมพลิจูดของสถานะเป้าหมายให้สูงสุดในกรณีที่ไม่มี noise สามารถหาได้จากนิพจน์นี้:

$$(2t+1)\theta = (2t+1)\sin^{-1}\left( \sqrt{\frac{|A_1|}{N}}\right) \approx (2t+1)\sqrt{\frac{|A_1|}{N}} \approx \frac{\pi}{2}\\ t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

ที่นี่ $A_1$ คือจำนวนคำตอบหรือสถานะเป้าหมาย บนคอมพิวเตอร์ควอนตัมที่มี noise ในปัจจุบัน จำนวนการวนซ้ำที่เหมาะสมในทางทดลองอาจแตกต่างกัน แต่ที่นี่เราคำนวณและใช้จำนวนที่เหมาะสมตามทฤษฎีโดยใช้ $A_1=1$

optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)
print(optimal_num_iterations)

3

มาสร้าง Circuit ที่รวม Hadamard Gate เริ่มต้นเพื่อสร้างซูเปอร์โพสิชันของสถานะที่เป็นไปได้ทั้งหมด และนำ Grover operator มาใช้จำนวนครั้งที่เหมาะสม

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

เราได้สร้าง Grover Circuit แล้ว!

ขั้นตอนที่ 2: ปรับแต่งปัญหาสำหรับการรันบน hardware ควอนตัม

เรานิยาม Circuit ควอนตัมนามธรรมแล้ว แต่เราต้องเขียนใหม่ในรูปของ Gate ที่เป็น native ของคอมพิวเตอร์ควอนตัมที่เราต้องการใช้จริงๆ เราต้องระบุด้วยว่าควรใช้ Qubit ตัวใดบนคอมพิวเตอร์ควอนตัม ด้วยเหตุนี้และเหตุผลอื่นๆ เราต้อง transpile Circuit ของเราก่อน มาระบุคอมพิวเตอร์ควอนตัมที่ต้องการใช้

ด้านล่างมีโค้ดสำหรับบันทึก credentials ในการใช้งานครั้งแรก ตรวจสอบให้แน่ใจว่าลบข้อมูลนี้ออกจาก notebook หลังจากบันทึกลงใน environment แล้ว เพื่อไม่ให้ credentials ของคุณถูกแชร์โดยไม่ตั้งใจเมื่อแชร์ notebook ดู ตั้งค่าบัญชี IBM Cloud และ เริ่มต้น service ในสภาพแวดล้อมที่ไม่น่าเชื่อถือ สำหรับคำแนะนำเพิ่มเติม

# To run on hardware, select the backend with the fewest number of jobs in the queue
from qiskit_ibm_runtime import QiskitRuntimeService

# Syntax for first saving your token.  Delete these lines after saving your credentials.
# QiskitRuntimeService.save_account(channel='ibm_quantum_platform', instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

backend = service.least_busy(operational=True, simulator=False)
backend.name

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.

'ibm_brisbane'

ตอนนี้เราใช้ preset pass manager เพื่อปรับแต่ง Circuit ควอนตัมของเราสำหรับ Backend ที่เลือก

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

circuit_isa = pm.run(qc)
# The transpiled circuit will be very large. Only draw it if you are really curious.
# circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

ในตอนนี้ควรสังเกตว่าความลึกของ Circuit ควอนตัมที่ transpile แล้วนั้นมีนัยสำคัญ

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  439
The depth of two-qubit gates is  113

นี่เป็นตัวเลขที่ค่อนข้างใหญ่มาก แม้แต่สำหรับกรณีง่ายๆ นี้ เนื่องจาก Gate ควอนตัมทั้งหมด (โดยเฉพาะ Gate สอง Qubit) ประสบกับข้อผิดพลาดและอยู่ภายใต้ noise ชุดของ Gate สอง Qubit กว่า 100 ตัวจะส่งผลเพียง noise เท่านั้น หาก Qubit ไม่มีประสิทธิภาพสูงเป็นพิเศษ มาดูกันว่าสิ่งเหล่านี้ทำงานอย่างไร

รันโดยใช้ Qiskit primitives

เราต้องการทำการวัดจำนวนมากและดูว่าสถานะใดน่าจะเป็นมากที่สุด การขยายแอมพลิจูดดังกล่าวเป็นปัญหาการสุ่มตัวอย่างที่เหมาะสำหรับการรันด้วย Sampler Qiskit Runtime primitive

สังเกตว่าเมธอด run() ของ Qiskit Runtime SamplerV2 รับ iterable ของ primitive unified blocks (PUBs) สำหรับ Sampler แต่ละ PUB เป็น iterable ในรูปแบบ (circuit, parameter_values) อย่างไรก็ตาม ขั้นต่ำต้องใช้รายการ Circuit ควอนตัม

# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

เพื่อให้ได้ประโยชน์สูงสุดจากประสบการณ์นี้ เราแนะนำให้รันการทดลองบนคอมพิวเตอร์ควอนตัมจริงจาก IBM Quantum อย่างยิ่ง อย่างไรก็ตาม หากคุณใช้เวลา QPU หมดแล้ว คุณสามารถ uncomment บรรทัดด้านล่างเพื่อทำกิจกรรมนี้โดยใช้ simulator

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

ขั้นตอนที่ 4: ประมวลผลหลังและคืนผลลัพธ์ในรูปแบบคลาสสิกที่ต้องการ

ตอนนี้เราสามารถพล็อตผลลัพธ์ของการสุ่มตัวอย่างในฮิสโตแกรม

plot_distribution(dist)

เราเห็นว่าอัลกอริทึมของ Grover คืนสถานะที่ต้องการด้วยความน่าจะเป็นสูงที่สุดอย่างมาก อย่างน้อยหนึ่ง order of magnitude สูงกว่าตัวเลือกอื่นๆ ในกิจกรรมถัดไป เราจะใช้อัลกอริทึมในวิธีที่สอดคล้องกับ workflow ของ query algorithm สองฝ่ายมากขึ้น

ทดสอบความเข้าใจ

อ่านคำถามด้านล่าง คิดหาคำตอบ แล้วคลิกสามเหลี่ยมเพื่อดูเฉลย

เราเพิ่งค้นหาคำตอบเดียวจากชุดของ $2^4=16$ สถานะที่เป็นไปได้ เราระบุจำนวนการวนซ้ำที่เหมาะสมของ Grover operator ว่า $t=3$ จำนวนที่เหมาะสมนี้จะเพิ่มขึ้นหรือลดลงหากเราค้นหา (a) คำตอบหลายตัว หรือ (b) คำตอบเดียวในพื้นที่ที่มีสถานะที่เป็นไปได้มากกว่า?

คำตอบ:

จำไว้ว่าตราบใดที่จำนวนคำตอบน้อยกว่าพื้นที่คำตอบทั้งหมดมาก เราสามารถขยาย sine function ใกล้มุมเล็กและใช้

$$(2t+1)\theta = (2t+1) \sin^{-1}{\sqrt{\frac{|\mathcal{A}_1|}{N}}}\approx (2t+1) \sqrt{\frac{|\mathcal{A}_1|}{N}} \approx \pi/2\\ t \approx \frac{\pi}{4}\sqrt{\frac{N}{|\mathcal{A}_1|}}-\frac{1}{2}$$

(a) เราเห็นจากนิพจน์ด้านบนว่าการเพิ่มจำนวนสถานะคำตอบจะลดจำนวนการวนซ้ำ ตราบใดที่อัตราส่วน $\frac{|\mathcal{A}_1|}{N}$ ยังเล็กอยู่ เราสามารถอธิบายว่า $t$ จะลดลงอย่างไร: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}$

(b) เมื่อพื้นที่ของคำตอบที่เป็นไปได้ ($N$) เพิ่มขึ้น จำนวนการวนซ้ำที่ต้องการเพิ่มขึ้น แต่เพียงแค่ $t~\sqrt{N}$

สมมติว่าเราสามารถเพิ่มขนาดของ target bitstring ให้ยาวได้ตามต้องการ และยังคงได้ผลลัพธ์ที่ความน่าจะเป็นของแอมพลิจูดของสถานะเป้าหมายสูงกว่าสถานะอื่นอย่างน้อยหนึ่ง order of magnitude นั่นหมายความว่าเราสามารถใช้อัลกอริทึมของ Grover เพื่อหาสถานะเป้าหมายได้อย่างน่าเชื่อถือหรือไม่?

คำตอบ:

ไม่ สมมติว่าเราทำกิจกรรมแรกซ้ำด้วย 20 Qubit และรัน Circuit ควอนตัมหลายครั้ง num_shots = 10,000 การกระจายความน่าจะเป็นสม่ำเสมอหมายความว่าทุกสถานะมีความน่าจะเป็น $10,000/2^{20}=0.00954$ ของการวัดแม้แต่ครั้งเดียว หากความน่าจะเป็นของการวัดสถานะเป้าหมายเป็น 10 เท่าของสถานะที่ไม่ใช่คำตอบ (และความน่าจะเป็นของแต่ละสถานะที่ไม่ใช่คำตอบลดลงเล็กน้อยตามสัดส่วน) จะมีโอกาสเพียงประมาณ 10% ในการวัดสถานะเป้าหมายแม้แต่ครั้งเดียว มีโอกาสน้อยมากที่จะวัดสถานะเป้าหมายหลายครั้ง ซึ่งทำให้แยกแยะจากสถานะที่ไม่ใช่คำตอบจำนวนมากที่ได้มาแบบสุ่มได้ยาก ข่าวดีคือเราสามารถได้ผลลัพธ์ที่มีความแม่นยำสูงกว่าโดยใช้ error suppression และ mitigation

กิจกรรมที่ 2: Workflow ของ query algorithm ที่แม่นยำ

เราจะเริ่มต้นกิจกรรมนี้เช่นเดียวกับกิจกรรมแรก ยกเว้นว่าตอนนี้คุณจะจับคู่กับผู้ที่ชื่นชอบ Qiskit อีกคน คุณจะเลือก secret bitstring และ partner ของคุณจะเลือก bitstring ที่ต่างออกไป (โดยทั่วไป) คุณแต่ละคนจะสร้าง Circuit ควอนตัมที่ทำหน้าที่เป็น oracle และแลกเปลี่ยนกัน จากนั้นคุณจะใช้อัลกอริทึมของ Grover กับ oracle นั้นเพื่อหา secret bitstring ของ partner

ขั้นตอนที่ 1: แมป input คลาสสิกไปยังปัญหาควอนตัม

ใช้ฟังก์ชัน grover_oracle ที่นิยามด้านบน สร้าง Circuit oracle สำหรับสถานะที่ทำเครื่องหมายหนึ่งสถานะหรือมากกว่า ตรวจสอบให้แน่ใจว่าบอก partner ว่าคุณทำเครื่องหมายกี่สถานะ เพื่อให้พวกเขานำ Grover operator ไปใช้จำนวนครั้งที่เหมาะสม อย่าทำให้ bitstring ยาวเกินไป ควรใช้ 3-5 บิตซึ่งทำงานได้โดยไม่ยุ่งยากมาก bitstring ที่ยาวกว่าจะส่งผลให้ Circuit ลึกซึ่งต้องใช้เทคนิคขั้นสูงกว่า เช่น error mitigation

# Modify the marked states to mark those you wish to target.
marked_states = ["1000"]
oracle = grover_oracle(marked_states)

ตอนนี้คุณได้สร้าง Circuit ควอนตัมที่พลิกเฟสของสถานะเป้าหมายแล้ว คุณสามารถบันทึก Circuit นี้เป็น my_circuit.qpy โดยใช้ syntax ด้านล่าง

from qiskit import qpy

# Save to a QPY file at a location where you can easily find it.
# You might want to specify a global address.
with open("C:\\Users\\...put your own address here...\\my_circuit.qpy", "wb") as f:
    qpy.dump(oracle, f)

ส่งไฟล์นี้ให้ partner (ทางอีเมล, messaging service, shared repo และอื่นๆ) ให้ partner ส่ง Circuit ของพวกเขาให้คุณด้วย ตรวจสอบให้แน่ใจว่าบันทึกไฟล์ไว้ที่ที่หาง่าย เมื่อได้รับ Circuit ของ partner แล้ว คุณอาจลองวาดมัน แต่นั่นจะทำให้ query model เสียหาย นั่นคือ เรากำลังจำลองสถานการณ์ที่คุณสามารถ query oracle (ใช้ Circuit oracle) ได้แต่ไม่สามารถตรวจสอบมันเพื่อหาสถานะที่มันเล็งเป้าหมาย

from qiskit import qpy

# Load the circuit from your partner's qpy file from the folder where you saved it.
with open("C:\\Users\\...file location here...\\my_circuit.qpy", "rb") as f:
    circuits = qpy.load(f)

# qpy.load always returns a list of circuits
oracle_partner = circuits[0]

# You could visualize the circuit, but this would break the model of a query algorithm.
# oracle_partner.draw("mpl")

ถาม partner ว่าพวกเขาเข้ารหัสกี่สถานะเป้าหมายและใส่ค่าด้านล่าง

# Update according to your partner's number of target states.
num_marked_states = 1

ค่านี้ถูกใช้ในนิพจน์ถัดไปเพื่อหาจำนวนการวนซ้ำของ Grover ที่เหมาะสม

grover_op = grover_operator(oracle_partner)
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_marked_states / 2**grover_op.num_qubits)))
)
qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

ขั้นตอนที่ 2: ปรับแต่งปัญหาสำหรับการรันบน hardware ควอนตัม

ดำเนินการเช่นเดียวกับก่อนหน้า

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
backend.name

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_partner_isa = pm.run(qc)

ขั้นตอนที่ 3: รันโดยใช้ Qiskit primitives

กระบวนการนี้เหมือนกับในกิจกรรมแรก

# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_partner_isa]).result()
dist = result[0].data.meas.get_counts()

ขั้นตอนที่ 4: ประมวลผลหลังและคืนผลลัพธ์ในรูปแบบคลาสสิกที่ต้องการ

ตอนนี้แสดงฮิสโตแกรมของผลลัพธ์การสุ่มตัวอย่าง สถานะหนึ่งหรือมากกว่าควรมีความน่าจะเป็นในการวัดสูงกว่าตัวอื่นมาก รายงานสิ่งเหล่านี้ให้ partner และตรวจสอบว่าคุณระบุสถานะเป้าหมายได้ถูกต้องหรือไม่ โดยค่าเริ่มต้น ฮิสโตแกรมที่แสดงเป็นของ Circuit เดียวกับกิจกรรมแรก คุณควรได้ผลลัพธ์ที่ต่างออกไปจาก Circuit ของ partner

plot_distribution(dist)

ทดสอบความเข้าใจ

อ่านคำถามหรือคำแนะนำด้านล่าง คิดหาคำตอบหรือพูดถึงกระบวนการกับ partner คลิกสามเหลี่ยมสำหรับคำใบ้หรือข้อเสนอแนะ

คุณควรได้รับสถานะเป้าหมายของ partner อย่างถูกต้อง หากไม่ได้ ให้ทำงานร่วมกับ partner เพื่อหาว่าเกิดอะไรผิดพลาด คลิกด้านล่างสำหรับไอเดียบางอย่าง

คำใบ้:

• วาด/แสดง Circuit ของ partner และตรวจสอบให้แน่ใจว่าโหลดถูกต้อง
• เปรียบเทียบ Circuit ที่ใช้และเปรียบเทียบผลลัพธ์ที่คาดหวังกับที่ได้มา
• ตรวจสอบความลึกของ Circuit ที่ใช้เพื่อให้แน่ใจว่า bitstring ไม่ยาวเกินไปหรือจำนวนการวนซ้ำของ Grover สูงเกินไปที่จะใช้งาน

หากยังไม่ได้ทำ วาด Circuit oracle ที่ partner ส่งมา ลองพูดถึงผลของ Gate แต่ละตัวและเถียงว่าสถานะเป้าหมายน่าจะเป็นอะไร สิ่งนี้จะง่ายกว่ามากสำหรับกรณีที่มีสถานะที่ทำเครื่องหมายเดียวกว่าหลายตัว

คำใบ้:

• จำไว้ว่าหน้าที่ของ oracle คือพลิกเครื่องหมายบนสถานะเป้าหมาย
• จำไว้ว่า MCMTGate พลิกเครื่องหมายบนสถานะก็ต่อเมื่อ Qubit ทั้งหมดที่ใช้ใน control อยู่ในสถานะ $|1\rangle$
• หากสถานะเป้าหมายของคุณมี $|1\rangle$ บน Qubit เฉพาะอยู่แล้ว คุณไม่จำเป็นต้องทำอะไรกับ Qubit นั้น หากเป้าหมายมี $|0\rangle$ บน Qubit เฉพาะและคุณต้องการให้ MCMTGate พลิกเครื่องหมาย คุณต้องนำ gate X ไปใช้กับ Qubit นั้นใน oracle ของคุณ (และจากนั้นยกเลิก gate X หลังจาก MCMTGate)

ทำซ้ำการทดลองโดยลดจำนวนการวนซ้ำของ Grover operator ลงหนึ่งครั้ง คุณยังได้คำตอบที่ถูกต้องหรือไม่? ทำไม?

แนวทาง:

น่าจะได้ แม้ว่าอาจขึ้นอยู่กับจำนวนคำตอบที่เข้ารหัส สิ่งนี้เน้นให้เห็นความละเอียดอ่อน: จำนวน "ที่เหมาะสม" ของการวนซ้ำ Grover คือจำนวนที่ทำให้ความน่าจะเป็นของการวัดสถานะที่ทำเครื่องหมายสูงที่สุดเท่าที่เป็นไปได้ แต่การวนซ้ำน้อยกว่านั้นอาจยังทำให้สถานะที่ทำเครื่องหมายน่าจะเป็นมากกว่าสถานะอื่นอย่างมีนัยสำคัญ ดังนั้นคุณอาจสามารถทำได้ด้วยการวนซ้ำน้อยกว่าจำนวนที่เหมาะสม ซึ่งลดความลึกของ Circuit และลดอัตราข้อผิดพลาด

ทำไมบางคนอาจต้องการใช้การวนซ้ำ Grover น้อยกว่า "จำนวนที่เหมาะสม" ที่ระบุไว้ที่นี่?

คำตอบ:

จำนวน "ที่เหมาะสม" ของการวนซ้ำ Grover คือจำนวนที่ทำให้ความน่าจะเป็นของการวัดสถานะที่ทำเครื่องหมายสูงที่สุดเท่าที่เป็นไปได้ในกรณีที่ไม่มี noise แต่การวนซ้ำน้อยกว่านั้นอาจยังทำให้สถานะที่ทำเครื่องหมายน่าจะเป็นมากกว่าสถานะอื่นอย่างมีนัยสำคัญ ดังนั้นคุณอาจสามารถทำได้ด้วยการวนซ้ำน้อยกว่าจำนวนที่เหมาะสม ซึ่งลดความลึกของ Circuit และลดอัตราข้อผิดพลาด

กิจกรรมที่ 3: เกณฑ์อื่นนอกจาก bitstring เฉพาะ

สำหรับภาพประกอบสุดท้ายว่าอัลกอริทึมของ Grover อาจมีประโยชน์อย่างไรในบริบทของซับรูทีน ลองจินตนาการว่าเราต้องการสถานะควอนตัมที่มีจำนวน 1 ในการแสดง bitstring เฉพาะ สิ่งนี้พบบ่อยในสถานการณ์ที่เกี่ยวข้องกับกฎอนุรักษ์ ตัวอย่างเช่น ในบริบทของเคมีควอนตัม เราบ่อยครั้งแมปสถานะ 1 ของ Qubit ไปยังการครอบครองของ orbital อิเล็กตรอน เพื่ออนุรักษ์ประจุ จำนวน 1 ทั้งหมดต้องคงที่ด้วย ข้อจำกัดเช่นนี้พบบ่อยมากจนมีชื่อพิเศษ: ข้อจำกัดน้ำหนัก Hamming และจำนวน 1 ในสถานะเรียกว่า น้ำหนัก Hamming

ขั้นตอนที่ 1:

มาเขียนฟังก์ชันที่ทำเครื่องหมายสถานะด้วยน้ำหนัก Hamming ที่ต้องการก่อน เราจะเขียนสิ่งนี้แบบทั่วไปสำหรับจำนวน Qubit ที่ไม่ระบุ num_qubits และน้ำหนัก Hamming เป้าหมาย target_weight

from qiskit import QuantumCircuit

def grover_oracle_hamming_weight(num_qubits, target_weight):
    """
    Build a Grover oracle that marks all states with Hamming weight == target_weight.

    Parameters:
        num_qubits (int): Number of qubits in the circuit.
        target_weight (int): The Hamming weight to mark.

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle.
    """
    qc = QuantumCircuit(num_qubits)
    marked_count = 0
    marked_list = []
    for x in range(2**num_qubits):
        bitstr = format(x, f"0{num_qubits}b")
        if bitstr.count("1") == target_weight:
            # Count the number of target states
            marked_count = marked_count + 1
            marked_list.append(bitstr)
            # Reverse for Qiskit bit order (qubit 0 is rightmost)
            rev_target = bitstr[::-1]
            zero_inds = [i for i, b in enumerate(rev_target) if b == "0"]
            # Apply X gates to 'open' controls (where bit is 0)
            qc.x(zero_inds)
            # Multi-controlled Z (as MCX conjugated by H)
            if num_qubits == 1:
                qc.z(0)
            else:
                qc.h(num_qubits - 1)
                qc.mcx(list(range(num_qubits - 1)), num_qubits - 1)
                qc.h(num_qubits - 1)
            # Undo X gates
            qc.x(zero_inds)
    return qc, marked_count, marked_list

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(3, 2)
print(marked_states)
oracle.draw(output="mpl", style="iqp")

['011', '101', '110']

จากนี้กระบวนการทั้งหมดเหมือนกับสองกิจกรรมก่อนหน้า เพื่อความกระชับ ขั้นตอน Qiskit patterns แสดงเฉพาะใน comment โค้ดที่นี่

from qiskit_ibm_runtime import SamplerV2 as Sampler

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(4, 2)
oracle.draw(output="mpl", style="iqp")

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)

qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()
qc.draw(output="mpl", style="iqp")

# Step 2: Optimize for running on real quantum computers

service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
print(backend.name)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

# Step 3: Execute using Qiskit primitives
# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:51,686: Default instance not set. Searching all available instances.

ibm_brisbane

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  502
The depth of two-qubit gates is  130

num_marked_states

6

plot_distribution(dist)

ที่นี่อัลกอริทึมของ Grover เตรียมสถานะที่มีน้ำหนัก Hamming 2 ให้น่าจะถูกวัดมากกว่าสถานะอื่นๆ อย่างมาก ประมาณหนึ่ง order of magnitude มากกว่า

แนวคิดสำคัญ:

ในโมดูลนี้ เราได้เรียนรู้คุณสมบัติสำคัญของอัลกอริทึมของ Grover:

• ขณะที่อัลกอริทึมการค้นหาแบบไม่มีโครงสร้างแบบคลาสสิกต้องการจำนวนการสอบถามที่ scale เชิงเส้นตามขนาดของพื้นที่ $N,$ อัลกอริทึมของ Grover ต้องการจำนวนการสอบถามที่ scale เหมือน $\sqrt{N}$
• อัลกอริทึมของ Grover เกี่ยวข้องกับการซ้ำชุดการดำเนินการ (มักเรียกว่า "Grover operator") จำนวน $t$ ครั้ง ซึ่งเลือกให้ทำให้สถานะเป้าหมายน่าจะถูกวัดมากที่สุด
• อัลกอริทึมของ Grover สามารถรันด้วยการวนซ้ำน้อยกว่า $t$ ครั้งและยังคงขยายสถานะเป้าหมาย
• อัลกอริทึมของ Grover เข้ากับโมเดลการสอบถามของการประมวลผลและมีความหมายมากที่สุดเมื่อบุคคลหนึ่งควบคุมการค้นหาและอีกคนควบคุม/สร้าง oracle และอาจมีประโยชน์เป็นซับรูทีนในการประมวลผลควอนตัมที่ซับซ้อนกว่า

คำถาม

คำถาม T/F:

1. T/F อัลกอริทึมของ Grover ให้การปรับปรุงแบบเลขยกกำลังเหนืออัลกอริทึมคลาสสิกในจำนวนการสอบถามที่จำเป็นเพื่อค้นหาสถานะที่ทำเครื่องหมายเดียวในการค้นหาแบบไม่มีโครงสร้าง

2. T/F อัลกอริทึมของ Grover ทำงานโดยการเพิ่มความน่าจะเป็นซ้ำๆ ว่าสถานะคำตอบจะถูกวัด

3. T/F ยิ่งวนซ้ำ Grover operator มากเท่าไหร่ ความน่าจะเป็นในการวัดสถานะคำตอบก็ยิ่งสูงขึ้น

คำถาม MC:

1. เลือกตัวเลือกที่ดีที่สุดเพื่อเติมประโยค กลยุทธ์ที่ดีที่สุดในการใช้อัลกอริทึมของ Grover ให้สำเร็จบนคอมพิวเตอร์ควอนตัมสมัยใหม่คือการวนซ้ำ Grover operator...

• a. เพียงครั้งเดียว
• b. เสมอ $t$ ครั้ง เพื่อเพิ่มแอมพลิจูดของสถานะคำตอบให้สูงสุด
• c. ไม่เกิน $t$ ครั้ง แม้ว่าน้อยกว่าอาจเพียงพอที่จะทำให้สถานะคำตอบโดดเด่น
• d. ไม่น้อยกว่า 10 ครั้ง

2. Circuit การสอบถามเฟสที่แสดงที่นี่ทำหน้าที่เป็น oracle เพื่อทำเครื่องหมายสถานะบางสถานะด้วยการพลิกเฟส สถานะใดต่อไปนี้ถูกทำเครื่องหมายโดย Circuit นี้?

• a. $|0000\rangle$
• b. $|0101\rangle$
• c. $|0110\rangle$
• d. $|1001\rangle$
• e. $|1010\rangle$
• f. $|1111\rangle$

3. สมมติว่าคุณต้องการค้นหาสามสถานะที่ทำเครื่องหมายจากชุดของ 128 จำนวนการวนซ้ำที่เหมาะสมของ Grover operator เพื่อเพิ่มแอมพลิจูดของสถานะที่ทำเครื่องหมายให้สูงสุดคือเท่าใด?

• a. 1
• b. 3
• c. 5
• d. 6
• e. 20
• f. 33

คำถามสำหรับถกเถียง:

1. เงื่อนไขอื่นใดที่คุณอาจใช้ใน quantum oracle? ลองพิจารณาเงื่อนไขที่ระบุหรือกำหนดบน bitstring ได้ง่าย แต่ไม่ใช่แค่การเขียน bitstring ที่ทำเครื่องหมายออกมา

2. คุณเห็นปัญหาใดๆ กับการ scale อัลกอริทึมของ Grover บนคอมพิวเตอร์ควอนตัมสมัยใหม่หรือไม่?