Ground-State Sampling Correspondence between Penalty-Based and Constrained Quantum Annealing
تُثبت هذه الورقة أن التلدين الكمي القائم على الجزاء والتلدين الكمي المقيد (CQA) يُنتجان توزيعات عينات للحالة الأرضية متكافئة لمسائل القيود العددية، لأن الانتقالات الافتراضية إلى الحالات غير الممكنة في طريقة الجزاء تولد تفاعلاً فعالاً من الدرجة الثانية يطابق الاقتران الخاص بمحرك الـ CQA ضمن المتشعب الممكن.
في عالم الحوسبة، تشبه بعض المشكلات البحث عن إبرة واحدة في كومة قش، بينما تشبه مشكلات أخرى البحث عن كل إبرة موجودة في حقل من كومات القش المتطابقة. المهمة الأخيرة أكثر صعوبة بكثير، ومع ذلك فهي غالباً ما تكون الأكثر أهمية في مجالات تتراوح من تصميم مواد جديدة إلى تحسين المحافظ الاستثمارية. ولتفكيك هذه الألغاز المعقدة، يستخدم العلماء تقنية تسمى التلدين الكمي (quantum annealing). تخيل مشهداً مليئاً بالتلال والوديان، حيث يمثل أعمق وادٍ الحل الأمثل لمشكلة ما. يعمل الحاسوب الكمي مثل ضباب يمكنه التدفق فوق التلال، ليستقر في أدنى النقاط. ومع ذلك، عندما تكون هناك وديان عديدة بنفس العمق تماماً، فإن الضباب لا يتوزع دائماً بشكل متساوٍ؛ بل يميل إلى تفضيل بعض الوديان على غيرها، مما يترك الحلول الأكثر رغبة ممثلة تمثيلاً ناقصاً. هذا التوزيع غير المتكافئ يمثل عقبة رئيسية أمام أي شخص يحاول إيجاد جميع الإجابات الممكنة لمشكلة صعبة.
لقد بحث باحثون في جامعة كيو وجامعة واسيدا مؤخراً في كيفية إصلاح هذا عدم التوازن، وتحديداً عندما تتضمن المشكلة قاعدة صارمة حول عدد العناصر التي يجب تضمينها في الحل. لقد قارنوا بين طريقتين مختلفتين لبرمجة الحاسوب الكمي لاحترام هذه القاعدة. الطريقة الأولى، المعروفة باسم نهج الجزاء (penalty approach)، تضيف تكلفة باهظة على أي حل يكسر القاعدة، مما يدفع الحاسوب فعلياً بعيداً عن الإجابات السيئة. أما الطৰيقة الثانية، المسماة التلدين الكمي المقيد (constrained quantum annealing)، فتبني القاعدة مباشرة داخل حركة الآلة، مما يضمن عدم خروجها من المنطقة الصالحة من الأساس. وبينما تعمل هاتان الطريقتان بشكل مختلف تماماً من الناحية التقنية، فقد سعى الباحثون لمعرفة ما إذا كانتا ستؤديان في النهاية إلى نفس النتيجة: اختيار عادل لجميع أفضل الحلول الممكنة.
ركز الفريق على لغز كلاسيكي يسمى تقسيم الرسم البياني (graph bipartitioning)، والذي يتضمن تقسيم شبكة من النقاط المتصلة إلى مجموعتين متساويتين مع تقليل الروابط بينهما إلى الحد الأدنى. قاموا بمحاكاة سلوك الحاسوب الكمي على عدد كبير من الشبكات العشوائية، بدءاً من الأنظمة الصغيرة المكونة من ست نقاط وصولاً إلى الأنظمة الأكبر المكونة من اثنتي عشرة نقطة. ومن خلال تشغيل هذه المحاكاة لفترات طويلة جداً، استطاعوا مراقبة كيفية تطور احتمالية عثور الحاسوب على أفضل الحلول. واكتشفوا أن طريقة الجزاء، عند ضبطها بتكلفة جزاء كافية، تبدأ في التصرف بشكل ملحوظ مثل الطريقة المقيدة. فكلما أصبح الجزاء كبيراً وطالت مدة المحاكاة، تقارب أسلوب اختيار الحاسوب للحلول في الطريقة القائمة على الجزاء مع أسلوب الحاسوب المقيد. تنتهي كلتا الطريقتين بتفضيل نفس الحلول المحددة وتجاهل الحلول الأخرى نفسها، بدلاً من توزيع خياراتهما بشكل متساوٍ.
هذا التقارب ليس مصادفة، بل هو نتيجة لآلية فيزيائية عميقة. فعندما يكون الجزاء مرتفعاً، تُجبر الطريقة القائمة على الجزاء على البقاء قريبة من الحلول الصالحة. ومع ذلك، للانتقال بين هذه الحلول الصالحة، يجب على الحاسوب زيارة حالات غير صالحة تكسر القاعدة لفترة وجيزة. وجد الباحثون أن هذه الزيارات الافتراضية القصيرة للحالات غير الصالحة تخلق تأثيراً ثانوياً يحاكي قواعد الحركة في الطريقة المقيدة. الأمر كما لو أن طريقة الجزاء، من خلال محاولتها تجنب كسر القاعدة، تتعلم بالصدفة التحرك بنفس الطريقة التي صُممت بها الطريقة التي لا تكسر القاعدة أبداً. ومن خلال التحليل الرياضي، أظهر الفريق أن قوة هذا التقليد تعتمد على النسبة بين تكلفة الجزاء وفروق الطاقة في المشكلة. وعندما يكون الجزاء كبيراً بما يكفي، يتقلص الفرق بين الطريقتين بسرعة، متبعاً نمطاً يمكن التنبؤ به حيث ينخفض الخطأ مع زيادة الجزاء.
تؤكد الدراسة أنه على الرغم من قدرة كلتا الطريقتين على إنتاج نتائج منحازة متشابهة، إلا أن أياً منهما لا تضمن توزيعاً عادلاً تماماً لجميع الحلول. فحتى مع الطريقة المقيدة، المصممة للبقاء داخل المنطقة الصالحة، لا يزال الحاسوب يظهر تفضيلاً لبعض الحلول على غيرها. وهذا يشير إلى أن الانحياز هو سمة متأصلة في كيفية اختيار التقلبات الكمية للحالات، وليس مجرد خلل في كيفية كتابة القواعد. تقدم هذه النتائج منظوراً جديداً للمهندسين الذين يبنون هذه الأنظمة: فبدلاً من النظر إلى طريقة الجزاء كحل مؤقت ضعيف، يمكن اعتبارها وسيلة لهندسة حركات كمية محددة تطابق النهج الأكثر تطوراً. وبينما أظهرت عمليات المحاكاة هذا الاتفاق بوضوح للأنظمة التي تم اختبارها، يشير الباحثون إلى أن الأنظمة الأكبر قد تفرض تعقيدات جديدة. وفي نهاية المطاف، يوفر هذا العمل خارطة طريق واضحة لكيفية وصول استراتيجيتين كميتين مختلفتين إلى نفس الوجهة، مما يقدم أساساً مشتركاً لفهم كيفية تحسين أخذ عينات من مشهد الحلول المثلى الشاسع.
ملخص تقني: مراسلة أخذ العينات للحالة الأرضية بين التلدين الكمي القائم على الجزاء والتلدين الكمي المقيد
بيان المشكلة التلدين الكمي (QA) هو خوارزمية استدلالية لإيجاد الحالة الأرضية لنماذج إيسينج (Ising models)، وهو قابل للتطبيق على العديد من مشكلات التحسين التوليفي (COPs). وبينما يكون العثور على حل أمثل واحد كافيًا في كثير من الأحيان، تتطلب بعض التطبيقات أخذ عينات من مجموعة الحالات الأرضية المتعددة (degenerate ground states). ومن الناحية المثالية، ينبغي أن يكون أخذ العينات هذا منتظمًا؛ ومع ذلك، يظهر التلدين الكمي عادةً "أخذ عينات غير عادل"، حيث يتم أخذ عينات من الحالات الأرضية المتعددة باحتمالات غير منتظمة. ينشأ هذا الانحياز من هاميلتوني المحرك المتبقي بالقرب من نهاية عملية التلدين، والذي يعمل كاضطراب داخل فضاء الحالة الأرضية المتعددة.
بالنسبة لمشكلات التحسين التوليفي ذات قيود الكاردينالية (تثبيت عدد الدورات للأعلى)، توجد استراتيجيتان رئيسيتان للتنفيذ:
التلدين الكمي القائم على الجزاء (Penalty-Based QA): يستخدم محرك مجال مستعرض قياسي ويضيف حد جزاء إلى هاميلتوني المشكلة لتثبيط انتهاكات القيود.
التلدين الكمي المقيد (CQA): يستخدم هاميلتوني محرك (مثل محرك XY كامل الاتصال) يتبادل مع مؤثر القيد، مما يضمن بقاء النظام ضمن الفضاء الممكن طوال عملية التطور.
بينما تختلف هاتان الطريقتان في هياكل المحرك وآليات الانتقال، إلا أنه كان من غير الواضح كيف تؤثر هذه الاختلافات على توزيعات الحالة الأرضية الشرطية، وتحديدًا ما إذا كان يمكن لطريقة الجزاء إعادة إنتاج انحياز أخذ العينات الخاص بـ CQA تحت ظروف معينة.
المنهجية يتقصى المؤلفون هذه المراسلة باستخدام مشكلة تقسيم الرسم البياني (Graph Bipartitioning Problem - GBP) مع قيد التوازن كحالة دراسية ممثلة. تستخدم الدراسة مزيجًا من:
المحاكاة العددية للأنظمة المغلقة: حل معادلة شرويدنجر لنماذج GBP عشوائية (تم إنشاؤها عبر نموذج إردوس-ريني) مع أحجام أنظمة N=6,8,10,12. تقارن عمليات المحاكاة بين التلدين الكمي القائم على الجزاء (مع معاملات جزاء متغيرة μ) وبين CQA (باستخدام محرك XY) عبر نطاق من أزمنة التلدين (T).
نظرية الاضطراب للاشتقاق (Degenerate Perturbation Theory): اشتقاق الهاميلتونيات الفعالة لكلا الطريقتين بالقرب من نهاية عملية التلدين لتفسير سلوكيات أخذ العينات الملحوظة تحليليًا.
المقاييس: تقيم الدراسة احتمالية الحالة الأرضية، وانتظام التوزيع الشرطي (مقاسًا عبر تباعد جينسن-شانون عن التوزيع المنتظم)، والاتفاق بين الطريقتين (مقاسًا عبر تباعد جينسن-شانون بين توزيعاتهما الشرطية).
المساهمات والنتائج الرئيسية
انحياز أخذ العينات في كلتا الطريقتين:
يظهر كل من التلدين الكمي القائم على الجزاء وCQA أخذ عينات غير منتظم للحالات الأرضية المتعددة.
في التلدين الكمي القائم على الجزاء، يؤدي زيادة معامل الجزاء عمومًا إلى تقليل انحياز أخذ العينات (جعل التوزيع أكثر انتظامًا) ولكنه لا يقضي عليه تمامًا في الأنظمة الأكبر.
في CQA، وبالرغم من ضمان الإمكانية (feasibility)، فإن أخذ العينات أيضًا غير منتظم، حيث يزدزد الانحياز مع حجم النظام N وزمن التلدين T.
مراسلة التوزيعات:
تجد الدراسة أنه بالنسبة لمعاملات جزاء كافية وأزمنة تلدين طويلة، فإن توزيع الحالة الأرضية الشرطي للتلدين الكمي القائم على الجزاء يتقارب مع توزيع CQA.
يتم قياس هذا الاتفاق عبر تباعد جينسن-شانون (JS) بين التوزيعين، والذي يتناقص مع زيادة الجزاء.
التفسير الاضطرابي:
يوضح المؤلفون أن هذا التقارب مفسر بهيكل الهاميلتونيات الفعالة.
CQA: يعمل محرك XY مباشرة داخل فضاء الحالة الأرضية الممكنة عند الدرجة الأولى، مما يولد تفاعلات تبادل الدورات (spin-exchange).
التلدين الكمي القائم على الجزاء: لا يقوم محرك المجال المستعرض بربط الحالات الممكنة مباشرة (الحد من الدرجة الأولى يتلاشى). ومع ذلك، عند الدرجة الثانية، تولد قلبات الدورات الفردية الافتراضية نحو حالات غير ممكنة تفاعلًا فعالًا.
المراسلة: في حد الجزاءات الكبيرة (μ)، يصبح التفاعل الفعال من الدرجة الثانية في التلدين الكمي القائم على الجزاء متناسبًا مع محرك XY المسقط لـ CQA. تحديدًا، يتناسب التفاعل الفعال مع ΓQA2/(2μ)، وهو ما يطابق شكل محرك CQA المسقط على الفضاء الممكن.
وبناءً على ذلك، إذا كان للمؤثر XY المسقط أدنى حالة ذات قيمة ذاتية فريدة ضمن قطاع التماثل ذي الصلة، فإن كلتا الطريقتين ستختاران نفس الحالات الأرضية، مما يؤدي إلى انحيازات أخذ عينات مماثلة.
تدرج الاتفاق:
تظهر النتائج العددية أن تباعد JS بين الطريقتين يتناقص تقريبًا مع مربع مقلوب النسبة r=4μ/Δmax، حيث Δmax هو أقصى فرق طاقة بين الحالة الممكنة المثلى وأقرب حالة غير ممكنة يمكن الوصول إليها عبر قلب دورة واحدة.
هذا التدرج r−2 يتوافق مع التحليل الاضطرابي، حيث تكون التصحيحات النسبية للمؤثر الفعال من الرتبة r−1، مما يؤدي إلى تباعد من الرتبة r−2.
الأهمية والادعاءات يدعي البحث إنشاء مراسلة نظرية وعددية بين تنفيذين مختلفين للتلدين الكمي للمشكلات المقيدة. تكمن الأهمية الأساسية في إثبات أن:
الآليات المجهرية المختلفة (المجال المستعرض مع الجزاءات مقابل محرك XY المقيد) يمكن أن تولد نفس التفاعل الفعال من الدرجة الأولى داخل فضاء متعدد الحالات.
يمكن للتلدين الكمي القائم على الجزاء إعادة إنتاج انحياز أخذ العينات الخاص بـ CQA بفعالية عندما يكون الجزاء كبيرًا بما يكفي، بشرط أن يكون زمن التلدين كافيًا للوصول إلى الحالة الأرضية.
تمتد هذه المراسلة إلى غيرها من قيود الوزن المتساوي (ثبات المغناطيسية) تحت نفس الظروف الاضطرابية.
يخلص المؤلفون إلى أن هذا الاكتشاف يوفر مثالاً ملموسًا لكيفية توليد عمليات تنفيذ مختلفة للقيود لنفس عملية اختيار الحالة عبر التقلبات الكمية. ويقترحون أن هذا المنظور يمكن أن يوجه تصميم الخلاطات (mixers) والهاميلتونيات لأهداف أخذ العينات التي تتجاوز مجرد تقليل الطاقة، رغم ملاحظتهم أن توسيع هذه النتائج لتشمل الخوارزميات القائمة على البوابات أو خوارزمية QAOA ذات العمق المحدود يتطلب مزيدًا من الاستقصاء حول ترتيب النبضات والمعلمات المتغيرة. لا يدعي البحث أن أيًا من الطريقتين تحقق أخذ عينات منتظمًا، بل يشيران إلى أنهما تشتركان في آلية مشتركة لأخذ العينات المنحاز.