خوارزمية غروفر

في هذه الوحدة من Qiskit in Classrooms، يجب أن يكون لدى الطلاب بيئة Python تعمل بشكل صحيح مع تثبيت الحزم التالية:

• qiskit الإصدار v2.1.0 أو أحدث
• qiskit-ibm-runtime الإصدار v0.40.1 أو أحدث
• qiskit-aer الإصدار v0.17.0 أو أحدث
• qiskit.visualization
• numpy
• pylatexenc

لإعداد وتثبيت الحزم أعلاه، راجع دليل تثبيت Qiskit. لتشغيل المهام على أجهزة الكمبيوتر الكمومية الحقيقية، يحتاج الطلاب إلى إنشاء حساب على IBM Quantum® باتباع الخطوات الموضّحة في دليل إعداد حساب IBM Cloud الخاص بك.

تم اختبار هذه الوحدة واستغرقت 12 ثانية من وقت QPU. هذا تقدير بحسن نية؛ قد يختلف استخدامك الفعلي.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

مقدّمة

خوارزمية غروفر هي خوارزمية كمومية أساسية تعالج مشكلة البحث غير المنظّم: بافتراض أن لديك مجموعة من $N$ عنصرًا وطريقة للتحقق مما إذا كان أيّ عنصر هو الذي تبحث عنه، فكيف يمكنك العثور على العنصر المطلوب بأسرع ما يمكن؟ في الحوسبة الكلاسيكية، إذا كانت البيانات غير مرتّبة ولا يوجد هيكل لاستغلاله، فإن أفضل نهج هو التحقق من كل عنصر واحدًا تلو الآخر، مما يؤدي إلى تعقيد استعلام يبلغ $O(N)$ — في المتوسط، ستحتاج إلى التحقق من نحو نصف العناصر قبل العثور على الهدف.

خوارزمية غروفر، التي قدّمها Lov Grover عام 1996، توضّح كيف يمكن للحاسوب الكمومي حلّ هذه المشكلة بكفاءة أعلى بكثير، إذ لا يحتاج سوى $O(\sqrt{N})$ خطوة للعثور على العنصر المحدَّد باحتمالية عالية. وهذا يمثّل تسريعًا تربيعيًا مقارنةً بالأساليب الكلاسيكية، وهو أمر مهم للغاية مع مجموعات البيانات الكبيرة.

تعمل الخوارزمية في السياق التالي:

• إعداد المشكلة: لديك دالة $f(x)$ تُرجع 1 إذا كان $x$ هو العنصر الذي تبحث عنه، و0 في غير ذلك. كثيرًا ما تُسمّى هذه الدالة أوراكل أو صندوق أسود، لأنك لا تستطيع معرفة البيانات إلا عبر الاستعلام عن $f(x)$.
• فائدة الحوسبة الكمومية: في حين تتطلّب الخوارزميات الكلاسيكية لهذه المشكلة في المتوسط $N/2$ استعلامًا، تستطيع خوارزمية غروفر إيجاد الحلّ في ما يقارب $\pi\sqrt{N}/4$ استعلامًا، وهو أسرع بكثير عند قيم $N$ الكبيرة.
• كيف تعمل (على مستوى عالٍ):
  • يُنشئ الحاسوب الكمومي أوّلًا تراكبًا لجميع الحالات الممكنة، ممثِّلًا جميع العناصر المحتملة في آنٍ واحد.
  • ثم يُطبّق بشكل متكرّر سلسلة من العمليات الكمومية (تكرار غروفر) التي تُضخّم احتمالية الإجابة الصحيحة وتُخفّض الإجابات الأخرى.
  • بعد عدد كافٍ من التكرارات، يُعطي قياس الحالة الكمومية الإجابة الصحيحة باحتمالية عالية.

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

بعض الملاحظات المهمة حول خوارزمية غروفر:

• هي الأمثل للبحث غير المنظّم: لا توجد خوارزمية كمومية قادرة على حلّ المشكلة بأقل من $O(\sqrt{N})$ استعلامًا.
• توفّر تسريعًا تربيعيًا فحسب، لا أسيًا — على عكس بعض الخوارزميات الكمومية الأخرى (مثل خوارزمية Shor للتحليل إلى عوامل أولية).
• لها تطبيقات عملية، كاحتمالية تسريع هجمات القوة الغاشمة على الأنظمة التشفيرية، وإن كان التسريع لا يكفي وحده لكسر معظم تقنيات التشفير الحديثة.

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

تضخيم السعة (Amplitude amplification) هو خوارزمية كمومية للأغراض العامة، أو روتين فرعي، يمكن استخدامه للحصول على تسريع تربيعي على عدد من الخوارزميات الكلاسيكية. كانت خوارزمية غروفر أوّل من أثبت هذا التسريع على مشاكل البحث غير المنظّم. تتطلّب صياغة مشكلة بحث غروفر دالة أوراكل تُعلّم حالة أساس حسابية واحدة أو أكثر باعتبارها الحالات التي نسعى إلى إيجادها، ودائرة تضخيم تزيد سعة الحالات المعلَّمة وبالتالي تُقلّل الحالات المتبقية.

نوضّح هنا كيفية بناء أوراكلات غروفر واستخدام GroverOperator من مكتبة دوائر Qiskit لإعداد نموذج بحث غروفر بسهولة. يتيح البدائي Sampler في وقت التشغيل تنفيذ دوائر غروفر بسلاسة.

النظرية

لنفترض وجود دالة $f$ تربط السلاسل الثنائية بمتغير ثنائي واحد، أي

$$f: \Sigma^n \rightarrow \Sigma$$

مثال على ذلك المعرَّف على $\Sigma^6$:

$$f(x)= \begin{cases} 1 \qquad \text{if }x=\{010101\}\\ 0 \qquad \text{otherwise } \end{cases}$$

ومثال آخر معرَّف على $\Sigma^{2n}$:

$$f(x)= \begin{cases} 1 \qquad \text{if equal numbers of 1's and 0's in string}\\ 0 \qquad \text{otherwise } \end{cases}$$

مهمّتك هي إيجاد الحالات الكمومية المقابلة لتلك الوسائط $x$ في $f(x)$ التي تُطابق القيمة 1. بعبارة أخرى، أوجد جميع $\{x_1\}\in \Sigma^n$ بحيث $f(x_1)=1$ (أو أبلّغ إن لم يكن هناك حلّ). سنُشير إلى عدم الحلول بـ$x_0$. وبطبيعة الحال، سنجري ذلك على حاسوب كمومي باستخدام الحالات الكمومية، لذا من المفيد التعبير عن هذه السلاسل الثنائية كحالات:

$$\{|x_1\rangle\} \in |\Sigma^n\rangle$$

باستخدام تدوين الحالة الكمومية (Dirac)، نبحث عن حالة خاصة واحدة أو أكثر $\{|x_1\rangle\}$ ضمن مجموعة من $N=2^n$ حالة ممكنة، حيث $n$ هو عدد الكيوبتات، مع الإشارة إلى عدم الحلول بـ$\{|x_0\rangle\}$.

