อัลกอริทึมของ 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®

ภาพทางเรขาคณิต

ตัวอย่างสอง Qubit ด้านบนแสดงให้เห็นว่าพีชคณิตทำงานอย่างไรสำหรับกรณีเล็กๆ แต่มีวิธีที่ง่ายกว่ามากในการทำความเข้าใจอัลกอริทึมของ Grover: เป็นลำดับของการสะท้อนทางเรขาคณิตในระนาบสองมิติ ด้านล่างเราจะอธิบายภาพนี้ คุณยังดูหลักสูตรของ John Watrous Fundamentals of Quantum Algorithms สำหรับรายละเอียดเพิ่มเติมได้

การตั้งค่าระนาบ เราสามารถแยกสถานะซูเปอร์โพสิชันเริ่มต้น $|\psi\rangle$ ออกเป็นสองส่วน สถานะที่ถูกต้อง — ที่เรากำลังค้นหา — เรียกว่า $|A_1\rangle$ ส่วนสถานะอื่นๆ ทั้งหมด รวมกัน เรียกว่า $|A_0\rangle$ ตามนิยาม $|A_1\rangle$ และ $|A_0\rangle$ ตั้งฉากกัน ดังนั้นเราสามารถพล็อตเป็นแกนตั้งฉากในพื้นที่สองมิตินามธรรม เนื่องจาก $|\psi\rangle$ เป็นการรวมเชิงเส้นของสองส่วนนี้ มันอยู่ที่มุมเล็กๆ $\theta$ กับแกน $|A_0\rangle$ — ใกล้ $|A_0\rangle$ เพราะในตอนเริ่มต้น เพียงเศษเล็กน้อยของสถานะอยู่ในส่วน $|A_1\rangle$ ที่ถูกต้อง

การสะท้อน ข้อเท็จจริงทางคณิตศาสตร์สำคัญที่เราต้องการคือ operator ในรูปแบบ

$$2|v\rangle\langle v| - I$$

สะท้อนสถานะใดก็ตามเกี่ยวกับแกนที่นิยามโดย $|v\rangle$ เพื่อดูว่าทำไม ให้พิจารณาสองกรณี: สถานะตาม $|v\rangle$ ไม่เปลี่ยนแปลง และสถานะตั้งฉากกับ $|v\rangle$ จะได้เครื่องหมายพลิก สถานะใดๆ สามารถแยกออกเป็นสองส่วนนี้ และ operator กระทำต่อแต่ละส่วนตามนั้น — ซึ่งเป็นการสะท้อนเกี่ยวกับ $|v\rangle$ พอดี

ปรากฏว่าทั้งขั้นตอน oracle และ diffusion ในอัลกอริทึมของ Grover สามารถแสดงเป็นการสะท้อนในภาพทางเรขาคณิตนี้

Oracle เป็นการสะท้อน Oracle พลิกเครื่องหมายของสถานะ $|A_1\rangle$ และปล่อยสิ่งอื่นๆ ไว้ตามเดิม ซึ่งเหมือนกับการสะท้อนเกี่ยวกับแกน $|A_0\rangle$

Diffusion เป็นการสะท้อน มันยุ่งยากกว่าเล็กน้อยที่จะเห็นว่า diffusion operator เป็นการสะท้อนด้วย Diffusion operator คือ

$$H^{\otimes n}\, Z_{\text{OR}}\, H^{\otimes n}$$

$Z_{\text{OR}}$ เองเป็นการสะท้อนเกี่ยวกับสถานะทั้งหมดเป็นศูนย์ เนื่องจากพลิกเครื่องหมายของสถานะทุกตัวที่ไม่ใช่ $|0\rangle^{\otimes n}$ สิ่งนี้เขียนได้เป็น $2|0\rangle\langle 0| - I$ เลเยอร์ Hadamard ที่ล้อมรอบนั้นทำการเปลี่ยนฐานอย่างมีประสิทธิภาพ เปลี่ยนแปลงแกนการสะท้อน จำไว้ว่า $H^{\otimes n}$ แมป $|0\rangle^{\otimes n}$ ไปยังซูเปอร์โพสิชันสม่ำเสมอ $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$ เนื่องจาก Hadamard เป็นตัวผกผันของตัวเอง นิพจน์เต็มจะกลายเป็น

$$H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n} = 2|u\rangle\langle u| - I$$

