การเลือกจำนวนรอบการวนซ้ำ

เราได้พิสูจน์แล้วว่าเวกเตอร์สถานะของ register $\mathsf{Q}$ ในอัลกอริทึมของ Grover ยังคงอยู่ใน subspace สองมิติที่ถูก span ด้วย $\vert A_0\rangle$ และ $\vert A_1\rangle$ เมื่อขั้นตอนการตั้งค่าเริ่มต้นเสร็จสิ้น

เป้าหมายคือการหาสมาชิก $x\in A_1$, และเป้าหมายนี้จะสำเร็จหากเราสามารถได้สถานะ $\vert A_1\rangle$ — เพราะถ้าเราวัดสถานะนี้ เรารับประกันว่าจะได้ผลการวัด $x\in A_1$ เมื่อสถานะของ $\mathsf{Q}$ หลังจาก $t$ รอบในขั้นตอนที่ 2 คือ

$$G^t \vert u \rangle = \cos\bigl((2t + 1)\theta\bigr) \vert A_0\rangle + \sin\bigl((2t + 1)\theta\bigr) \vert A_1\rangle,$$

เราควรเลือก $t$ เพื่อให้

$$\langle A_1 \vert G^t \vert u \rangle = \sin((2t + 1)\theta)$$

ใกล้เคียง $1$ มากที่สุดในค่าสัมบูรณ์ เพื่อเพิ่มความน่าจะเป็นที่จะได้ $x\in A_1$ จากการวัด สำหรับมุมใดๆ $\theta \in (0,2\pi)$, ค่า $\sin((2t + 1)\theta)$ จะ แกว่ง เมื่อ $t$ เพิ่มขึ้น แม้ว่าจะไม่จำเป็นต้องเป็น periodic — ไม่มีการรับประกันว่าเราจะได้ค่าเดิมซ้ำ

ตามธรรมชาติ นอกจากการทำให้ความน่าจะเป็นที่จะได้สมาชิก $x\in A_1$ จากการวัดมีค่าสูงแล้ว เราก็ต้องการเลือก $t$ ให้น้อยที่สุดเท่าที่จะทำได้ เพราะการใช้ $t$ ครั้งของการดำเนินการ $G$ ต้องการ $t$ คำถามถึงฟังก์ชัน $f$ เพราะเรามุ่งทำให้ $\sin( (2t + 1) \theta)$ ใกล้เคียง $1$ ในค่าสัมบูรณ์ วิธีที่เป็นธรรมชาติในการทำเช่นนี้คือเลือก $t$ เพื่อให้

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

การหาค่า $t$ ให้ได้

$$t \approx \frac{\pi}{4\theta} - \frac{1}{2}.$$

แน่นอนว่า $t$ ต้องเป็นจำนวนเต็ม ดังนั้นเราอาจไม่สามารถได้ค่านี้พอดี — แต่สิ่งที่เราทำได้คือเลือกจำนวนเต็มที่ใกล้เคียงที่สุดกับค่านี้ ซึ่งคือ

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor.$$

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

(สำหรับข้อสังเกต หากค่าเป้าหมาย $\pi/(4\theta) - 1/2$ อยู่กึ่งกลางระหว่างจำนวนเต็มสองตัวพอดี นิพจน์ $t$ นี้คือสิ่งที่ได้จากการปัดขึ้น เราอาจเลือกปัดลงแทน ซึ่งสมเหตุสมผลเพราะหมายถึงคำถามน้อยลงหนึ่งครั้ง — แต่นี่เป็นเรื่องรองและไม่สำคัญสำหรับบทเรียนนี้)

จำไว้ว่าค่าของมุม $\theta$ ให้โดยสูตร

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{\vert A_1\vert}{N}}\biggr),$$

เราจะเห็นว่าจำนวนรอบการวนซ้ำที่แนะนำ $t$ ขึ้นอยู่กับจำนวนสตริงใน $A_1$ นี่สร้างความท้าทายหากเราไม่รู้จำนวนคำตอบ ดังที่เราจะพูดถึงในภายหลัง

การค้นหาเอกลักษณ์

ก่อนอื่น ลองมุ่งเน้นไปที่สถานการณ์ที่มีสตริง $x$ เดียวที่ $f(x)=1$ อีกวิธีในการพูดนี้คือเรากำลังพิจารณา instance ของปัญหา Unique search ในกรณีนี้เรามี

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr),$$

