الشفرة الطارية

سنناقش الآن شفرة CSS محددة تُعرف بـالشفرة الطارية، التي اكتشفها أليكسي كيتاييف عام 1997. في الواقع، الشفرة الطارية ليست شفرة واحدة، بل هي عائلة من الشفرات، واحدة لكل عدد صحيح موجب ابتداءً من 2. تمتلك هذه الشفرات بعض الخصائص الرئيسية:

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

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

• أعضاء عائلة الشفرة الطارية لها مسافة كبيرة متزايدة ويمكنها تحمّل معدل خطأ مرتفع نسبياً.

وصف الشفرة الطارية

ليكن $L\geq 2$ عدداً صحيحاً موجباً، وافترض شبكة $L\times L$ ذات ما يُسمى حدوداً دورية. على سبيل المثال، يصوّر هذا الشكل شبكة $L\times L$ عند $L=9$.

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

لتحقيق هذا النوع من التكوين مادياً يلزم ثلاثة أبعاد. تحديداً، يمكننا تشكيل الشبكة على شكل أسطوانة بمطابقة الجانبَين الأيسر والأيمن أولاً، ثم ثني الأسطوانة بحيث تلتقي الدوائر عند الطرفَين اللتان كانتا الحوافَّ العلوية والسفلية للشبكة. أو يمكننا مطابقة الجانبَين العلوي والسفلي أولاً ثم الجانبَين الجانبيَّين؛ كلتا الطريقتَين تعملان ولا يهم أيهما نختار لأغراض هذه المناقشة.

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

طريقة "التنقل" على طارة كهذه بين النقاط المتجاورة في الشبكة ستكون مألوفة على الأرجح لمن لعب ألعاب فيديو قديمة، حيث يظهر عند تجاوز حافة الشاشة العلوية من أسفلها، وكذلك للحافتَين اليسرى واليمنى. هكذا سننظر إلى هذه الشبكة ذات الحدود الدورية، بدلاً من الحديث تحديداً عن طارة في الفضاء ثلاثي الأبعاد.

بعد ذلك، تُرتَّب الكيوبتات على حواف هذه الشبكة، كما هو موضّح في الشكل التالي، حيث تُشار إلى الكيوبتات بدوائر زرقاء صلبة.

لاحظ أن الكيوبتات الموضوعة على الخطوط المنقطة ليست صلبة لأنها ممثَّلة بالفعل على الخطوط الأعلى والأيسر في الشبكة. في المجموع يوجد $2L^2$ كيوبت: $L^2$ كيوبت على الخطوط الأفقية و$L^2$ كيوبت على الخطوط الرأسية.

لوصف الشفرة الطارية ذاتها، يتبقى وصف مولّدات المثبّت:

• لكل مربّع تكوّنه خطوط الشبكة، يوجد مولّد مثبّت $Z$ واحد، يُحصل عليه بضرب تنسوري لمصفوفات $Z$ على الكيوبتات الأربع الملامسة لذلك المربع مع مصفوفات الوحدة على جميع الكيوبتات الأخرى.

• لكل رأس تكوّنه خطوط الشبكة، يوجد مولّد مثبّت $X$ واحد، يُحصل عليه بضرب تنسوري لمصفوفات $X$ على الكيوبتات الأربع المجاورة لذلك الرأس مع مصفوفات الوحدة على جميع الكيوبتات الأخرى.

في كلتا الحالتَين نحصل على عملية باولي ذات وزن 4. يمكن توضيح مولّدات المثبّت هذه بشكل فردي على النحو التالي.

إليك رسماً توضيحياً يُظهر بعض أمثلة مولّدات المثبّت في سياق الشبكة ذاتها. لاحظ أن مولّدات المثبّت التي تلتف حول الحدود الدورية مشمولة. هذه المولّدات التي تلتف حول الحدود الدورية ليست مميزة أو مختلفة بأي طريقة عن تلك التي لا تلتف.

يجب أن تتبادل مولّدات المثبّت لتكون هذه شفرة مثبّت صالحة. كالمعتاد، تتبادل جميع مولّدات المثبّت $Z$ مع بعضها، لأن $Z$ يتبادل مع نفسه والوحدة تتبادل مع كل شيء، وبالمثل لمولّدات المثبّت $X$. من الواضح أن مولّدات المثبّت $Z$ و$X$ تتبادل عندما تعمل بشكل غير تافه على مجموعات منفصلة من الكيوبتات، كالأمثلة الموضحة في الشكل السابق. الإمكانية المتبقية هي أن يتداخل مولّد مثبّت $Z$ ومولّد مثبّت $X$ على الكيوبتات التي يعملان عليها بشكل غير تافه، وكلما حدث ذلك يجب أن يتداخل المولّدان دائماً على كيوبتَين، كما في الشكل التالي.

