QAOA على نطاق الأداة

شاهد الفيديو حول QAOA على نطاق الأداة مع أوليفيا لينز، أو افتح الفيديو في نافذة منفصلة على يوتيوب.

نظرة عامة على الدرس

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

في هذا الدرس، سنتعمق في مثال على نطاق الأداة لمسألة Max-Cut، وهي مسألة شهيرة في نظرية الرسوم البيانية تتعلق بأفضل طريقة لتقسيم رسم بياني إلى قسمَين. سنبدأ برسم بياني بسيط من خمس عقد لبناء حدسنا حول كيفية مساعدة الحاسوب الكمي في حل المسألة، ثم نطبّق هذا على نسخة من المسألة على نطاق الأداة.

سيكون هذا الدرس نظرة عامة واسعة على النهج الذي نتبعه لحل هذه المسألة. لن يكون شرحاً للكود خطوة بخطوة. ولكن هناك درس تطبيقي مرفق يحتوي على كود فعلي يمكنك تشغيله لحل مسألة Max-Cut على حاسوب كمي.

المسألة

للتذكير، لا تُعدّ جميع المسائل الحسابية مناسبة للحوسبة الكمية. "المسائل السهلة" لن تستفيد من هذه التقنية لأن الحواسيب الكلاسيكية ممتازة بالفعل في حلها.

حالات الاستخدام الثلاث التي نتفاءل أكثر باستكشافها هي:

1. محاكاة الطبيعة
2. معالجة البيانات ذات البنية المعقدة
3. التحسين

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

مسألة التحسين التي تهمنا اليوم تُسمى Max-Cut، وسنحلّها باستخدام خوارزمية تُعرف بخوارزمية التحسين الكمي التقريبي (QAOA).

ما هي Max-Cut؟

نبدأ برسم بياني يتكوّن من مجموعة من الرؤوس (أو العقد)، يتصل بعضها بحوافّ. في المسألة، يُطلب منا تقسيم عقد الرسم البياني إلى مجموعتَين فرعيتَين بـ"قطع" الحوافّ التي تربطهما. نريد إيجاد التقسيم الذي يُعظّم عدد الحوافّ المقطوعة بهذه الطريقة — ومن هنا جاء الاسم "Max-Cut".

على سبيل المثال، الشكل أعلاه يُظهر رسماً بيانياً من خمس عقد مع حل Max-Cut على اليمين. يقطع خمس حوافّ، وهو أفضل ما يمكن تحقيقه مع هذا الرسم البياني.

نظراً لصغر رسم بياني من خمس عقد، ليس من الصعب جداً تحديد Max-Cut ذهنياً أو بتجربة بعض القطوعات على ورقة. لكن كما تتخيل، تصبح المسألة أصعب وأصعب كلما زاد عدد الرؤوس — جزئياً لأن عدد القطوعات المحتملة التي يجب مراعاتها يزداد بشكل أسّي بزيادة عدد العقد. وعند نقطة معينة، يصبح هذا صعباً حتى بالنسبة للحواسيب العملاقة مع أي خوارزمية كلاسيكية معروفة.

نريد طريقة لحل مسألة Max-Cut لهذه الرسوم البيانية الأكبر والأكثر تعقيداً، لأن المسألة لها تطبيقات عملية كثيرة، بما فيها اكتشاف الاحتيال في التمويل، وتجميع الرسوم البيانية، وتصميم الشبكات، وتحليل وسائل التواصل الاجتماعي. كثيراً ما تظهر Max-Cut كمسألة فرعية ضمن نهج معيّن لمسألة أكبر. لذا فهي أكثر شيوعاً مما قد نتصور للوهلة الأولى.

الحل

الآن سنستعرض النهج الذي نتبعه لحل مسألة Max-Cut على حاسوب كمي. سنفعل ذلك برسم بياني بسيط من خمس عقد. يمكنك المتابعة باستخدام درس دفتر Python التطبيقي. بعد ذلك المثال البسيط، سيرشدك الدرس التطبيقي خلال مثال على نطاق الأداة للمسألة.

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

