Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization

ملخص تقني: الجمع الخطي للوحدات المعتمد على فوريه بكفاءة وتطبيقاته في التحسين الكمي

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

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

1. الجمع الخطي للوحدات بدون كيوبت مساعد لأخذ العينات: على عكس تطبيقات LCU القياسية التي تستخدم كيوبت مساعداً لتنفيذ الجمع الخ meminta للوحدات بشكل متماسك (مما يتطلب عمليات محكومة)، يركز هذا العمل على التطبيقات القائمة على أخذ العينات. من خلال إسقاط عوامل الإشارة المرتبطة بـ "تفكيك الاحتمالية شبه الكمية" (QPD) واستبدال الكيوبت المساعد بالعشوائية الكلاسيكية، يلغي هذا الأسلوب الحاجة إلى الكيوبتات المساعدة والبوابات المحكومة. هذا يحول التنفيذ إلى خليط احتمالي من دوائر أبسط، حيث يتم قياس عبء أخذ العينات بمعامل $\Gamma$.
2. تفكيك فوريه للوحدات القطرية: بالنسبة للوحدات القطرية (الشائعة في دالات التكلفة وحدود الجزاء)، يستخدم المؤلفون تحويل فوريه المتقطع. يتم تفكيك وحدة مستهدفة $U_f(\gamma) = \sum_x e^{-i\gamma f(g(x))} |x\rangle\langle x|$ إلى مجموعة من الوحدات الأبسط $V(\theta_j)$، والتي غالباً ما تكون مجرد طبقات من بوابات $R_Z$ أحادية الكيوبت. تُشتق المعاملات من تحويل فوريه للدالة التي تُعرف الوحدة. هذا النهج يستبدل التفاعلات متعددة الكيوبتات المعقدة (مثل جزاءات التربيع التي تتطلب $O(n^2)$ من البوابات) بطبقات أحادية الكيوبت مقابل عبء أخذ عينات $\Gamma \le m+1$.
3. التوسع إلى الوحدات غير القطرية المتبادلة التماثل: يتم تعميم إطار العمل ليشمل الوحدات غير القطرية، مثل مُقلب XY (XY-mixer) كامل الاتصال المستخدم للحفاظ على قيود الوزن الهامينج (Hamming weight). بالاستفادة من ثنائية شور-وايلد (Schur-Weyl duality) ونظرية التمثيل لـ $SU(2)$، يعبر المؤلفون عن الوحدات المتبادلة التماثل كتركيب خطي مستمر من الدورات الجماعية أحادية الكيوبت $R(g)^{\otimes n}$. يتيح ذلك تنفيذ مُقلبات غير محلية للغاية باستخدام بوابات أحادية الكيوبت فقط، مع عبء أخذ عينات نظري محدود بـ $O(n^3)$.
4. الارتباط بالاسترخاء اللاغرانجي: يضع البحث رابطاً رسمياً بين جزاءات فوريه الكمية والاسترخاء اللاغرانجي الكلاسيكي. وقد أظهر أن تحسين فرع واحد من تفكيك LCU يكافئ تحسين معامل لاغرانج، مما يوفر منظوراً موحداً لمعالجة القيود.

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

• تطوير إطار العمل: تقديم إطار عمل LCU يعتمد على فوريه وخالٍ من الكيوبت المساعد، يقوم بتفكيك فئات واسعة من الوحدات القطرية وغير القطرية إلى مجموعات من طبقات البوابات أحادية الكيوبت.
• كفاءة الأجهزة: إثبات أنه يمكن استبدال العمليات المعقدة ذات الاتصال "الكل-إلى-الكل" (مثل جزاءات الكاردينالية ومقلبات XY) بدوائر أبسط بكثير، وذلك عبر المقايضة بين عمق الدائرة والاتصال وبين عبء أخذ عينات متعدد الحدود.
• الضمانات النظرية: تقديم حدود أداء صارمة، تظهر أن احتمال أخذ عينات لسلاسل بت (bitstrings) عالية الجودة في نهج LCU مقيد من أسفل بالاحتمالية المتماسكة مقسومة على $\Gamma$. كما يربط البحث بين تحسين القيمة المتوقعة المشروطة (CVaR) وهذه الحدود.
• التحقق من القابلية للتوسع: التطبيق الناجح لإطار العمل على مشكلة أدنى رسم بياني $k$-subgraph لنماذج تصل إلى 106 كيوبت على أجهزة IBM Quantum الحقيقية، وهو مقياس كان مستعصياً سابقاً على عمليات التنفيذ المتماسكة بالكامل لهذه القيود.

النتائج التجريبية
تحقق المؤلفون من نهجهم من خلال محاكاة الحالة المتجهة الدقيقة لنموذج مكون من 12 عقدة، وتجارب واسعة النطاق على جهاز بـ 106 كيوبت:

• محاكاة الـ 12 عقدة: أظهرت المقارنات بين QAOA المتماسك بالكامل ونهج LCU المعتمد على فوريه أنه بينما كانت القيم المتوقعة الخام لدوائر LCU أقل (بسبب عبء أخذ العينات)، فإن تحسين دائرة أساس واحدة لـ LCU (نموذج متغير مشتق من LCU) أعطى أعلى احتمال لأخذ الحلول المثلى، متفوقاً على الخط المرجعي المتماسك في مقاييس محددة.
• تجربة الأجهزة بـ 106 عقدة: تم تنفيذ نهجي الجزاء والمقلب المعتمد على LCU على رسم بياني (heavy-hex) مكون من 106 كيوبت (تم توسيعه عبر طبقات SWAP). أظهرت النتائج أن عبء أخذ العينات العملي كان أقل بكثير من الحدود النظرية في الحالة الأسوأ ($\Gamma \approx 10^4$). نجح نموذج LCU ذو الفرع الواحد في إيجاد حلول عالية الجودة (تصل إلى 81 حافة في الرسم البياني الأدنى) باحتمالات عملية تتراوح بين 2.7% و4.8%، مما يشير إلى جدوى الطريقة للمشكلات الكبيرة.
• مُقلب XY مقابل الجزاء: تفوق نهج LCU المعتمد على مُقلب XY بشكل عام على نهج الجزاء، خاصة عند استخدام دائرة أساس واحدة محسنة، مما يشير إلى أن المُقلبات التي تحافظ على القيود أكثر فعالية عند دمجها مع هذا التفكيك.

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