การวิเคราะห์

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

คำตอบและที่ไม่ใช่คำตอบ

มาเริ่มต้นด้วยการกำหนดสองเซตของสตริง

$$\begin{aligned} A_0 &= \bigl\{ x\in\Sigma^n : f(x) = 0\bigr\} \\ A_1 &= \bigl\{ x\in\Sigma^n : f(x) = 1\bigr\} \end{aligned}$$

เซต $A_1$ ประกอบด้วยคำตอบทั้งหมดของปัญหาการค้นหา ส่วน $A_0$ ประกอบด้วยสตริงที่ไม่ใช่คำตอบ (ซึ่งเราอาจเรียกว่า ที่ไม่ใช่คำตอบ เมื่อสะดวก) สองเซตนี้มีคุณสมบัติ $A_0 \cap A_1 = \varnothing$ และ $A_0 \cup A_1 = \Sigma^n,$ กล่าวคือ นี่คือ การแบ่งสองส่วน ของ $\Sigma^n.$

ต่อไปเราจะกำหนดเวกเตอร์หน่วยสองตัวที่แทน superposition สม่ำเสมอเหนือเซตของคำตอบและที่ไม่ใช่คำตอบ

$$\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$ ไม่ว่างเปล่า กรณีที่ $A_0 = \varnothing$ และ $A_1 = \varnothing$ สามารถจัดการแยกกันได้ง่าย และเราจะทำในภายหลัง

สำหรับข้อสังเกต สัญกรณ์ที่ใช้ที่นี่เป็นเรื่องปกติ: เมื่อใดก็ตามที่เรามีเซตจำกัดและไม่ว่างเปล่า $S,$ เราสามารถเขียน $\vert S\rangle$ เพื่อแทนเวกเตอร์สถานะควอนตัมที่สม่ำเสมอเหนือสมาชิกของ $S.$

ลองกำหนด $\vert u \rangle$ ให้เป็นสถานะควอนตัม สม่ำเสมอ เหนือสตริง $n$ บิตทั้งหมด:

$$\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.$$

สังเกตว่า

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle.$$

นอกจากนี้เรายังมี $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle,$ ดังนั้น $\vert u\rangle$ แทนสถานะของ register $\mathsf{Q}$ หลังจากการตั้งค่าเริ่มต้นในขั้นตอนที่ 1 ของอัลกอริทึมของ Grover

ซึ่งหมายความว่า ก่อนที่การวนซ้ำของ $G$ จะเกิดขึ้นในขั้นตอนที่ 2 สถานะของ $\mathsf{Q}$ อยู่ในปริภูมิเวกเตอร์สองมิติที่ถูก span ด้วย $\vert A_0\rangle$ และ $\vert A_1\rangle$ และยิ่งกว่านั้น ค่าสัมประสิทธิ์ของเวกเตอร์เหล่านี้เป็นจำนวนจริง ดังที่เราจะเห็น สถานะของ $\mathsf{Q}$ จะมีคุณสมบัติเหล่านี้เสมอ — กล่าวคือ สถานะเป็นผลรวมเชิงเส้นจริงของ $\vert A_0\rangle$ และ $\vert A_1\rangle$ — หลังจากการวนซ้ำใดๆ ของการดำเนินการ $G$ ในขั้นตอนที่ 2

ข้อสังเกตเกี่ยวกับการดำเนินการของ Grover

ตอนนี้เราจะหันมาสนใจการดำเนินการของ Grover

$$G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f,$$

โดยเริ่มต้นด้วยข้อสังเกตที่น่าสนใจ

ลองจินตนาการว่าเราแทนที่ฟังก์ชัน $f$ ด้วยการประกอบของ $f$ กับฟังก์ชัน NOT — หรือพูดอีกอย่างคือ ฟังก์ชันที่ได้จากการกลับบิตเอาต์พุตของ $f$ เราจะเรียกฟังก์ชันใหม่นี้ว่า $g,$ และเราสามารถแสดงมันด้วยสัญลักษณ์ได้หลายวิธี

$$g(x) = \neg f(x) = 1 \oplus f(x) = 1 - f(x) = \begin{cases} 1 & f(x) = 0\\[1mm] 0 & f(x) = 1 \end{cases}$$

สังเกตว่า

$$(-1)^{g(x)} = (-1)^{1 \oplus f(x)} = - (-1)^{f(x)}$$

สำหรับทุกสตริง $x\in\Sigma^n,$ และดังนั้น

$$Z_g = - Z_f.$$

ซึ่งหมายความว่า ถ้าเราแทนที่ฟังก์ชัน $f$ ด้วยฟังก์ชัน $g$ อัลกอริทึมของ Grover จะไม่ทำงานแตกต่างกันเลย — เพราะสถานะที่เราได้จากอัลกอริทึมในทั้งสองกรณีจำเป็นต้องสมมูลกันจนถึง global phase

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