وبالتالي، يتبادل مولّدان من هذا النوع، تماماً كما يتبادل $Z\otimes Z$ و$X\otimes X$. وبالتالي تتبادل جميع مولّدات المثبّت مع بعضها.

الشرط الثاني المطلوب في مولّدات المثبّت لشفرة المثبّت هو أن تشكّل مجموعة توليد أدنى. هذا الشرط غير متحقق فعلياً في هذه المجموعة: إذا ضربنا جميع مولّدات المثبّت $Z$ معاً، نحصل على عملية الوحدة، وبالمثل لمولّدات المثبّت $X$. وبالتالي، يمكن التعبير عن أي مولّد مثبّت $Z$ كحاصل ضرب جميع المولّدات المتبقية، وبالمثل، يمكن التعبير عن أي مولّد مثبّت $X$ كحاصل ضرب مولّدات المثبّت $X$ المتبقية. إذا أزلنا أياً من مولّدات المثبّت $Z$ وأياً من مولّدات المثبّت $X$، نحصل على مجموعة توليد أدنى.

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

هذا يترك $L^2 - 1$ مولّد مثبّت من كل نوع، أو $2L^2 - 2$ في المجموع، في مجموعة التوليد الأدنى (الافتراضية). بما أن إجمالي الكيوبتات $2L^2$، هذا يعني أن الشفرة الطارية تُرمّز $2L^2 - 2 (L^2 - 1) = 2$ كيوبت.

الشرط الأخير المطلوب لمولّدات المثبّت هو أن يكون ثمة متجه حالة كمية واحد على الأقل مثبَّت بجميع مولّدات المثبّت. سنرى أن هذا صحيح مع تقدمنا في تحليل الشفرة، لكن يمكن أيضاً الاستدلال بأنه لا توجد طريقة لتوليد $-1$ مضروبة في الوحدة على جميع كيوبتات $2L^2$ من مولّدات المثبّت.

اكتشاف الأخطاء

للشفرة الطارية وصف بسيط وأنيق، لكن خصائص تصحيح الأخطاء الكمية قد لا تكون واضحة للوهلة الأولى. كما اتضح، إنها شفرة رائعة! لفهم لماذا وكيف تعمل، لنبدأ بالنظر في الأخطاء المختلفة ومتلازماتها.

الشفرة الطارية هي شفرة CSS، لأن جميع مولّدات المثبّت إما مولّدات $Z$ أو $X$. هذا يعني أن أخطاء $X$ وأخطاء $Z$ يمكن اكتشافها (وربما تصحيحها) بشكل منفصل. في الواقع، هناك تماثل بسيط بين مولّدات المثبّت $Z$ و$X$ يتيح لنا تحليل أخطاء $X$ وأخطاء $Z$ بنفس الطريقة تقريباً. لذا سنركّز على أخطاء $X$، التي يمكن اكتشافها بمولّدات المثبّت $Z$ — لكن يمكن ترجمة النقاش كله التالي من أخطاء $X$ إلى أخطاء $Z$، التي تُكتشف بالمثل بمولّدات المثبّت $X$.

يصوّر المخطط التالي تأثير خطأ $X$ على كيوبت واحدة. يُفترض هنا أن كيوبتاتنا $2L^2$ كانت في حالة مضمّنة في فضاء الشفرة للشفرة الطارية، مما جعل جميع قياسات مولّدات المثبّت تُخرج $+1$. تكتشف مولّدات المثبّت $Z$ أخطاء $X$، وهناك مولّد واحد كهذا لكل مربّع في الشكل، لذا يمكننا الإشارة إلى نتيجة قياس مولّد المثبّت المقابل بلون ذلك المربّع: تُشار إلى نتائج $+1$ بمربّعات بيضاء وتُشار إلى نتائج $-1$ بمربّعات رمادية. إذا حدث خطأ قلب بت على إحدى الكيوبتات، يكون التأثير أن قياسات مولّد المثبّت المقابلة للمربّعَين الملامسَين للكيوبت المتأثرة تُخرج الآن $-1$.