ซึ่งสามารถประมาณได้อย่างสะดวกเป็น

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr) \approx \sqrt{\frac{1}{N}}$$

เมื่อ $N$ มีค่ามาก ถ้าเราแทน $\theta = 1/\sqrt{N}$ ในนิพจน์

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor$$

เราจะได้

$$t = \Bigl\lfloor \frac{\pi}{4}\sqrt{N} \Bigr\rfloor.$$

เมื่อนึกถึงว่า $t$ ไม่เพียงแต่เป็นจำนวนครั้งที่การดำเนินการ $G$ ถูกนำไปใช้ แต่ยังเป็นจำนวนคำถามถึงฟังก์ชัน $f$ ที่อัลกอริทึมต้องการ เราจะเห็นว่าเรากำลังดำเนินการสู่การได้อัลกอริทึมที่ต้องการ $O(\sqrt{N})$ คำถาม

ตอนนี้เราจะตรวจสอบว่าการเลือก $t$ ที่แนะนำทำงานได้ดีแค่ไหน ความน่าจะเป็นที่การวัดสุดท้ายจะให้ผลเป็นคำตอบเอกลักษณ์สามารถแสดงได้อย่างชัดเจนเป็น

$$p(N,1) = \sin^2 \bigl( (2t + 1) \theta \bigr).$$

อาร์กิวเมนต์แรก $N$ หมายถึงจำนวนไอเทมที่เราค้นหา และอาร์กิวเมนต์ที่สองซึ่งเป็น $1$ ในกรณีนี้ หมายถึงจำนวนคำตอบ ในภายหลังเราจะใช้สัญกรณ์เดิมนี้อย่างทั่วไปขึ้น โดยมีคำตอบหลายตัว

ต่อไปนี้คือตารางความน่าจะเป็นของความสำเร็จสำหรับค่า $N = 2^n$ ที่เพิ่มขึ้น

$$\begin{array}{ll} N & p(N,1)\\ \hline 2 & 0.5000000000\\ 4 & 1.0000000000\\ 8 & 0.9453125000\\ 16 & 0.9613189697\\ 32 & 0.9991823155\\ 64 & 0.9965856808\\ 128 & 0.9956198657\\ 256 & 0.9999470421\\ 512 & 0.9994480262\\ 1024 & 0.9994612447\\ 2048 & 0.9999968478\\ 4096 & 0.9999453461\\ 8192 & 0.9999157752\\ 16384 & 0.9999997811\\ 32768 & 0.9999868295\\ 65536 & 0.9999882596 \end{array}$$

สังเกตว่าความน่าจะเป็นเหล่านี้ไม่ได้เพิ่มขึ้นอย่างเคร่งครัด โดยเฉพาะอย่างยิ่ง เรามีความผิดปกติที่น่าสนใจเมื่อ $N=4$ ที่เราได้คำตอบอย่างแน่นอน อย่างไรก็ตาม สามารถพิสูจน์ได้โดยทั่วไปว่า

$$p(N,1) \geq 1 - \frac{1}{N}$$

สำหรับ $N$ ทั้งหมด ดังนั้นความน่าจะเป็นของความสำเร็จจะเข้าหา $1$ ในขีดจำกัดเมื่อ $N$ มีค่ามาก ดังที่ค่าข้างต้นดูเหมือนจะบ่งบอก ดีมาก!

แต่สังเกตว่า แม้แต่ขอบเขตอ่อนเช่น $p(N,1) \geq 1/2$ ก็ยังแสดงถึงประโยชน์ของอัลกอริทึมของ Grover ไม่ว่าผลการวัด $x$ ที่เราได้จากการรันขั้นตอน เราสามารถตรวจสอบเสมอว่า $f(x) = 1$ โดยใช้คำถามเดียวถึง $f$ และถ้าเราล้มเหลวในการได้สตริงเอกลักษณ์ $x$ ที่ $f(x) = 1$ ด้วยความน่าจะเป็นสูงสุด $1/2$ จากการรันขั้นตอนหนึ่งครั้ง หลังจากรัน $m$ ครั้งอิสระ เราจะล้มเหลวในการได้สตริงเอกลักษณ์ $x$ นี้ด้วยความน่าจะเป็นสูงสุด $2^{-m}$ กล่าวคือ โดยใช้ $O(m \sqrt{N})$ คำถามถึง $f$ เราจะได้คำตอบเอกลักษณ์ $x$ ด้วยความน่าจะเป็นอย่างน้อย $1 - 2^{-m}$ การใช้ขอบเขตที่ดีกว่า $p(N,1) \geq 1 - 1/N$ แสดงให้เห็นว่าความน่าจะเป็นที่จะหา $x\in A_1$ โดยวิธีนี้จริงๆ แล้วอย่างน้อย $1 - N^{-m}$

