مسألة القطع الأعظمي 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 أمثلة عملية في تصميم الدارات الإلكترونية (تقليل الوصلات بين طبقتين) وفي الفيزياء الإحصائية (الحالات الأساسية لزجاج اللف)، وهو ما يجعلها مسألة اختبار مرجعية للخوارزميات الكمّية والكلاسيكية معًا.
الصيغة الرياضية
مثال محلول
- المربع (حلقة 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.
- المثلث: أي تقسيم يقطع ضلعين على الأكثر، لأن ثلاث عقد لا يمكن أن تتعاكس كلها مثنى مثنى، فـ $C_{\max}=2$. القطع العشوائي يعطي في المتوسط $3\times0.5=1.5$.
- $K_4$: تقسيم 2–2 يقطع $2\times2=4$ أضلاع من 6، وتقسيم 1–3 يقطع 3، فـ $C_{\max}=4$.
اختبر فهمك
يحتاج الاختبار إلى JavaScript.
موضوعات مرتبطة
المراجع
- 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
- Edward Farhi; Jeffrey Goldstone; Sam Gutmann (2014). A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 doi:10.48550/arXiv.1411.4028
- Andrew Lucas (2014). Ising formulations of many NP problems. Frontiers in Physics 2:5 doi:10.3389/fphy.2014.00005