ซึ่งเป็นการสะท้อนเกี่ยวกับ $|u\rangle$ เนื่องจาก $|u\rangle$ ใกล้ $|\psi\rangle$ มาก (ทั้งคู่อยู่ใกล้ $|A_0\rangle$) การสะท้อนครั้งที่สองนี้ส่งสถานะไปยังมุม $2\theta$ จากจุดเริ่มต้น

การหมุน $2\theta$ ผลรวมของการสะท้อนสองครั้งนี้คือการหมุน $2\theta$ ไปทาง $|A_1\rangle$ การวนซ้ำของ Grover operator แต่ละครั้งหมุนสถานะอีก $2\theta$

จำนวนการวนซ้ำที่เหมาะสม เป้าหมายของเราคือหมุนสถานะให้ใกล้ $|A_1\rangle$ ที่สุด หมายความว่าหมุนรวมประมาณ $\pi/2$ เรเดียน (หนึ่งในสี่รอบ) หากแต่ละการวนซ้ำให้ $2\theta$ จำนวนการวนซ้ำที่เหมาะสม $t$ จะต้องตรงตาม

$$(2t + 1)\theta \approx \frac{\pi}{2}$$

สำหรับคำตอบเดียวในบรรดา $N$ สถานะ มุมเริ่มต้นคือ $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (สำหรับ $N$ ขนาดใหญ่) แทนค่า

$$t \approx \frac{\pi}{4}\sqrt{N} - \frac{1}{2}$$

นี่คือที่มาของการเร่งความเร็ว $\sqrt{N}$ อันโด่งดัง: เราต้องการเพียง $O(\sqrt{N})$ การวนซ้ำเพื่อถึงเป้าหมาย แทนที่จะต้องตรวจสอบ $O(N)$ ครั้งตามที่การค้นหาแบบคลาสสิกต้องการ

โดยทั่วไปแล้ว หากมีสถานะคำตอบ $|A_1|$ สถานะในบรรดา $N$ สถานะทั้งหมด จำนวนการวนซ้ำที่เหมาะสมคือ

$$t \approx \frac{\pi}{4}\sqrt{\frac{N}{|A_1|}} - \frac{1}{2}$$

สังเกตว่าหากใช้การวนซ้ำมากเกินไป คุณจะหมุนเลย $|A_1\rangle$ และความน่าจะเป็นในการหาสถานะเป้าหมายจะเริ่มลดลงอีกครั้ง การหาจำนวนการวนซ้ำที่ถูกต้องนั้นสำคัญ แม้ว่าบน hardware ควอนตัมที่มี noise จำนวนที่เหมาะสมในทางทดลองอาจแตกต่างจากสูตรในอุดมคตินี้

ทำไมอัลกอริทึมของ Grover ถึงมีประโยชน์?

ณ จุดนี้คุณอาจสงสัยว่า: เราเพิ่งสร้าง oracle ที่ทำเครื่องหมายสถานะเป้าหมาย — แต่ในการสร้าง เราต้องรู้สถานะเป้าหมาย แล้วเรากำลังค้นหาอะไรจริงๆ?

นี่เป็นคำถามที่สมเหตุสมผล และมีคำตอบที่ดีหลายข้อ

• โมเดลการสอบถามเป็นเครื่องมือเชิงทฤษฎี โมเดลการสอบถามของการประมวลผลไม่ได้ออกแบบมาให้ใช้งานได้จริงโดยตรง จุดประสงค์คือให้เราวิเคราะห์ความซับซ้อนของอัลกอริทึมได้อย่างชัดเจนโดยแยกปัญหาออกเป็นสองส่วน: oracle และสิ่งอื่นๆ การค้นหายากแค่ไหน เมื่อการตรวจสอบฟรี? จำนวนการสอบถาม scale อย่างไรตามขนาดของ input? คำถามเหล่านี้มีประโยชน์แม้ว่าจะไม่มีระบบจริงที่ทำงานแบบนี้พอดี

• คุณยังคิดได้ว่าเป็น กิจกรรมสองฝ่าย: คนหนึ่งรู้สถานะเป้าหมายและสร้าง oracle ส่วนงานของอีกคนคือหาคำตอบโดยใช้ oracle เป็นกล่องดำโดยไม่แอบดูข้างใน ในกิจกรรมที่ 2 ด้านล่าง คุณจะทำแบบนี้กับ partner พอดี