يمكننا اعتبار الدالة $f$ مقدَّمةً من قِبل أوراكل: صندوق أسود نستطيع الاستعلام عنه لتحديد تأثيره على الحالة $|x\rangle$. من الناحية العملية، كثيرًا ما نعرف الدالة، لكنها قد تكون بالغة التعقيد في التطبيق، مما يجعل تقليل عدد الاستعلامات أو تطبيقات $f$ أمرًا مهمًا. وبالمثل، يمكننا تصوّر نموذج يستعلم فيه شخص عن أوراكل يتحكّم فيه شخص آخر، بحيث لا نعرف دالة الأوراكل بل نعرف فقط تأثيرها على حالات معيّنة عبر الاستعلام.

هذه "مشكلة بحث غير منظّم"، إذ لا يوجد في $f$ أي شيء مميّز يُعيننا في البحث. المخرجات غير مرتّبة ولا يُعرف أن الحلول تتمركز، وهكذا. فكّر في دلائل الهاتف الورقية القديمة كتشبيه: هذا البحث غير المنظّم يشبه تصفّح الدليل بحثًا عن رقم معيّن، لا كالبحث في قائمة أسماء مرتّبة أبجديًا.

في حالة البحث عن حلّ واحد، يتطلّب ذلك كلاسيكيًا عددًا من الاستعلامات يتناسب خطيًا مع $N$. من الواضح أنك قد تجد الحلّ في أوّل محاولة، أو قد لا تجد أي حلّ في أوّل $N-1$ تخمين، مما يستدعي الاستعلام عن المدخل رقم $N$ للتحقق من وجود أي حلّ. ونظرًا لأن الدوال لا تحمل أي بنية يمكن استغلالها، فستحتاج إلى $N/2$ تخمين في المتوسط. أما خوارزمية غروفر فتتطلّب عددًا من الاستعلامات أو حسابات $f$ يتناسب مع $\sqrt{N}$.

لمحة عامة عن الدوائر في خوارزمية غروفر

يمكن إيجاد شرح رياضي مفصّل لخوارزمية غروفر في أساسيات الخوارزميات الكمومية مثلًا، وهو مقرّر من تأليف John Watrous على IBM Quantum Learning. يُقدَّم عرض موجز في ملحق في نهاية هذه الوحدة. لكن في الوقت الراهن، سنستعرض الهيكل العام للدائرة الكمومية التي تُنفّذ خوارزمية غروفر.

يمكن تقسيم خوارزمية غروفر إلى المراحل التالية:

• إعداد تراكب ابتدائي (تطبيق بوابات هادامارد على جميع الكيوبتات)
• "تعليم" الحالة (أو الحالات) الهدف بقلب الطور
• مرحلة "الانتشار" (diffusion) حيث تُطبَّق بوابات هادامارد وقلب الطور على جميع الكيوبتات
• تكرارات محتملة لمرحلتَي التعليم والانتشار لتعظيم احتمالية قياس الحالة الهدف
• القياس

كثيرًا ما يُشار إلى بوابة التعليم $Z_f$ وطبقات الانتشار المكوّنة من $H,$ و$Z_{\text{OR}},$ و$H$ مجتمعةً باسم "مؤثر غروفر". في هذا المخطط، يظهر تكرار واحد فقط من مؤثر غروفر.

بوابات هادامارد $H$ معروفة وتُستخدم على نطاق واسع في الحوسبة الكمومية. تُنشئ بوابة هادامارد حالات التراكب. وتحديدًا، تُعرَّف بـ

$$H|0\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)\\ H|1\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)$$

يُحدَّد تأثيرها على أي حالة أخرى من خلال الخطيّة. بشكل خاص، تتيح لنا طبقة من بوابات هادامارد الانتقال من الحالة الابتدائية حيث جميع الكيوبتات في $|0\rangle$ (يُرمز لها بـ$|0\rangle^{\otimes n}$) إلى حالة يكون فيها لكل كيوبت احتمالية ما لقياسه إما في $|0\rangle$ أو $|1\rangle$؛ مما يُتيح لنا استكشاف فضاء جميع الحالات الممكنة بطريقة مختلفة عن الحوسبة الكلاسيكية.

خاصية أساسية مترتّبة مهمة لبوابة هادامارد هي أن تطبيقها مرة ثانية يُلغي حالات التراكب:

$$H\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)=|0\rangle\\ H\frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)=|1\rangle$$

سيكون هذا مهمًا بعد قليل.

تحقق من فهمك

اقرأ السؤال التالي، فكّر في إجابتك، ثم اضغط على المثلث لإظهار الحل.

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

الإجابة:

عندما نُطبّق X على الحالة $|+\rangle$، نحصل على القيمة +1، وعلى الحالة $|-\rangle$ نحصل على -1، لذا لو كان لدينا توزيع 50-50، فسنحصل على قيمة توقع تساوي 0.

بوابة $Z_\text{OR}$ أقل شيوعاً، وتُعرَّف وفق:

$$\text{Z}_\text{OR}|x\rangle = \begin{cases} |x\rangle & \text{if } x = 0^n \\ -|x\rangle & \text{if } x \neq 0^n \end{cases} \qquad \forall x \in \Sigma^n$$

أما بوابة $Z_f$ فتُعرَّف بـ:

$$Z_f:|x\rangle \rightarrow (-1)^{f(x)}|x\rangle \qquad \forall x \in \Sigma^n$$

لاحظ أن تأثير هذه البوابة هو أن $Z_f$ تعكس الإشارة على الحالة المستهدفة التي يكون فيها $f(x) = 1$، وتترك الحالات الأخرى دون تغيير.

على مستوى عالٍ ومجرّد، يمكنك التفكير في خطوات الدائرة على النحو التالي:

• طبقة هادامارد الأولى: تضع الكيوبتات في تراكب لجميع الحالات الممكنة.
• $Z_f$: تُعلِّم الحالة (أو الحالات) المستهدفة بإضافة إشارة "-" أمامها. هذا لا يُغيِّر احتمالات القياس فوراً، لكنه يُغيِّر سلوك الحالة المستهدفة في الخطوات اللاحقة.
• طبقة هادامارد أخرى: إشارة "-" التي أُدخِلت في الخطوة السابقة ستُغيِّر الإشارة النسبية بين بعض الحدود. بما أن بوابات هادامارد تُحوِّل خليطاً من الحالات الحسابية $(|0\rangle+|1\rangle)/\sqrt{2}$ إلى حالة حسابية واحدة $|0\rangle$، وتُحوِّل $(|0\rangle-|1\rangle)/\sqrt{2}$ إلى $|1\rangle$، فإن هذا الفرق في الإشارة النسبية يبدأ الآن في التأثير على الحالات المقاسة.
• تُطبَّق طبقة أخيرة من بوابات هادامارد، ثم تُجرى القياسات. سنرى في القسم التالي كيف يعمل هذا بتفصيل أكبر.

مثال

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

هذا هو مخطط الدائرة مع الحالات الكمومية مُعلَّمة في مواضع مختلفة. لاحظ أنه مع كيوبتين فقط، هناك أربع حالات محتملة فقط يمكن قياسها في أي ظرف: $|00\rangle$، $|01\rangle$، $|10\rangle$، و$|11\rangle$.

لنفترض أن الأوراكل ($Z_f$، غير المعروف لنا) يُعلِّم الحالة $|01\rangle$. سنعمل على إجراءات كل مجموعة من البوابات الكمومية بما فيها الأوراكل، ونرى ما هو توزيع الحالات الممكنة عند القياس. في البداية تماماً، لدينا:

$$|\psi_0\rangle = |00\rangle$$

باستخدام تعريف بوابات هادامارد، لدينا:

$$|\psi_1\rangle = \frac{1}{2}\left(|0\rangle+|1\rangle\right)\left(|0\rangle+|1\rangle\right)=\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)$$

الآن يُعلِّم الأوراكل الحالة المستهدفة:

$$|\psi_2\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle+|11\rangle\right)$$

لاحظ أن في هذه الحالة، جميع النتائج الأربع المحتملة لها نفس احتمالية القياس. كلها لها وزن بمقدار $1/2$، أي أن لكل منها احتمالية $|1/2|^2=1/4$ للقياس. لذا بينما الحالة $|01\rangle$ مُعلَّمة بالطور "-"، لم يؤدِّ ذلك بعد إلى زيادة احتمالية قياس تلك الحالة. نكمل بتطبيق الطبقة التالية من بوابات هادامارد.

$$\begin{aligned} |\psi_3\rangle = &\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

بجمع الحدود المتشابهة، نجد:

$$|\psi_3\rangle = \frac{1}{2}\left(|00\rangle+|01\rangle-|10\rangle+|11\rangle\right)$$

الآن $Z_{\text{OR}}$ تعكس الإشارة على جميع الحالات ما عدا $|00\rangle$:

$$|\psi_4\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)$$

وأخيراً، نطبّق الطبقة الأخيرة من بوابات هادامارد:

$$\begin{aligned} |\psi_5\rangle =&\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

يستحق الأمر أن تعمل على جمع هذه الحدود بنفسك لتتأكد أن النتيجة هي بالفعل:

$$|\psi_5\rangle =|01\rangle$$

أي أن احتمالية قياس $|01\rangle$ هي 100% (في غياب الضوضاء والأخطاء)، واحتمالية قياس أي حالة أخرى هي صفر.

هذا المثال بكيوبتين كان حالة نظيفة بشكل خاص؛ لن تُنتج خوارزمية غروفر دائماً احتمالية 100% لقياس الحالة المستهدفة. بل ستُضخِّم احتمالية قياس الحالة المستهدفة. كما قد يحتاج مؤثر غروفر إلى تكراره أكثر من مرة.

في القسم التالي، سنُطبِّق هذه الخوارزمية عملياً باستخدام حواسيب IBM® الكمومية الحقيقية.

الصورة الهندسية

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

إعداد المستوى. يمكننا تحليل حالة التراكب الابتدائية $|\psi\rangle$ إلى مكوّنين. الحالة الصحيحة — التي نبحث عنها — نسميها $|A_1\rangle$. أما كل حالة أخرى مجمّعة معاً، فنسميها $|A_0\rangle$. بحكم التعريف، $|A_1\rangle$ و$|A_0\rangle$ متعامدتان، فيمكننا رسمهما كمحورين متعامدين في فضاء مجرد ثنائي الأبعاد. بما أن $|\psi\rangle$ مزيج خطي من هذين المكوّنين، فإنها تقع عند زاوية صغيرة $\theta$ من محور $|A_0\rangle$ — قريبة من $|A_0\rangle$، لأنه في البداية، جزءٌ ضئيلٌ جدًا من الحالة يقع في المكوّن الصحيح $|A_1\rangle$.

الانعكاسات. الحقيقة الرياضية الأساسية التي نحتاجها هي أن مؤثرًا بالشكل

$$2|v\rangle\langle v| - I$$

يعكس أي حالة حول المحور المحدد بـ$|v\rangle.$ للتحقق من ذلك، نأخذ حالتين: حالة على طول $|v\rangle$ تبقى دون تغيير، وحالة عمودية على $|v\rangle$ تُعكس إشارتها. يمكن تحليل أي حالة أخرى إلى هذين المكوّنين، ويعمل المؤثر على كلٍّ منهما وفق ذلك — وهو بالضبط انعكاس حول $|v\rangle$.

يتبيّن أن كلًا من الأوراكل وخطوات الانتشار في خوارزمية غروفر يمكن التعبير عنهما كانعكاسات في هذه الصورة الهندسية.

الأوراكل كانعكاس. يقلب الأوراكل إشارة الحالة $|A_1\rangle$ ويترك كل شيء آخر كما هو. هذا مكافئ لانعكاس حول محور $|A_0\rangle$.

الانتشار كانعكاس. يصعب قليلًا رؤية كيف أن مؤثر الانتشار هو أيضاً انعكاس. مؤثر الانتشار هو

$$H^{\otimes n}\, Z_{\text{OR}}\, H^{\otimes n}$$

$Z_{\text{OR}}$ بحد ذاته انعكاس حول الحالة الصفرية الكاملة، إذ يقلب إشارة كل حالة ليست $|0\rangle^{\otimes n}$. يمكن كتابة ذلك كـ$2|0\rangle\langle 0| - I$. طبقات هادامارد المحيطة تُجري فعليًا تغييرًا في الأساس يحوّل محور الانعكاس. تذكّر أن $H^{\otimes n}$ تربط $|0\rangle^{\otimes n}$ بالتراكب المنتظم $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$. بما أن هادامارد معكوسها هي نفسها، يصبح التعبير الكامل

$$H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n} = 2|u\rangle\langle u| - I$$

وهو انعكاس حول $|u\rangle$. بما أن $|u\rangle$ قريبة جدًا من $|\psi\rangle$ (كلاهما يقعان قريبًا من $|A_0\rangle$)، يُرسل هذا الانعكاس الثاني الحالةَ إلى زاوية $2\theta$ من موضعها الابتدائي.

دوران بمقدار $2\theta$. التأثير المشترك لهذين الانعكاسين هو دوران بمقدار $2\theta$ نحو $|A_1\rangle$. كل تكرار متعاقب لمؤثر غروفر يدير الحالة بمقدار $2\theta$ إضافي.

العدد الأمثل من التكرارات. هدفنا هو تدوير الحالة بأقرب ما يمكن من $|A_1\rangle$، وهذا يعني الدوران بما يقارب $\pi/2$ راديان (ربع دورة). إذا أسهم كل تكرار بـ$2\theta$، فإن العدد الأمثل من التكرارات $t$ يُحقق

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

لحل واحد بين $N$ حالة، تكون الزاوية الابتدائية $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (لقيم $N$ الكبيرة). بالتعويض،

$$t \approx \frac{\pi}{4}\sqrt{N} - \frac{1}{2}$$

هذا هو مصدر التسريع الشهير $\sqrt{N}$: نحتاج فقط $O(\sqrt{N})$ تكرارًا للوصول إلى الهدف، بدلًا من $O(N)$ فحصًا تستلزمه الخوارزمية الكلاسيكية.

بشكل أعم، إذا كان هناك $|A_1|$ حالة حلّ بين $N$ حالة إجمالية، فإن العدد الأمثل من التكرارات هو

$$t \approx \frac{\pi}{4}\sqrt{\frac{N}{|A_1|}} - \frac{1}{2}$$

