A Factor-Graph Formulation of CSS Syndrome Decoding: Joint BP and Four-State BP

ملخص تقني: صياغة مخطط العامل (Factor-Graph) لفك تشفير متلازمة أكواد CSS

بيان المشكلة
يتناول البحث صياغة فك التشفير باستخدام انتشار الاعتقاد (BP) لأكواد كالدربيرك-شور-ستين (CSS). في فك تشفير متلازمة CSS، يكون التوزيع البعدي لأخطاء باولي مقيدًا بمصفوفتي فحص تماثل ثنائيتين ($H_X$ و $H_Z$) تعملان على مكونات خطأ $X$ و $Z$ على التوالي. ويتمثل التحدي المركزي في فك تشفير هذه الأكواد في التعامل مع الارتباط المحلي بين مكونات خطأ $X/Z$ عند كل كيوبت، لا سيما عندما لا تكون القناة مجرد حاصل ضرب مستقل لأخطاء $X$ و $Z$ (مثل قناة التبديد/depolarizing channel).

تنقسم النهج الحالية عمومًا إلى فئتين:

1. الـ BP المنفصل (Separate BP): يقوم بفك تشفير مكونات $X$ و $Z$ بشكل مستقل باستخدام مخططات تانر ثنائية منفصلة. يطرح هذا النهج الارتباط المحلي لـ $X/Z$ عبر استبدال التوزيع القبلي المشترك $Q_j(x_j, z_j)$ بتوزيعات قبلية هامشية.
2. الـ BP رباعي الحالات (Four-State BP): يعامل كل كيوبت كمتغير واحد فوق الحقل $\mathbb{F}_4$ (أو مجموعة حالات باولي الأربع الأربع)، مستخدمًا مخطط تانر أحادي الحالة رباعي. وبينما يحافظ هذا النهج على الارتباط، إلا أنه يبتعد عن بنية مخطط تانر الثنائي القياسية المستخدمة في تصميم أكواد LDPC.

يستقصي البحث ما إذا كان يمكن لتمثيل مخطط العامل الثنائي أن يحتفظ بالارتباط المحلي لـ $X/Z$ دون اللجوء إلى تمثيل كامل رباعي الحالات، وإذا كان الأمر كذلك، كيف يرتبط رياضيًا بنهج الحالات الأربع.

المنهجية
يقوم المؤلف بصياغة مشكلة فك التشفية باستخدام مخططات العامل وخوارزمية الجمع-الضرب (sum-product algorithm). يتم تعريف ثلاثة نماذج محددة لفك التشفير بناءً على تجزئة التوزيع البعدي المختلفة:

1. مفكك الـ BP المشترك (Joint BP Decoder): هذا هو التركيز الأساسي. يستخدم مخطط عامل ثنائي مقترن يتكون من مجموعتين من عقد المتغيرات الثنائية ($X$ و $Z$) ومجموعتين من عقد الفحص. ومن الأهمية بمكان أن التوزيع القبلي المحلي عند كل كيوبت $j$ هو التوزيع المشترك $Q_j(x_j, z_j)$. هذا العامل يربط بين المتغيرين الثنائيين، مما يسمح بتدفق المعلومات بين مكونات $X$ و $Z$ عبر العقدة المحلية مع الحفاظ على قيود الفحص الثنائية.
2. مفكك الـ BP المنفصل (Separate BP Decoder): وهو نموذج مرجعي حيث يتم استبدال التوزيع القبلي المشترك $Q_j(x_j, z_j)$ بهوامشه $Q^X_j(x_j)$ و $Q^Z_j(z_j)$. ينتج عن ذلك مفككان ثنائيان مستقلان يتجاهلان الارتباطات المحلية.
3. مفكك الـ BP رباعي الحالات (Four-State BP Decoder): حيث يتم تمثيل كل كيوبت كمتغير واحد $\alpha_j \in \mathbb{F}_4$ عبر إعادة التسمية $\alpha = x + \omega z$. يتم تحويل التوزيع القبلي المحلي وفقًا لذلك، وتعمل قيود الفحص على إحداثيات ثنائية محددة لـ $\alpha$.

