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

مسألة القطع الأعظمي Max-Cut

Maximum Cut (Max-Cut)

مسألة القطع الأعظمي (Max-Cut) تطلب تقسيم عقد رسم إلى مجموعتين بحيث يُعظَّم مجموع أوزان الأضلاع بينهما؛ وهي NP-صعبة، ولها خوارزمية تقريبية كلاسيكية بنسبة $\approx0.878$.

Max-Cut asks for a partition of a graph's vertices into two sets that maximizes the total weight of edges between them; it is NP-hard and has a classical approximation algorithm with ratio $\approx0.878$.

لرسم $G=(V,E)$ بأوزان $w_{ij}\ge0$، القطع (Cut) تقسيم للعقد إلى مجموعتين، نرمّزه بسلسلة بتات $x\in\{0,1\}^n$ أو لفّات $z_i=1-2x_i$. قيمة القطع مجموع أوزان الأضلاع التي تقع أطرافها في مجموعتين مختلفتين: $$C(z)=\sum_{(i,j)\in E}w_{ij}\frac{1-z_iz_j}{2}.$$ ومسألة القطع الأعظمي (Max-Cut) هي إيجاد $\max_zC(z)$. صيغتها الكمّية الهاملتوني القطري $H_C=\sum w_{ij}(1-Z_iZ_j)/2$، وهي الهدف المعياري لـ QAOA.

تعقيد المسألة: صيغة القرار لـ Max-Cut (هل يوجد قطع بقيمة لا تقل عن $k$؟) NP-كاملة، فالمسألة NP-صعبة، ولا تُعرف خوارزمية دقيقة متعددة الحدود. لكن لها خوارزميات تقريبية جيدة. التقسيم العشوائي يعطي في المتوسط نصف مجموع الأوزان، أي نسبة تقريب $0.5$. وقدّم غومانس وويليامسون (1995) خوارزمية تعتمد على البرمجة شبه المحددة (Semidefinite Programming) والتقريب بمستوى فائق عشوائي، تضمن قطعًا متوقعًا لا يقل عن $\alpha\approx0.878$ من الأمثل. ومن المعروف في نظرية التعقيد أنه، بافتراض حدسية الألعاب الفريدة (Unique Games Conjecture)، لا يمكن لخوارزمية متعددة الحدود أن تضمن نسبة أفضل.

هذه الأرقام تضع نتائج QAOA في سياقها: ضمان QAOA بعمق $p=1$ على الرسوم 3-المنتظمة هو $0.6924$، أقل من ضمان غومانس–ويليامسون. لذا فتشغيل QAOA على رسم صغير والحصول على القطع الأعظمي لا يعني أفضلية، فالحصر الشامل يحل هذه الرسوم فورًا.

اصطلاح مهم في المختبر: السلاسل تُعرض بترتيب $q_{n-1}\dots q_0$، والكيوبت $i$ يمثل العقدة $i$. والقطع متناظر: قلب كل البتات، مثل $0101\leftrightarrow1010$، يعطي القطع نفسه، فكل حل أمثل يظهر مرتين على الأقل في توزيع القياس.

رسوم المختبر الجاهزة: المثلث، والمربع (حلقة من 4)، و«البيت»، والحلقة من 6، والرسم التام $K_4$، ورسم موزون من 5 عقد، والمنشور. وكل منها صغير بما يكفي لحساب القطع الأعظمي بدقة ومقارنته بنتيجة QAOA.

ولتطبيقات Max-Cut أمثلة عملية في تصميم الدارات الإلكترونية (تقليل الوصلات بين طبقتين) وفي الفيزياء الإحصائية (الحالات الأساسية لزجاج اللف)، وهو ما يجعلها مسألة اختبار مرجعية للخوارزميات الكمّية والكلاسيكية معًا.

الصيغة الرياضية

$$C(z)=\sum_{(i,j)\in E}w_{ij}\,\frac{1-z_iz_j}{2},\qquad z_i\in\{+1,-1\}$$

مثال محلول

  1. المربع (حلقة 4 عقد، أضلاع $0\!-\!1,1\!-\!2,2\!-\!3,3\!-\!0$، أوزان 1): السلسلة 0101 (أي $q_3=0,q_2=1,q_1=0,q_0=1$) تضع العقد المتجاورة في مجموعتين مختلفتين دائمًا، فكل الأضلاع الأربعة مقطوعة و $C=4=C_{\max}$. وكذلك 1010.
  1. المثلث: أي تقسيم يقطع ضلعين على الأكثر، لأن ثلاث عقد لا يمكن أن تتعاكس كلها مثنى مثنى، فـ $C_{\max}=2$. القطع العشوائي يعطي في المتوسط $3\times0.5=1.5$.
  1. $K_4$: تقسيم 2–2 يقطع $2\times2=4$ أضلاع من 6، وتقسيم 1–3 يقطع 3، فـ $C_{\max}=4$.

اختبر فهمك

يحتاج الاختبار إلى JavaScript.

موضوعات مرتبطة

المراجع

  1. Michel X. Goemans; David P. Williamson (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM 42(6):1115–1145 doi:10.1145/227683.227684
  2. Edward Farhi; Jeffrey Goldstone; Sam Gutmann (2014). A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 doi:10.48550/arXiv.1411.4028
  3. Andrew Lucas (2014). Ising formulations of many NP problems. Frontiers in Physics 2:5 doi:10.3389/fphy.2014.00005