⚛️ الفيزياء الكمومية

QASPA-MaxCut on Unweighted Graphs: Edge Encoding and QAOA Restarts

تقدم هذه الورقة QASPA-MaxCut، وهو دارة إزاحة طور (shift-phase circuit) تقوم بتشفير حواف الرسم البياني عبر دورات $R_y$ محكومة، وتثبت من خلال عمليات محاكاة دقيقة على رسوم بيانية متنوعة غير موزونة أن نهج الزاوية الثابتة الخاص بها مع مرحلة اختيار كلاسيكية يتفوق على خوارزمية QAOA ذات العمق الواحد حتى عندما تستخدم الأخيرة عمليات إعادة تشغيل كلاسيكية متعددة.

المؤلف الأصلي: Dmytro Sapozhnyk

نُشر 2026-11-05

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

CC BY 4.0

المؤلف الأصلي: Dmytro Sapozhnyk

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

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

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

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

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

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

ملخص تقني: خوارزمية QASPA-MaxCut على الرسوم البيانية غير الموزونة

بيان المشكلة
تتناول الورقة البحثية اختناقات الأداء في خوارزمية التحسين التقريبي الكمي (QAOA) في عصر الأجهزة الكمية متوسطة الحجم ذات الضجيج (NISQ). وبينما تُعد QAOA نهجاً تباينياً نموذجياً للتحسين التوليفي (تحديداً لمسألة Max-Cut)، فإن أداءها المُبلغ عنه يعتمد بشكل كبير على عملية التحسين الكلاسيكية في الحلقة الخارجية للمعلمات التباينية. ومن الناحية العملية، فإن عمق البوابات المحدود، والضجيج، والتكلفة الحسابية لعمليات تقييم الدارات المتكررة، كلها عوامل تقيد القدرة على إيجاد المعلمات المثلى. يهدف المؤلف إلى عزل تأثير ميزانية البحث الكلاسيكي من خلال مقارنة خوارزمية QAOA قياسية بعمق واحد مقابل بناء دائرة جديد، وهو QASPA-MaxCut، الذي يدمج بنية الرسم البياني مباشرة في "الأنزات" (ansatz) الخاص بالدائرة لتقليل الاعتماد على ضبط المعلمات.

المنهجية
تقدم الدراسة QASPA-MaxCut، وهي دائرة تحول الطور (shift-phase) مصممة للرسوم البيانية غير الموزونة. وخلافاً لـ QAOA القياسية، التي تبادل بين مؤثر مسألة عالمي ( $e^{-i\gamma H_C}$ ) ومُخلط مجال عرضي عالمي ( $e^{-i\beta \sum X_i}$ )، تستبدل QASPA المُخلط العالمي بدوارات محكومة موضعية لكل حافة.

بناء الدائرة: تبدأ أنزات QASPA بطبقة هادامارد (Hadamard) لإنشاء تراكب منتظم. ولكل حافة $(i, j)$ في الرسم البياني، يتم تطبيق كتلة محددة: $CX_{i,j} R_y^{(j)}(\theta_{ij}) CX_{i,j}$ .
ترميز الحواف: يتم تثبيت زاوية الدوران $\theta_{ij}$ عالمياً عند $\alpha = \pi/4$ لجميع الحواف في الحالة غير الموزونة. تعمل الكتلة جبرياً كـ $\exp(-i \frac{\alpha}{2} Z_i Y_j)$ ، مما يعيد توزيع السعة بين التكوينات المقطوعة وغير المقطوعة للحافة المزدوجة المحددة، بدلاً من تطبيق طور قطري.
البروتوكول التجريبي:
- الرسوم البيانية: تستخدم الدراسة محاكاة دقيقة لحالة المتجه (state-vector) على نماذج صغيرة ( $n=8$ رؤوس). تشمل الرسوم البيانية هياكل العمود الفقري المعزز بالاتصال (connected backbone-augmented) مع احتمالات حافة إضافية $p_{edge} \in \{0.1, 0.3, 0.5, 0.7\}$ و19 طوبولوجيا مخصصة محددة يدوياً.
- خط الأساس QAOA: يتم تحسين دائرة QAOA بعمق واحد باستخدام مُحسن Nelder-Mead محلي. ويُقاس الأداء عبر منحنى "أفضل من- $k$ " (best-of- $k$ )، حيث تمثل $k$ عدد عمليات إعادة التشغيل العشوائية المستقلة (تتراوح من 1 إلى 10).
- تقييم QASPA: يتم تشغيل QASPA مع الزاوية الثابتة $\alpha = \pi/4$ دون بحث في الحلقة الخارجية. ويُبلغ عن النتيجة كـ نسبة الاختيار الكلاسيكي: حيث تختار الخوارزمية أكثر أربعة سلاسل بت (bit strings) ذات احتمالات مخرجات عالية، وتقيمها مقابل هدف Max-Cut، وتُبلغ عن أفضل قطع (cut) تم العثور عليه من بينها.
- القراءة (Readout): بالنسبة للطوبولوجيا المخصصة، يتم إجراء فحص قراءة بطلقات محدودة باستخدام ميزانية طلقات تكيفية ( $N_{shots} = \lceil 0.03047 \cdot 2^n + 1016.2 \rceil$ ) للتحقق من الاستقرار تحت ضجيج أخذ العينات.

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

