⚛️ quantum physics

Introduction to QUDO, Tensor QUDO and HOBO formulations: Qudits, Equivalences, Knapsack Problem, Traveling Salesman Problem and Combinatorial Games

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

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

نُشر 2026-05-04

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

CC BY 4.0

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

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

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

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

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

إليك تفصيل للغات الثلاث الجديدة والألعاب المستخدمة لاختبارها:

1. QUDO: "المؤشر" بدلاً من "المفتاح"

المفهوم:
في لغة QUBO القديمة، تكون المتغيرات مفاتيح ثنائية (0 أو 1). تقوم QUDO (التحسين التربيعي غير المقيد متعدد القيم - Quadratic Unconstrained D-ary Optimization) بترقية هذه المفاتيح إلى مؤشرات (Dials). فبدلاً من أن يكون المؤشر مجرد تشغيل أو إيقاف، يمكن ضبط المؤشر على أي رقم من 0 حتى حد معين (مثل مقبض التحكم في مستوى الصوت الذي يمتد من 0 إلى 10).

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

نهج QUBO: يتعين عليك أن تقرر لكل جورب وقميص وحذاء على حد سواء ما إذا كنت ستضعه في الحقيبة (1) أم لا (0). إذا كنت تريد حزم 5 قمصان، فستحتاج إلى 5 مفاتيح منفصلة.
نهج QUDO: لديك مؤشر واحد لـ "القمصان". ما عليك سوى تدوير المؤشر إلى "5"، وسيعرف الكمبيوتر أنك تحمل خمسة قمصان.

أمثلة الورقة البحثية:

مسألة الحقيبة (The Knapsack Problem): هذه هي المسألة الكلاسيكية "ما الذي يتسع في الحقيبة". توضح الورقة أن استخدام مؤشرات QUDO أكثر كفاءة بكثير من استخدام مئات المفاتيح الثنائية لعدّ كمية كل نوع من العناصر التي تأخذها.
هاشي ووكاكيرو (Hashiwokakero - الجسور): لغز حيث تقوم بتوصيل الجزر بالجسور. بما أنه يمكنك بناء 0 أو 1 أو 2 من الجسور بين الجزر، فإن المؤشر (0، 1، أو 2) يناسب المسألة تماماً، بينما تتطلب المفاتيح الثنائية حِيلاً إضافية للعد حتى 2.

2. T-QUDO: خريطة "العلاقة الذكية"

المفه concept:
أحياناً، لا تتعلق قواعد اللغز بقيمة مؤشر واحد فحسب، بل بـ العلاقة بين مؤشرين. T-QUDO (التحسين التنسوري التربيعي غير المقيد - Tensor QUDO) هي لغة تفهم هذه العلاقات المعقدة بشكل مباشر.

التشبيه:
تخيل حفلة حيث يتعين عليك إجلاس الضيوف.

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

أمثلة الورقة البحثية:

مسألة البائع المتجول (Traveling Salesman Problem): يجب على البائع زيارة كل مدينة مرة واحدة بالضبط. تجعل T-QUDO من السهل قول: "إذا كنت في المدينة (أ) في الخطوة 1، فلا يمكنك أن تكون في المدينة (أ) في الخطوة 2".
لعبة الملكات (N-Queens): الهدف هو وضع الملكات على رقعة الشطرنج بحيث لا يهاجم بعضها البعض. تتعامل T-QUDO مع قاعدة "إذا كانت الملكة (أ) في الصف 1، العمود 3، فإن الملكة (ب) لا يمكن أن تكون في الصف 2، العمود 4" بشكل طبيعي جداً.
كاكورو (Kakuro) وإنشي نو هييا (Inshi no Heya): هذه ألغاز أرقام (مثل السودوكو ولكن مع مجموع وضرب الأرقام). تسمح T-QUDO للكمبيوتر بالتحقق من مجموع وناتج ضرب مجموعات الأرقام مباشرة، بدلاً من إجبارها على التحول إلى رياضيات ثنائية.

3. HOBO: "العناق الجماعي"

المفهوم:
أحياناً، تتضمن القاعدة ثلاثة أو أكثر من المتغيرات التي تعمل معاً في وقت واحد. HOBO (التحسين الثنائي عالي الرتبة - Higher-Order Binary Optimization) هي لغة تسمح للمتغيرات بالتفاعل في مجموعات، وليس فقط في أزواج.