لاحظ أنك إذا طبّقت تكرارات أكثر من اللازم، تتجاوز $|A_1\rangle$ وتبدأ احتمالية إيجاد حالة الهدف في الانخفاض مجددًا. إيجاد العدد الصحيح من التكرارات مهم، وإن كان العدد الأمثل تجريبيًا على الأجهزة الكمومية ذات الضوضاء قد يختلف عن هذه الصيغة المثالية.

لماذا خوارزمية غروفر مفيدة؟

قد تتساءل في هذه المرحلة: لقد بنينا للتو أوراكل يُعلّم حالة مستهدفة — لكن لبنائه كان علينا معرفة الحالة المستهدفة. إذن ما الذي نبحث عنه أصلًا؟

هذا سؤال وجيه، وثمة عدة إجابات جيدة.

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

• يمكنك أيضًا التفكير فيها كـنشاط بين طرفين: شخص يعرف الحالة المستهدفة ويبني الأوراكل؛ ومهمة الشخص الآخر إيجاد الإجابة باستخدام الأوراكل كصندوق أسود دون إطلاع. في النشاط 2 أدناه، ستفعل ذلك بالضبط مع شريك.

• تضخيم السعة هو روتين فرعي مفيد على نطاق واسع. حتى لو بدا هذا العرض الأول دائريًا، فإن الآلية الأساسية — المسماة تضخيم السعة — تظهر مرارًا وتكرارًا في الحوسبة الكمومية. ما نبنيه هنا في الحقيقة هو حدس لأداة تظهر كروتين فرعي في خوارزميات كمومية أكثر تعقيدًا.

• ثمة مشاكل يمكن فيها بناء أوراكل دون معرفة الإجابة. الرؤية الجوهرية هي أن هناك فئة كاملة من المشاكل يصعب جدًا إيجاد حلٍّ لها، لكن يسهل جدًا التحقق من صحة حلٍّ معطى. التحليل إلى عوامل أولية مثال على ذلك: بالنسبة لحاصل ضرب عددين أوليين كبيرين، يصعب جدًا تحديد ما هما، لكن حين تحصل عليهما يمكنك بسهولة ضربهما للتحقق. (لدينا خوارزمية أفضل من غروفر للتحليل إلى عوامل أولية تحديدًا — انظر خوارزمية Shor — لكن هذه ليست المشكلة الوحيدة ذات هذه الخاصية.) السودوكو، ومشاكل إرضاء القيود، وحتى لعبة الألغام الكلاسيكية Minesweeper، كلها مشاكل يصعب حلها لكن يسهل التحقق منها.

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

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

الاستيرادات العامة والنهج

نبدأ باستيراد عدة حزم ضرورية.

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

في هذا الدرس وغيره من الدروس، سنستخدم إطار عمل للحوسبة الكمومية يُعرف بـ "أنماط Qiskit"، الذي يُقسِّم سير العمل إلى الخطوات التالية:

• الخطوة 1: تحويل المدخلات الكلاسيكية إلى مسألة كمومية
• الخطوة 2: تحسين المسألة للتنفيذ الكمومي
• الخطوة 3: التنفيذ باستخدام Qiskit Runtime Primitives
• الخطوة 4: المعالجة اللاحقة والتحليل الكلاسيكي

سنتبع هذه الخطوات بشكل عام، وإن كنا قد لا نُعلِّمها صراحةً دائماً.

النشاط 1: إيجاد حالة مستهدفة واحدة محددة

الخطوة 1: تحويل المدخلات الكلاسيكية إلى مسألة كمومية

نحتاج بوابة استعلام الطور لوضع طور كلي (-1) على حالات الحل، وترك الحالات غير الحلول دون تأثير. بعبارة أخرى، تتطلب خوارزمية غروفر أوراكل يحدد حالة أساسية حسابية واحدة أو أكثر "مُعلَّمة"، حيث تعني "مُعلَّمة" حالةً ذات طور يساوي -1. يتم ذلك باستخدام بوابة Z المتحكَّم بها، أو تعميمها المتعدد التحكم على $N$ كيوبت. لفهم كيفية عمل هذا، دعنا نتأمل مثالاً محدداً لسلسلة البت {110}. نريد دائرة تعمل على الحالة $|\psi\rangle = |q_2,q_1,q_0\rangle$ وتُطبق طوراً إذا كانت $|\psi\rangle = |011\rangle$ (حيث عكسنا ترتيب السلسلة الثنائية بسبب طريقة الترميز في Qiskit، التي تضع الكيوبت الأقل أهمية (عادةً 0) على اليمين).

وبالتالي، نريد دائرة $Z_f$ تحقق

$$Z_f|\psi\rangle = \begin{cases} -|\psi\rangle \qquad \text{if} \qquad |\psi\rangle = |011\rangle \\ |\psi\rangle \qquad \text{if} \qquad |\psi\rangle \neq |011\rangle\end{cases}$$

يمكننا استخدام بوابة متعددة التحكم ومتعددة الأهداف (MCMTGate) لتطبيق بوابة Z يتحكم بها جميع الكيوبتات (قلب الطور إذا كانت كل الكيوبتات في حالة $|1\rangle$). بالطبع، قد تكون بعض الكيوبتات في حالتنا المطلوبة $|0\rangle$. لذا، على تلك الكيوبتات يجب أولاً تطبيق بوابة X، ثم تنفيذ بوابة Z متعددة التحكم، ثم تطبيق بوابة X أخرى للتراجع عن تغييرنا. تبدو MCMTGate هكذا:

mcmt_ex = QuantumCircuit(3)
mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)
mcmt_ex.draw(output="mpl", style="iqp")

لاحظ أن كثيراً من الكيوبتات قد تشارك في عملية التحكم (هنا ثلاث كيوبتات)، لكن لا يُحدَّد أي كيوبت منفرد باعتباره هدفاً. هذا لأن الحالة الكاملة تحصل على إشارة "-" كلية (قلب الطور)؛ إذ تؤثر البوابة على جميع الكيوبتات بالتساوي. يختلف هذا عن كثير من بوابات الكيوبتات المتعددة الأخرى، كبوابة CX التي لها كيوبت تحكم واحد وكيوبت هدف واحد.