الاشتقاق الجبري: توفر الورقة الاشتقاق الجبري الدقيق لكتلة حافة QASPA، موضحة كيف تقوم تسلسلات $CX-R_y-CX$ بإعادة توزيع السعة بين حالات القطع وعدم القطع، مما يدمج بنية الحافة بفعالية في خطوة الخلط.
مثال عملي: تم تقديم مسار رياضي وعددي كامل وقابل للتتبع لرسم بياني غير موزون مكون من أربعة رؤوس، يوضح جدول الحواف، وتطور الحالة، واحتمالات المخرجات للتحقق من صحة البناء.
مقارنة مضبوطة: تؤسس الدراسة لإطار تجريبي قابل للتكرار يقارن بين دائرة ذات زاوية ثابتة وبنية مدمجة (QASPA) وبين نموذج تبايني (QAOA) مع ميزانية بحث كلاسيكي شفافة. هذا يعزل "تأثير إعادة التشغيل" لتحديد مقدار التحسين الكلاسيكي المطلوب للمنافسة مع نهج الزاوية الثابتة.

النتائج

جودة المرشحين: في النماذج الصغيرة المختبرة، تضع حالة QASPA ذات الزاوية الثابتة الحلول المثلى (أو القريبة من المثلى) لمسألة Max-Cut ضمن أعلى أربعة سلاسل بت من حيث الاحتمالية. وبناءً على ذلك، تكون نسبة الاختيار الكلاسيكي لـ QASPA مرتفعة للغاية، حيث تتراوح بين 0.955 و1.000 عبر مجموعات الرسوم البيانية.
حساسية QAOA: أداء QAOA بعمق واحد حساس للغاية لعدد عمليات إعادة التشغيل الكلاسيكية. وبينما يتحسن معدل التقريب المتوقع مع زيادة عمليات إعادة التشغيل (على سبيل المثال، يرتفع من ~0.71 إلى ~0.79 للرسوم البيانية المتفرقة)، إلا أنه يظل باستمرار أقل من درجة اختيار QASPA ضمن ميزانية الـ 10 عمليات إعادة تشغيل المختبرة.
الاستقرار: تُظهر فحوصات القراءة بطلقات محدودة على الطوبولوجيا المخصصة أن درجة اختيار QASPA تظل مستقرة (متوسط 1.000 مع انحراف معياري صفر) تحت ميزانية الطلقات المقررة، مما يؤكد قوة قاعدة اختيار المرشح لهذه الحالات المحددة.
حساسية ترتيب الحواف: تشير الدراسة إلى أن QASPA ليست مستقلة عن الترتيب بسبب كتل الحواف غير التبادلية. ومع ذلك، فإن التبديلات العشوائية لترتيب الحواف في الاختبارات أسفرت عن متوسطات مجموع قريبة من القيم الأصلية الثابتة، مما يشير إلى بعض المرونة في الاختبارات صغيرة النطاق.

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

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

أبحاث مشابهة