التشبيه:
تخيل لعبة الكراسي الموسيقية.

الثنائي/الزوجي: يمكنك فقط التحقق مما إذا كان الشخص (أ) يجلس بجانب الشخص (ب).
HOBO: يمكنك التحقق مما إذا كان الشخص (أ) والشخص (ب) والشخص (ج) جميعهم يجلسون في تشكيل مثلث محدد في نفس الوقت. إنها تلتقط "ديناميكية المجموعة" في خطوة واحدة.

مثال الورقة البحثية:

لعبة سوليتير الوتد (Peg Solitaire): هي اللعبة التي تقفز فيها الأوتد فوق بعضها البعض لإزالتها. تتضمن الحركة ثلاثة مواضع محددة: الوتد الذي يبدأ، والوتد الذي يتم القفز فوقه، وموضع الهبوط. تعتبر HOBO مثالية لوصف هذا التفاعل الثلاثي في خطوة واحدة، مما يجعل الحل أكثر وضوحاً.

لماذا يهم هذا؟

تجادل الورقة بأنه بينما تعتبر هذه اللغات الجديدة (QUDO، T-QUDO، HOBO) أكثر تعقيداً في التعلم من اللغة الثنائية القديمة، إلا أنها غالباً ما تكون أكثر كفاءة لأنواع معينة من المسائل.

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

ملخص

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

يثبت المؤلف ذلك من خلال أخذ ألعاب منطقية صعبة (مثل Hashiwokakero، وN-Queens، وPeg Solitaire) ويظهر كيف تحل هذه الصياغات الجديدة المسائل بموارد أقل وقواعد أوضح من الطرق التقليدية.

إليك ملخص تقني مفصل لورقة البحث بعنوان "مقدمة في صياغات QUDO وTensor QUDO وHOBO: الكيوديتات (Qudits)، التكافؤات، مسألة الحقيبة، مسألة البائع المتجول، والألعاب التوليفية" للباحث أليخاندرو ماتا علي.

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

غالبًا ما تكون مسائل التحسين التوليفي (مثل مسألة الحقيبة، مسألة البائع المتجول، ومسألة N-Queens) من فئة المسائل الصعبة حاسوبيًا (NP-Hard) وتفتقر إلى حلول كلاسيكية فعالة. وعلى الرغم من أن صياغة التحسين الثنائي غير المقيد التربيعي (QUBO) هي المعيار المتبع لربط هذه المسائل بالأجهزة الكمومية (تحديدًا عبر نموذج Ising Hamiltonian وخوارزمية QAOA)، إلا أنها تعاني من بعض القيود:

عدم كفاءة المتغيرات: تتطلب المسائل ذات الحالات الطبيعية متعددة القيم (مثل اختيار $k$ من العناصر من أصل $n$ ) ترميزًا ثنائيًا، مما يزيد من عدد المتغيرات ويستحدث حالات غير صالحة تتطلب حدود عقوبة (penalty terms).
قيود القيود: يصعب أو يستحيل تنفيذ بعض القيود المنطقية (مثل استلزام قيم معينة أو عدم تطابق قيم محددة) بكفاءة في نماذج QUBO القياسية بسبب الطبيعة الثنائية للمتغيرات ( $x_i^2 = x_i$ ).
عدم التوافق مع الأجهزة: توفر التقنيات الكمومية الناشئة، مثل الكيوديتات (qudits) (الأنظمة الكمومية ذات المستويات $d$ )، طريقة طبيعية لتمثيل المتغيرات غير الثنائية ولكنها تتطلب صياغات تحسين تتجاوز QUBO.

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

2. المنهجية

يقدم المؤلف ويحلل ثلاثة أطر عمل للتحسين المعمم، موفرًا صياغات رياضية صريحة وموضحًا تطبيقها على المسائل الكلاسيكية والألعاب التوليفية.

أ. التحسين الرقمي التربيعي غير المقيد (QUDO)

