Quantum Query Complexity of Tournament Solutions
تتقصى هذه الورقة تعقيد الاستعلام الكمي لمختلف حلول البطولات، مظهرةً أنه في حين تتطلب الخوارزميات الكلاسيكية من الاستعلامات، يمكن للخوارزميات الكمية تحسين الكفاءة بشكل كبير لإيجاد الدورة العليا () وفائز كوندورسي ()، مع وضع حدود وثيقة لحلول أخرى مثل الملوك الأقوياء وقمم درجات الخروج القصوى.
البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل
تخيل بطولة بنظام الدوري (الكل ضد الكل)، حيث يواجه كل مشارك جميع المشاركين الآخرين مرة واحدة بالضبط، دون وجود تعادلات. في مثل هذه المسابقة، تكون النتيجة عبارة عن خريطة كاملة توضح من هزم من. ومن خلال هذه الخريطة، يحاول الرياضيون وعلماء الحاسوب تحديد "الفائزين" باستخدام قواعد مختلفة. بعض القواعد تبحث عن الشخص الذي هزم الجميع بشكل مباشر؛ وأخرى تبحث عن الشخص الذي يمكنه الوصول إلى أي شخص آخر في خطوتين فقط؛ ولا تزال هناك قواعد تبحث عن مجموعة الأشخاص الذين هزموا، كفريق واحد، كل من هم خارج المجموعة. تُسمى هذه القواعد "حلول البطولة". في العالم الحقيقي، قد لا نعرف نتيجة كل مباراة على الفور؛ فربما يتعين علينا إجراء تجربة جديدة أو استطلاع رأي جديد لمعرفة من فاز في زوج معين. وهذا يخلق لغزاً: كم عدد المباريات التي نحتاج إلى فحصها لمعرفة الفائزين؟ لفترة طويلة، بدا أن الإجابة هي أنه يتعين علينا فحص كل مباراة تقريباً، وهو رقم ينمو بسرعة كبيرة مع كبر حجم البطولة. هذا هو المنظور الكلاسيكي للمشكلة.
لقد أعاد فريق من الباحثين في المعهد الهندي للتكنولوجيا بجاناغار النظر في هذه المسألة باستخدام أدوات الحوسبة الكمومية. فبدلاً من فحص المباريات واحدة تلو الأخرى، تساءلوا عن عدد المباريات التي ستحتاج الحوسبة الكمومية لفحصها لتحديد الفائزين. يمكن للحواسيب الكمومية النظر في العديد من الاحتمالات في وقت واحد، وهي قدرة تسمح لها غالباً بحل المشكلات بشكل أسرع بكثير من الآلات الكلاسيكية. وقد وجد الباحثون أن الإجابة تعتمد كلياً على القاعدة التي تستخدمها لاختيار الفائز. فبالنسبة لبعض القواعد، تقدم الحوسبة الكمومية تسارعاً هائلاً، حيث لا تحتاج إلا لفحص كسر ضئيل جداً من المباريات. وبالنسبة لقواعد أخرى، يكون التفوق الكمومي أقل بكثير، وبالنسبة لقاعدة واحدة محددة، لا تقدم الحوسبة الكمومية أي تفوق على الإطلاق، بل تتطلب نفس عدد الفحوصات التي تتطلبها الحوسبة الكلاسيكية.
ركزت الدراسة على عدة طرق معيارية لتعريف الفائز. الأسهل في العثور عليه في عالم الكم هو "الدورة العليا" (top cycle). وهي أصغر مجموعة من اللاعبين الذين يهزمون، كفريق، جميع الآخرين. وأظهر الباحثون أن خوارزمية كمومية يمكنها تحديد هذه المجموعة من خلال فحص عدد من المباريات ينمو تقريباً بما يتناسب مع عدد اللاعبين. وهذا يمثل تحسناً كبيراً مقارنة بالمتطلب الكلاسيكي، الذي ينمو مع مربع عدد اللاعبين. ولإيجاد هذه المجموعة، تقوم الخوارضة الكمومية أولاً بترتيب جميع اللاعبين في خط واحد بناءً على انتصاراتهم، وهي عملية تشبه ترتيب مجموعة من أوراق اللعب. ثم تستخدم استراتيجية "فرق تسد" لتحديد مكان انتهاء مجموعة الفوز في ذلك الخط بدقة. هذا النهج فعال للغاية لدرجة أنه يحل أيضاً مشكلة ذات صلة: وهي تحديد ما إذا كانت البطولة بأكملها "متصلة بقوة"، بمعنى أن كل لاعب يمكنه الوصول إلى أي لاعب آخر عبر سلسلة من الانتصارات.
في المقابل، يصبح العثور على فائز "كوندورست" (Condorcet winner) منفرد -وهو لاعب يهزم الجميع مباشرة- أسهل حتى بالنسبة للحاسوب الكمومي. فقد أثبت الباحثون أن مثل هذا اللاعب يمكن العثود عليه من خلال فحص عدد من المباريات يتناسب مع الجذر التربيعي لعدد اللاعبين. وهذا يمثل انخفاضاً دراماتيكياً من المتطلب الكلاسيكي. وتتضمن الطريقة أولاً إيجاد "ملك"، وهو لاعب يمكنه الوصول إلى أي شخص آخر في خطوتين على الأكثر، ثم التحقق مما إذا كان هذا الملك قد تعرض لأي خسائر. إذا لم يتلقَّ الملك أي خسائر، فهو فائز "كوندورست"؛ وإذا تلقى خسائر، فلا يوجد مثل هذا الفائز. تؤكد هذه النتيجة أنه بالنسبة لهذا النوع المحدد من الفائزين، توفر ميكانيكا الكم اختصاراً قوياً.
ومع ذلك، تتغير القصة عندما يكون الهدف هو العثور على "مجموعة كوبلاند" (Copeland set)، والتي تتكون من جميع اللاعبين الذين لديهم أعلى عدد من الانتصارات. هنا، أثبت الباحثون أن الحاسوب الكمومي لا يحقق أي ميزة. فلتحديد المجموعة الكاملة لأعلى المسجلين، لا يزال يتعين على الحاسوب الكمومي فحص عدد من المباريات يتناسب مع مربع عدد اللاعبين، تماماً مثل الحاسوب الكلاسيكي. وهذه نتيجة مفاجئة لأن العثور على لاعب واحد فقط من هؤلاء المسجلين الأوائل هو أمر أسهل بكثير للحاسوب الكمومي. وتكمن الصعوبة في أن تحديد المجموعة بأكملها يتطلب حساب الانتصارات لكل لاعب بدقة متناهية، وهي مهمة لا تستفيد من قوة البحث المتوازي لميكانيكا الكم بنفس الطريقة التي يستفيد منها البحث عن هدف واحد.
كما بحث الباحثون في "المجموعة غير المغطاة" (uncovered set)، والتي تضم اللاعبين الذين يمكنهم الوصول إلى الجميع في خطوتين أو أقل. ووجدوا أن العثور على هذه المجموعة بأكملها أصعب من العثور على لاعب واحد مثلها، ولكنه أسهل من إيجاد مجموعة "كوبلاند" الكاملة. يحتاج الحاسوب الكمومي إلى فحص عدد من المباريات يتناسب مع عدد اللاعبين مرفوعاً للقوة 1.5. وهذا يضع المجموعة غير المغطاة في منطقة وسطى، مما يوضح أن صعوبة حل البطولة ليست موحدة؛ فبعض الحلول سهلة، وبعضها صعب، والتفوق الكمومي يتفاوت وفقاً لذلك.
ولإثبات هذه الحدود، طور الفريق حججاً رياضية جديدة. فقد ابتكروا سيناريوهات بطولة محددة وصعبة مصممة لخداع أي خوارزمية لجعلها تفحص العديد من المباريات. ومن خلال إظهار أن حتى الحاسوب الكمومي لا يمكنه حل هذه الألغاز المحددة دون فحص حد أدنى معين من المباريات، وضعوا حدوداً دنيا ثابتة للعمل المطلوب. وبالنسبة لمشكلة إيجاد اللاعب الذي لديه أكبر عدد من الانتصارات، قدموا برهاناً جديداً ومستقلاً لمتطلب معروف، مما يوضح أن الصعوبة تأتي من الحاجة إلى العد وليس مجرد البحث. لقد أوضح عملهم أنه بينما تعد الحواسيب الكمومية قوية، إلا أنها ليست عصا سحرية تسرع كل أنواع الحسابات. فالتسارع يعتمد على الهيكل المحدد للمشكلة، وفي حالة حلول البطولات، فإن القواعد المستخدمة لاختيار الفائز هي التي تحدد ما إذا كان الجهاز الكمومي يمكنه حقاً التألق.
غارق في أبحاث مجالك؟
تصلك نشرة يومية بأحدث الأبحاث المطابقة لكلماتك البحثية المفتاحية — مع ملخصات تقنية، بلغتك.