⚛️ quantum physics

Optimized QUBO formulation methods for quantum computing

تقدم هذه الورقة طرقاً مبتكرة تعتمد على كثيرات الحدود التربيعية التكرارية وطرق "التابع-الأم" لتقليل عدد المتغيرات بشكل جذري في صياغات مسألة التربيع التربيعية (QUBO) المخصصة لأجهزة الحوسبة الكمومية ذات النطاق المتوسط والمحدود (NISQ)، مما يثبت كفاءتها المتفوقة على النهج القياسية في مسألة تسوية توازن الأرباح القصوى (Max-Profit Balance Settlement) وهي مسألة من فئة المسائل الصعبة (NP-hard)، وذلك باستخدام أجهزة داف (D-Wave) للتقليب الكمي.

المؤلفون الأصليون: Dario De Santis, Salvatore Tirone, Stefano Marmi, Vittorio Giovannetti

نُشر 2026-02-25

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Dario De Santis, Salvatore Tirone, Stefano Marmi, Vittorio Giovannetti

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك تحاول حل لغز "بازل" ضخم ومعقد، ولكن هناك عقبة: أنت تحاول حل هذا اللغز على طاولة صغيرة وهشة لا يمكنها تحمل سوى قطع قليلة في كل مرة. إذا حاولت وضع الكثير من القطع بالقوة على الطاولة، سينهار الهيكل بأك-مله ولن تتمكن من رؤية الصورة.

هذا هو الوضع الحالي مع الحواسيب الكمومية (تحديداً أجهزة NISQ التي نمتلكها الآن). هذه الأجهزة قوية، لكنها "مشوشة" ولديها مساحة محدودة جداً (الكيوبتات/Qubits) للعمل بها.

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

إليك تفصيل اكتشافهم، باستخدام تشبيهات بسيطة:

1. المشكلة: حمل زائد من "الفراغ" (Slack)

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

ومع ذلك، فإن مشاكل العالم الحقيقي لها قواعد (قيود). على سبيل المثال: "لا يمكنك إنفاق أكثر مما تملك"، أو "يجب أن تستلم دفعة مالية قبل أن ترسل أخرى".

الطريقة القديمة: لإجبار الحاسوب الكمومي على اتباع هذه القواعد، كان العلماء يستخدمون "قطعاً مساعدة" تسمى متغيرات الفراغ (Slack Variables).
- التشبيه: تخيل أنك تحاول إدخال أريكة كبيرة (القاعدة) في غرفة صغيرة (الحاسوب الكمومي). كانت الطريقة القديمة هي بناء سقالات ضخمة حول الأريكة فقط لتثبيتها في مكانها. كانت هذه السقالات تأخذ مساحة كبيرة لدرجة أن الغرفة امتلأت تماماً، ولم تعد قاد ability على استيعاب الأريكة نفسها.
- النتيجة: بالنسبة للمشاكل المعقدة، أصبحت "السقالات" (متغيرات الفراغ) أكبر بـ 10 مرات من المشكلة الفعلية. وبذلك، ينفد من الحاسوب الكمومي المساحة فوراً.

2. الحل: أداتان جديدتان

ابتكر المؤلفون، داريو دي سانتيس وفريقه، طريقتين لبناء سقالات أصغر وأذكى بك كثيراً. ويطلقون عليهما اسم الحدوديات التربيعية التكرارية (IQP) وطريقة "الرئيس والتابع" (Master-Satellite).

الأداة (أ): "النحات الذكي" (الحدوديات التربيعية التكرارية - IQP)

بدلاً من بناء سقالات ضخمة لكل قاعدة على حدة، تعمل هذه الأداة مثل النحات الذي ينحت القاعدة مباشرة في شكل الأريكة.

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

الأداة (ب): "الرئيس والتابع" (طريقة Master-Satellite)

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

الطريقة القديمة: كنت تعامل كل قاعدة كأنها "رئيس" منفصل وثقيل، يتطلب سقالاته الضخمة الخاصة.
الطريقة الجديدة: تختار قاعدة واحدة لتكون هي "الرئيس" (Master) والأخرى تكون "تابعة" (Satellite).
- يتم فرض قاعدة الرئيس بصرامة على الجميع.
- أما القواعد التابعة، فلا يتم فرضها إلا إذا كان "الرئيس" راضياً بالفعل.
- التشبيه: تخيل حارس أمن عند ملهى ليلي (الرئيس). إذا لم تكن تملك تذكرة، فلن يسمح لك بالدخول، وبالتالي لن يحتاج حارس الأمن حتى للتحقق من هويتك (قاعدة التابع). من خلال إدراك أن قاعدة "التابع" لا تهم إلا بعد اجتياز قاعدة "الرئيس"، فإنك توفر كمية هائلة من عمليات التحقق (متغيرات الفراغ).

