خوارزمية بحث Grover

مكتمل

في الوحدات السابقة، تعلمت عن مشكلة البحث وتنفيذ مثيلاتها كـ oracle الكم.

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

لتحقيق الفعالية، يجب عليك التأكد من أن المحطتين المتصلتين لا يستخدمان نفس النطاق الترددي.

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

دعونا نبدأ مع مخطط تفصيلي للخوارزمية ومن ثم نناقش كل خطوة في التفاصيل.

  1. نبدأ بإعداد تراكب متساوٍ لجميع الحالات الأساس.
    هذه خطوة أولى شائعة لخوارزميات الكم بشكل عام.

  2. الجزء الرئيسي من الخوارزمية يكرر سلسلة من الخطوات. يسمى هذا التسلسل ⁧⁩تكرار Grover⁧⁩ ويتكون من خطوتين:

    • تطبيق Oracle الكم -- هذه العملية تضاعف مراحل جميع الدول التي هي حلول لمشكلتنا بـ $-1$، كما رأينا في وقت سابق في هذه الوحدة. لاحظ أن هذه هي الخطوة الوحيدة التي تستخدم المعلومات حول المشكلة.

    • تطبيق ما يسمى "عامل تشغيل الانتشار" - هذا العامل يغير السعات الخاصة بالحالات الأساس على النحو التالي: السعات التي هي أكبر من متوسط السعات سوف تصبح أصغر، والسعة التي هي أقل من المتوسط سوف تصبح أكبر. هذه الخطوة لا تعتمد على مشكلتنا.

    بشكل عام، ⁧⁩يقلل⁧⁩ التكرار الواحد من اتساع الحالات الأساس التي ليست حلولاً لمشكلتنا ⁧⁩ويزيد⁧⁩ من اتساع حالات الأساس التي هي حلول، مع الحفاظ على كلا النوعين من السعات إيجابيًا.

  3. أخيرًا، نقيس حالة النظام. إن تكرار التكرار عدة مرات يدخل اختلافات كبيرة بين نوعين من السعات، ومن ثمَّ فإن القياس يعطي الجواب مع احتمالية عالية.

مرئيات الخوارزمية

الآن، دعونا نلقي نظرة على خوارزمية Grover من زاوية مختلفة قليلا، ونتصور حالة النظام في كل خطوة.

افترض أن لدينا مساحة البحث (وهذا يعني كل القيم الممكنة التي يمكن أن تأخذ المتغيرات لدينا) فيها عناصر $N$، و$M$ منهم هي حلول لمشكلتنا.

سنحدد خطين متجهين للحالات:

  • تراكب متساو من حالات الأساس $M$ "الجيدة" (الحالات التي هي حلول لمشكلتنا)

    $$|\textrm{good}\rangle = \frac⁧{1}⁩{\sqrt{M}} \sum_{x : f(x) = 1} |x\rangle$$

  • تراكب متساوٍ من حالات الأساس $N - M$ «السيئة» (الحالات التي هي ⁧⁩ليست⁧⁩ حلول لمشكلتنا)

    $$|\textrm{bad}\rangle = \frac⁧{1}⁩{\sqrt{N-M}} \sum_{x : f(x) = 0} |x\rangle$$

الخوارزمية لا تميز الحالات "الجيدة" أو "السيئة" المختلفة حتى يحصل القياس النهائي، لذلك تظل جميع السعات من الحالات "الجيدة" مساوية لبعضها البعض، وتظل جميع السعات من الحالات "السيئة" متساوية مع بعضها البعض. وهذا يعني أننا يمكن أن نمثل دائمًا حالة النظام الكلية كتراكب من الحالات $|\textrm{good}\rangle$ and $|\textrm{bad}\rangle$.

  1. نبدأ مع تراكب متساوٍ من جميع الحالات الأساس، سواء "جيدة" و"سيئة". يتم تمثيل هذه الحالة كما يلي:

    $$|\textrm{all}\rangle = \sqrt{\frac{M}{N}} |\textrm{good}\rangle + \sqrt{\frac{N-M}{N}} |\textrm{bad}\rangle$$

    إذا تخيلنا طائرة فيها خطوط متجهة $|\textrm{good}\rangle$ and $|\textrm{bad}\rangle$ تتوافق مع محاور عمودية وأفقية، على التوالي، يمكننا رسم هذه الحالة كالتالي:

    الشكل الذي يظهر دائرة يوضح تراكب جميع الدول.

    تعتمد الزاوية $\theta$ على نسبة الحالات "جيدة" بين جميع الحالات الأساس:$\sin \theta = \sqrt{\frac{M}{N}}$

  2. تاليًا، نقوم بتطبيق Oracle. تذكر أن هذه العملية تضرب السعات الخاصة بالحالات "الجيدة" بـ $-1$. في مخطط الدائرة، هذا التحول يترك المكون الأفقي لمتجه الحالة دون تغيير ويعكس مكونه العمودي. وبعبارة أخرى، هذه العملية هي انعكاس على طول المحور الأفقي:

    الشكل الذي يظهر دائرة يوضح نتيجة الانعكاس الأول.

  3. الآن نقوم بتطبيق عامل تشغيل الانتشار. تأثيره هو انعكاس آخر، وهذه المرة على طول متجه $|\textrm{all}\rangle$:

    الشكل الذي يظهر الدائرة التي توضح نتيجة الانعكاس الثاني.

    لاحظ كيف يصبح هذا التسلسل من انعكاسي دوران عكس عقارب الساعة بزاوية $2\theta$ إذا كررنا هذا التسلسل، وعكسنا الحالة الجديدة أولاً على طول المحور الأفقي ثم على طول متجه $|\textrm{all}\rangle$، فإنه ينفذ دورانًا بزاوية $ 2\theta $ مرة أخرى. زاوية هذا الدوران تعتمد فقط على الزاوية بين محاور الانعكاس وليس على الحالة التي نعكسها.

  4. لذا، إذا كان كل تكرار نؤديه يقوم بتدوير متجه حالتنا بزاوية $2\theta $ عكس عقارب الساعة، متى يجب علينا إجراء القياس؟

    إن احتمال الحصول على حالة أساس معينة كنتيجة قياس تساوي السعة التربيعية لتلك الحالة في التراكب. كلما كانت السعة أكبر، ارتفعت فرصة الحصول على الحالة المقابلة عند إجراء القياس.

    بحكم أن هدفنا هو الحصول على واحدة من الحالات "جيدة" مع أعلى احتمالية ممكنة، فإننا بحاجة إلى زيادة سعات الحالات "الجيدة" بقدر ما نستطيع (والحد من اتساع الحالات "السيئة" في المقابل). من الناحية الهندسية، هذا يعني أننا نريد تدوير متجه الحالة أقرب إلى المحور العمودي قدر الإمكان.

    الشكل الذي يظهر الدائرة التي توضح عدة دورات.

    إذا اخترنا العدد الصحيح من التكرارات، فسنصل إلى النقطة التي سينتج فيها القياس إجابة صحيحة مع احتمالية كبيرة بما فيه الكفاية.

