Quantum Approximation Optimization Algorithm for the Trellis based Viterbi Decoding of Classical Error Correcting Codes

إليك ملخص تقني مفصل للورقة البحثية بعنوان "خوارزمية التقريب الأمثل للتحسين (QAOA) لفك تشفير فيتيربي القائم على الشبكة (Trellis) لأكواد تصحيح الأخطاء الكلاسيكية" من تأليف مينايك بهاتاشاريا وأنكور راينا.

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

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

• التعقيد: فك التشفير بالاحتمال الأقصى (ML) هو عموماً مسألة من فئة NP-hard، مع تعقيد زمني قدره $O(2^n)$ لكلمة مشفرة بطول $n$.
• فك تشفير فيتيربي (Viterbi Decoding): بينما يوفر فك تشفير فيتيربي نهجاً قائماً على الشبكة (Trellis) لإيجاد المسار ذو الحد الأدنى من مسافة هامينج (حل ML)، إلا أنه يظل عملية استقصائية كلاسيكية للأكواد الخطية العامة.
• القيود الكمومية: غالباً ما تعاني المحاولات الكمومية السابقة، مثل البحث القائم على غروفر (Grover) أو تضخيم السعة التكراري (IAA)، من عمق دوائر مرتفع أو الحساسية للضوضاء في الأجهزة الكمومية ذات المقياس المتوسط المشوبة بالضجيج (NISQ).
• تحدي التحسين: تعد الخوارزميات الكمومية التباينية (VQAs) مثل خوارزمية التقريب الأمثل للتحسين (QAOA) واعدة للأجهزة التي تعمل بنظام NISQ، لكنها تواجه مشكلة "الهضاب القاحلة" (Barren Plateau)، حيث تؤدي التهيئة العشوائية للمعلمات إلى تلاشي التدرجات، مما يجعل عملية التحسين صعبة.

2. المنهجية

يقترح المؤلفون مفكك تشفير فيتيربي هجين (كمومي-كلاسيكي) يقوم بخرائط عملية فك التشفير القائمة على الشبكة إلى إطار عمل QAOA.

أ. رسم خرائط المشكلة إلى QAOA

1. دالة التكلفة ($f(c)$): هدف فك التشفير هو تقليل مسافة هامينج بين كلمة مشفرة مرشحة $c$ ومتجه مستلم خاطئ $y$. يتم صياغة ذلك كدالة بولية كاذبة (pseudo-Boolean):
   $$f(c) = \sum_{i=1}^{n} (c_i \oplus y_i)$$
2. هاميلتوني التكلفة ($H_f$): يتم رسم خريطة لدالة التكلفة إلى هاميلتوني قطري باستخدام مؤثرات Pauli-Z. يستخدم النظام سجلين:
   • السجل $x$: يمثل بتات الكلمة المشفرة.
   • السجل $r$: يمثل المتجه المستلم (qubits مساعدة مهيأة إلى $|y\rangle$).
     $$H_f = \sum_{i=1}^{n} \left( \frac{1}{2}I - \frac{1}{2}Z_{x_i}Z_{r_i} \right)$$
3. هاميلتوني المزج ($H_m$): المساهمة الجوهرية هي بناء "مزيج" يحافظ على فضاء الكود (ضمان تطور النظام عبر الكلمات المشفرة الصالحة فقط).
   • النظرية 1: يثبت المؤلفون أنه بالنسبة لكود خطي بمسافة هامينج دنيا $d$، فإن هاميلتوني المزج هو مجموع مؤثرات Pauli-X الموضعية بمقدار $d$. هذه المؤثرات تنقل الحالة الصفرية (الكلمة المشفرة صفرية الكل) إلى كلمات مشفرة صالحة أخرى بمسافة هامينج $d$.
   • يضمن هذا تقييد مساحة البحث لتقتصر على الكلمات المشفرة الصالحة، مما يمنع الخوارزمية من استكشاف حالات غير صالحة.

ب. استراتيجية تحسين المعلمات الموحدة (UPO)

لمعالجة مشكلة الهضاب القاحلة وصعوبة إيجاد المعلمات المثلى ($\gamma, \beta$) في الدائرة الكمومية المحددة بالمعلمات (PQC):

