التحليل

سنحلّل الآن خوارزمية غروفر لنفهم كيف تعمل. سنبدأ بما يمكن وصفه بالتحليل الرمزي، حيث نحسب كيف تؤثر عملية غروفر $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$.

بعد ذلك سنعرّف شعاعَي وحدة يمثّلان تراكبات متجانسة على مجموعتَي الحلول وغير الحلول.

$$\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$ يمثّل حالة السجل $\mathsf{Q}$ بعد التهيئة في الخطوة 1 من خوارزمية غروفر.

هذا يعني أنه قُبيل تكرارات $G$ في الخطوة 2، تقع حالة $\mathsf{Q}$ في الفضاء الشعاعي ثنائي الأبعاد المُمتَدّ بـ$\vert A_0\rangle$ و$\vert A_1\rangle$، كما أن معاملات هذين الشعاعين أعداد حقيقية. وكما سنرى، ستحتفظ حالة $\mathsf{Q}$ بهذه الخصائص دائماً — أي أنها تظل تركيباً خطياً حقيقياً لـ$\vert A_0\rangle$ و$\vert A_1\rangle$ — بعد أي عدد من تكرارات العملية $G$ في الخطوة 2.

ملاحظة حول عملية غروفر

سننتقل الآن إلى عملية غروفر

$$G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_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$، فلن تتغير خوارزمية غروفر في شيء — لأن الحالات التي نحصل عليها من الخوارزمية في الحالتين متكافئة بالضرورة حتى الطور الكلي.

ليس هذا مشكلة! بشكل حدسي، الخوارزمية لا تكترث بأي السلاسل حلول وأيها ليس كذلك — بل تحتاج فقط إلى التمييز بين الحلول وغير الحلول كي تعمل بشكل صحيح.

تأثير عملية غروفر

لننظر الآن في تأثير $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}}$ هي تقييم تأثيره على حالات الأساس القياسية.

يمكن كتابة العملية $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$ الذي استخدمناه أعلاه للتراكب المتجانس على جميع سلاسل $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{و}\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 في الفضاء ثنائي الأبعاد الممتدّ بـ$\vert A_0\rangle$ و$\vert A_1\rangle$، وقد أثبتنا للتو أن $G$ تحوّل أي شعاع في هذا الفضاء إلى شعاع آخر في نفس الفضاء. هذا يعني أنه لأغراض التحليل، يمكننا التركيز حصراً على هذا الفضاء الجزئي.

لنفهم ما يجري داخل هذا الفضاء ثنائي الأبعاد بشكل أوضح، لنعبّر عن تأثير $G$ على هذا الفضاء كمصفوفة:

$$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$ على التوالي. حتى الآن في هذه السلسلة، كنا نربط دائماً صفوف وأعمدة المصفوفات بالحالات الكلاسيكية لنظام ما، غير أن المصفوفات يمكن استخدامها أيضاً لوصف تأثيرات التطبيقات الخطية على أسس مختلفة كما هو الحال هنا.

على الرغم من أنه ليس واضحاً للوهلة الأولى، فإن المصفوفة $M$ هي ما نحصل عليه بـتربيع مصفوفة أبسط شكلاً.

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

المصفوفة

$$\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} \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$ ستلعب دوراً محورياً في التحليل التالي، لذا يستحق التأكيد على أهميتها هنا حين نراها لأول مرة.

في ضوء هذا التعبير عن المصفوفة، نلاحظ أن

$$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),$$

إلى جانب صيغ الزاوية المضاعفة من حساب المثلثات:

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

خلاصة القول، حالة السجل $\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$ داخل الفضاء الممتدّ بـ$\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}$. والتأثير الصافي لأداء انعكاسَين هو إجراء دوران.

لنبدأ بـ$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}$$

داخل الفضاء الشعاعي ثنائي الأبعاد الممتدّ بـ$\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$.

حين نؤلّف هذين الانعكاسين، نحصل على دوران — بمقدار ضعف الزاوية بين خطَّي الانعكاس — كما يوضّح هذا الشكل.

هذا يفسّر، بمصطلحات هندسية، لماذا يؤدي تأثير عملية غروفر إلى تدوير التركيبات الخطية لـ$\vert A_0\rangle$ و$\vert A_1\rangle$ بزاوية $2\theta$.