คำตอบหลายตัว

เมื่อจำนวนสมาชิกใน $A_1$ เปลี่ยนแปลง มุม $\theta$ ก็เปลี่ยนตาม ซึ่งอาจส่งผลอย่างมีนัยสำคัญต่อความน่าจะเป็นของความสำเร็จของอัลกอริทึม เพื่อความกระชับ ลองเขียน $s = \vert A_1 \vert$ เพื่อแทนจำนวนคำตอบ และดังก่อนหน้านี้เราจะสมมติว่า $s\geq 1$

สำหรับตัวอย่างที่จูงใจ ลองจินตนาการว่าเรามี $s = 4$ คำตอบแทนที่จะเป็นคำตอบเดียวอย่างที่เราพิจารณาข้างต้น ซึ่งหมายความว่า

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{4}{N}} \biggr),$$

ซึ่งมีค่าประมาณสองเท่าของมุมที่เรามีในกรณี $\vert A_1 \vert = 1$ เมื่อ $N$ มีค่ามาก สมมติว่าเราไม่รู้ดีกว่านี้ และเลือกค่า $t$ เดิมอย่างในการตั้งค่าคำตอบเอกลักษณ์:

$$t = \Biggl\lfloor \frac{\pi}{4\sin^{-1}\bigl(1/\sqrt{N}\bigr)}\Biggr\rfloor.$$

ผลจะเป็นหายนะดังที่ตารางความน่าจะเป็นต่อไปนี้เปิดเผย

$$\begin{array}{ll} N & \text{ความน่าจะเป็นของความสำเร็จ}\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 0.2500000000\\ 32 & 0.0122070313\\ 64 & 0.0203807689\\ 128 & 0.0144530758\\ 256 & 0.0000705058\\ 512 & 0.0019310741\\ 1024 & 0.0023009083\\ 2048 & 0.0000077506\\ 4096 & 0.0002301502\\ 8192 & 0.0003439882\\ 16384 & 0.0000007053\\ 32768 & 0.0000533810\\ 65536 & 0.0000472907 \end{array}$$

คราวนี้ความน่าจะเป็นของความสำเร็จเข้าหา $0$ เมื่อ $N$ เข้าหาอนันต์ สิ่งนี้เกิดขึ้นเพราะเราหมุนเร็วเป็นสองเท่าของตอนที่มีคำตอบเอกลักษณ์ ทำให้เราพุ่งผ่านเป้าหมาย $\vert A_1\rangle$ และไปลงที่ใกล้ $-\vert A_0\rangle$

อย่างไรก็ตาม ถ้าแทนที่เราใช้การเลือก $t$ ที่แนะนำ ซึ่งคือ

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor$$

สำหรับ

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{s}{N}} \biggr),$$

ประสิทธิภาพจะดีขึ้น พูดให้ชัดขึ้น การใช้การเลือก $t$ นี้นำไปสู่ความสำเร็จด้วยความน่าจะเป็นสูง

$$\begin{array}{ll} N & p(N,4)\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 1.0000000000\\ 32 & 0.9453125000\\ 64 & 0.9613189697\\ 128 & 0.9991823155\\ 256 & 0.9965856808\\ 512 & 0.9956198657\\ 1024 & 0.9999470421\\ 2048 & 0.9994480262\\ 4096 & 0.9994612447\\ 8192 & 0.9999968478\\ 16384 & 0.9999453461\\ 32768 & 0.9999157752\\ 65536 & 0.9999997811 \end{array}$$

เมื่อสรุปสิ่งที่กล่าวไว้ก่อนหน้านี้ สามารถพิสูจน์ได้ว่า

$$p(N,s) \geq 1 - \frac{s}{N},$$