التعريف: هو تعميم لـ QUBO حيث تكون المتغيرات $x_i$ أعدادًا صحيحة غير سالبة محدودة ( $x_i \in \{0, 1, \dots, d_i-1\}$ ) بدلاً من كونها ثنائية.
دالة التكلفة: $C(\vec{x}) = \sum_{i \le j} Q_{ij}x_i x_j + \sum D_i x_i$ .
الميزات الرئيسية:
- يتطلب تنفيذًا مباشرًا باستخدام الكيوديتات (qudits).
- يسمح بوجود حدود خطية (على عكس QUBO الخالص حيث $x_i^2=x_i$ ).
- القيود: يصعب تنفيذ بعض القيود (مثل "إذا كان $x_i=a$ فإن $x_j \neq b$ ") لأن إشارة حدود التفاعل تعتمد على القيم المحددة للمتغيرات غير الثنائية.
- التنفيذ: يمكن ربطه بخوارزمية QAOA باستخدام بوابات الطور للكيوديت $P(\theta)$ وبوابات الطور المتحكم بها.

ب. التحسين التنسوري التربيعي غير المقيد الرقمي (T-QUDO)

التعريف: هو تعميم فئوي (categorical) لـ QUDO يعامل المتغيرات كملصقات فئوية وليس كقيم عددية.
دالة التكلفة: $C(\vec{x}) = \sum U_i(x_i) + \sum_{i<j} V_{ij}(x_i, x_j)$ .
الميزات الرئيسية:
- يستخدم تنسور التكلفة $Q_{i,j, a, b}$ لتحديد تكلفة تخصيص القيمة $a$ للمتغير $i$ والقيمة $b$ للمتغير $j$ .
- الميزة: يتغلب على قيود QUDO من خلال تسهيل تنفيذ القيود المنطقية المعقدة (مثل استلزام قيم معينة، أو عدم تطابق قيم محددة) دون الاعتماد على الخصائص الحسابية.
- الترميز: يمكن ترميزه في HOBO أو QUBO (عبر الترميز بنظام One-hot أو الترميز الثنائي)، رغم أن هذا قد يزيد من عدد المتغيرات.

ج. التحسين الثنائي من الرتب العليا (HOBO)

التعريف: صياغة تستخدم دوال بولية كاذبة متعددة الخطية (multilinear pseudo-Boolean functions) من الرتبة $m$ (حيث $m > 2$ ).
دالة التكلفة: $C(\vec{y}) = \sum_{S} q_S \prod_{i \in S} y_i$ , حيث $y_i \in \{0, 1\}$ .
الميزات الرئيسية:
- يسمح بالتفاعلات بين أكثر من متغيرين.
- العلاقة بـ T-QUDO: يمكن ترميز تفاعلات T-QUDO في HOBO عن طريق تحويل تسميات الكيوديت إلى صيغة ثنائية.
- التنفيذ: قابل للتطبيق مباشرة على الأجهزة الكمومية القائمة على الكيوبت (qubit) التي تدعم التفاعلات من الرتب العليا أو عبر تقنيات الاختزال.

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

تتحقق الورقة من صحة هذه الصياغات من خلال تطبيقها على مسألة الحقيبة، ومسألة البائع المتجول (TSP)، وخمس ألعاب توليفية.