تحليل الخوارزمية

خوارزمية البحث Grover فيها العديد من الخصائص الهامة التي تستحق الذكر.

خوارزمية Grover تستند إلى الاحتمالية

القياس النهائي ينتج نتيجة تحل مشكلتنا مع احتمالية عالية، ولكن عادة من دون اليقين المطلق. في معظم الحالات، لا يزال هناك احتمال ضئيل للفشل.

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

المزيد من التكرارات ليست بالضرورة أفضل!

بالنسبة إلى العديد من الخوارزميات الكلاسيكية المتكررة، يؤدي تشغيل التكرارات الإضافية إلى إبطائها ولكنها لا تقلل في نهاية المطاف من احتمال نجاح الخوارزمية. يحتوي بحث Grover على "بقعة مثالية" معينة - وهي عدد تكرارات الخوارزمية التي تسفر عن أعلى احتمالية للنجاح. إذا كانت مشكلتنا فيها عدد $N$ تعيينات متغيرة ممكنة، فإن $M$ منها هي حلول للمشكلة، وإن العدد الأمثل من التكرارات هو

$$R_{opt} \approx \frac{\pi}⁧{4}⁩ \sqrt{\frac{N}{M}}$$

الاستمرار في التكرار لما بعد هذا العدد يبدأ بتقليل هذه الاحتمالية حتى نصل إلى ما يقرب من الصفر من احتمالية النجاح على التكرار $ 2 R_ {opt}$. بعد ذلك، تزداد الاحتمالية مرة أخرى وتقترب من 100٪ على التكرار 3 $ R_ {opt} $، وهكذا.

ملاحظة

لفهم هذا السلوك، تذكر مرئيات الدائرة لدينا.

بعد التكرار $k$، الزاوية بين المحور الأفقي ومتجه الحالة تساوي $ 2k + 1 $، ونحن نريد جعله أقرب ما يمكن إلى $\frac {\pi} ⁧{2}⁩ $ بالنسبة إلى معظم التطبيقات، $M$ أصغر بكثير من $N$، لذلك يمكننا تقريب $\theta \approx \sin \theta = \sqrt{\frac{M}{N}}$. وهذا يسمح لنا بتقدير العدد الأمثل من التكرارات.

يمكن تفسير السلوك الدوري لاحتمالية النجاح باستخدام نفس التصور المرئي. كل تكرار هو دوران في نفس الاتجاه بزاوية ثابتة. إذا واصلنا التكرار، فسوف نبالغ في تدوير حالتنا، والتي ستبدأ في الابتعاد أكثر وأكثر عن المحور العمودي، ومن ثمَّ سيتسبب ذلك بتقليل احتمالية نجاحنا.

الشكل الذي يظهر الدائرة التي توضح الإفراط في الدوران.

عندما تمر الحالة بالمحور الأفقي، فإن المزيد من الدورانات تجعلها أقرب إلى المحور العمودي من الاتجاه المعاكس، ما يزيد من احتمالية نجاحنا مرة أخرى. (تذكر أن احتمالات القياس يتم تعريفها بواسطة ⁧⁩مربعات⁧⁩ السعات، وليس فقط السعات.)

ولكن لا أعرف كم عدد الحلول التي تصلح لمشكلتي!

في المثال، لديك مشكلة صغيرة وسهلة التحليل، بحيث يمكنك حساب عدد الحلول يدويًا. في التطبيقات العملية، أنت لا تعرف عادة كم من الحلول لديك لمشكلتك قبل حلها.

لمعالجة هذه المشكلة، يمكنك اختيار عدد صغير، تشغيل الخوارزمية مع هذا العدد من التكرارات، وإذا لم ينتج إجابة، يمكنك إعادة المحاولة مع عدد مختلف وأكبر من التكرارات. ستعمل مع ذلك استراتيجية فعالة لزيادة عدد التكرارات تدريجيًا على إيجاد الحل مع متوسط عدد التكرارات حوالي $\sqrt{\frac{N}{M}}$

في الوحدة التالية، عليك تنفيذ خوارزمية Grover في Q# وتشغيلها لحل مشكلة تلوين ذروة لمشكلة الاتصالات الفضائية!