3. الاختبار الواقعي: لغز "تحويلات البنوك"

لإثبات نجاح ذلك، طبقوا هذه الطريقة على مشكلة مالية حقيقية تسمى تسوية توازن الأرباح القصوى (MPBS).

السيناريو: تخيل أن بنكاً لديه آلاف الأشخاص الذين يدينون لبعضهم البعض بالمال. الهدف هو إلغاء أكبر قدر ممكن من الديون بحيث ينتهي الأمر بكل شخص بالحصول على المبلغ الصحيح، دون أن يقع أي شخص في العجز المالي.
التحدي: هذه مشكلة من نوع "NP-Hard"، مما يعني أنها صعبة الحل للغاية.
النتيجة:
- باستخدام الطريقة القديمة، كانت "السقالات" ضخمة جداً لدرجة أن الحاسوب الكمومي بالكاد استطاع التعامل مع أمثلة صغيرة.
- باستخدام الطريقة الجديدة، قللوا عدد "القطع المساعدة" المطلوبة بنسبة 90% تقريباً.
- التشبيه: لقد حولوا لغزاً يتطلب طاولة بحجم مستودع إلى لغز يناسب طاولة قهوة.

4. النتيجة: أسرع وأفضل

لقد اختبروا ذلك على نوعين مختلفين من الحواسيب الكمومية (أجهزة D-Wave).

معدل النجاح: عند استخدام "تقنية الطي" الجديدة، وجدت الحواسيب الكمومية الإجابة الصحيحة 7 إلى 184 مرة أكثر مما كانت عليه عند استخدام الطريقة القديمة.
القابلية للتوسع: مع زيادة حجم المشاكل، انهار معدل نجاح الطريقة القديمة ليصل إلى الصفر تقريباً، بينما ظلت الطريقة الجديدة قوية، مما يثبت قدرتها على التعامل مع مشكلات أكبر بكثير من الواقع.

الملخص

هذه الورقة البحثية هي طفرة في الكفاءة. هي لا تجعل الحاسوب الكمومي أسرع من حيث السرعة؛ بل تجعل المشكلة أصغر لكي يتمكن الحاسوب من حلها فعلياً.

قبل: محاولة إدخال حوت في حوض استحمام عن طريق بناء خزان ضخم حوله.
بعد: إدراك أن الحوت يمكنه في الواقع أن يناسب حوض الاستحمام إذا قمت فقط بضغطه في الشكل الصحيح، وإزالة كل المياه غير الضرورية (متغيرات الفراغ).

هذا يسمح لنا باستخدام حواسيبنا الكمومية الحالية، رغم عدم كمالها، لحل مشكلات حقيقية وذات قيمة في مجالات التمويل والخدمات اللوجستية كانت مستحيلة الحل سابقاً.

فيما يلي ملخص تقني مفصل لورقة بحثية بعنوان "طرق صياغة QUBO المحسنة للحوسبة الكمومية" من تأليف دي سانتيس وآخرون.

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

تعالج الورقة البحثية عقبة حرجة في حل مشكلات التحسين التوليفي على أجهزة الحوسبة الكمومية ذات المقياس المتوسط المشوبة بالضجيج (NISQ)، وتحديداً أجهزة التلدين الكمومي (Quantum Annealers).

التحدي: يجب إعادة صياغة العديد من المشكلات الصعبة (NP-hard) (مثل تسوية موازنة الربح الأقصى - Max-Profit Balance Settlement) كمسائل تحسين ثنائي تربيعي غير مقيد (QUBO) لتشغيلها على هذه الأجهزة.
العقبة: تتطلب تقنيات إعادة صياغة QUBO القياسية عدداً كبيراً من متغيرات الفراغ (Slack Variables) لفرض القيود (خاصة قيود عدم المساواة).
- تزيد متغيرات الفراغ من العدد الإجمالي للمتغيرات المنطقية، مما يتطلب المزيد من الكيوبتات (Qubits) الفيزيائية.
- غالباً ما تستلزم هذه المتغيرات اتصالاً عالياً بين المتغيرات، وهو ما يتجاوز الاتصال المحدود في الأجهزة الكمومية الحالية (مثل طوبولوجيا Pegasus أو Zephyr في D-Wave).
- يحد هذا من حجم المشكلات التي يمكن حلها ويقلل من جودة الحل مع زيادة حجم المشكلة.
الهدف: تقليل عدد متغيرات الفراغ المطلوبة لإعادة صياغة QUBO بشكل جذري دون تقريب المشكلة الأصلية أو حل مسائل QUBO تمهيدية، مما يسمح بحل نماذج أكبر من الواقع على أجهزة NISQ.