المسألة	الصياغة المستخدمة	الرؤية/النتيجة الرئيسية
الحقيبة (Knapsack)	QUDO	يظهر تقليلًا كبيرًا في الموارد. بدلاً من المتغيرات الثنائية لأعداد العناصر، يمثل كيوديت واحد لكل فئة عنصر العدد مباشرة. يقلل ذلك من عدد المتغيرات ومتغيرات الارتخاء (slack variables) المطلوبة مقارنة بـ QUBO.
Hashiwokakero	QUDO	ينمذج اتصالات الجسور (0، 1، أو 2) بشكل طبيعي. يستخدم متغيرات تدفق مساعدة (مُرمزة ككيوديتات) لفرض الاتصال العالمي، مما يثبت أن QUDO يمكنه التعامل مع القيود الطوبولوجية المعقدة بدقة.
البائع المتجول (TSP)	T-QUDO	يستخدم المتغيرات $x_t$ لتمثيل العقدة في الخطوة الزمنية $t$ . يتم التعامل مع قيد "عدم التكرار" بشكل طبيعي عبر حد عقوبة زوجي $\delta_{x_t, x_{t'}}$ , مما يتجنب الحاجة إلى ترميزات الأعداد الأولية المعقدة أو المصفوفات الثنائية الضخمة.
N-Queens	T-QUDO	يقلل المتغيرات من $N^2$ (شبكة ثنائية) إلى $N$ (مؤشر العمود لكل صف). يقوم تنسور T-QUDO بترميز قيود الصف والعمود والقطر بشكل طبيعي كمدخلات تنسورية محددة، مما يبسط هيكل دالة التكلفة.
Kakuro	T-QUDO	يجمع بين QUDO (لقيود المجموع) وT-QUDO (لقيود عدم التكرار). الطبيعة الفئوية لـ T-QUDO تتعامل بشكل مثالي مع قاعدة "الرقم الفريد في الصف/العمود".
Inshi no Heya	T-QUDO	يتعامل مع قيود المناطق الضربيه عن طريق تحويل الضرب إلى مجموع أسس الأعداد الأولية، والتي تتناسب طبيعيًا مع إطار عمل T-QUDO.
Peg Solitaire	HOBO	ينمذج اللعبة كتسلسل من الحالات. يتطلب منطق الحركة (القفز فوق قطعة) تفاعلات رباعية المتغيرات (المصدر، المنتصف، الوجهة، والزمن)، وهو ما يُعبر عنه بشكل طبيعي في HOBO دون الحاجة إلى اختزاله إلى حدود تربيعية.

4. النتائج

كفاءة الموارد: غالبًا ما تتطلب صياغات QUDO وT-QUDO متغيرات أقل من نظيراتها في QUBO. على سبيل المثال، تنخفض مسألة N-Queens من $N^2$ من المتغيرات الثنائية إلى $N$ من الكيوديتات.
مرونة القيود: تتيح T-QUDO التنفيذ المباشر للقيود المنطقية (الاستلزام، وعدم التطابق) التي تكون صعبة أو مستحيلة في QUDO/QUBO دون استخدام متغيرات مساعدة.
القابلية للتنفيذ: تقدم الورقة دوال تكلفة صريحة وحدود عقوبة لجميع الأمثلة، مما يثبت أن هذه الصياغات سليمة رياضيًا و"دقيقة" (أي أن الحلول الصالحة لها تكلفة صفرية).
التنفيذ الكمومي: يوضح المؤلف كيفية تنفيذ دوال التكلفة هذه في خوارزمية QAOA:
- QUDO: يستخدم بوابات طور الكيوديت المفردة وبوابات الكيوديت الثنائية.
- T-QUDO: يستخدم بوابات طور التركيز المتحكم بها (controlled focus phase gates).
- HOBO: يستخدم بوابات طور متعددة التحكم (أو اختزالات تعتمد على العناصر المساعدة/ancilla).

5. الأهمية

الربط بين النظرية والأجهزة: تعمل الورقة كدليل عملي للاستفادة من الأجهزة الكمومية الناشئة القائمة على الكيوديتات (qudits)، وتتجاوز القيود الثنائية لأبحاث الكيوبت الحالية.
تحسين الخوارزميات: توضح أن اختيار الصياغة الصحيحة (QUDO/T-QUDO/HOBO) بناءً على البنية الطبيعية للمسألة يمكن أن يقلل بشكل كبير من تعقيد مشهد التحسين، مما يحسن أداء الخوارزميات الكمومية مثل QAOA.
إطار تعليمي: باستخدام الألعاب والألغاز المعروفة، تخفض الورقة حاجز الدخول لفهم أطر التحسين المعقدة ذات الرتب العليا والمتعددة القيم.
الاتجاهات المستقبلية: تشير الورقة إلى أن بنيات الأجهزة الكمومية المستقبلية يجب أن تدعم التفاعلات من الرتب العليا والكيوديتات بشكل أصيل لحل المسائل التوليفية بكفاءة أكبر مما تسمح به طرق الاختزال الثنائي الحالية.

في الختام، تجادل الورقة بأنه بينما تعد QUBO أداة قوية، فإن QUDO وT-QUDO وHOBO توفر كفاءة وقدرة تعبيرية متفوقة لفئات معينة من المسائل التوليفية، لا سيالما تلك التي تتضمن متغيرات متعددة القيم أو قيودًا منطقية معقدة، وهي قابلة للتنفيذ مباشرة على الأجهزة من الجيل التالي.