• Amplitude amplification เป็นซับรูทีนที่มีประโยชน์กว้างขวาง แม้ว่าการสาธิตครั้งแรกนี้อาจดูวนเวียน กลไกพื้นฐาน — ที่เรียกว่า amplitude amplification — ปรากฏซ้ำๆ ในการประมวลผลเชิงควอนตัม สิ่งที่เราสร้างที่นี่จริงๆ คือสัญชาตญาณสำหรับเครื่องมือที่ปรากฏเป็นซับรูทีนในอัลกอริทึมควอนตัมที่ซับซ้อนกว่ามากมาย

• มีปัญหาที่คุณสามารถสร้าง oracle ได้โดยไม่รู้คำตอบ ข้อมูลเชิงลึกสำคัญคือมีคลาสของปัญหาทั้งหมดที่มันยากมากที่จะ หา คำตอบ แต่ง่ายมากที่จะ ตรวจสอบ ว่าคำตอบที่กำหนดนั้นถูกต้อง การแยกตัวประกอบเป็นตัวอย่างหนึ่ง: ให้ผลคูณของจำนวนเฉพาะขนาดใหญ่สองตัว มันยากมากที่จะหาว่าจำนวนเฉพาะเหล่านั้นคืออะไร แต่เมื่อมีแล้ว คุณสามารถคูณเพื่อตรวจสอบได้ง่าย (เรามีอัลกอริทึมที่ดีกว่า Grover สำหรับการแยกตัวประกอบโดยเฉพาะ — ดูอัลกอริทึมของ Shor — แต่นี่ไม่ใช่ปัญหาเดียวที่มีคุณสมบัตินี้) Sudoku, constraint satisfaction และแม้แต่เกมคลาสสิก Minesweeper ล้วนเป็นปัญหาที่ยากต่อการแก้แต่ง่ายต่อการตรวจสอบ

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

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

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

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

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
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 คือ

$$t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

โดยที่ $|A_1|$ คือจำนวนสถานะคำตอบและ $N=2^n$ คือจำนวนสถานะทั้งหมด บนคอมพิวเตอร์ควอนตัมที่มี 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 ไม่มีประสิทธิภาพสูงเป็นพิเศษ มาดูกันว่าสิ่งเหล่านี้ทำงานอย่างไร

ขั้นตอนที่ 3: รันโดยใช้ 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: แก้ตาราง Minesweeper ด้วยอัลกอริทึมของ Grover

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

Minesweeper ได้รับการพิสูจน์แล้วว่าเป็น NP-complete: ยากต่อการแก้แต่ง่ายต่อการตรวจสอบ ทำให้เป็นตัวเลือกที่เหมาะสมสำหรับอัลกอริทึมของ Grover แน่นอนว่าเราไม่สามารถแก้ตาราง 9$\times$9 เต็มรูปแบบบนคอมพิวเตอร์ควอนตัมที่มี noise ได้ — Circuit จะลึกเกินไปมาก แต่เราจะใช้ตารางขนาดเล็กเป็นการสาธิตของเล่นว่าจะใช้วิธีนี้กับบอร์ดขนาดใหญ่กว่าบนเครื่องที่ทนต่อความผิดพลาดในอนาคตได้อย่างไร

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

ตาราง

นี่คือตาราง minesweeper ขนาดเล็กของเรา:

แต่ละช่องว่างสามารถแสดงด้วยตัวแปรไบนารีที่บ่งบอกว่ามีระเบิดอยู่หรือไม่ เราระบุด้วย $x_0$, $x_1$, และ $x_2$ โดยที่ $x_i = 1$ หมายความว่ามีระเบิดบนช่องนั้นและ $x_i = 0$ หมายความว่าไม่มี:

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

เข้ารหัสข้อจำกัด

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

ช่อง "1" ที่อยู่ติดกับ $x_0$ และ $x_1$ บอกว่าหนึ่งในนั้นมีระเบิด นี่คือ exclusive-OR (XOR) พอดี ซึ่งระบุด้วย $\oplus$ ที่คืนค่าจริงเมื่อมีเพียงหนึ่งใน input ที่เป็นจริง:

$$(x_0 \oplus x_1)$$

ในทำนองเดียวกัน ช่อง "1" อีกช่อง (ที่อยู่ติดกับ $x_1$ และ $x_2$) ให้เรา:

$$(x_1 \oplus x_2)$$

ช่อง "2" บอกว่าสองในสามช่องว่างต้องมีระเบิด เนื่องจาก XOR เป็นการดำเนินการ parity $x_0 \oplus x_1 \oplus x_2$ คืนค่าจริงเมื่อตัวแปร จำนวนคี่ เป็นจริง เราต้องการ จำนวนคู่ (โดยเฉพาะสอง) ที่เป็นจริง ดังนั้นเราปฏิเสธด้วย $\lnot$:

$$\lnot(x_0 \oplus x_1 \oplus x_2)$$

ด้วยตัวเอง นิพจน์นี้จะตรงตามเงื่อนไขเมื่อ qubit ศูนย์หรือสอง qubit อยู่ในสถานะ $|1\rangle$ เนื่องจากเป็นการระบุ parity แต่เมื่อรวมกับอีกสองข้อที่แต่ละข้อต้องการอย่างน้อยหนึ่งระเบิด การกำหนดที่ตรงตามเงื่อนไขเท่านั้นมีระเบิดสองลูก

เงื่อนไขทั้งสามต้องตรงตามพร้อมกัน ดังนั้นเราเชื่อมด้วย and $\land$:

$$(x_0 \oplus x_1) \;\land\; (x_1 \oplus x_2) \;\land\; \lnot(x_0 \oplus x_1 \oplus x_2)$$

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

ตอนนี้เราต้องเข้ารหัสนิพจน์บูลีนนี้ลงใน Circuit ควอนตัมที่ทำหน้าที่เป็น oracle XOR เวอร์ชันควอนตัมสามารถทำได้ด้วย CX (CNOT) gate: การใช้ CX gate สองตัวจาก data qubit ไปยัง workspace (ancilla) qubit ทำการคำนวณ XOR ของพวกมันและเก็บผลลัพธ์ใน ancilla ได้อย่างมีประสิทธิภาพ

เราแนะนำ workspace qubit สามตัว — หนึ่งตัวสำหรับแต่ละข้อ เราเก็บผลลัพธ์ของแต่ละนิพจน์บูลีนใน workspace qubit ที่สอดคล้องกัน จากนั้นใช้ multi-controlled Z gate เพื่อพลิกเฟสของสถานะสาม qubit ที่ทำให้ workspace qubit ทั้งสามอยู่ใน $|1\rangle$ (หมายความว่าทุกข้อตรงตามเงื่อนไขพร้อมกัน)

ใน code cell แรกด้านล่าง เราสร้างครึ่ง "compute" ของ oracle — ส่วนที่ประเมินแต่ละข้อและเขียนผลลัพธ์ลงใน workspace qubit

x = QuantumRegister(3, "x")
a = QuantumRegister(3, "a")
qc = QuantumCircuit(x, a)

# Clause 1: x0 XOR x1 -> stored in a[0]
qc.cx(x[0], a[0])
qc.cx(x[1], a[0])

# Clause 2: x1 XOR x2 -> stored in a[1]
qc.cx(x[1], a[1])
qc.cx(x[2], a[1])

# Clause 3: NOT(x0 XOR x1 XOR x2) -> stored in a[2]
qc.cx(x[0], a[2])
qc.cx(x[1], a[2])
qc.cx(x[2], a[2])
qc.x(a[2])  # The NOT

qc.draw("mpl", style="iqp")

ณ จุดนี้ ผลลัพธ์ของแต่ละข้อถูกเก็บใน workspace qubit ที่สอดคล้องกัน ตอนนี้เราต้องให้สถานะ data qubit สาม qubit ที่ทำให้ workspace qubit ทั้งสามอยู่ใน $|1\rangle$ รับเครื่องหมายลบ เราทำสิ่งนี้ด้วย multi-controlled Z gate (ใช้งานเป็น MCX gate ที่ประกบด้วย Hadamard gate บน target)

หลังจากใช้การพลิกเฟส เราต้อง uncompute — ยกเลิกขั้นตอนการประเมินข้อทั้งหมดในลำดับย้อนกลับ — เพื่อรีเซ็ต workspace qubit กลับไปที่ $|0\rangle$ สิ่งนี้สำคัญเพื่อให้ workspace qubit สะอาดสำหรับการวนซ้ำต่อๆ ไปของ Grover operator