هذا بديهي عند النظر في مولّدات المثبّت $Z$ وكيفية سلوكها. في جوهره، يقيس كل مولّد مثبّت $Z$ تكافؤ الكيوبتات الأربع الملامسة للمربّع المقابل (بالنسبة للأساس القياسي). لذا، نتيجة $+1$ لا تشير إلى عدم حدوث أخطاء $X$ على هذه الكيوبتات الأربع، بل تشير إلى حدوث عدد زوجي من أخطاء $X$ على هذه الكيوبتات، بينما تشير نتيجة $-1$ إلى حدوث عدد فردي من أخطاء $X$. خطأ $X$ واحد بالتالي يعكس تكافؤ البتات الأربع على كلا المربّعَين اللذَين يلمسهما، مما يجعل قياسات مولّد المثبّت تُخرج $-1$.

بعد ذلك لنقدّم أخطاء $X$ متعددة لنرى ما يحدث. تحديداً، سنأخذ بعين الاعتبار سلسلة من أخطاء $X$ المتجاورة، حيث يكون خطآن من $X$ متجاورَين إذا أثّرا على كيوبتَين تلمسان نفس المربّع.

مولّدا المثبّت $Z$ عند طرفَي السلسلة كلاهما يُخرجان النتيجة $-1$ في هذه الحالة، لأن حدث عدد فردي من أخطاء $X$ على المربّعَين المقابلَين اللذَين يتوافقان مع تلك الطرفَين. جميع مولّدات المثبّت $Z$ الأخرى، من ناحية أخرى، تُخرج النتيجة $+1$، بما فيها تلك الملامسة للسلسلة لكن ليست في الطرفَين، لأن حدث عدد زوجي من أخطاء $X$ على الكيوبتات الملامسة للمربّعات المقابلة.

وبالتالي، طالما لدينا سلسلة من أخطاء $X$ لها طرفان، ستكتشف الشفرة الطارية حدوث أخطاء، مما ينتج نتائج قياس $-1$ لمولّدات المثبّت $Z$ المقابلة لطرفَي السلسلة. لاحظ أن السلسلة الفعلية من الأخطاء لا تُكشف، بل الطرفَين فقط! هذا مقبول — في القسم الفرعي التالي سنرى أننا لا نحتاج إلى معرفة بالضبط أي الكيوبتات تأثرت بأخطاء $X$ لتصحيحها. (الشفرة الطارية مثال على شفرة عالية التحلل، بمعنى أنها في العموم لا تُحدد بشكل فريد الأخطاء التي تصحّحها.)

من الممكن، مع ذلك، أن تكون سلسلة من أخطاء $X$ المتجاورة خالية من الطرفَين، أي أن سلسلة الأخطاء قد تشكّل حلقة مغلقة، كما في الشكل التالي.

في مثل هذه الحالة، حدث عدد زوجي من أخطاء $X$ على كل مربّع، لذا تُخرج كل قياسات مولّد المثبّت نتيجة $+1$. وبالتالي لا تكتشف الشفرة الحلقات المغلقة من أخطاء $X$ المتجاورة.

قد يبدو هذا مخيّباً للآمال، لأننا نحتاج فقط أربعة أخطاء $X$ لتشكيل حلقة مغلقة (ونأمل بشيء أفضل بكثير من شفرة ذات مسافة 4). لكن الحلقة المغلقة من أخطاء $X$ بالشكل الموضح في الشكل السابق ليست في الواقع خطأً — لأنها في المثبّت! تذكّر أنه بالإضافة إلى مولّدات المثبّت $Z$، لدينا أيضاً مولّد مثبّت $X$ لكل رأس في الشبكة. وإذا ضربنا مولّدات المثبّت $X$ المتجاورة معاً، نحصل على حلقات مغلقة من عمليات $X$. على سبيل المثال، الحلقة المغلقة في الشكل السابق يمكن الحصول عليها بضرب مولّدات المثبّت $X$ الموضحة في الشكل التالي معاً.

لكن هذا ليس النوع الوحيد من الحلقات المغلقة لأخطاء $X$ — وليس صحيحاً أن كل حلقة مغلقة من أخطاء $X$ مضمّنة في المثبّت. تحديداً، يمكن تصنيف الأنواع المختلفة من الحلقات على النحو التالي:

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

2. الحلقات المغلقة من أخطاء $X$ بعدد فردي من أخطاء $X$ على خط أفقي واحد على الأقل أو خط رأسي واحد على الأقل من الكيوبتات. حلقات بهذا الشكل غير مضمّنة في المثبّت أبداً وبالتالي تمثّل أخطاءً غير تافهة لا تكتشفها الشفرة.

مثال على حلقة مغلقة من أخطاء $X$ في الفئة الثانية موضّح في المخطط التالي.

سلسلة الأخطاء كهذه غير مضمّنة في المثبّت لأن كل مولّد مثبّت $X$ يضع عدداً زوجياً من عمليات $X$ على كل خط أفقي وعلى كل خط رأسي من الكيوبتات. هذا بالتالي مثال فعلي على خطأ غير تافه لا تنجح الشفرة في اكتشافه.