في الكود التالي، نُعرِّف بوابة استعلام الطور (أو الأوراكل) التي تفعل ما وصفناه للتو: تُعلِّم حالة أساسية مدخلة واحدة أو أكثر محددة من خلال تمثيل سلسلة البت الخاصة بها. تُستخدم بوابة MCMT لتنفيذ بوابة Z متعددة التحكم.

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bitstring to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bitstring
        zero_inds = [
            ind for ind in range(num_qubits) if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bitstring has a '0' entry
        qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        qc.x(zero_inds)
    return qc

الآن نختار حالة "مُعلَّمة" محددة لتكون هدفنا، ونطبق الدالة التي عرفناها للتو. دعنا نرى نوع الدائرة التي أنشأتها.

marked_states = ["1110"]
oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

إذا كانت الكيوبتات 1-3 في حالة $|1\rangle$، والكيوبت 0 في البداية في حالة $|0\rangle$، فإن بوابة X الأولى ستقلب الكيوبت 0 إلى $|1\rangle$ وستكون جميع الكيوبتات في حالة $|1\rangle.$ وهذا يعني أن بوابة MCMT ستُطبق تغييراً كلياً في الإشارة أو قلباً للطور، كما هو مطلوب. في أي حالة أخرى، إما أن تكون الكيوبتات 1-3 في حالة $|0\rangle$، أو يُقلب الكيوبت 0 إلى حالة $|0\rangle$، ولن يُطبَّق قلب الطور. نرى أن هذه الدائرة تُعلِّم فعلاً حالتنا المطلوبة $|0111\rangle,$ أو سلسلة البت {1110}. يتكون مؤثر غروفر الكامل من بوابة استعلام الطور (الأوراكل)، وطبقات هادامارد، ومشغل $Z_\text{OR}$. يمكننا استخدام grover_operator المدمج لبناء هذا من الأوراكل الذي عرفناه أعلاه.

grover_op = grover_operator(oracle)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

كما ناقشنا في الصورة الهندسية أعلاه، قد نحتاج إلى تطبيق مؤثر غروفر عدة مرات. العدد الأمثل من التكرارات $t$ لتعظيم سعة الحالة المستهدفة في غياب الضوضاء هو

$$t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

حيث $|A_1|$ هو عدد حالات الحل و$N=2^n$ هو العدد الإجمالي للحالات. على أجهزة الكمبيوتر الكمي الحديثة ذات الضوضاء، قد يختلف العدد الأمثل تجريبياً من التكرارات — لكننا هنا نحسب ونستخدم هذا العدد الأمثل النظري باستخدام $|A_1|=1$.

optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)
print(optimal_num_iterations)

3

لنقم الآن ببناء دائرة تتضمن بوابات هادامارد الأولية لإنشاء تراكب لجميع الحالات الممكنة، وتطبيق مؤثر غروفر العدد الأمثل من المرات.

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

لقد بنينا دائرة غروفر الخاصة بنا!

الخطوة 2: تحسين المسألة لتنفيذها على الأجهزة الكمية

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

يوجد أدناه كود لحفظ بيانات اعتمادك عند الاستخدام الأول. تأكد من حذف هذه المعلومات من الدفتر بعد حفظها في بيئتك، حتى لا تتشارك بيانات اعتمادك عن طريق الخطأ عند مشاركة الدفتر. راجع Set up your IBM Cloud account وInitialize the service in an untrusted environment للاطلاع على مزيد من التوجيهات.

# To run on hardware, select the backend with the fewest number of jobs in the queue
from qiskit_ibm_runtime import QiskitRuntimeService

# Syntax for first saving your token.  Delete these lines after saving your credentials.

# QiskitRuntimeService.save_account(channel='ibm_quantum_platform',
# instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

backend = service.least_busy(operational=True, simulator=False)
backend.name

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.

'ibm_brisbane'

الآن نستخدم مدير التمريرات المُعدّ مسبقًا لتحسين دائرتنا الكمية للخلفية التي اخترناها.

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

circuit_isa = pm.run(qc)
# The transpiled circuit will be very large. Only draw it if you are really curious.
# circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

تجدر الإشارة في هذه المرحلة إلى أن عمق الدائرة الكمية بعد التحويل كبير جدًا.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  439
The depth of two-qubit gates is  113

هذه أرقام كبيرة فعلًا، حتى في هذه الحالة البسيطة. بما أن كل البوابات الكمية (وخاصةً بوابات الكيوبتين) تتأثر بالأخطاء والضوضاء، فإن سلسلة تضم أكثر من 100 بوابة ثنائية الكيوبت ستنتج ضوضاءً محضة إن لم تكن الكيوبتات عالية الأداء للغاية. لنرى كيف تؤدي هذه الدوائر أداءها.

الخطوة 3: التنفيذ باستخدام Qiskit primitives

نريد إجراء قياسات كثيرة ومعرفة الحالة الأكثر احتمالًا. هذا التضخيم في السعة هو مسألة أخذ عينات تناسب التنفيذ باستخدام primitive الـ Sampler من Qiskit Runtime.

لاحظ أن الدالة run() في Qiskit Runtime SamplerV2 تأخذ عناصر قابلة للتكرار تُسمى primitive unified blocks أو PUBs. بالنسبة للـ Sampler، كل PUB هو عنصر قابل للتكرار بالصيغة (circuit, parameter_values). على الأقل، يمكن تمرير قائمة من الدوائر الكمية.

# To run on a real quantum computer (this was tested on a Heron r2 processor and
# used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

للاستفادة القصوى من هذه التجربة، ننصحك بشدة بتشغيل تجاربك على الحواسيب الكمية الحقيقية المتاحة من IBM Quantum. لكن إن استنفدت وقت المعالج الكمي (QPU)، يمكنك إلغاء تعليق الأسطر أدناه لإتمام هذا النشاط باستخدام محاكٍ.

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

الخطوة 4: المعالجة اللاحقة وإرجاع النتيجة بالصيغة الكلاسيكية المطلوبة

الآن يمكننا رسم نتائج أخذ العينات في مخطط توزيع.

plot_distribution(dist)

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

تحقق من فهمك

اقرأ الأسئلة أدناه، فكّر في إجابتك، ثم اضغط على المثلث لكشف الحل.

بحثنا للتو عن حل واحد في مجموعة تضم $2^4=16$ حالة ممكنة. وحددنا العدد الأمثل لتكرارات مؤثر غروفر بـ $t=3$. هل كان هذا العدد الأمثل سيزداد أم يقل لو بحثنا عن (أ) أي من عدة حلول، أو (ب) حل واحد في فضاء يضم حالات ممكنة أكثر؟

الجواب:

تذكّر أنه طالما عدد الحلول صغير مقارنةً بالفضاء الكامل للحلول، يمكننا توسيع دالة الجيب حول زوايا صغيرة واستخدام

$$(2t+1)\theta = (2t+1) \sin^{-1}{\sqrt{\frac{|\mathcal{A}_1|}{N}}}\approx (2t+1) \sqrt{\frac{|\mathcal{A}_1|}{N}} \approx \pi/2\\ t \approx \frac{\pi}{4}\sqrt{\frac{N}{|\mathcal{A}_1|}}-\frac{1}{2}$$

(أ) نرى من التعبير أعلاه أن زيادة عدد الحالات الحلول تُقلل عدد التكرارات. بشرط أن تظل النسبة $\frac{|\mathcal{A}_1|}{N}$ صغيرة، يمكن وصف كيف يقل $t$: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

(ب) مع زيادة فضاء الحلول الممكنة ($N$)، يزيد عدد التكرارات المطلوبة، لكن بمعدل $t~\sqrt{N}$ فقط.

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

الجواب:

لا. لنفترض أننا كررنا النشاط الأول بـ 20 كيوبت، وشغّلنا الدائرة الكمية عددًا من المرات num_shots = 10,000. توزيع الاحتمالات المنتظم يعني أن كل حالة لها احتمال $10,000/2^{20}=0.00954$ لقياسها مرة واحدة على الأقل. لو كان احتمال قياس الحالة المستهدفة 10 أضعاف احتمال الحلول غير الصحيحة (مع انخفاض طفيف مقابل في احتمال كل حل غير صحيح)، فستكون هناك فرصة 10% فقط لقياس الحالة المستهدفة ولو مرة واحدة. ومن المستبعد جدًا قياس الحالة المستهدفة عدة مرات، مما يجعلها غير قابلة للتمييز عن الحالات غير الحلول التي يتم الحصول عليها عشوائيًا. والخبر الجيد هو أنه يمكننا الحصول على نتائج بدقة أعلى باستخدام قمع الأخطاء والتخفيف منها.

