Projected Variational Quantum Extragradient for Zero-Sum Games

إليك ملخص تقني مفصل لورقة البحث بعنوان "Projected Variational Quantum Extragradient for Zero-Sum Games" (خوارزمية التدرج الفائق الكمي المتغير المسقط للألعاب صفريّة المجموع).

1. بيان المشكلة

تتناول الورقة التحدي الحسابي المتمثل في إيجاد توازن ناش (Nash Equilibria - NE) في الألعاب المصفوفية ذات اللاعبين اثنين وصفريّة المجموع ذات النهاية المحدودة. وبينما يمكن للطرق الكلاسيكية (مثل البرمجة الخطية) حل هذه الألعاب بدقة، إلا أنها تصبح غير عملية في الإعدادات واسعة النطاق أو القائمة على "الأوراكل" (Oracle-based). علاوة على ذلك، تتطلب التطبيقات الحديثة غالبًا طرقًا تكرارية قابلة للتوسع تعتمد على المشتقات من الدرجة الأولى.

يقترح المؤلفون نهجًا كميًا متغيرًا (Variational Quantum) لحل هذه الألعاب. يكمن التحدي الجوهري في أن تمثيل الاستراتيجيات المختلطة الكلاسيكية (توزيعات الاحتمالات) باستخدام الدوائر الكمية يحول مشكلة نقطة السرج ثنائية الخطية (Bilinear Saddle-Point) الأصلية (وهي مسألة محدبة-مقعرة) إلى مسألة تحسين (Min-Max) سلسة ولكنها بشكل عام غير محدبة-غير مقعرة في فضاء معاملات الدائرة. بالإضافة إلى ذلك، تتطلب قيود الأجهزة الكمية (عدد الكيوبتات) رسم خرائط لأبعاد اللعبة $(m, n)$ التعسفية إلى أبعاد قوى العدد اثنين دون تشويه هيكل التوازن.

2. المنهجية

يتكون الإطار المقترح، Projected Variational Quantum Extragradient (VQEG)، من أربعة مكونات تقنية رئيسية:

أ. التضمين المهيمن المحافظ على التوازن (Equilibrium-Preserving Dominated Embedding)

للتعامل مع أحجام الألعاب $(m, n)$ التعسفية على الأجهزة الكمية (التي تتطلب أن تكون الأبعاد $M, N$ قوى للعدد 2، أي $2^q$)، قدم المؤلفون تضمينًا مهيمنًا:

• يتم تضمين مصفوفة العوائد الأصلية $A \in \mathbb{R}^{m \times n}$ في مصفوفة أكبر $\tilde{A} \in \mathbb{R}^{M \times N}$ حيث $M=2^{\lceil \log_2 m \rceil}$ و $N=2^{\lceil \log_2 n \rceil}$.
• الآلية: يتم إضافة "أفعال وهمية" (Dummy actions) إضافية. بالنسبة لأفعال لاعب الصف $i > m$، يتم ضبط العائد على $-C$ (حيث $C > \|A\|_\infty$)؛ وبالنسبة لأفعال لاعب العمود $j > n$، يتم ضبطه على $+C$.
• النتيجة: هذه الأفعال الوهمية هي أفعال مهيمنة تمامًا. يثبت البرهان النظري أنه في أي توازن ناش للعبة المضمنة، يكون احتمال لعب الفعل الوهمي صفرًا. وبالتالي، فإن توازن اللعبة المضمنة يعود بدقة إلى اللعبة الأصلية.

ب. المعلمة الكمية المتغيرة (Variational Quantum Parameterization)

يتم تمثيل الاستراتيجيات المختلطة باستخدام دوائر كمية معلمة (Parameterized Quantum Circuits - PQCs):

• التمثيل: يتم تمثيل استراتيجية كل لاعب كـ "توزيع بورن" (Born distribution) ناتج عن دائرة موحدة (Unitary circuit) ($U_\theta$ للاعب الصف، و $V_\phi$ للاعب العمود) تعمل على الحالة $|0\rangle$.
• النموذج (Ansatz): يُستخدم نموذج فعال من حيث الأجهزة، يتكون من طبقات متبادلة من دورات الكيوبت الواحد ($R_y, R_z$) وبوابات التشابك (Entangling gates) من نوع الجار الأقرب ($CZ$).
• دالة الهدف: يتم إعادة التعبير عن العائد ثنائي الخطي الكلاسيكي $f(x, y) = x^T A y$ كقيمة توقع لمؤثر قطري:
  $$L(\theta, \phi) = \text{Tr}(\rho_\theta D(y_\phi)) = \langle x_\theta, \tilde{A} y_\phi \rangle$$
  هذا يحول اللعبة إلى مسألة (Min-Max) معلمية: $\max_\theta \min_\phi L(\theta, \phi)$.

ج. تقدير التدرج عبر قاعدة إزاحة المعلمة (Parameter-Shift Rule)

بما أن الدالة غير قابلة للاشتقاق بالمعنى الكلاسيكي فيما يتعلق بالقياسات الكمية، يتم تقدير التدرجات باستخدام قاعدة إزاحة المعلمة:

• تُحسب المشتقة الجزئية بالنسبة للمعلمة $\theta_k$ كالتالي:
  $$\frac{\partial L}{\partial \theta_k} = \frac{1}{2} \left( L(\theta_k^+, \phi) - L(\theta_k^-, \phi) \right)$$
  حيث $\theta_k^\pm = \theta_k \pm \frac{\pi}{2}$.
