Fault-tolerant cost of shallow QAOA on near-symmetric optimization problems

ملخص تقني: التكلفة المتحملة للأخطاء لخوارزمية QAOA ضحلة على مسائل التحسين شبه المتماثلة

بيان المشكلة
أثبت مونتانارو وجو [1] أن دوائر خوارزمية التقريب الكمي للتحسين (QAOA) بعمق واحد يمكنها إيجاد الحل المزروع لبعض مسائل تحقيق القيود (CSPs) شبه المتماثلة باحتمالية ثابتة $\Omega(1)$. وفي المقابل، تُظهر التطبيقات الصريحة لهذه المسائل توسعاً زمنياً يبدو أسياً للمحللات الكلاسيكية القوية. وبينما يشير هذا إلى تسريع تجريبي أسي، فإن متطلبات الموارد لتنفيذ هذه الدوائر على الحواسيب الكمية المبكرة المتحملة للأخطاء تظل غير واضحة. تحتوي هاميلتونيّات التكلفة لهذه المسائل على $\Theta(n^\ell$ من القيود (حيث $\ell \ge 5$)، مما يعني أن عدد بوابات غير كليفورد (non-Clifford) يتوسع بمعدل $\tilde{O}(n^\ell)$ عند تجميعها باستخدام تركيب Clifford+$T$ القياسي. هذا التوسع يضع أحجام المسائل ذات الصلة خارج نطاق الوصول لأجهزة الحوسبة الكمية القريبة من المستقبل (near-term) المتحملة للأخطاء.

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

1. مطابقة الطور وتوسع الزاوية: يعيد المؤلفون النظر في شرط مطابقة الطور المطلوب لضمان احتمالية نجاح ثابتة. بالنسبة لدوال التكلفة المتماثلة تحت تبديلات المتغيرات بالنسبة لحل مزروع، يجب أن تتوسع زاوية فاصل الطور $\gamma$ كـ $\gamma = \Theta(n^{1-\ell})$ لضمان التداخل البناء لغلافات هامينج (Hamming shells) المهيمنة.
2. تركيب الزوايا الصغيرة: بالاستفادة من حقيقة أن $\gamma$ تتقلص مع حجم النظام، يطبق المؤلفون تقنيات تركيب دوران Clifford+$T$ للزوايا الصغيرة (تحديداً تلك الخاصة بـ Bothe وآخرون [9]). يستخدمون صياغات الاحتمالية شبه العشوائية ومزيج الاحتمالات حيث يتم تقريب الدورات ذات الزوايا الصغيرة بالهوية (identity) باحتمالية عالية، بينما تتطلب نسبة صغيرة فقط من الدورات تركيباً غير كليفورد.
3. تجميع القيود الصريح وتحليل التسرب: ينتقل المؤلفون من نموذج أوراكل القيمة (حيث يتم الاستعلام فقط عن قيم التكلفة $C(x)$) إلى نموذج قائمة القيود الصريح المطلوب لتجميع الدائرة. يحللون معاملات فوريه لدالة التكلفة المستمدة من قائمة القيود الصريحة لتحديد ما إذا كانت عملية التجميع تكشف عن الحل دون قصد.
4. بناء حالات مخادعة: لاختبار متانة التسريع ضد الهجمات الكلاسيكية التي تستغل البنية الصريحة، يبني المؤلفون حالات "غير مزروعة" شبه متماثلة. تتميز هذه الحالات بغلاف هامج أمثل ضخم أسياً يحتوي على مسألة فرعية (sub-problem) من فئة NP-hard، مع تصميم مشهد التكلفة بحيث يوقع خوارزميات البحث المحلي في فخ.

المساهمات والنتائج الرئيسية

• التوسع التربيعي لغير كليفورد: النتيجة الأساسية هي أن تكلفة غير كليفورد لكل دائرة لـ QAOA بعمق واحد على هذه الحالات تنخفض إلى $\tilde{O}(n^2)$، بشكل مستقل عن موضعية القيود $\ell$ ومعدل التخلخل (sparsification rate). يحدث هذا الانخفاض لأن إجمالي كتلة الطور ($m\gamma$، حيث $m$ هو عدد القيود) يتوسع خطياً مع $n$، وتعتمد تكاليف تركيب الزوايا الصغيرة على مربع كتلة الطور هذه. وبناءً على ذلك، فإن أحجام المسائل التي كانت تُعتبر سابقاً غير مجدية بسبب التوسع $\tilde{O}(n^\ell)$ تصبح قابلة للتنفيذ على الأجهزة المبكرة المتحملة للأخطاء (انظر الشكل 2).
• التسرب الكلاسيكي في العائلات المزروعة: بالنسبة للعائلات المزروعة المدروسة في المرجع [1]، يوضح المؤلفون أن قائمة القيود الصريحة المطلوبة للتجميع تكشف عن الحل المزروع. إن شرط مطابقة الطور ($F'(1/2) \neq 0$) يحدد إشارات معاملات الدرجة الأولى (المجالات المحلية) لدالة التكلفة. هذه الإشارات تكشف مباشرة عن الحل المزروع $s$ عبر مسح خطي بسيط للزمن للبحث في قائمة القيود. وبالتالي، بينما تنجح خوارزمية QAOA باحتمالية ثابتة، فإن التنفيذ الصريح يجعل المسألة تافهة كلاسيكياً.
• وجود حالات غير مزروعة صعبة: يوضح المؤلفون أن نظام الزوايا الصغيرة والتوسع $\tilde{O}(n^2)$ لا يعتمدان على وجود حل مزروع. فقد بنوا حالات شبه متماثلة بدون حل مزروع حيث:
  • يقع الأمثل العالمي ضمن غلاف هامج ضخم أسياً.
  • إيجاد الأمثل الدقيق داخل ذلك الغلاف هو مسألة NP-hard.
  • مشهد التكلفة "مخادع"، مما يوقع خوارزميات البحث المحلي والمحللات العامة لـ MaxSAT في فخ في قطاعات فرعية غير مثالية مفصولة بحواجز طاقة عالية.
  • QAOA بعمق واحد عند الزاوية الصغيرة يركز مخرجاته على الغلاف الأمثل بنفس تكلفة غير كليفورد $\tilde{O}(n^2)$.
  • في هذه الحالات غير المزروعة، تكون معاملات الدرجة الأولى موحدة ولا تكشف عن الحل، مما يحافظ على صعوبة المسألة للخوارزميات الكلاسيكية التي لا تستغل بنية التماثل المحددة.

الأهمية
تثبت هذه الورقة أن التسريع التجريبي لـ QAOA منخفض العمق على المسائل شبه المتماثلة يمكن تحقيقه بموارد أقل بكثير من تحمل الأخطاء مما كان يُفترض سابقاً، وتحديداً $\tilde{O}(n^2)$ من بوابات غير كليفورد بدلاً من $\tilde{O}(n^\ell)$. وهذا يجعل هذه الدوائر الضحلة ذات الزوايا الصغيرة هدفاً واقعياً لأجهزة الحوسبة الكمية المبكرة المتحملة للأخطاء.

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