ที่เราใช้สัญกรณ์ที่แนะนำก่อนหน้านี้: $p(N,s)$ แทนความน่าจะเป็นที่อัลกอริทึมของ Grover ที่รันเป็นเวลา $t$ รอบจะเปิดเผยคำตอบเมื่อมี $s$ คำตอบทั้งหมดจาก $N$ ความเป็นไปได้

ขอบเขตล่าง $1 - s/N$ ของความน่าจะเป็นของความสำเร็จนี้ค่อนข้างแปลก ตรงที่คำตอบมากขึ้นหมายถึงขอบเขตล่างที่แย่ลง — แต่ภายใต้สมมติฐานว่า $s$ น้อยกว่า $N$ อย่างมีนัยสำคัญ เราก็ยังสรุปได้ว่าความน่าจะเป็นของความสำเร็จอยู่ในระดับที่ดีพอสมควร ดังเดิม ข้อเท็จจริงที่ว่า $p(N,s)$ มีค่าพอสมควรแสดงถึงประโยชน์ของอัลกอริทึม

นอกจากนี้ยังเป็นความจริงที่ว่า

$$p(N,s) \geq \frac{s}{N}.$$

ขอบเขตล่างนี้อธิบายความน่าจะเป็นที่สตริง $x\in\Sigma^n$ ที่เลือกแบบสุ่มสม่ำเสมอจะเป็นคำตอบ — ดังนั้นอัลกอริทึมของ Grover จะทำงานได้ดีอย่างน้อยเท่ากับการเดาแบบสุ่มเสมอ (ที่จริงแล้ว เมื่อ $t=0$, อัลกอริทึมของ Grover คือ การเดาแบบสุ่ม)

ตอนนี้ลองดูจำนวนรอบการวนซ้ำ (และด้วยเหตุนี้จำนวนคำถาม)

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor,$$

สำหรับ

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{s}{N}}\biggr).$$

สำหรับทุก $\alpha \in [0,1]$, เป็นความจริงที่ว่า $\sin^{-1}(\alpha)\geq \alpha$, ดังนั้น

$$\theta = \sin^{-1}\left(\sqrt{\frac{s}{N}}\right) \geq \sqrt{\frac{s}{N}}.$$

ซึ่งหมายความว่า

$$t \leq \frac{\pi}{4\theta} \leq \frac{\pi}{4}\sqrt{\frac{N}{s}}.$$

นี่แปลไปสู่การประหยัดในจำนวนคำถามเมื่อ $s$ เพิ่มขึ้น โดยเฉพาะอย่างยิ่ง จำนวนคำถามที่ต้องการคือ

$$O\biggl(\sqrt{\frac{N}{s}}\biggr).$$

จำนวนคำตอบที่ไม่รู้

หากจำนวนคำตอบ $s = \vert A_1 \vert$ ไม่ทราบ จำเป็นต้องใช้วิธีการที่ต่างออกไป เพราะในสถานการณ์นี้เราไม่มีความรู้เกี่ยวกับ $s$ เพื่อแจ้งการเลือก $t$ ของเรา อันที่จริงมีหลายวิธีการ

วิธีหนึ่งที่เรียบง่ายคือการเลือก

$$t \in \Bigl\{ 1,\ldots,\bigl\lfloor\pi\sqrt{N}/4\bigr\rfloor \Bigr\}$$

แบบสุ่มสม่ำเสมอ การเลือก $t$ ในลักษณะนี้จะหาคำตอบได้เสมอ (สมมติว่ามีคำตอบอยู่) ด้วยความน่าจะเป็นมากกว่า 40% แม้ว่าสิ่งนี้จะไม่ชัดเจนและต้องการการวิเคราะห์ที่จะไม่รวมอยู่ที่นี่ อย่างไรก็ตาม มันสมเหตุสมผล โดยเฉพาะเมื่อเราคิดถึงภาพเรขาคณิต: การหมุนสถานะของ $\mathsf{Q}$ จำนวนครั้งแบบสุ่มเช่นนี้ไม่ต่างจากการเลือกเวกเตอร์หน่วยแบบสุ่มในปริภูมิที่ถูก span ด้วย $\vert A_0\rangle$ และ $\vert A_1\rangle$ ซึ่งมีแนวโน้มที่ค่าสัมประสิทธิ์ของ $\vert A_1\rangle$ จะมีค่าพอสมควร ด้วยการทำซ้ำขั้นตอนนี้และตรวจสอบผลลัพธ์ในลักษณะเดียวกับที่อธิบายก่อนหน้านี้ ความน่าจะเป็นที่จะหาคำตอบสามารถทำให้ใกล้เคียง $1$ มากได้