• التقدير القائم على عدد الضربات (Shot-Based Estimation): يتم تقدير قيم التوقع باستخدام عدد $S$ من ضربات القياس (Measurement shots). أثبت المؤلفون أن مُقدّر التدرج الناتج هو غير منحاز وأن التباين يتناسب مع $O(1/S)$.

د. خوارزمية التدرج الفائق المسقط (Projected Extragradient Algorithm)

لحل مسألة نقطة السرج غير المحدبة-غير المقعرة، يستخدم المؤلفون طريقة التدرج الفائق المسقط (Projected Extragradient):

1. خطوة المتنبئ (Predictor Step): حساب تحديث مؤقت باستخدام تقدير التدرج العشوائي الحالي $\hat{G}(\omega_t)$.
2. خطوة المصحح (Corrector Step): تقييم التدرج عند نقطة المتنبئ وإجراء التحديث النهائي.
3. الإسقاط (Projection): يتم إسقاط كلتا الخطوتين على مجموعة محدبة مقيدة $W$ لضمان الاستقرار.
4. الخوارزمية: تتكرر العملية حتى التقارب، مما ينتج عنه معاملات الدائرة التي تحدد الاستراتيجيات.

3. المساهمات الرئيسية

1. الصياغة الكمية المتغيرة: تقديم طريقة لتمثيل الاستراتيجيات المختلطة عبر توزيعات "بورن" المستحثة بواسطة PQC، مما يحول مسألة مصفوفة اللعبة إلى مسألة تحسين (Min-Max) معلمية.
2. التضمين المهيمن: تطوير تقنية تضمين مبتكرة تقوم برسم خرائط لألعاب $(m, n)$ التعسفية إلى أبعاد متوافقة مع الكيوبتات مع ضمان رياضي بأن هيكل التوازن سيظل محفوظًا (الأفعال الوهمية تتلقى احتمالية صفرية).
3. خوارزمية VQEG: اقتراح خوارزمية تدرج فائق محددة مصممة للأجهزة الكمية، تستخدم تدرجات إزاحة المعلمة وتتعامل مع ضجيج الضربات (Shot noise).
4. تحليل التقارب: إثبات التقارب إلى الاستقرار التقريبي من الدرجة الأولى في فضاء المعلمات تحت افتراضات السلاسة والتباين المحدود القياسية. يثبت التحليل أن تباين مُقدّر التدرج يتناسب مع $O(1/S)$.
5. شهادة التوازن: الإقرار بأن الاستقرار في فضاء المعلمات لا يضمن بالضرورة وجود توازن ناش في فضاء اللعبة الأصلي. لذلك، يقيم المؤلفون الأداء باستخدام فجوة ناش (Nash Gap) (فجوة الثنائية) كشهادة تجريبية على المثالية.

4. النتائج العددية

قام المؤلفون بتقييم VQEG على ألعاب مهيكلة وغير مهيكلة بأحجام تصل إلى $32 \times 32$:

• الحالات المهيكلة (Dominant-Row & Matching Pennies):
  • حققت VQEG حلولاً عالية الدقة حيث تقترب فجوات ناش غالبًا من الدقة العددية ($10^{-10}$ إلى $10^{-16}$).
  • أظهرت الخوارزمية تقاربًا مستقرًا لآخر تكرار (الاستراتيجية النهائية قريبة من التوازن، وليس فقط المتوسط).
  • كان "التسرب" (Leakage) إلى الأفعال الوهمية ضئيلاً للغاية ($\approx 10^{-16}$)، مما يؤكد صحة التضمين.
• الحالات غير المهيكلة (الألعاب العشوائية):
  • كان الأداء متباينًا. بينما حققت VQEG غالبًا معيار $\epsilon$-equilibrium (حيث $\epsilon = 5 \times 10^{-3}$)، كانت فجوات ناش أكبر مقارًا بالألعاب المهيكلة.
  • تدهور الأداء مع زيادة حجم المشكلة، مما يسلط الضوء على التحديات المتعلقة بالتعبيرية الدائرية (Circuit expressivity) والضجيج العشوائي في البيئات غير المهيكلة.
• المقارنة: تفوقت الطريقة على المتغيرات التي تعتمد على تنظيم الإنتروبيا (Entropy-regularized variants) في المقاييس الأكبر، وحافظت على الاستقرار في حين تدهورت الطرق الأخرى.

5. الأهمية

• الربط بين نظرية الألعاب والحوسبة الكمية: يوفر هذا العمل إطارًا صارمًا لتطبيق الأجهزة الكمية القريبة من العصر الحالي (NISQ) على مشكلات نظرية الألعاب الكلاسيكية، متجاوزًا مجرد الأمثلة البسيطة إلى الألعاب المصفوفية المهيكلة.
• التعامل مع عدم التحدب: تعالج الورقة عدم التحدب المتأصل الناتج عن المعلمة الكمية، مقدمةً خوارزمية تحسين مستقرة (Extragradient) مكيفة خصيصًا للتدرجات الكمية.
• القابلية للتوسع: تحل تقنية التضمين المهيمن المشكلة الحرجة المتمثلة في رسم خرائط أحجام المشكلات التعسفية إلى قيود الأجهزة الكمية دون تغيير حل اللعبة.
• التحقق العملي: من خلال استخدام فجوة ناش كمقياس، تتجاوز الورقة مجرد التقارب النظري في فضاء المعلمات إلى التحقق العملي من جودة التوازن، مما يثبت أن الطرق الكمية المتغيرة يمكن أن تحقق دقة عالية في المشكلات المهيكلة حتى حجم $32 \times 32$.

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