2. المنهجية

قدم المؤلفون تقنيتين جديدتين ومستقلتين يمكن استخدما بشكل منفصل أو مجتمعين (يُشار إليهما باسم IQPMS):

أ. طريقة متعدد الحدود التربيعي التكراري (IQP)

المفهوم: بدلاً من الطريقة القياسية لتحويل عدم المساواة إلى مساواة عبر مجموع خطي لمتغيرات الفراغ (والتي تتطلب $\lceil \log_2(\text{range}) \rceil$ من المتغيرات)، تقوم طريقة IQP ببناء متعدد حدود تربيعي عام $P(x, s)$ مباشرة.
الآلية:
- تبحث الطريقة عن معاملات لمتعدد حدود تربيعي بحيث يكون $P(x, s) = 0$ عندما تكون القيود مستوفاة، و $P(x, s) \le -1$ عندما يتم انتهاكها.
- تستخدم نهجاً تكرارياً: تبدأ بصفر من متغيرات الفراغ. إذا تعذر إيجاد حل لمعاملات متعدد الحدود (بسبب نقص درجات الحرية)، فإنها تضيف متغير فراغ واحد وتعيد التقييم.
- الرؤية الجوهرية: قيود عدم المساواة أقل تقييداً من قيود المساواة. تستغل الطة ذلك من خلال اشتراط أن يكون $P(x, s) \le -1$ عند الانتهاكات (مما يسمح بقيم جزاء مختلفة لتكوينات الفراغ المختلفة) بدلاً من قيمة ثابتة، مما يسمح غالباً باستيفاء القيد بعدد أقل أو بصفر من متغيرات الفراغ.
القابلية للتطبيق: فعالة بشكل خاص للقيود المعرفة على عدد صغير من المتغيرات الثنائية (مثل قيود العقد المحلية). وهي تعمل مع القيود الخطية وغير الخطية، والمعاملات الصحيحة وغير الصحيحة.

ب. طريقة السيد والتابع (Master-Satellite - MS)

المفهوم: تستغل هذه الطريقة التآزر بين قيود متعددة تشترك في نفس مجموعة المتغيرات الثنائية.
الآلية:
- تُقسم القيود إلى سيد (Master) وتابع (Satellite).
- قيود السيد (Master Constraints): تُفرض لجميع التشكيلات الممكنة من المتغيرات الثنائية.
- قيود التابع (Satellite Constraints): تُفرض فقط للتشكيلات التي تستوفي قيود السيد بالفعل.
- ضبط الجزاء (Penalty Tuning): نظراً لأن قيود التابع لا تُفرض عندما يتم انتهاك قيد السيد، فقد توفر حوافز إيجابية عن طريق الخطأ (تقليل الجزاء) للحالات غير الصالحة. يقدم المؤلفون مضاعفاً نسبياً ( $\lambda_{MC} > 1$ ) لقيد السيد لتضخيم جزائه، مما يضمن أنه حتى لو قدم قيد تابع حافزاً عرضياً، فإن صافي الجزاء لانتهاك السيد يظل سالباً.
التسلسل (Concatenation): بالنسبة لثلاثة قيود أو أكثر، يتم استخدام تسلسل هرمي "متسلسل" (على سبيل المثال، $C_1$ هو سيد لـ $C_2$ ، و $C_1 \land C_2$ هو سيد لـ $C_3$ )، مما يقلل بشكل أكبر من عدد القيود الفرعية التي يجب استيفاؤها.

ج. التطبيق على المشكلات ذات القيود المحلية

طبق المؤلفون هذه الطرق على مشكلات التحسين ذات القيود المحلية، حيث تُعرف القيود عقدة بعقدة (على سبيل المثال، القيود على الأقواس الواردة/الصادرة لعقدة معينة في رسم بياني). هذا الهيكل يسمح بتطبيق طرق IQP و MS بكفاءة لكل عقدة بشكل مستقل.

3. دراسة حالة: تسوية موازنة الربح الأقصى (MPBS)

تحقق المؤلفون من طرقهم باستخدام مشكلة MPBS، وهي مشكلة تحسين مالية صعبة (NP-hard) تتضمن تسوية المستحقات في شبكة.

