⚛️ quantum physics

A QUBO Formulation for the Generalized LinkedIn Queens and Takuzu/Tango Game

تقدم هذه الورقة صياغة QUBO متعددة الاستخدامات لحل النسخ المعممة من الألعاب المنطقية مثل LinkedIn Queens وTakuzu وTango، مع تقديم مشكلات جديدة قائمة على الشطرنج وتحسين النموذج للتنفيذ على الأجهزة الكمومية عبر التلدين الكمي (Quantum Annealing) أو خوارزمية التحسين التقريبي الكمي (QAOA).

المؤلفون الأصليون: Alejandro Mata Ali, Edgar Mencia

نُشر 2026-05-01

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

CC BY 4.0

المؤلفون الأصليون: Alejandro Mata Ali, Edgar Mencia

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

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

إليك تفصيل للأفك والأفكار الرئيسية للورقة باستخدام تشبيهات من الحياة اليومية:

1. المفهوم الجوهري: لعبة "الطاقة"

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

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

2. ألعاب الملكات (LinkedIn و N-Queens)

تطلب مسألة N-Queens الكلاسيكية منك وضع $N$ من الملكات على رقعة شطرنج بحيث لا يمكن لأي منها مهاجمة الأخرى.

القاعدة القديمة: لا يمكن للملكات مشاركة نفس الصف أو العمود أو أي خط قطري.
لمسة LinkedIn: تنظر الورقة إلى نسخة أحدث (LinkedIn Queens) حيث تكون القاعدة القطرية "أكثر مرونة". لا يمكن للملكات مهاجمة بعضها البعض إذا كانت بجانب بعضها مباشرة قطرياً، ولكن يمكنها تجاهل الملكات البعيدة. كما أن الرقعة مقسمة إلى مناطق ملونة، ويجب وضع ملكة واحدة بالضبط في كل منطقة.
مساهمة الورقة: ابتكر المؤلفون "وصفة" مرنة (صيغة QUBO) يمكنها التعامل مع:
- N-Queens القياسية.
- قواعد LinkedIn الأكثر مرونة.
- أشكال الرقع غير المنتظمة (مثل الرقع ذات الزوايا المفقودة).
- الرقع التي تلتف حول نفسها مثل شكل "الدونات" (Toroidal)، حيث القطعة التي تغادر الحافة اليمنى تظهر مجدداً من الحافة اليسرى.
- لعبة "الخيام والأشجار": قاموا بتكييف وصفتهم للعبة تتطلب منك وضع خيام بجانب الأشجار دون أن تلمس أي خيمة أخرى، حتى قطرياً.

3. توسيع "قطع الشطرنج"

أدرك المؤلفون أن وصفتهم لم تكن مقتصرة على الملكات فقط، بل قاموا بتعميمها لتناسب أي قطعة شطرنج.

مسألة قطع الشطرنج الملونة: تخيل رقعة تحتوي على مناطق ملونة مختلفة يجب أن تحتوي كل منها على قطعة واحدة بالضبط. يمكن أن تكون القطع رخ (Rooks)، أو فيل (Bishops)، أو حصان (Knights)، ولها طرق حركة مختلفة. الهدف هو وضع أكبر عدد ممكن منها دون أن تهدد بعضها البعض.
مسألة أقصى عدد لقطع الشطرنج: هنا، الهدف هو ببساطة حشر أكبر عدد ممكن من القطع في الرقعة دون أن تهاجم بعضها البعض. أضاف المؤلفون "مكافأة" في معادلتهم الرياضية: في كل مرة تنجح فيها في وضع قطعة، تنخفض الطاقة قليلاً، مما يشجع الحاسوب على ملء الرقعة.

4. ألعاب Takuzu و Tango

هذه ألعاب تعتمد على ملء الشبكات (مثل السودوكو ولكن باستخدام 0 و 1، أو شمس وقمر).

القواعد:
1. يجب أن يكون لكل صف وعمود عدد متساوٍ من الأصفار والآحاد.
2. لا يمكنك وضع ثلاثة رموز متماثلة في صف واحد (لا "000" ولا "111").
3. Tango (نسخة LinkedIn): تضيف رموزاً خاصة بين الخلايا. الرمز "=" يعني أن الخليتين يجب أن تكونا متماثلتين؛ والرمز "x" يعني أنهما يجب أن تكونا مختلفتين.
4. Takuzu الكلاسيكي: يضيف قاعدة صارمة وهي أنه لا يمكن أن يكون هناك صفان متطابقان ولا عمودان متطابقان.
الاختراق الذي حققته الورقة:
- ابتكروا وصفة QUBO مثالية لـ Tango والقواعد المحلية لـ Takuzu.
- الجزء الصعب: قاعدة "عدم وجود صفوف متطابقة" في Takuzu الكلاسيكي صعبة على الحواسيب الكمومية. حل المؤلفون ذلك عن طريق إدخال "متغيرات الشاهد" (Witness Variables).
- التشبيه: تخيل أن لديك صفين من الناس وتحتاج إلى إثبات أنهما مختلفان. تقوم بتعيين "شاهد" لكل زوج من الصفوف. وظيفة الشاهد هي الإشارة إلى عمود واحد بالضبط حيث يختلف الصفان. إذا لم يستطع الشاهد إيجاد اختلاف، تزداد العقوبة (الطاقة). هذا يسمح للحاسوب الكمومي بفرض قاعدة "عدم وجود صفوف متطابقة" في Takuzu بشكل مثالي دون الحاجة إلى متغيرات "فراغ" (slack variables) تهدر الموارد.