المفتاح هنا أن الطريقة الوحيدة لتشكيل حلقة من النوع الثاني هي الالتفاف حول الطارة، سواء حول الثقب في وسط الطارة أو من خلاله أو كليهما معاً. بشكل بديهي، سلسلة من أخطاء $X$ كهذه لا يمكن تقليصها إلى لا شيء بضربها بمولّدات المثبّت $X$ لأن تبولوجيا الطارة تحول دون ذلك. لهذا السبب تُصنَّف الشفرة الطارية أحياناً كشفرة تصحيح خطأ كمي طبولوجية. أقصر حلقة كهذه طولها $L$، وبالتالي هذه هي مسافة الشفرة الطارية: أي حلقة مغلقة من أخطاء $X$ طولها أقل من $L$ يجب أن تقع في الفئة الأولى، وبالتالي مضمّنة في المثبّت؛ وأي سلسلة من أخطاء $X$ لها طرفان تكتشفها الشفرة.

بما أن الشفرة الطارية تستخدم $2L^2$ كيوبت لترميز $2$ كيوبت ولها مسافة $L$، يتضح أنها شفرة مثبّت $[[2L^2,2,L]]$.

تصحيح الأخطاء

ناقشنا اكتشاف الأخطاء في الشفرة الطارية، والآن سنناقش بإيجاز كيفية تصحيح الأخطاء. الشفرة الطارية هي شفرة CSS، لذا يمكن اكتشاف أخطاء $X$ وأخطاء $Z$ وتصحيحها بشكل مستقل. مع إبقاء تركيزنا على مولّدات المثبّت $Z$ التي تكتشف أخطاء $X$، لننظر في كيفية تصحيح سلسلة من أخطاء $X$. (تُصحَّح أخطاء $Z$ بطريقة متماثلة.)

إذا ظهرت متلازمة مختلفة عن متلازمة $(+1,\ldots,+1)$ عند قياس مولّدات المثبّت $Z$، تكشف نتائج $-1$ عن طرفَي سلسلة أو أكثر من أخطاء $X$. يمكننا محاولة تصحيح هذه الأخطاء بإجراء تناظر بين نتائج $-1$ وتشكيل سلسلة من تصحيحات $X$ بينها. عند القيام بهذا، من المنطقي اختيار أقصر المسارات التي تجري عليها التصحيحات.

على سبيل المثال، افترض المخطط التالي الذي يصوّر متلازمة بنتيجتَي $-1$، مشاراً إليهما بمربّعات رمادية، ناجمتَين عن سلسلة من أخطاء $X$ موضّحة بالخط والدوائر الوردية. كما لاحظنا بالفعل، السلسلة ذاتها لا تُكشف بالمتلازمة؛ الطرفَان وحدهما مرئيان.

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

لن تكون هذه الاستراتيجية ناجحة دائماً. على سبيل المثال، تبيان مختلف لنفس المتلازمة كما في الشكل السابق موضّح في الشكل التالي.

في هذه المرة، نفس سلسلة التصحيحات السابقة تفشل في تصحيح سلسلة الأخطاء هذه، لأن التأثير المشترك للأخطاء والتصحيحات يمنحنا حلقة مغلقة من عمليات $X$ تلتف حول الطارة، وبالتالي لها تأثير غير تافه على فضاء الشفرة. لذا لا يوجد ما يضمن أن الاستراتيجية التي وصفناها للتو، وهي اختيار أقصر مسار من تصحيحات $X$ بين نتيجتَي متلازمة $-1$، ستصحّح بشكل صحيح الخطأ الذي أحدث تلك المتلازمة.

ما هو أكثر احتمالاً، بحسب نموذج الضوضاء، هو قياس متلازمة بأكثر من مدخلَين $-1$، كما يوحي الشكل التالي.

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

هذا النهج ليس الأمثل عموماً لنماذج الضوضاء الأكثر دراسةً، لكن استناداً إلى المحاكاة العددية يعمل جيداً في التطبيق العملي عند معدل ضوضاء أقل من 10% تقريباً، على افتراض أخطاء باولي مستقلة حيث $X$ و$Y$ و$Z$ متساوية الاحتمال. زيادة $L$ لا يؤثر تأثيراً كبيراً على نقطة التعادل التي تبدأ عندها الشفرة في المساعدة، لكن يؤدي إلى انخفاض أسرع في احتمالية الخطأ المنطقي مع انخفاض معدل الخطأ إلى ما دون نقطة التعادل.