سنستخدم إطار أنماط Qiskit لإيجاد حلول Max-Cut لهذا الرسم البياني على حاسوبنا الكمي.

التخطيط

نحتاج إلى تخطيط المسألة على حاسوبنا الكمي. للقيام بذلك، لنلاحظ أولاً أن تعظيم عدد القطوعات في رسم بياني يمكن كتابته رياضياً كـ:

$$\max\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {x_i + x_j - 2x_ix_j}$$

حيث $i$ و$j$ هما عقدتان في الرسم البياني، و$x_i$ و$x_j$ إما 0 أو 1 بحسب أي جانب من التقسيم توجد فيه كل عقدة (إحدى المجموعتَين مُسمّاة بـ"0" والأخرى بـ"1"). عندما يكون $x_i$ و$x_j$ على الجانب ذاته من التقسيم، يساوي التعبير في المجموع صفراً. أما عند وجودهما على الجانبَين المختلفَين، أي عند وجود قطع بينهما، يساوي التعبير واحداً. وهكذا يُعظّم تعظيم عدد القطوعات المجموع.

يمكننا أيضاً قلب المسألة والبحث عن الحد الأدنى بضرب كل قيمة في السالب.

$$\min\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {2x_ix_j - x_i - x_j}$$

الآن أصبحنا مستعدّين للتخطيط. قد يبدو مرهباً التفكير في كيفية الانتقال من رسم بياني كالذي رسمناه للتو إلى دائرة كمية. لكننا سنفعل ذلك خطوةً خطوة.

تذكّر أننا سنحاول حل Max-Cut باستخدام QAOA. في منهجية QAOA، نريد في نهاية المطاف الحصول على مشغّل (أو بعبارة أخرى هاميلتوني) يُستخدم لتمثيل دالة التكلفة لخوارزميتنا الهجينة، إضافةً إلى دائرة مُعاملة (ansatz) نستخدمها لتمثيل الحلول المحتملة للمسألة.

QUBO

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

$$\min\limits_{x\in\{0,1\}^n} x^TQx$$

حيث $Q$ مصفوفة $n\times n$ من الأعداد الحقيقية، ويقابل $n$ عدد العقد في رسمنا البياني، وهو خمسة هنا.

لتطبيق QAOA، نحتاج إلى صياغة مسألتنا كهاميلتوني — وهو دالة أو مصفوفة تمثّل إجمالي طاقة النظام. تحديداً، نريد إنشاء هاميلتوني دالة تكلفة بالخاصية التي تكون فيها حالته الأرضية مقابلةً للقيمة الدنيا للدالة. لذا، لحل مسألة التحسين لدينا، سنحاول تحضير الحالة الأرضية لـ$H$ على حاسوب كمي. ثم يُسفر أخذ العينات من هذه الحالة عن حل $\min 𝑓(𝑥)$ باحتمالية عالية.

التخطيط إلى هاميلتوني دالة تكلفة

كما اتضح، نحن محظوظون، لأن مسألة QUBO وثيقة الصلة جداً بل هي مكافئة حسابياً لأحد أشهر الهاميلتونيَّات في الفيزياء وأكثرها شيوعاً: هاميلتوني إيزينج.

لكتابة مسألة QUBO كهاميلتوني إيزينج، كل ما نحتاجه هو إجراء تغيير بسيط في المتغيرات:

$$x_i = \frac{1-z_i}{2}.$$

لن نتتبع جميع الخطوات هنا، لكنها موضّحة في الدفتر المرفق. في النهاية، تصغير تعبير QUBO يعادل تصغير هذا التعبير:

$$\min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz$$

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

$$H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_i Z_i$$