การกระทำของการดำเนินการ Grover

ตอนนี้ลองพิจารณาการกระทำของ $G$ บนเวกเตอร์สถานะควอนตัม $\vert A_0\rangle$ และ $\vert A_1\rangle$

ก่อนอื่น สังเกตว่าการดำเนินการ $Z_f$ มีการกระทำที่เรียบง่ายมากบน $\vert A_0\rangle$ และ $\vert A_1\rangle$

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle \end{aligned}$$

ประการที่สอง เรามีการดำเนินการ $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ การดำเนินการ $Z_{\mathrm{OR}}$ ถูกกำหนดเป็น

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

อีกครั้งสำหรับทุกสตริง $x\in\Sigma^n,$ และวิธีที่สะดวกในการแสดงการดำเนินการนี้คือ:

$$Z_{\mathrm{OR}} = 2 \vert 0^n \rangle \langle 0^n \vert - \mathbb{I}.$$

วิธีง่ายๆ ในการตรวจสอบว่านิพจน์นี้สอดคล้องกับนิยามของ $Z_{\mathrm{OR}}$ คือการประเมินการกระทำของมันบนสถานะ basis มาตรฐาน

การดำเนินการ $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ จึงสามารถเขียนได้ดังนี้:

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 H^{\otimes n} \vert 0^n \rangle \langle 0^n \vert H^{\otimes n} - \mathbb{I} = 2 \vert u \rangle \langle u \vert - \mathbb{I},$$

โดยใช้สัญกรณ์เดิม $\vert u \rangle$ ที่เราใช้ข้างต้นสำหรับ superposition สม่ำเสมอเหนือสตริง $n$ บิตทั้งหมด

และตอนนี้เรามีสิ่งที่จำเป็นในการคำนวณการกระทำของ $G$ บน $\vert A_0\rangle$ และ $\vert A_1\rangle$ ก่อนอื่นลองคำนวณการกระทำของ $G$ บน $\vert A_0\rangle$

$$\begin{aligned} G \vert A_0 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f \vert A_0\rangle \\ & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert A_0\rangle \\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \vert u\rangle -\vert A_0 \rangle\\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \biggl( \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) -\vert A_0 \rangle \\ & = \biggl( \frac{2\vert A_0\vert}{N} - 1\biggr) \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \\ & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \end{aligned}$$

และประการที่สอง ลองคำนวณการกระทำของ $G$ บน $\vert A_1\rangle$

$$\begin{aligned} G \vert A_1 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) Z_f \vert A_1\rangle \\ & = - \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) \vert A_1\rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \vert u\rangle + \vert A_1 \rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \biggl(\sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) + \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \biggl( 1 - \frac{2\vert A_1\vert}{N} \biggr) \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle \end{aligned}$$

ในทั้งสองกรณีเราใช้สมการ

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle$$

พร้อมกับนิพจน์

$$\langle u \vert A_0\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \qquad\text{and}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}$$

ที่ตามมา

โดยสรุป เรามี

$$\begin{aligned} G \vert A_0 \rangle & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle\\[2mm] G \vert A_1 \rangle & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle. \end{aligned}$$

ดังที่เราสังเกตไปแล้ว สถานะของ $\mathsf{Q}$ ก่อนขั้นตอนที่ 2 อยู่ในปริภูมิสองมิติที่ถูก span ด้วย $\vert A_0\rangle$ และ $\vert A_1\rangle,$ และเราได้พิสูจน์แล้วว่า $G$ แมปเวกเตอร์ใดๆ ในปริภูมินี้ไปยังเวกเตอร์อื่นในปริภูมิเดิม ซึ่งหมายความว่า เพื่อวัตถุประสงค์ของการวิเคราะห์ เราสามารถมุ่งความสนใจไปที่ subspace นี้เท่านั้น

เพื่อให้เข้าใจได้ดีขึ้นว่าเกิดอะไรขึ้นภายในปริภูมิสองมิตินี้ ลองแสดงการกระทำของ $G$ บนปริภูมินี้เป็น matrix

$$M = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix},$$

โดยที่แถว/คอลัมน์แรกและที่สองสอดคล้องกับ $\vert A_0\rangle$ และ $\vert A_1\rangle$ ตามลำดับ จนถึงตอนนี้ในซีรีส์นี้ เราเชื่อมโยงแถวและคอลัมน์ของ matrix กับสถานะแบบ classical ของระบบเสมอ แต่ matrix ยังสามารถใช้อธิบายการกระทำของการแมปเชิงเส้นบน basis ต่างๆ อย่างที่เราทำที่นี่

แม้ว่าจะไม่ชัดเจนในทันที matrix $M$ คือสิ่งที่ได้จากการ ยกกำลังสอง ของ matrix ที่ดูเรียบง่ายกว่า

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}^2 = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix} = M$$