النشاط 2: سير عمل خوارزمية استعلام دقيقة

سنبدأ هذا النشاط تمامًا كما بدأنا الأول، إلا أنك الآن ستعمل مع متحمس آخر لـ Qiskit. ستختار أنت سلسلة بت سرية، وسيختار شريكك سلسلة بت (مختلفة عمومًا). ستولّد كلٌّ منكما دائرة كمية تعمل كأوراكل، وستتبادلانهما. ستستخدم بعدها خوارزمية غروفر مع أوراكل شريكك لتحديد سلسلة البت السرية لديه.

الخطوة 1: تحويل المدخلات الكلاسيكية إلى مسألة كمية

باستخدام الدالة grover_oracle المعرّفة أعلاه، أنشئ دائرة أوراكل لحالة واحدة أو أكثر من الحالات المُعلَّمة. تأكد من إخبار شريكك بعدد الحالات التي علّمتها، حتى يتمكن من تطبيق مؤثر غروفر العدد الأمثل من المرات. لا تجعل سلسلة البت الخاصة بك طويلة جدًا. 3-5 بتات تعمل بدون مشاكل تُذكر. سلاسل البت الأطول ستؤدي إلى دوائر عميقة تتطلب تقنيات أكثر تقدمًا مثل تخفيف الأخطاء.

# Modify the marked states to mark those you wish to target.
marked_states = ["1000"]
oracle = grover_oracle(marked_states)

الآن أنشأت دائرة كمية تقلب طور حالتك المستهدفة. يمكنك حفظ هذه الدائرة بصيغة my_circuit.qpy باستخدام الصيغة أدناه.

from qiskit import qpy

# Save to a QPY file at a location where you can easily find it.
# You might want to specify a global address.
with open("C:\\Users\\...put your own address here...\\my_circuit.qpy", "wb") as f:
    qpy.dump(oracle, f)

الآن أرسل هذا الملف لشريكك (عبر البريد الإلكتروني، أو تطبيق مراسلة، أو مستودع مشترك، وما إلى ذلك). اطلب منه أيضاً أن يرسل لك دائرته. تأكد من حفظ الملف في مكان يسهل عليك إيجاده. بمجرد حصولك على دائرة شريكك، يمكنك عرضها بصريًا - لكن هذا يكسر نموذج الاستعلام. أي أننا نحاكي موقفاً يمكنك فيه الاستعلام عن الأوراكل (استخدام دائرة الأوراكل) لكن لا تفحصها لتحديد الحالة التي تستهدفها.

from qiskit import qpy

# Load the circuit from your partner's qpy file from the folder where you saved it.
with open("C:\\Users\\...file location here...\\my_circuit.qpy", "rb") as f:
    circuits = qpy.load(f)

# qpy.load always returns a list of circuits
oracle_partner = circuits[0]

# You could visualize the circuit, but this would break the model of a query algorithm.
# oracle_partner.draw("mpl")

اسأل شريكك عن عدد الحالات المستهدفة التي برمجها وأدخلها أدناه.

# Update according to your partner's number of target states.
num_marked_states = 1

يُستخدم هذا في التعبير التالي لتحديد العدد الأمثل لتكرارات غروفر.

grover_op = grover_operator(oracle_partner)
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_marked_states / 2**grover_op.num_qubits)))
)
qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

الخطوة 2: تحسين المسألة لتنفيذها على العتاد الكمومي

هذه الخطوة تسير تماماً كما في السابق.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
backend.name

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_partner_isa = pm.run(qc)

الخطوة 3: التنفيذ باستخدام Qiskit primitives

هذه الخطوة أيضاً مطابقة لما فعلناه في النشاط الأول.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used
# 4 seconds of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_partner_isa]).result()
dist = result[0].data.meas.get_counts()

الخطوة 4: معالجة النتائج وإرجاعها بالصيغة الكلاسيكية المطلوبة

الآن اعرض مخطط توزيع (histogram) لنتائج أخذ العينات. يجب أن تظهر حالة واحدة أو أكثر باحتمالية قياس أعلى بكثير من غيرها. أبلغ شريكك بهذه النتائج وتحقق إذا كنت حددت الحالات المستهدفة بشكل صحيح. افتراضياً، المخطط المعروض هو لنفس الدائرة من النشاط الأول. من المفترض تحصل على نتائج مختلفة من دائرة شريكك.

plot_distribution(dist)

تحقق من فهمك

اقرأ الأسئلة أو التعليمات أدناه، فكّر في إجابتك أو ناقش العملية مع شريكك. اضغط على المثلث للحصول على تلميحات أو اقتراحات.

من المفترض أنك حصلت على الحالة/الحالات المستهدفة لشريكك بشكل صحيح. إذا لم تحصل على ذلك، اعمل مع شريكك لتحديد أين المشكلة. اضغط أدناه لبعض الأفكار.

تلميحات:

• اعرض/ارسم دائرة شريكك وتأكد من أنها تحمّلت بشكل صحيح.
• قارن الدوائر المستخدمة وقارن النتيجة المتوقعة بما حصلت عليه.
• تحقق من عمق الدوائر المستخدمة للتأكد من أن سلسلة البت لم تكن طويلة جداً أو عدد تكرارات غروفر مرتفعاً بشكل مفرط.

إذا لم تكن قد فعلت ذلك، ارسم دائرة الأوراكل التي أرسلها لك شريكك. حاول تشرح تأثير كل بوابة وتبرر ما يجب أن تكون عليه الحالة المستهدفة. سيكون هذا أسهل بكثير في حالة حالة مستهدفة واحدة مقارنةً بحالات متعددة.

تلميحات:

• تذكر أن مهمة الأوراكل هي قلب الإشارة على الحالة المستهدفة.
• تذكر أن MCMTGate يقلب الإشارة على حالة ما إذا وفقط إذا كانت جميع الكيوبتات المشاركة في التحكم في حالة $|1\rangle$.
• إذا كانت حالتك المستهدفة ستحتوي بالفعل على $|1\rangle$ على كيوبت معين، فلا تحتاج لعمل أي شيء لذلك الكيوبت. إذا كانت حالتك المستهدفة تحتوي على $|0\rangle$ على كيوبت معين وتريد من MCMTGate قلب الإشارة، تحتاج إلى تطبيق بوابة X على ذلك الكيوبت في أوراكلك (ثم التراجع عن بوابة X بعد MCMTGate).

كرر التجربة بتكرار واحد أقل من مؤثر غروفر. هل ما زلت تحصل على الإجابة الصحيحة؟ لماذا أو لماذا لا؟

توجيه:

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

لماذا قد يستخدم أحد عدد تكرارات غروفر أقل من "العدد الأمثل" الذي تحدد هنا؟

الإجابة:

العدد "الأمثل" لتكرارات غروفر هو العدد الذي يجعل احتمال قياس الحالة المُعلَّمة أعلى ما يكون في غياب الضوضاء. لكن عدد تكرارات أقل من ذلك قد يظل يجعل الحالة المُعلَّمة أكثر احتمالاً بكثير من الحالات الأخرى. أي يمكنك العمل بعدد تكرارات أقل من العدد الأمثل. هذا يقلل عمق الدائرة، وبالتالي يقلل معدلات الخطأ.