الآن بعد أن حصلنا على هاميلتونينا، نحتاج إلى إعادة كتابته بدلالة مشغّلات باولي ZZ ثنائية المحلية، التي يمكننا تحويلها بسهولة إلى بوابات ثنائية الكيوبت في دائرتنا الكمية. سنحصل في النهاية على ستة كائنات — أو سلاسل باولي — كل منها يقابل إحدى الحوافّ الستة في الرسم البياني. كل عنصر من العناصر الخمسة في السلسلة يمثّل عملية على عقدة — الوحدة إذا لم تكن العقدة متصلة بتلك الحافة، ومشغّل باولي Z إذا كانت. في Qiskit، تُفهرَس سلاسل البت التي تمثّل الكيوبتات بشكل معكوس. على سبيل المثال، حافة بين العقدتَين 0 و1 تُرمَّز كـIIIZZ، وحافة بين العقدتَين 2 و4 تُرمَّز كـZIZII.

بناء الدائرة الكمية

بكتابة هاميلتونينا بدلالة مشغّلات باولي، أصبحنا مستعدّين لبناء دائرتنا الكمية التي تتيح لنا أخذ عينات من حلول جيدة باستخدام حاسوب كمي:

تستوحي خوارزمية QAOA من المبرهنة الأديباتية، التي تنص على أنه إذا بدأنا في الحالة الأرضية لهاميلتوني معتمد على الزمن، وإذا تطور الهاميلتوني ببطء كافٍ، وبمرور وقت كافٍ، فستكون الحالة النهائية هي الحالة الأرضية للهاميلتوني النهائي. يمكن اعتبار QAOA النسخة المنفصلة والمقطّعة (trotterized) من خوارزمية الكم الأديباتية، حيث تمثّل كل خطوة ترويتر طبقةً من خوارزمية QAOA. بدلاً من التطور من حالة إلى أخرى، في كل طبقة سنتبادل بين هاميلتوني دالة التكلفة وما يُسمى الهاميلتوني "الخلّاط"، الذي سنتناوله لاحقاً في هذا الدرس.

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

لإنشاء دائرتنا الكمية، سنطبّق مشغّلَين متناوبَين مُعاملَين بـ$\gamma$ و$\beta$، يمثّلان تقطيع تطور الزمن.

الأجزاء الثلاثة الرئيسية لدائرة QAOA هي:

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

هاميلتونينا الابتدائي يُسمى الخلّاط لأن حالته الأرضية هي التراكب لجميع سلاسل البت الممكنة المعنية: ومن ثَمّ فرض خليط من جميع الحلول الممكنة في البداية.

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

كل تكرار لهذه المشغّلَين يُسمى طبقة. يمكن النظر إلى هذه الطبقات كتقطيع لتطور الزمن للنظام، كما وُصف سابقاً. يأتي النمط المتناوب من تحليل ترويتر ويقرّب الدوال الأسية للمصفوفات غير المتبادلة. بشكل عام، كلما أضفنا طبقات أو خطوات أكثر، كلما اقتربنا من تطور الزمن المستمر كما في QAA، وبالتالي نظرياً كلما كانت النتيجة أدق. لكن في هذا المثال سنبدأ بأخذ عينات بطبقة واحدة فقط. تذكّر أن كلاً من هاميلتوني دالة التكلفة والخلّاط مُعاملان، ولا نزال بحاجة إلى التوصل إلى القيم المثلى لـ$\gamma$ و$\beta$.

التحسين

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

تقدّم مكتبة Qiskit سلسلة من خطوات التحويل التي تلبّي مجموعة واسعة من تحويلات الدائرة. نريد التأكد من أن الدائرة محسَّنة لأغراضنا.

تذكّر من درسنا السابق أن عملية التحويل تتضمن عدة خطوات:

• التعيين الأولي للكيوبتات في الدائرة (أي متغيرات القرار) على الكيوبتات المادية على الجهاز.
• نشر التعليمات في الدائرة الكمية إلى التعليمات الأصيلة للعتاد التي تفهمها الخلفية.
• توجيه أي كيوبتَين تتفاعلان في الدائرة إلى كيوبتَين مجاورتَين ماديتَين.

