A mixed-precision quantum-classical algorithm for solving linear systems

إليك ملخص تقني مفصل للورقة البحثية بعنوان "خوارزمية هجينة بين الحوسبة الكمومية والكلاسيكية لحل الأنظمة الخطية."

1. بيان المشكلة

تتناول الورقة البحثية مشكلة حوسبية أساسية تتمثل في حل نظام من المعادلات الخطية ($Ax = b$) حيث $A$ مصفوفة غير منفردة و$b$ متجه. وبينما تُعد الخوارزميات الكلاسيكية (مثل حذف غاوس) ناضجة للغاية، توفر الخوارزميات الكمومية إمكانية تحقيق تسريع أسي في ظل ظروف محددة.

ومع ذلك، تواجه النهج الكمومية الحالية، وتحديداً تحويل القيم المفردة الكمومي (QSVT)، قيوداً كبيرة:

• كثافة الموارد: يتطلب تحقيق دقة عالية (على سبيل المثال، خطأ $< 10^{-5}$) تقريبات متعددة الحدود ذات درجة عالية، مما يؤدي إلى دوائر كمومية عميقة ومتطلبات موارد مفرطة.
• الحساسية للشرطية: تتناسب التعقيدات بشكل سيئ مع رقم الشرط ($\kappa$) للمصفوفة.
• قيود الأجهزة: يتجاوز العمق المطلوب لـ QSVT عالي الدقة قدرات الأجهزة الكمومية الحالية ذات المقياس المتوسط المشوبة بالضجيج (NISQ)، مما يستدعي سياق الحوسبة الكمومية واسعة النطاق (LSQ).

التحدي الجوهري هو تقليل التكلفة الكمومية مع الحفاظ على دقة حل مقبولة.

2. المنهجية

يقترح المؤلفون خوارزمية هجينة (كمومية-كلاسيكية) تجمع بين طريقة QSVT والتحسين التكراري مختلط الدقة. يجمع هذا النهج بين سرعة الحوسبة الكمومية منخفضة الدقة ودقة الحوسبة الكلاسيكية عالية الدقة.

الخوارزمية الجوهرية (الخوارزمية 2)

تتبع العملية الخطوات التالية:

1. الحل الأولي منخفض الدقة ($x_0$):
   • حساب حل تقريبي أولي باستخدام QSVT على وحدة معالجة كمومية (QPU).
   • تستخدم هذه الخطوة دقة منخفضة ($\epsilon_l$)، مما يسمح بتقريب متعدد حدود ذي درجة أقل وعمليات بوابات كمومية أقل.
   • تتعامل الـ QPU مع ترميز الكتلة (block-encoding) لـ $A^\dagger$ وتطبيق التحويل.
2. حلقة التحسين التكراري:
   • حساب المتبقي (CPU): حساب المتبقي $r_i = b - Ax_i$ باستخدام دقة عالية (معالج مركزي كلاسيكي CPU).
   • حساب التصحيح (QPU): حل نظام التصحيح $Ae_i = r_i$ باستخدام طريقة QSVT مرة أخرى، ولكن لا تزال عند الدقة المنخفضة $\epsilon_l$.
   • التحديث (CPU): تحديث الحل $x_{i+1} = x_i + e_i$ باستخدام دقة عالية.
3. الإنهاء: تستمر الحلقة حتى يلبي المتبقي المقياس $\omega = \|b - A\tilde{x}\| / \|b\|$ الدقة المستهدفة $\epsilon$.

التكيفات التقنية الرئيسية

• التطبيع (Normalization): بما أن الخوارزميات الكمومية تتطلب حالات مطبعة، يتم تطبيع المتجه $b$ قبل الإدخال. ويتم استعادة المعيار $\|x\|$ على الـ CPU عن طريق حل مسألة تقليل بعد قياس QSVT.
• تدفق البيانات الهجين: يتم نقل المصفوفة $A$ (عبر دوائر ترميز الكتلة) مرة واحدة فقط. في التكرارات اللاحقة، يتم فقط نقل متجه المتبقي $r_i$ (المشفر كدائرة تحضير حالة) إلى الـ QPU، مما يقلل من عبء الاتصالات.
• تقريب متعدد الحدود: يتم تقريب الدالة العكسية باستخدام كثيرات حدود تشيبيشيف. يتم تكييف درجة متعدد الحدود مع الدقة المنخفضة $\epsilon_l$ بدلاً من الدقة النهائية $\epsilon$، مما يقلل بشكل كبير من عمق الدائرة.

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