5. لماذا هذا مهم (وفقاً للورقة)

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

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

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

إليك ملخص تقني مفصل لورقة البحث بعنوان "صياغة QUBO للعبة ملكات LinkedIn المعممة ولعبة Takuzu/Tango" من تأليف أليخاندرو ماتا علي وإدغار مينسيا.

1. تعريف المشكلة

تتناول الورقة تحدي حل العديد من الألغاز المنطقية التوافقية باستخدام التلدين الكمي (Quantum Annealing) وخوارزمية التحسين التقريبي الكمي (QAOA). تتطلب هذه الخوارزميات صياغة المشكلات في شكل مسائل تحسين ثنائية تربيعية غير مقيدة (QUBO). يركز المؤلفون على تعميم وتوحيد صياغات QUBO لعدة ألعاب محددة:

N-Queens & LinkedIn Queens (L-Queens): مسألة N-Queens الكلاسيكية (وضع N من الملكات على لوحة $N \times N$ دون هجمات متبادلة) ومتغير LinkedIn الخاص بها، والذي يخفف قيود الأقطار لتقتصر فقط على الأقطار "المجاورة" ويضيف قيوداً قائمة على المناطق (ملكة واحدة لكل منطقة ملونة).
Takuzu (Binairo) & Tango: ألغاز منطقية تتضمن ملء شبكة بالأصفار والآحاد (أو الشمس والقمر) خاضعة لقيود: أعداد متساوية من الأصفار والآحاد في كل صف/عمود، عدم وجود أكثر من قيمتين متتاليتين متطابقتين، وفريدة من نوعها للصفوف/الأعمدة (في Takuzu). تضيف لعبة Tango قيود المساواة ("=") وعدم المساواة ("x") المحددة بين الخلايا.
التوسعات: تقدم الورقة أيضاً صياغات لـ Tents & Trees، و Coloured Chess Piece Problems، و Max Chess Pieces Problem.

2. المنهجية

تتمثل المنهجية الجوهرية في ترجمة القيود المنطقية لهذه الألعاب إلى دوال عقوبة تربيعية. يستخدم المؤلفون هويات المتغيرات الثنائية القياسية ( $x^2 = x$ ) لضمان بقاء جميع الحدود تربيعية.

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

عقوبات القيود: يحدد المؤلفون حدود عقوبة قياسية لـ:
- الأعداد الدقيقة: $(s - k)^2$ لفرض وجود $k$ من المتغيرات النشطة بالضبط.
- الأقصى واحد (At-most-one): $\sum x_i x_j$ لمنع التنشيط المتزامن.
- القيم المتتالية: عقوبات للأنماط مثل 000 أو 111 باستخدام $(s-1)(s-2)$ .
- المساواة/عدم المساواة: $(x-y)^2$ و $(x+y-1)^2$ .
رسوم البيانية للصراع (Conflict Graphs): بدلاً من معالجة قيود الأقطار كأقاليم معقدة، يصيغ المؤلفون نماذجها كرسوم بيانية للصراع حيث تمثل الحواف التنشيطات المتزامنة المحظورة. أثبت هذا النهج أنه أكثر دقة وكفاءة لمتغيرات N-Queens.
المعالجة المسبقة وتقليل المتغيرات:
- المتغيرات الثابتة: يتم تثبيت القطع الموضوعة مسبقاً (الأدلة/Clues) على 0 أو 1، ويتم تثبيت جيرانها المتعارضين على 0، مما يقلل عدد متغيرات التحسين.
- تقليل التكافؤ (Takuzu/Tango): بالنسبة لقيود "=" و "x"، يقترح المؤلفون هيكل Union-Find مع التكافؤ (parity). هذا يقلل عدد المتغيرات الحرة من خلال التعبير عن الخلايا المعتمدة كـ $x_v = y_C \oplus \pi_v$ ، حيث $y_C$ هو متغير ممثل للمكون المتصل.
التعامل مع التفرد العالمي (Takuzu): تتطلب لعبة Takuzu الكلاسيكية عدم تكرار أي صف أو عمود. لا يمكن للقيود المحلية القياسية فرض ذلك. يقدم المؤلفون متغيرات الشاهد (Witness Variables) ( $u_{rsj}$ ) لإثبات أن كل زوج من الصفوف $r, s$ يوجد فيه على الأقل عمود $j$ يختلفان فيه. هذا يخلق صياغة QUBO دقيقة دون الحاجة لمتغيرات الارتخاء (slack variables)، رغم أنه يزيد عدد المتغيرات إلى $O(N^3)$ .

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