تتمثل المنهجية الجوهرية في اشتقاق معادلات تحديث الجمع-الضرب لكل من مفككي الـ BP المشترك (الثنائي) والـ BP رباعي الحالات ($\mathbb{F}_4$). ثم يقوم المؤلف بإجراء مقارنة رياضية دقيقة لديناميكيات تمرير الرسائل بين هذين النموذجين.

المساهمات والنتائج الرئيسية
تتمثل المساهمة المركزية للبحث في النظرية 1، التي تثبت وجود تكافؤ دقيق بين مفكك الـ BP المشترك ومفكك الـ BP رباعي الحالات. تثبت النظرية ما يلي:

• تكافؤ التوزيع البعدي: أوزان التوزيع البعدي غير المعيرة المخصصة لتكوينات الخطأ المقابلة متطابقة تحت خريطة إعادة التسمية $\phi(x, z) = x + \omega z$.
• تكافؤ الرسائل: يمكن ربط الرسائل الممررة في مفكك الـ BP رباعي الحالات مباشرة بالرسائل في مفكك الـ BP المشترك. وتحديدًا، عمليات الهامش (marginalization) لرسائل الفحص إلى المتغير في نموذج الحالات الأربع تؤدي إلى رسائل الفحص إلى المتغير الثنائية، كما تتوافق رسائل المتغير إلى الفحص الثنائية مع عملية الهامش لرسائل المتغير إلى الفحص في نموذج الحالات الأربع.
• تكافؤ الاعتقاد: الاعتقادات النهائية (الاحتمالات الهامشية) عند كل كيوبت متطابقة تحت إعادة التسمية. وبناءً على ذلك، فإن القرارات الصلبة (تقديرات الاحتمال الأقصى البعدي) التي يتخذها كلا المفككين متطابقة.

يعتمد الإثبات على عمليات الجمع-الضرب القياسية، حيث يوضح أنه نظرًا لأن قيود الفحص في مخطط الحالات الأربع تعتمد فقط على إحداثي ثنائي واحد من التسمية (على سبيل المثال، فحوصات $X$ تعتمد فقط على $z$)، فإن خوارزمية الجمع-الضرب تقوم تلقائيًا بجمع (marginalize) الإحداثي غير ذي الصلة. وتستعيد هذه العملية تمرير الرسائل الثنائية المقترنة بدقة لمفكك الـ BP المشترك.

بالإضافة إلى ذلك، يقدم البحث صياغة نسبة لوغاريتم الاحتمال (LLR) لمفكك الـ BP المشترك. وهذا يسمح بتنفيذ الخوارزمية بكفاءة في النطاق اللوغاريتمي، على غرار مفككات LDPC الثنائية القياسية، مع استمرار دمج التوزيع القبلي المشترك $Q_j$ من خلال تحديث جدول $2 \times 2$ عند عقد المتغيرات.

الأهمية والادعاءات
يقدم البحث ادعاءً متواضعًا ودقيقًا فيما يتعلق بطبيعة فك تشفير CSS:

1. التمييز عن الـ BP المنفصل: يوضح البحث أن "الـ BP الثنائي" لا يعني بالضرورة "الـ BP المنفصل". إن فقدان الارتباط في الـ BP المنفصل هو نتيجة لهامش التوزيع القبلي قبل فك التشفير، وليس قيدًا متأصلًا في استخدام الرسائل الثنائية.
2. تكافؤ التمثيلات: القدرة على الاستفادة من ارتباط قناة $X/Z$ المحلية هي خاصية لـ تجزئة التوزيع البعدي، وليست حجم الأبجدية للرسائل. وقد ثبت أن الـ BP المشترك (الثنائي المقترن) والـ BP رباعي الحالات هما تمثيلان مختلفان لنفس عملية حساب الجمع-الضرب بالضبط.
3. التمثيل الطبيعي: بالنسبة لأكواد CSS تحديدًا، يُقدم مخطط فانر الثنائي المقترن (الـ BP المشترك) كتمثيل "طبيعي". فهو يحتفظ ببنية مخطط تانر الثنائي المألوفة وتعقيد عقد الفحص لأكواد LDPC الكلاسيكية، مع الحفاظ الكامل على ارتباطات القناة المحلية التي غالبًا ما تُفقد في فك التشفير المنفصل.

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