• النهج القياسي: يتضمن عادةً تهيئة عشوائية أو تحسين المعلمات ثابتة (FPO)، حيث يتم تحسين المعلمات طبقة تلو الأخرى.
• المقترح (UPO): يفرض المؤلفون قيداً للتوحيد حيث تكون جميع معلمات المزج متساوية ($\beta_1 = \beta_2 = \dots = \beta_p = \beta_0$) وجميع معلمات التكلفة متساوية ($\gamma_1 = \gamma_2 = \dots = \gamma_p = \gamma_0$).
• الأساس المنطقي: يقلل هذا من أبعاد مشهد التحسين، مما يتجنب المناطق المسطحة (الهضاب القاحلة) ويجعل الدائرة أكثر قابلية للتدريب عند أعماق ضحلة.

ج. سير عمل الخوارزمية

1. التهيئة: إنشاء تراكب موحد لجميع الكلمات المشفرة الصالحة في فضاء الكود باستخدام وحدة مولدة (generator unitary) $U_g$.
2. الترميز: تهيئة الكيوبتات المساعدة لتمثيل المتجه المستلم $y$.
3. الحلقة التباينية: تطبيق $p$ من طبقات وحدة التكلفة ($U_f(\gamma_0)$) ووحدة المزج ($U_m(\beta_0)$).
4. التحسين: استخدام محسن كلاسيكي لتقليل القيمة المتوقعة $\langle H_f \rangle$ عن طريق ضبط $\gamma_0$ و $\beta_0$ عبر استراتيجية UPO.
5. القياس: قياس سجل الكلمة المشفرة للحصول على المسار المفكك ذو الاحتمالية الأعلى.

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

1. رسم خرائط معمّم: طريقة لرسم خريطة لمشكلة فك تشفير فيتيربي لأي كود خطي كلاسيكي ضمن إطار عمل QAOA عن طريق تعريف دالة تكلفة تعتمد على مسافة هامينج.
2. النظرية 1 (بناء المزج): إثبات رسمي وبناء لهاميلتوني المزج الذي يعتمد على مسافة هامينج الدنيا للكود ($d$)، مما يضمن بقاء التطور الكمومي داخل فضاء الكود الصالح بدقة.
3. تحسين المعلمات الموحدة (UPO): استراتيجية منهجية (heuristic) جديدة تتفوق بشكل كبير على التهيئة العشوائية وتحسين المعلمات الثابتة (FPO) في إيجاد المعلمات الجيدة للدوائر ذات الأعماق الضحلة.
4. كفاءة العمق المنخفض: إثبات أن مفكك التشفير الهجين يعمل بفعالية مع أعماق دوائر منخفضة، مما يجعله مناسباً لأجهزة NISQ الحالية.

4. النتائج

قام المؤلفون بمحاكاة الخوارزمية باستخدام محاكي IBM's Qiskit و QASM على عدة أكواد:

• كود [6, 3, 3]:
  • المتجه المستلم: $y = 111011$.
  • النتيجة: نجحت استراتيجية UPO في تضخيم الكلمة المشفرة الصحيحة $|011011\rangle$ (مسافة هامينج 1) باحتمالية عالية.
  • المقارنة: أظهرت UPO تضخيماً منتظماً وعالي الاحتمالية للحل. في المقابل، أظهرت FPO والتهيئة العشوائية نتائج عشوائية وغير متسقة وفشلت غالباً في إيجاد المعلمات المثلى.
• كود [9, 4, 4]: تم فك تشفيرها بنجاح باستخدام مقياس مسار موحد باستخدام 3 طبقات من الوحدات.
• كود [3, 2, 1]: حدد بنجاح مسارين بمتريات دنيا متساوية، مما يعكس بدقة الغموض النظري للكود.
• الاختبار المرجعي: تمت مقارنة مفكك التشفير الهجين مع مفكك كلاسيكي (Min-Sum Belief Propagation) على أكواد التكرار. أظهرت النتائج معدلات خطأ في الكلمة (WER) متقاربة، مما يؤكد صلاحية النهج الهجين كمفكك نشط.
• تحليل المشهد: أكدت التصورات لمشهد دالة التكلفة أن UPO يخلق مشهداً غير مسطح مع تدرجات متميزة، بينما تؤدي FPO غالباً إلى مناطق مسطحة (هضاب قاحلة) حيث تتلاشى التدرجات.

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

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

باخت-صار، نجحت الورقة في الربط بين نظرية الترميز الكلاسيكية والحوسبة الكمومية من خلال تحويل فك تشفير فيتيربي إلى مشكلة QAOA، وحل عقبة تحسين المعلمات عبر UPO، وإثبات فك تشفير عالي الدقة على أجهزة NISQ محاكاتية.