أ. التحليل النظري

• إثبات التقارب: يثبت المؤلفون (النظرية III.1) أن الخوارزمية تتقارب إذا كان $\epsilon_l \kappa < 1$. يتقلص المتبقي المقياس بمعامل $\epsilon_l \kappa$ في كل تكرار.
• حد التكرار: عدد التكرارات المطلوبة للوصين إلى الدقة المستهدفة $\epsilon$ محكوم بـ $\lceil \log(\epsilon) / \log(\epsilon_l \kappa) \rceil$.
• تقليل التعقيد:
  • التكلفة الكمومية: يتم تقليل التعقيد الإجمالي لأن عدد العينات المطلوبة يتناسب مع $O(1/\epsilon_l^2)$ (دقة أقل) بدلاً من $O(1/\epsilon^2)$. علاوة على ذلك، تعتمد درجة متعدد الحدود (وبالتالي عدد استدعاءات ترميز الكتلة) على $\log(\kappa/\epsilon_l)$ بدلاً من $\log(\kappa/\epsilon)$.
  • التكلفة الكلاسيكية: يتم إجراء العمليات الكلاسيكية (حساب المتبقي، التحديث) بدقة عالية ولكنها رخيصة حوسبياً مقارداً بالمحلل الكمومي.

ب. مقارنة التعقيد

تقدم الورقة تفصيلاً دقيقاً (الجدول I) يوضح أنه بالنسبة للدقات المستهدفة العالية ($\epsilon \ll \epsilon_l$)، فإن النهج مختلط الدقة أكثر كفاءة بكثير من تشغيل QSVT مباشرة بدقة عالية. تأتي التوفيرات من:

1. عدد أقل من عمليات تنفيذ الدائرة الكمومية (العينات).
2. درجات أقل لمتعدد الحدود (عدد أقل من استدعاءات ترميز الكتلة).

ج. التنفيذ

قام المؤلفون بتنفيذ الخوارزمية باستخدام حزمة البرمجيات الكمومية myQLM (محاكي قائم على Python). وقد استخدموا:

• تحضير الحالة القائم على الأشجار.
• تقنيات ترميز الكتلة للمصفوفات ثلاثية الأقطاب (معادلة بواسون) والمصفوفات العشوائية.
• الحساب العددي لمراحل (phases) QSVT.

4. النتال التجريبية

أجرى المؤلفون تجارب عددية على مصفوفات عشوائية ومعادلة بواسون أحادية البعد مجزأة ($N=16$، $n=4$ كيوبت).

• التقارب: أكدت التجارب معدل التقارب النظري. انخفض المتبقي المقياس خطياً على مقياس لوغاريتمي، متوافقاً مع الحد $\lceil \log(\epsilon) / \log(\epsilon_l \kappa) \rceil$.
• أرقام الشرط: تم إجراء الاختبارات مع أرقام شرط $\kappa = 10, 100, 200, 300$. نجحت الخوارزمية في التقارب حتى عند $\kappa=300$ ضمن حدود وقت المحاكاة.
• ميزة التعقيد: يوضح الشكل 5 أنه بالنسبة لرقم شرط ثابت ($\kappa=2$)، فإن عدد استدعاءات ترميز الكتلة المطلوبة لطريقة الدقة المختلطة أقل بكثير من نهج QSCT المباشر عالي الدقة، خاصة عندما تصبح الدقة المستهدفة $\epsilon$ صغيرة جداً.

5. الأهمية والعمل المستقبلي

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

في الختام، تقترح الورقة استراتيجية قابلة للتطبيق للتغلب على عنق زجاجة الموارد في حلول الأنظمة الخطية القائمة على QSVT، مما يوفر خارطة طريق للخوارزميات الهجينة المستقبلية التي تستفيد من نقاط القوة في كل من البنى الكلاسيكية والكمومية.