# Multi-controlled Z: flip phase if all workspace qubits are |1>
qc.h(a[2])
qc.mcx([a[0], a[1]], a[2])
qc.h(a[2])

# Uncompute clause 3: NOT(x0 XOR x1 XOR x2)
qc.x(a[2])
qc.cx(x[2], a[2])
qc.cx(x[1], a[2])
qc.cx(x[0], a[2])

# Uncompute clause 2: x1 XOR x2
qc.cx(x[2], a[1])
qc.cx(x[1], a[1])

# Uncompute clause 1: x0 XOR x1
qc.cx(x[1], a[0])
qc.cx(x[0], a[0])

qc.draw("mpl", style="iqp")

Circuit นี้คือ oracle ของเรา: พลิกเฟสของสถานะ data qubit ที่ตรงตามข้อจำกัด Minesweeper ทั้งสามข้อ และปล่อย workspace qubit กลับไปที่ $|0\rangle$

ตอนนี้เราสร้าง Grover operator เต็มรูปแบบจาก oracle นี้ สังเกต argument reflection_qubits: เราส่งเฉพาะ data qubit x เนื่องจาก workspace qubit ไม่ได้เป็นส่วนหนึ่งของพื้นที่ค้นหา งานของพวกมันเสร็จสิ้นเมื่อ oracle ถูกใช้แล้ว

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

ด้วย data qubit สามตัวและสถานะคำตอบหนึ่งสถานะ จำนวนการวนซ้ำที่เหมาะสมของ Grover คือ $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$ ดังนั้นเราใช้สองการวนซ้ำ เราใช้ Hadamard gate กับ data qubit เพื่อสร้างซูเปอร์โพสิชันเริ่มต้น compose Grover operator สองครั้ง และวัดเฉพาะ data qubit

x = QuantumRegister(3, "x")
a = QuantumRegister(4, "a")
meas = ClassicalRegister(3, "meas")

qc = QuantumCircuit(x, a, meas)
# Create superposition over the data qubits only
qc.h(x)
# Apply 2 iterations of the Grover operator
qc.compose(grover_op.power(2), inplace=True)
# Measure only the data qubits
qc.measure(x, meas)
qc.decompose().draw(output="mpl", style="iqp")

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

เช่นเดิม เรา transpile Circuit สำหรับ backend เป้าหมาย

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)

ตอนนี้เราสามารถตรวจสอบความลึกของ Circuit ที่ transpile แล้ว เนื่องจาก Minesweeper oracle ใช้ workspace qubit และ CX gate หลายตัว 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),
)

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

# 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()

# 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)

สถานะ 101 ควรปรากฏด้วยความน่าจะเป็นสูงกว่าตัวอื่นมาก บ่งชี้ว่ามีระเบิดอยู่ที่ $x_0$ และ $x_2$ เราใช้คอมพิวเตอร์ควอนตัมแก้เกม Minesweeper ขนาดเล็กได้แล้ว!

แน่นอนว่าอัลกอริทึมคลาสสิกที่ดีที่สุดสำหรับ minesweeper ดีกว่าการค้นหาแบบ brute-force ผ่านการจัดวางระเบิดที่เป็นไปได้ทั้งหมด — พวกมันใช้ประโยชน์จากโครงสร้างของตาราง อัลกอริทึมของ Grover จะให้ข้อได้เปรียบเฉพาะบนบอร์ดที่ยากมากที่ออกแบบให้คลุมเครือที่สุด และแม้แต่ในกรณีนั้น ความเร่งแบบกำลังสองก็ไม่สามารถตามทันการเติบโตแบบเลขชี้กำลังได้ไม่สิ้นสุด แต่สิ่งที่ได้ข้อสรุปจริงๆ คือเทคนิค: การเข้ารหัสข้อจำกัดของปัญหาลงใน quantum oracle เป็นรูปแบบที่ทรงพลังซึ่งขยายไปสู่ constraint satisfaction, combinatorial optimization และอีกหลายโดเมน

คำถามและแนวคิดสำคัญ:

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

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

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

คำถาม 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. ปัญหาอื่นใดที่คุณสามารถกำหนดเป็นการค้นหาแบบ Grover ได้? ลองคิดถึงปัญหาที่การหาคำตอบทำได้ยากแต่การตรวจสอบคำตอบทำได้ง่าย

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