وكالعادة، يمكن العثور على مزيد من التفاصيل حول هذا في الوثائق.

لكن قبل التحويل، نحتاج إلى اختيار الخلفية التي ستشغّل دائرتنا عليها، إذ يُحسّن المحوّل بشكل مختلف لمعالجات مختلفة. هذا سبب آخر لأهمية استخدام محوّل آلي — لن تريد المرور بعملية تحسين دائرتك يدوياً المستهلِكة للوقت، لتكتشف بعدها أنك تريد فعلاً تشغيل دائرتك على معالج مختلف بخصائص مختلفة.

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

وبذلك، يكون لدينا دائرة محوَّلة جاهزة للتنفيذ على العتاد!

التنفيذ

حتى الآن، قمنا بتحويل الدائرة تاركَين المعاملات gamma وbeta كما هي — لكن لا يمكننا فعلياً تشغيل الدائرة دون تحديد هذه المعاملات. في سير عمل QAOA، تُوجَد معاملات QAOA المثلى في حلقة تحسين تكرارية، حيث نُجري سلسلة من تقييمات الدائرة ثم نستخدم محسِّناً كلاسيكياً لإيجاد المعاملَين المثليَّين 𝛽 و𝛾. لكن نحتاج إلى نقطة بداية، لذا نبدأ بتخمين أولي $\gamma=\pi/2$ و$\beta=\pi$.

أوضاع التنفيذ

الآن أصبحنا شبه مستعدّين لتشغيل الدائرة — أعدك! لكن أولاً، من المهم ملاحظة أنه يمكنك إرسال مهمتك بعدة طرق مختلفة تُسمى أوضاع التنفيذ.

• وضع المهمة: يُقدَّم طلب primitive واحد من المُقدِّر أو أداة الأخذ من العينات دون مدير سياق. تُعبَّأ الدوائر والمدخلات كوحدات primitive موحّدة (PUBs) وتُقدَّم كمهمة تنفيذ على الحاسوب الكمي.

• وضع الدُّفعة: مدير متعدد المهام لتشغيل تجربة بكفاءة مكوّنة من مجموعة من المهام المستقلة. استخدم وضع الدُّفعة لتقديم مهام primitive متعددة في آنٍ واحد.

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

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

بالعودة إلى مسألة التحسين. نحتاج إلى إيجاد قيم أفضل لـgamma وbeta من مجرد تخميناتنا الأولية التقريبية. سنفعل ذلك بإدخال دالة التكلفة وهذه التخمينات الأولية في محسِّن scipy باسم COBYLA.

هنا يمكنك رؤية قيمة دالة التكلفة عبر التكرارات. تبدأ بعدم الاستقرار وترتفع وتنخفض، ثم تستقر عند قيمة منخفضة. سنستخدم القيم التي وجدها scipy والتي تقابل أدنى تقييم لدالة التكلفة.

بعد أن تمكنّا من تخفيض دالة التكلفة بإيجاد قيم أفضل للمعاملات، سنُشغّل دائرتنا باستخدام القيم الجديدة التي وجدناها لـgamma وbeta. ذكرت القيم المحددة التي أستخدمها هنا، لكن تذكّر أنه عند تجربتك بنفسك أو حتى مجرد إعادة تشغيل نفس دفتر الدرس التطبيقي، قد تتغير هذه القيم قليلاً. الآن سنُشغّل دائرتنا المحسَّنة بهذه القيم ونجد الحل المرشح لمسألة Max-Cut.

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

ما بعد المعالجة

لنرسم الآن مخطط تكراري للبيانات للاطلاع على الحل النهائي:

سلاسل البت تمثّل كيفية تقسيم كل عقدة إلى مجموعتَين (مُسمّاتَين "0" و"1") بالقطع. يجب أن تكون هناك أربعة حلول تُعطي الحد الأقصى لعدد الحوافّ المقطوعة. هذه الأربعة موضّحة باللون البنفسجي. يمكنك أن ترى على الفور أن 4 حلول أكثر احتمالاً بكثير من أي من الحلول الأخرى. سلسلة البت الأعلى والأكثر احتمالاً هي 0,1,0,1,1. (تذكّر — ترتيب الكيوبتات معكوس في سلاسل البت الموضّحة في الرسم البياني!)

من هذا الرسم البياني، يمكننا أخذ سلسلة البت الأكثر احتمالاً وتمثيلها كرسم بياني مقسَّم مع قطع يمرّ عبر خمس حوافّ:

هكذا يكون هذا فعلاً حل Max-Cut. لكنه ليس الحل الوحيد! بسبب تماثل هذا الرسم البياني، ثمة حلول صحيحة متعددة. بدلاً من وجود العقدتَين 0 و3 داخل القطع، يمكن أن تكون العقدتان 2 و4 مشمولتَين. يمكنك أن ترى أن كل ما فعلته هو تدوير قطعي لتشمل هذه النقاط الجديدة. يبقى عدد الحوافّ المقطوعة خمسة. اتضح أن هناك أربعة حلول Max-Cut، إذ يمتلك كل حلٍّ من الحلَّين اللذَين لاحظناهما أيضاً "نظيراً معاكساً"، حيث تصبح العقد البنفسجية رمادية والعقد الرمادية بنفسجية — يبقى القطع ذاته، لكن كل عقدة تنتقل فعلياً إلى الجانب الآخر من التقسيم.

لنعد النظر في المخطط التكراري والحلول الأربعة الأكثر احتمالاً للحظة. من الناحية المثلى، ينبغي أن تكون كل واحدة من الحلول الأربعة الصحيحة لـMax-Cut. المشكلة أن الخوارزمية في الواقع لم تُحدد الحل الرابع والأخير بوصفه أحد أعلى أربعة حلول من حيث الاحتمالية. كان خامس الأكثر احتمالاً. الحل الرابع الذي حدّدته الخوارزمية غير صحيح — لو رسمته، سترى أن الحل لا يحتوي إلا على أربع قطوعات.

لكن تذكّر: هذه خوارزمية تقريبية. فهي ليست معصومة من الخطأ ولا صحيحة 100% من الوقت. تحتاج إلى توظيف بعض معرفتك وفهمك للتحقق من صحة الحلول.

يمكن أن ينشأ هذا الخطأ من عدة أماكن:

1. قد يكون الطابع التقريبي للخوارزمية ذاتها، والعدد الصغير من الطبقات التي استخدمتها.
2. قد يكون خطأ أخذ عينات محدود، يمكن تخفيفه بزيادة عدد اللقطات في تجربتي.
3. قد يكون خطأ قراءة، إذ يختلف الحل الصحيح الرابع بمقدار بت واحد فقط.

هذا النوع من تحليل الأخطاء هو ما يلزم لتصبح ممارساً للحوسبة الكمية. تحتاج إلى فهم أداء العتاد وكيف يمكن أن يساهم ذلك في أنواع معينة من الأخطاء وكيفية تصحيحها.

مع ذلك، لا تنسَ أن هناك 32 سلسلة بت ممكنة، وأن الحلول الأربعة الصحيحة مشمولة في أفضل خمسة مرشحين. واستخدمنا طبقتَين فقط لإيجاد هذا. بشكل عام، إذا أردنا زيادة احتمالاتنا في إيجاد أفضل Max-Cut في كل مرة، يمكننا زيادة عمق الطبقات. ثمة بعض الدقائق في هذا، لكن ذلك موضوع لدرس لاحق.

على نطاق الأداة

بعد أن تذوّقت عملية حل مسألة Max-Cut صغيرة على حاسوب كمي، أتحداك تطبيق ذلك على نطاق أوسع. تابع في الدرس التطبيقي المرتبط لترى كم عدد القطوعات التي يمكنك الحصول عليها في رسم بياني من 125 عقدة.