القيود:
1. الحد الأعلى/الأدنى (CAP/FLOOR): يجب أن يظل صافي الميزانية لكل مستخدم ضمن نطاق محدد $[FL, CAP]$ .
2. داخل/خارج (IN/OUT): إذا شارك المستخدم في التسوية، يجب أن يكون لديه معاملة واحدة واردة واحدة وصادرة واحدة على الأقل.
النهج القياسي: يتطلب متغيرات فراغ تتناسب مع نطاق قيد CAP/FLOOR (غالباً $\sim 16+$ متغيراً لكل عقدة في البيانات المالية الواقعية) ومتغيرات لوغاريتمية لـ IN/OUT.
النهج المقترح (IQPMS):
- داخل/خارج (IN/OUT): عوملت كقيد السيد (Master). بالنسبة للعقد التي تحتوي على $\le 4$ أقواس، لا يلزم وجود صفر من متغيرات الفراغ. بالنسبة لـ 5 أقواس، يلزم فقط متغير أو اثنين.
- الحد الأعلى/الأدنى (CAP/FLOOR): عوملت كقيد التابع (Satellite). بما أنها تُفرض فقط عند استيفاء IN/OUT، فإن نطاق القيم التي يجب تغطيتها ينخفض بشكل كبير.
- النتيجة: بالنسبة للعقد التي تحتوي على $\le 4$ أقواس، لا يلزم وجود صفر من متغيرات الفراغ لـ CAP/FLOOR. بالنسبة لـ 5 أقواس، يلزم فقط 0–2 من المتغيرات.

4. النتائج الرئيسية

اختبر المؤلفون نهجهم على 20 حالة من MPBS باستخدام جهازي تلدين كمومي من D-Wave: Advantage_system4.1 (Adv1) والنموذج الأولي للجيل القادم Advantage2_prototype1.1 (Adv2).

تقليل متغيرات الفراغ:
- قللت طرق IQPMS عدد متغيرات الفراغ بنسبة تقارب 90% مقارنة بالطرق القياسية.
- بالنسبة لأكبر الحالات ( $N=18$ قوساً)، تطلبت الطريقة القياسية حوالي 90 متغيراً لـ QUBO، بينما تطلبت IQPMS حوالي 28 متغيراً فقط.
كفاءة الكيوبت:
- الطريقة القياسية: تطلبت $\approx 10.5$ كيوبت فيزيائي لكل قوس مضاف إلى الرسم البياني.
- طريقة IQPMS: تطلبت $\approx 2$ كيوبت فيزيائي لكل قوس.
جودة الحل (معدلات النجاح):
- كان معدل نجاح إيجاد الحل الأمثل باستخدام IQPMS أعلى بكثير من الطريقة القياسية.
- عامل الربح (Gain Factor): تراوحت نسبة التشغيل الناجح (IQPMS مقابل Standard) من 7 أضعاف (لأصغر الحالات على Adv1) إلى 184 ضعفاً (لأكبر الحالات على Adv2).
- على عكس الطريقة القياسية، حيث انخفضت معدلات النجاح بسرعة مع زيادة حجم المشكلة، حافظت طريقة IQPMS على معدلات نجاح عالية حتى مع المدخلات الأكبر.
مقارنة الأجهزة: تفوق جهاز Advantage2 الأحدث (اتصال أعلى وضجيج أقل) على Advantage_system4.1، لكن التحسن النسبي الذي وفره صياغة IQPMS كان متسقاً عبر كلا الجهازين.

5. الأهمية والخاتمة

القابلية للتوسع: يوضح العمل أنه من خلال تحسين صياغة المشكلة (تقليل متغيرات الفراغ والاتصال المطلوب)، يمكن لأجهزة NISQ الحالية حل حالات أكبر بكثير من المشكلات الصعبة (NP-hard) مما كان يُعتقد سابقاً.
استقلالية الأجهزة: يحسن هذا الأسلوب الأداء على كل من أجهزة التلدين الحالية والجيل القادم من خلال تقليل العبء على عدد الكيوبتات واتصالها.
لا يوجد تقريب: على عكس الأساليب الأخرى (مثل ADMM أو إعادة القياس التقريبي)، توفر هذه الطريقة إعادة صياغة دقيقة للمشكلة الأصلية دون تقريبات أو خطوات حل كلاسيكية تمهيدية.
الآفاق المستقبلية: يشير المؤلفون إلى أن هذه التقنيات قابلة للتطبيق على مجموعة واسعة من المشكلات ذات القيود المحلية (مثل متغيرات Knapsack أو Subset Sum)، ويمكن دمجها مع الحلول الهجينة أو تقنيات تقليل المتغيرات لدفع حدود التحسين الكمي القريب.

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