وصف خوارزمية Grover

في هذا القسم، سنصف خوارزمية Grover. سنبدأ بمناقشة بوابات الاستعلام بالطور وكيفية بنائها، ثم ننتقل إلى وصف الخوارزمية نفسها. وأخيرًا، سنناقش باختصار كيف تُطبَّق هذه الخوارزمية بصورة طبيعية على مسائل البحث.

بوابات الاستعلام بالطور

تستخدم خوارزمية Grover عمليات تُعرف بـبوابات الاستعلام بالطور. على النقيض من بوابة الاستعلام العادية $U_f$، المعرَّفة لدالة معطاة $f$ بالطريقة المعتادة الموصوفة سابقًا، تُعرَّف بوابة الاستعلام بالطور للدالة $f$ على النحو التالي:

$$Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle$$

لكل سلسلة $x\in\Sigma^n$.

يمكن تنفيذ العملية $Z_f$ باستخدام بوابة استعلام واحدة $U_f$ كما يوضح هذا الرسم البياني:

يستخدم هذا التنفيذ ظاهرة الركل بالطور، ويتطلب توفر كيوبت عمل واحد مهيَّأ في حالة $\vert -\rangle$. يبقى هذا الكيوبت في حالة $\vert - \rangle$ بعد اكتمال التنفيذ، ويمكن إعادة استخدامه (لتنفيذ بوابات $Z_f$ لاحقة، مثلًا) أو تجاهله.

إضافة إلى العملية $Z_f$، سنستخدم أيضًا بوابة استعلام بالطور لدالة OR ذات $n$ بت، المعرَّفة على النحو التالي لكل سلسلة $x\in\Sigma^n$:

$$\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}$$

بشكل صريح، تعمل بوابة الاستعلام بالطور لدالة OR ذات $n$ بت على النحو الآتي:

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

للتوضيح، هكذا تعمل $Z_{\mathrm{OR}}$ على حالات الأساس القياسية؛ ويُستنتج سلوكها على الحالات التعسفية من هذه العبارة بالخطية.

يمكن تنفيذ العملية $Z_{\mathrm{OR}}$ كدائرة كمومية بالبدء بدائرة بولية لدالة OR، ثم بناء عملية $U_{\mathrm{OR}}$ (أي بوابة استعلام قياسية لدالة OR ذات $n$ بت) باستخدام الإجراء الموصوف في درس أسس الخوارزميات الكمومية، وأخيرًا عملية $Z_{\mathrm{OR}}$ باستخدام ظاهرة الركل بالطور كما هو موضح أعلاه. لاحظ أن العملية $Z_{\mathrm{OR}}$ لا تعتمد على الدالة $f$ وبالتالي يمكن تنفيذها بدائرة كمومية لا تحتوي على أي بوابات استعلام.

وصف الخوارزمية

الآن بعد أن توفرت لدينا العمليتان $Z_f$ و$Z_{\mathrm{OR}}$، يمكننا وصف خوارزمية Grover.

تشير الخوارزمية إلى عدد $t$، وهو عدد التكرارات التي تُجريها (وبالتالي عدد الاستعلامات عن الدالة $f$ التي تحتاجها). لا تحدد خوارزمية Grover هذا العدد $t$ كما نصفها هنا، وسنناقش لاحقًا في الدرس كيفية اختياره.

خوارزمية Grover

1. هيّئ سجلًا مؤلفًا من $n$ كيوبت $\mathsf{Q}$ في الحالة الصفرية الكاملة $\vert 0^n \rangle$، ثم طبّق عملية Hadamard على كل كيوبت في $\mathsf{Q}$.
2. طبّق $t$ مرة العملية الوحدوية $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ على السجل $\mathsf{Q}$.
3. قِس كيوبتات $\mathsf{Q}$ بالنسبة لقياسات الأساس القياسية وأخرج السلسلة الناتجة.

ستُسمى العملية $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ المتكررة في الخطوة 2 بـعملية Grover طوال بقية هذا الدرس. إليك تمثيل دائرة كمومية لعملية Grover حين $n=7$:

في هذا الرسم، تظهر عملية $Z_f$ أكبر من $Z_{\mathrm{OR}}$ كإشارة بصرية غير رسمية تُوحي بأنها على الأرجح العملية ذات التكلفة الأعلى. بخاصة، حين نعمل ضمن نموذج الاستعلام، تتطلب $Z_f$ استعلامًا واحدًا بينما لا تحتاج $Z_{\mathrm{OR}}$ إلى أي استعلامات. أما إذا توفرت لدينا دائرة بولية للدالة $f$، وحوّلناها إلى دائرة كمومية لـ$Z_f$، فمن المعقول توقع أن تكون الدائرة الكمومية الناتجة أكبر وأكثر تعقيدًا من نظيرتها لـ$Z_{\mathrm{OR}}$.

هنا رسم لدائرة كمومية للخوارزمية بأكملها حين $n=7$ و$t=3$. لقيم أكبر من $t$، يمكن ببساطة إدراج نسخ إضافية من عملية Grover مباشرة قبل القياسات.

التطبيق على البحث

يمكن تطبيق خوارزمية Grover على مسألة البحث على النحو التالي:

• اختر العدد $t$ في الخطوة 2. (يُناقش هذا لاحقًا في الدرس.)
• شغّل خوارزمية Grover على الدالة $f$، باستخدام الاختيار الذي اتخذناه لـ$t$، للحصول على سلسلة $x\in\Sigma^n$.
• استعلم عن الدالة $f$ بالسلسلة $x$ لمعرفة ما إذا كانت حلًا صالحًا:
  • إذا كان $f(x) = 1$، فقد وجدنا حلًا، لذا يمكننا التوقف وإخراج $x$.
  • وإلا، إذا كان $f(x) = 0$، فيمكننا إما تشغيل الإجراء مرة أخرى، ربما باختيار مختلف لـ$t$، أو نقرر الاستسلام وإخراج "لا يوجد حل".

بمجرد تحليل كيفية عمل خوارزمية Grover، سنرى أنه باختيار $t = O(\sqrt{N})$، نحصل على حل لمسألة البحث (إن وُجد) باحتمالية عالية.