matrix

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}$$

คือ rotation matrix ซึ่งเราสามารถแสดงในรูปแบบอื่นได้เป็น

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix} = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}$$

สำหรับ

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

มุม $\theta$ นี้จะมีบทบาทสำคัญมากในการวิเคราะห์ที่ตามมา จึงควรเน้นความสำคัญของมันในครั้งแรกที่เราพบ

เมื่อพิจารณาจากการแสดงนิพจน์ของ matrix นี้ เราสังเกตว่า

$$M = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}^2 = \begin{pmatrix} \cos(2\theta) & -\sin(2\theta) \\[2mm] \sin(2\theta) & \cos(2\theta) \end{pmatrix}.$$

เพราะการหมุนด้วยมุม $\theta$ สองครั้งเทียบเท่ากับการหมุนด้วยมุม $2\theta$ อีกวิธีหนึ่งในการเห็นสิ่งนี้คือการใช้นิพจน์อื่น

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

พร้อมกับสูตร double angle จากตรีโกณมิติ:

$$\begin{aligned} \cos(2\theta) & = \cos^2(\theta) - \sin^2(\theta)\\[1mm] \sin(2\theta) & = 2 \sin(\theta)\cos(\theta). \end{aligned}$$

โดยสรุป สถานะของ register $\mathsf{Q}$ ณ จุดเริ่มต้นของขั้นตอนที่ 2 คือ

$$\vert u\rangle = \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle = \cos(\theta) \vert A_0\rangle + \sin(\theta) \vert A_1\rangle,$$

และผลของการนำ $G$ ไปใช้กับสถานะนี้คือการหมุนมันด้วยมุม $2\theta$ ภายในปริภูมิที่ถูก span ด้วย $\vert A_0\rangle$ และ $\vert A_1\rangle$ ตัวอย่างเช่น เรามี

$$\begin{aligned} G \vert u \rangle &= \cos(3\theta) \vert A_0\rangle + \sin(3\theta) \vert A_1\rangle\\[1mm] G^2 \vert u \rangle &= \cos(5\theta) \vert A_0\rangle + \sin(5\theta) \vert A_1\rangle\\[1mm] G^3 \vert u \rangle &= \cos(7\theta) \vert A_0\rangle + \sin(7\theta) \vert A_1\rangle \end{aligned}$$

และโดยทั่วไป

$$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.$$

ภาพเรขาคณิต

ตอนนี้ลองเชื่อมโยงการวิเคราะห์ที่เราเพิ่งผ่านไปกับภาพเรขาคณิต แนวคิดคือการดำเนินการ $G$ คือผลคูณของ การสะท้อน สองครั้ง ได้แก่ $Z_f$ และ $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ และผลสุทธิของการทำ reflection สองครั้งคือการทำ rotation

เริ่มจาก $Z_f$ ดังที่เราสังเกตไว้ก่อนหน้านี้ เรามี

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle. \end{aligned}$$

ภายในปริภูมิเวกเตอร์สองมิติที่ถูก span ด้วย $\vert A_0\rangle$ และ $\vert A_1\rangle,$ นี่คือ การสะท้อน เกี่ยวกับเส้นที่ขนานกับ $\vert A_0\rangle$ ซึ่งเราจะเรียกว่า $L_1$ ต่อไปนี้คือรูปที่แสดงการกระทำของการสะท้อนนี้บนเวกเตอร์หน่วยสมมติ $\vert\psi\rangle,$ ซึ่งเราสมมติว่าเป็นผลรวมเชิงเส้นจริงของ $\vert A_0\rangle$ และ $\vert A_1\rangle$

ประการที่สอง เรามีการดำเนินการ $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n},$ ซึ่งเราได้เห็นแล้วว่าสามารถเขียนได้เป็น

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 \vert u \rangle \langle u \vert - \mathbb{I}.$$

นี่ก็เป็นการสะท้อนเช่นกัน คราวนี้เกี่ยวกับเส้น $L_2$ ที่ขนานกับเวกเตอร์ $\vert u\rangle$ ต่อไปนี้คือรูปที่แสดงการกระทำของการสะท้อนนี้บนเวกเตอร์หน่วย $\vert\psi\rangle$

เมื่อเราประกอบการสะท้อนสองครั้งนี้ เราจะได้การหมุน — ด้วยสองเท่าของมุมระหว่างเส้นสะท้อน — ดังที่รูปนี้แสดง

นี่อธิบายในแง่เรขาคณิตว่าทำไมผลของการดำเนินการ Grover จึงเป็นการหมุนผลรวมเชิงเส้นของ $\vert A_0\rangle$ และ $\vert A_1\rangle$ ด้วยมุม $2\theta$