มีวิธีที่ปรับปรุงแล้วซึ่งหาคำตอบเมื่อมีอยู่โดยใช้ $O(\sqrt{N/s})$ คำถาม แม้ไม่ทราบจำนวนคำตอบ $s$ และต้องการ $O(\sqrt{N})$ คำถามเพื่อพิจารณาว่าไม่มีคำตอบเมื่อ $s=0$

แนวคิดพื้นฐานคือการเลือก $t$ แบบสุ่มสม่ำเสมอจากเซต $\{1,\ldots,T\}$ แบบวนซ้ำ สำหรับค่า $T$ ที่เพิ่มขึ้น โดยเฉพาะอย่างยิ่ง เราสามารถเริ่มต้นด้วย $T = 1$ และเพิ่มขึ้นแบบ exponential โดยสิ้นสุดกระบวนการทันทีที่หาคำตอบได้ และกำหนดเพดาน $T$ เพื่อไม่สูญเสียคำถามเมื่อไม่มีคำตอบ กระบวนการใช้ประโยชน์จากข้อเท็จจริงที่ว่าต้องการคำถามน้อยกว่าเมื่อมีคำตอบมากขึ้น อย่างไรก็ตาม ต้องระมัดระวัง เพื่อสมดุลอัตราการเติบโตของ $T$ กับความน่าจะเป็นของความสำเร็จในแต่ละรอบ (การใช้ $T \leftarrow \lceil \frac{5}{4}T\rceil$ ทำงานได้ ตามที่การวิเคราะห์แสดงให้เห็น แต่การเพิ่มสองเท่าของ $T$ ไม่ทำงาน — นี่กลายเป็นการเพิ่มที่เร็วเกินไป)

กรณีพื้นฐาน

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

$$\begin{aligned} \vert A_0\rangle &= \frac{1}{\sqrt{\vert A_0\vert}} \sum_{x\in A_0} \vert x\rangle \\ \vert A_1\rangle &= \frac{1}{\sqrt{\vert A_1\vert}} \sum_{x\in A_1} \vert x\rangle \end{aligned}$$

เราได้สมมติโดยนัยว่า $A_0$ และ $A_1$ ทั้งคู่ไม่ว่างเปล่า ที่นี่เราจะพิจารณาโดยย่อว่าจะเกิดอะไรขึ้นเมื่อเซตใดเซตหนึ่งว่างเปล่า

ก่อนที่เราจะวิเคราะห์ ลองสังเกตสิ่งที่ชัดเจน: หากทุกสตริง $x\in\Sigma^n$ เป็นคำตอบ เราก็จะเห็นคำตอบเมื่อเราวัด และเมื่อไม่มีคำตอบ เราก็จะไม่เห็น ในแง่หนึ่งไม่จำเป็นต้องไปลึกกว่านี้

อย่างไรก็ตาม เราสามารถตรวจสอบคณิตศาสตร์สำหรับกรณีพื้นฐานเหล่านี้ได้อย่างรวดเร็ว สถานการณ์ที่ $A_0$ หรือ $A_1$ หนึ่งในนั้นว่างเปล่าเกิดขึ้นเมื่อ $f$ เป็น constant; $A_1$ ว่างเปล่าเมื่อ $f(x) = 0$ สำหรับทุก $x\in\Sigma^n,$ และ $A_0$ ว่างเปล่าเมื่อ $f(x) = 1$ สำหรับทุก $x\in\Sigma^n$ ซึ่งหมายความว่า

$$Z_f \vert u\rangle = \pm \vert u\rangle,$$

และดังนั้น

$$\begin{aligned} G \vert u \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f\vert u\rangle \\ & = \pm \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert u\rangle \\ & = \pm \vert u\rangle. \end{aligned}$$

ดังนั้น ไม่ว่าจำนวนรอบการวนซ้ำ $t$ ที่เราทำในกรณีเหล่านี้ การวัดจะเปิดเผยสตริงสุ่มสม่ำเสมอ $x\in\Sigma^n$ เสมอ