أ. إطار عمل N-Queens المعمم

يقترح المؤلفون صياغة QUBO موحدة لـ N-Queens تدعم:

أعداد متغيرة من الملكات لكل صف/عمود.
"المناطق الناعمة" (التي تسمح بـ 0 أو 1 من الملكات) والمناطق المتداخلة.
اللوحات الحلقية (Toroidal boards) (حيث تلتف الحواف حول نفسها).
رؤية جوهرية: يوضحون أن قيود الأقطار تُنمذج بشكل أفضل كرسوم بيانية للصراع الزوجي بدلاً من قيود المنطقة "الأقصى واحد"، مما يحافظ على دقة فضاء الحل.

ب. صياغة Takuzu/Tango الدقيقة

المحلي مقابل العالمي: يميزون بين "المحلية" TTP (مشكلة Takuzu/Tango)، التي تتعامل مع توازن الصف والقيود التكرارية، وبين قيد التفرد "العالمي".
بناء متغيرات الشاهد: يقدمون طريقة مبتكرة لفرض تفرد الصفوف/الأعمدة في Takuzu باستخدام متغيرات شاهد مساعدة. يسمح هذا بصياغة QUBO دقيقة للعبة Takuzu الكلاسيكية، وهو أمر كان صعب التحقيق سابقاً بدون ارتخاء أو متغيرات إضافية.
التوسعات: يوسعون Takuzu لتشمل التكرار غير المتوازن (أعداد مختلفة من 0 و 1)، وقيود التكرار القطرية، ورموز المساواة/عدم المساواة بعيدة المدى.

ج. تعريفات مشكلات جديدة

مسألة قطع الشطرنج الملونة (Coloured Chess Piece Problem): تعميم حيث يجب وضع أنواع مختلفة من القطع (بأنماط حركة مختلفة) بحيث لا تهدد أي قطعة أخرى، مع قطعة واحدة لكل منطقة ملونة.
مسألة أقصى قطع الشطرنج (Max Chess Pieces Problem): مسألة تحسين لوضع أكبر عدد من القطع غير المتعارضة على لوحة، مصاغة مع حد مكافأة ( $-\sum w_{ij}x_{ij}$ ) وعقوبة صراع.

4. النتائج والتحليل النظري

الدقة: تثبت الورقة أن الصياغات المقترحة دقيقة.
- بالنسبة لـ LinkedIn Queens، تضمن المعالجة المسبقة أن النسخة المختزلة من QUBO تطابق فضاء حل المسألة الأصلية.
- بالنسبة لـ Takuzu، تضمن طريقة متغيرات الشاهد أن أي حالة ذات طاقة صفرية تقابل حلاً صالحاً بصفوف وأعمدة فريدة.
- بالنسبة لـ Max Chess Pieces، يثبت المؤلفون أنه إذا كان معامل العقوبة $\lambda$ للصراعات أكبر من وزن المكافأة الأقصى، فلن يحتوي أي مُقلل عالمي (global minimizer) على قطع متعارضة.
التعقيد:
- تتوسع صياغة Takuzu المحلية القياسية مع حجم اللوحة ( $O(N^2)$ متغيرات).
- تتوسع صياغة Takuz الدقيقة مع متغيرات الشاهد لتصل إلى $O(N^3)$ بسبب المتغيرات المساعدة $2N^2(N-1)$ المطلوبة لفرض التفرد.
التحسين: يتم تسليط الضوء على استخدام حدود العقوبة "الكسرية" (مثل $(s - (q+0.5))^2$ ) كتقنية لتقليل عدد المتغيرات (تجنب متغيرات الارتخاء) مع إدخال إزاحة ثابتة للطاقة لا تؤثر على القيم الصغرى.

5. الأهمية

الجاهزية للأجهزة الكمية: من خلال توفير صياغات QUBO دقيقة وصارمة، تسد الورقة الفجوة بين الألغاز المنطقية المجردة والتطبيق العملي على الملدنات الكمية (مثل D-Wave) والحواسيب الكمية القائمة على البوابات (عبر QAOA).
إطار عمل موحد: يوضح العمل أنه يمكن نمذجة أنواع متنوعة من الألغاز (Queens, Takuz, Tents) تحت إطار رياضي واحد باستخدام رسوم بيانية للصراع وقيود المناطق، مما يسهل تطوير حلول كمية عامة للألغاز التوافقية.
الاختبار المرجعي: تعمل هذه الصياغات كمعايير اختبار قوية لاختبار الخوارزميات الكمية، خاصة فيما يتعلق بالتعامل مع القيود، وتقليل المتغيرات، والمفاضلة بين دقة الحل وتكلفة الكيوبت (على سبيل المثال، تكلفة متغيرات الشاهد).
الاتجاهات المستقبلية: تحدد الورقة مسارات للبحث المستقبلي، بما في ذلك تنفيذ هذه الصياغات على أجهزة كمية حقيقية، وتقليل العبء الإضافي للمتغيرات المساعدة للقيود العالمية، واستكشاف الصياغات ذات الرتب الأعلى (HOBO/QUDO).

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