Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives

إليك ملخص تقني مفصل للورقة البحثية بعنوان "رفع كفاءة البرامج الخطية شبه المحددة التباينية للنماذج متعددة الحدود" (Elevating Variational Quantum Semidefinite Programs for Polynomial Objectives).

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

تعتبر العديد من مشكلات التحسين ذات الصعوبة الحسابية (NP-hard) المهمة عملياً (مثل Max-kSAT، وpolynomial knapsack، وk-local Ising models) في جوهرها تحسينات متعددة الحدود من درجات عليا (درجة $k > 2$).

• القيود الكلاسيكية: تتعامل النهج الكلاسيكية القياسية، مثل تسلسلات "مجموع المربعات" (Sum-of-Squares - SOS)، مع هذه المشكلات عبر تحويلها إلى صيغة تربيعية. ومع ذلك، فإن عملية "الرفع" (lifting) هذه إلى بديل تربيعي تؤدي إلى تضخم حجم المشكلة بشكل كبير (يزداد عدد المتغيرات والقيود بشكل أسّي أو غير ملائم مع درجة متعدد الحدود)، مما يؤدي إلى تدهور أداء التقريب ويجعل المشكلات واسعة النطاق غير قابلة للحل.
• القيود الكمومية: على الرغم من اقتراح البرامج الخطية شبه المحددة الكمومية التباينية (vQSDPs) لحل الأهداف التربيعية على الأجهزة الكمومية المتاحة حالياً، إلا أنها تقتصر حالياً على المشكلات من الدرجة الثانية (التربيعية). تتطلب حلول الـ QSDP الكمومية دوائر عميقة وهي غير مناسبة للأجهزة الكمومية ذات المقياس المتوسط والمشوبة بالضجيج (NISQ).

التحدي الجوهري: كيف يمكن توسيع نطاق الـ vQSDPs للتعامل مع أهداف متعددة الحدود من الدرجة $k$ بشكل أصيل دون الانفجار في الموارد الأسّي المعتاد في التخفيفات الكلاسيكية.

2. المنهجية: الرفع بحالة الضرب (Product-State Lifting - PSL)

قدم المؤلفون الرفع بحالة الضرب (PSL)، وهو مخطط ترميز مبتكر يعمل على ترقية أي vQSDP قائم على حالات الأساس لحل مشكلات تحسين متعددة الحدود من الدرجة $k$.

المكونات التقنية الرئيسية:

• التحويل إلى درجة زوجية: يمكن تحويل أي هدف متعدد الحدود إلى متعدد حدود ذي درجة زوجية (درجة $2D$) عن طريق إدخال متغير وهمي (مشابه لـ $y_0$ في صياغات Max-kSAT). يسمح هذا للأسلوب بالتركيز على الحدود أحادية الحد ذات الدرجة الزوجية.
• ترميز الضرب التنسوري: بدلاً من توسيع القاعدة أو إضافة قيود جديدة، يقوم PSL بتمثيل حد من الدرجة $2d$ عبر إعداد $d$ من النسخ المتطابقة من نفس الحالة الكمومية $n$-qubit $\rho = |\psi\rangle\langle\psi|$.
  • رياضياً، يتم ترميز حد من الدرجة $2d$ في حالة الضرب التنسوري $\rho^{\otimes d}$.
  • على سبيل المثال، يتم تمثيل حد من الدرجة 4 ($y_i y_j y_q y_l$) من خلال القيمة المتوقعة فوق $\rho \otimes \rho$.
• الاتساق الجبري: على عكس SOS الكلاسيكية، التي تتطلب قيوداً إضافية لفرض الاتساق اللحظي (على سبيل المثال، ضمان أن $E[y_i y_j] = E[y_i]E[y_j]$ عند الاقتضاء)، فإن PSL يفرض الاتساق الجبري بشكل متأصل. بما أن كل سجل هو نسخة متطابقة من الحالة الأساسية $\rho$، فإن البنية الضربية مضمونة بالبناء.
• توسع الموارد:
  • الكيوبتات (Qubits): يتطلب $O(nk)$كيوبت (زيادة خطية مع الدرجة$k$).
  • القيود: يظل عدد القيود ثابتاً بغض النظر عن درجة متعدد الحدود. تعمل آلية القيود (سلاسل Pauli ووحدات موازنة التعداد) المستخدمة للحالة التربيعية مباشرة على الحالة المرفوعة دون تعديل.
  • القياسات: يتطلب $O(k)$ من اختبارات هادامارد لتقييم دالة الهدف.

سير العمل الخوارزمي:

1. الترميز: يتم تعيين المشكلة إلى متعدد حدود من الدرجة $2D$.
2. إعداد الحالة: تقوم دائرة تباينية $U_V$ بإعداد حالة $n$-qubit $|\psi\rangle$.
3. تقييم الهدف:
   • للحدود من الدرجة $2d$، يتم إعداد $d$ من النسخ لـ $|\psi\rangle$.
   • يتم إجراء اختبار هادامارد على النظام المدمج ($nd$كيوبت) باستخدام وحدة$U_W = e^{i\alpha W}$لتقدير القيمة المتوقعة$\text{Im}(\langle \psi|^{\otimes d} U_W |\psi\rangle^{\otimes d})$.