النشاط 3: حلّ شبكة Minesweeper بخوارزمية غروفر

في القسم السابق، أشرنا إلى أن خوارزمية غروفر تصبح مفيدة فعلًا حين نستطيع بناء أوراكل من قيود المشكلة لا من معرفة الإجابة. Minesweeper مثال مثالي: الخلايا المرقّمة تُخبرنا بعدد الألغام المجاورة، وتلك القيود تُحدّد تمامًا أين يجب أن تكون الألغام — لكن إيجاد التوزيع يستلزم البحث.

ثبت أن Minesweeper مكتملة على NP (NP-complete): يصعب حلّها لكن يسهل التحقق منها. هذا يجعلها مرشحًا طبيعيًا لخوارزمية غروفر. بالطبع، لا يمكننا بعدُ حل شبكة 9$\times$9 كاملة على حاسوب كمومي ذي ضوضاء — إذ ستكون الدوائر عميقة جدًا. بدلًا من ذلك، سنستخدم شبكة صغيرة جدًا كعرض توضيحي لكيفية معالجة لوحة أكبر على آلة متسامحة مع الأخطاء في المستقبل.

بعض التحفظات المهمة. تُوفّر خوارزمية غروفر تسريعًا تربيعيًا فحسب على البحث الكلاسيكي غير المنظّم. يمتلك Minesweeper على الأرجح بنية قابلة للاستغلال يمكن لخوارزمية كلاسيكية ذكية استخدامها. وبالنسبة لفضاء بحث متنامٍ أسيًا، فإن تحسين $\sqrt{N}$ وحده لا يكفي إلى ما لا نهاية. لكن دعنا نتجاوز تلك المخاوف ونستخدم هذه المسألة التوضيحية لتوضيح كيفية ترميز قيود المشكلة في أوراكل كمومي.

الشبكة

إليك شبكة Minesweeper الصغيرة:

يمكن تمثيل كل خلية فارغة بمتغير ثنائي يُشير إلى وجود لغم أو غيابه. نُسمّيها $x_0$ و$x_1$ و$x_2$، حيث يعني $x_i = 1$ وجود لغم في تلك الخلية و$x_i = 0$ غيابه:

بإمكاننا حلّ هذه الشبكة ذهنيًا في نصف ثانية، لكننا نستخدم هذه المسألة التوضيحية لتوضيح كيفية التعامل مع لوحة أصعب بكثير باستخدام حاسوب كمومي.

ترميز القيود

تضع كل خلية مرقّمة شرطًا على الخلايا الفارغة المجاورة. نحتاج إلى التعبير عن هذه الشروط كتعبيرات منطقية قابلة للترميز في دائرة كمومية.

الخلية "1" المجاورة لـ$x_0$ و$x_1$ تقول إن واحدًا منهما بالضبط يحتوي لغمًا. هذا هو تمامًا عملية XOR (OR الحصري)، $\oplus$، التي تُعيد true عندما يكون أحد مدخلاتها فحسب true:

$$(x_0 \oplus x_1)$$

وبالمثل، الخلية الأخرى "1" (المجاورة لـ$x_1$ و$x_2$) تُعطينا:

$$(x_1 \oplus x_2)$$

الخلية "2" تقول إن اثنتين من الخلايا الفارغة الثلاث يجب أن تحويا ألغامًا. بما أن XOR عملية تكافؤ (parity)، فإن $x_0 \oplus x_1 \oplus x_2$ تُعيد true عندما يكون عدد فردي من المتغيرات true. نريد عددًا زوجيًا (تحديدًا اثنين)، لذا ننفي بـ$\lnot$:

$$\lnot(x_0 \oplus x_1 \oplus x_2)$$

هذا التعبير وحده يتحقق إذا كان صفر كيوبتات أو كيوبتان في حالة $|1\rangle$، إذ هو تصريح عن التكافؤ. لكن مع الشرطين الآخرين اللذين يتطلبان وجود لغم واحد على الأقل في كلٍّ منهما، يكون التعيين الوحيد المُرضي هو وجود لغمين بالضبط.

يجب استيفاء الشروط الثلاثة في آنٍ واحد، لذا نربطها بعلامات "و" $\land$:

$$(x_0 \oplus x_1) \;\land\; (x_1 \oplus x_2) \;\land\; \lnot(x_0 \oplus x_1 \oplus x_2)$$

الخطوة 1: تحويل المدخلات الكلاسيكية إلى مسألة كمومية

نحتاج الآن إلى ترميز هذا التعبير المنطقي في دائرة كمومية تعمل كالأوراكل. يمكن تحقيق نظير XOR الكمومي بوابات CX (CNOT): تطبيق بوابتَي CX من الكيوبتات البيانية إلى كيوبت مساحة عمل (ancilla) يحسب فعليًا XOR ويُخزّن النتيجة في ancilla.

نُدخل ثلاثة كيوبتات مساحة عمل — واحد لكل شرط. نُخزّن نتيجة كل تعبير منطقي في كيوبت مساحة العمل المقابل له، ثم نستخدم بوابة Z متعددة التحكم لقلب طور حالة الكيوبتات الثلاثة التي تجعل جميع كيوبتات مساحة العمل الثلاثة $|1\rangle$ (أي استيفاء جميع الشروط في آنٍ واحد).

في خلية الكود الأولى أدناه، نبني النصف "الحسابي" من الأوراكل — الجزء الذي يُقيّم كل شرط ويكتب النتيجة في كيوبتات مساحة العمل.

x = QuantumRegister(3, "x")
a = QuantumRegister(3, "a")
qc = QuantumCircuit(x, a)

# Clause 1: x0 XOR x1 -> stored in a[0]
qc.cx(x[0], a[0])
qc.cx(x[1], a[0])

# Clause 2: x1 XOR x2 -> stored in a[1]
qc.cx(x[1], a[1])
qc.cx(x[2], a[1])

# Clause 3: NOT(x0 XOR x1 XOR x2) -> stored in a[2]
qc.cx(x[0], a[2])
qc.cx(x[1], a[2])
qc.cx(x[2], a[2])
qc.x(a[2])  # The NOT

qc.draw("mpl", style="iqp")

عند هذه النقطة، تُخزَّن نتيجة كل شرط في كيوبت مساحة العمل المقابل له. نحتاج الآن إلى أن تكتسب حالة الكيوبتات البيانية الثلاثية التي تجعل جميع كيوبتات مساحة العمل الثلاثة $|1\rangle$ إشارةً سالبة. نفعل ذلك ببوابة Z متعددة التحكم (مُنفَّذة كبوابة MCX محاطة ببوابات هادامارد على الهدف).

بعد تطبيق قلب الطور، يجب أن نحسب عكسيًا — نتراجع عن جميع خطوات تقييم الشروط بترتيب عكسي — لإعادة كيوبتات مساحة العمل إلى $|0\rangle.$ هذا ضروري حتى تكون كيوبتات مساحة العمل نظيفة للتكرارات اللاحقة لمؤثر غروفر.

# Multi-controlled Z: flip phase if all workspace qubits are |1>
qc.h(a[2])
qc.mcx([a[0], a[1]], a[2])
qc.h(a[2])