4. التحسين: يتم تقليل دالة الخسارة (الهدف + حدود الجزاء للقيود) تباينياً.
5. استخراج الحل:
   • كفاءة العينة (SE): يقدر مباشرة الحل غير المستدير من القيم المتوقعة.
   • توموجرافيا الحالة (ST): يعيد بناء مصفوفة الكثافة $\rho$ لاستخراج حل قابل للتقريب (على سبيل المثال، $y_i = \text{sign}(\psi_i)$).

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

1. إطار عمل PSL: طريقة عامة وصديقة للأجهزة لرفع قدرات vQSDPs من الدرجة التربيعية إلى درجات متعددة الحدود عشوائية مع نمو خطي فقط في الموارد.
2. التعامل الأصيل مع متعدد الحدود: يلغي الحاجة إلى "النماذج التربيعية البديلة" الكلاسيكية التي تضخم حجم المشكلة، مما يحافظ على البنية الأصلية للأهداف متعددة الحدود.
3. كفاءة القيود: يوضح أن الاتساق الجبري يتم الحفاظ عليه من خلال بنية الضرب التنسوري، مما يلغي الحاجة إلى تسلسلات القيود المعقدة المطلوبة في SOS.
4. التطبيق على Max-kSAT: تم تطبيق إطار العمل بنجاح على Max-3SAT (وتعميمه إلى Max-kSAT)، وهو معيار قياسي للتحسينات ذات الرتب العليا.

4. النتائج

أجرى المؤلفون محاكاة كلاسيكية للحلقة التباينية لنماذج Max-3SAT (تصل إلى 110 متغيراً و1500 بند).

• المقارنة مع SOS الكلاسيكية (المشكلات الصغيرة):
  • بالنسبة للمشكلات التي تحتوي على 20 متغيراً، حقق النهج القائم على PSL باستمرار حلولاً مستديرة تساوي أو تتفوق على حلول SOS الكلاسيكية.
  • والأهم من ذلك، لم يعانِ PSL من "تدهور التقريب" الذي يُلاحظ غالباً في SOS، حيث تتسع فجوة التقريب بشكل كبير بعد عملية التقريب (rounding).
• المقارنة مع الخوارزميات الاستدلالية الكلاسيكية (المشكلات الكبيرة):
  • بالنسبة للنماذج الأكبر (70-110 متغيراً)، حيث تصبح SOS غير قابلة للحل، تمت مقارنة نهج PSL مع أفضل حلول MaxSAT الاستدلالية المعروفة.
  • حقق نهج PSL حلولاً ضمن ~98-99% من أفضل النتائج الاستدلالية المعروفة.
  • رغم تأخر PSL قليلاً عن الحلول الاستدلالية المتخصصة في الدرجة الخام، إلا أن طريقة PSL توفر ضماناً نظرياً وإطار عمل قابلاً للتعميم، بينما غالباً ما تكون الحلول الاستدلالية مرتبطة بمشكلات محددة.
• القابلية للتوسع: أكدت المحاككات أن النهج قابل للتنفيذ للمشكلات التي تفشل فيها SOS الكلاسيكية، وأن الحلول غير المستديرة أظهرت ارتباطاً قوياً مع دالة الخسارة.

5. الأهمية والتوجهات المستقبلية

• سد الفجوة: يوفر PSL مساراً عاماً من التحسين التربيعي إلى التحسين متعدد الحدود على الأجهزة الكمومية القريبة من المدى دون انفجار القيود المعتاد في التخفيفات الكلاسيكية.
• الخوارزميات المستوحاة من الكم: يشير المؤلفون إلى أن إطار عمل PSL، حتى عند محاكاته كلاسيكياً، يعمل كخوارزمية "مستوحاة من الكم" قوية. فهو يقدم نموذجاً جديداً للتحسين الكلاسيكي يتجنب مشكلات نقص الرتبة (rank-deficiency) الموجودة في تخفيفات SDP القياسية (بما أن الحل يكون دائماً حالة نقية، أي رتبة-1).
• العمومية: لا تقتصر الطريقة على Max-kSAT؛ بل يمكن تطبيقها على أي مشكلة تحسين متعددة الحدود، بما في ذلك تلك التي تعمل على متغيرات مستمرة (مثل الكيمياء الكمومية أو طرق مصفوفة الكثافة المختزلة).
• العمل المستقبلي: يقترح المؤلفون صياغة ضمانات التقارب للملاحظات المرفوعة، واختبارها على مجموعات معايير أكثر صعوبة، وتطوير متغيرات مستوحاة من الكم تتجاوز الحاجة إلى الأجهزة الكمومية مع الاحتفاظ بالمزايا الهيكلية لـ PSL.

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