# Uncompute clause 3: NOT(x0 XOR x1 XOR x2)
qc.x(a[2])
qc.cx(x[2], a[2])
qc.cx(x[1], a[2])
qc.cx(x[0], a[2])

# Uncompute clause 2: x1 XOR x2
qc.cx(x[2], a[1])
qc.cx(x[1], a[1])

# Uncompute clause 1: x0 XOR x1
qc.cx(x[1], a[0])
qc.cx(x[0], a[0])

qc.draw("mpl", style="iqp")

هذه الدائرة هي أوراكلنا: تقلب طور حالة الكيوبتات البيانية التي تستوفي جميع قيود Minesweeper الثلاثة، وتترك كيوبتات مساحة العمل في $|0\rangle.$

الآن نبني مؤثر غروفر الكامل من هذا الأوراكل. لاحظ وسيطة reflection_qubits: نُمرّر فقط الكيوبتات البيانية x، لأن كيوبتات مساحة العمل ليست جزءًا من فضاء البحث. دورها ينتهي بمجرد تطبيق الأوراكل.

grover_op = grover_operator(qc, reflection_qubits=x)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

مع ثلاثة كيوبتات بيانية وحالة حلٍّ واحدة، العدد الأمثل لتكرارات غروفر هو $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$، فنستخدم تكرارين. نُطبّق بوابات هادامارد على الكيوبتات البيانية لإنشاء التراكب الابتدائي، ونركّب مؤثر غروفر مرتين، ونقيس الكيوبتات البيانية فحسب.

x = QuantumRegister(3, "x")
a = QuantumRegister(4, "a")
meas = ClassicalRegister(3, "meas")

qc = QuantumCircuit(x, a, meas)
# Create superposition over the data qubits only
qc.h(x)
# Apply 2 iterations of the Grover operator
qc.compose(grover_op.power(2), inplace=True)
# Measure only the data qubits
qc.measure(x, meas)
qc.decompose().draw(output="mpl", style="iqp")

الخطوة 2: تحسين المسألة لتنفيذها على الأجهزة الكمية

كما في السابق، نُحوّل (transpile) الدائرة للخلفية المستهدفة.

service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
print(backend.name)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

الآن يمكننا التحقق من عمق الدائرة بعد التحويل. بما أن أوراكل Minesweeper يستخدم كيوبتات مساحة عمل وبوابات CX متعددة، ستكون الدائرة المُحوَّلة أعمق من تلك الموجودة في الأنشطة السابقة.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

الخطوة 3: التنفيذ باستخدام Qiskit primitives

# To run on a real quantum computer (this was tested on a Heron r2 processor and
#  used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

الخطوة 4: المعالجة اللاحقة وإرجاع النتيجة بالصيغة الكلاسيكية المطلوبة

plot_distribution(dist)

يجب أن تظهر الحالة 101 باحتمالية أعلى بكثير من أي حالة أخرى، مما يُشير إلى وجود ألغام عند $x_0$ و$x_2$. لقد استخدمنا حاسوبًا كموميًا لحلّ لعبة Minesweeper صغيرة!

بالطبع، أفضل الخوارزميات الكلاسيكية لـ Minesweeper أفضل من البحث بالقوة الغاشمة في جميع توزيعات الألغام المحتملة — فهي تستغل بنية الشبكة. لن تُوفّر خوارزمية غروفر ميزة إلا في اللوحات البالغة الصعوبة المُصمَّمة لتكون غامضة إلى أقصى حد، وحتى في تلك الحالة، فإن التسريع التربيعي لا يستطيع مواكبة النمو الأسي إلى الأبد. لكن الفائدة الحقيقية هي الأسلوب: ترميز قيود المشكلة في أوراكل كمومي نمط قوي يمتد إلى إرضاء القيود، والتحسين التوافقي، وكثير من المجالات الأخرى.

الأسئلة والمفاهيم الأساسية:

المفاهيم الأساسية:

في هذه الوحدة، تعلمنا بعض الميزات الرئيسية لخوارزمية غروفر:

• بينما تتطلب خوارزميات البحث الكلاسيكية غير المنظمة عدداً من الاستعلامات يتناسب خطياً مع حجم الفضاء $N,$ فإن خوارزمية غروفر تتطلب عدداً من الاستعلامات يتناسب مع $\sqrt{N}.$
• تتضمن خوارزمية غروفر تكرار سلسلة من العمليات (المعروفة عادةً بـ"مؤثر غروفر") عدداً من المرات $t,$ يُختار بحيث تكون احتمالية قياس الحالات المُعلَّمة مثلى.
• يمكن تشغيل خوارزمية غروفر بعدد أقل من $t$ تكرارات ومع ذلك تُضخّم الحالات المُعلَّمة.
• تنتمي خوارزمية غروفر إلى نموذج الحوسبة القائم على الاستعلامات، وتكون أكثر منطقية حين يتحكم شخص في البحث ويتحكم آخر في بناء الأوراكل. وقد تكون مفيدة أيضاً كروتين فرعي في عمليات حوسبة كمية أخرى.
• يمكن بناء الأوراكل من قيود المشكلة لا من معرفة الحل، كما أُوضح بمثال Minesweeper.

أسئلة صح/خطأ:

1. صح/خطأ: توفر خوارزمية غروفر تحسناً أسياً مقارنة بالخوارزميات الكلاسيكية في عدد الاستعلامات اللازمة للعثور على حالة واحدة مُعلَّمة في بحث غير منظم.

2. صح/خطأ: تعمل خوارزمية غروفر عن طريق زيادة احتمالية قياس حالة الحل بشكل تكراري.

3. صح/خطأ: كلما زاد عدد تكرارات مؤثر غروفر، ارتفعت احتمالية قياس حالة الحل.

أسئلة الاختيار من متعدد:

1. اختر الخيار الأنسب لإكمال الجملة. أفضل استراتيجية لاستخدام خوارزمية غروفر بنجاح على أجهزة الكمبيوتر الكمية الحديثة هي تكرار مؤثر غروفر...

• أ. مرة واحدة فقط.
• ب. دائماً $t$ مرة، لتعظيم سعة احتمالية الحالة (الحالات) المُعلَّمة.
• ج. حتى $t$ مرة، وإن كان عدد أقل قد يكفي لإبراز الحالات المُعلَّمة.
• د. لا يقل عن 10 مرات.

2. يظهر هنا دائرة استعلام الطور التي تعمل كأوراكل لتمييز حالة معينة بقلب الطور. أي من الحالات التالية يتم تمييزها بواسطة هذه الدائرة؟

• أ. $|0000\rangle$
• ب. $|0101\rangle$
• ج. $|0110\rangle$
• د. $|1001\rangle$
• هـ. $|1010\rangle$
• و. $|1111\rangle$

3. افترض أنك تريد البحث عن ثلاث حالات مُعلَّمة من مجموعة مكونة من 128. ما هو العدد الأمثل من تكرارات مؤثر غروفر لتعظيم سعات الحالات المُعلَّمة؟

• أ. 1
• ب. 3
• ج. 5
• د. 6
• هـ. 20
• و. 33

أسئلة للنقاش:

1. ما هي المشاكل الأخرى التي يمكنك صياغتها كبحث غروفر؟ فكّر في مشاكل يصعب إيجاد حلٍّ لها لكن يسهل التحقق منه.