DOI: https://doi.org/10.22331/q-2025-01-20-1600
تاريخ النشر: 2025-01-20
المؤلف: Oscar Higgott وآخرون
الموضوع الرئيسي: خوارزميات وهندسة الحوسبة الكمومية
نظرة عامة
في هذا البحث، يقدم المؤلفون تنفيذًا جديدًا لفك الشيفرة باستخدام المطابقة المثالية ذات الوزن الأدنى (MWPM)، والذي يُطلق عليه “بلوسوم المتناثر”، والذي تم تصميمه خصيصًا لتصحيح الأخطاء الكمومية، وخاصةً لرموز السطح. يعزز هذا الخوارزمية خوارزمية البلوسوم التقليدية من خلال القضاء على الحاجة إلى عمليات بحث دايكسترا الشاملة، والتي تتطلب حسابات مكثفة. يظهر بلوسوم المتناثر أداءً مثيرًا للإعجاب، حيث يعالج بيانات المتلازمة لكل من قواعد X و Z لدارات رموز السطح ذات المسافة 17 في أقل من ميكروثانية لكل جولة من استخراج المتلازمة، مما يتماشى مع معدل توليد البيانات لأجهزة الكمبيوتر الكمومية فائقة التوصيل. التنفيذ مفتوح المصدر ومتوافر في الإصدار 2 من مكتبة PyMatching.
كما يقدم المؤلفون تقنيات مثل التتبع المضغوط، الذي يبسط فك الشيفرة باستخدام الاتحاد-البحث من خلال التركيز على التنبؤ بالملاحظات المنطقية بدلاً من الأخطاء الفيزيائية. يسمح هذا النهج بتمثيل أكثر كفاءة للطرق في رسم بياني للكاشف، مما يحسن بشكل كبير من أداء فك الشيفرة. بينما يبلغ معدل الإنتاج الحالي لبلوسوم المتناثر حوالي 3.5 مرات أبطأ من المعدل المطلوب لفك الشيفرة في الوقت الحقيقي، يقترح المؤلفون أن العمل المستقبلي يمكن أن يتضمن توازي التنفيذ أو تكييفه لأخذ الأخطاء المترابطة في نماذج الضوضاء الواقعية في الاعتبار. بشكل عام، يمثل فك الشيفرة بلوسوم المتناثر تقدمًا كبيرًا في مجال تصحيح الأخطاء الكمومية، مع تطبيقات محتملة تمتد إلى استراتيجيات فك الشيفرة الأخرى.
مقدمة
تستعرض المقدمة التحديات المرتبطة بفك الشيفرة في الوقت الحقيقي في أجهزة الكمبيوتر الكمومية فائقة التوصيل، وخاصة تلك التي تستخدم رموز السطح مع مليون كيوبت فيزيائي تولد بيانات قياس بمعدل يقارب 1 تيرابت في الثانية. تعتبر فك الشيفرات السريعة ضرورية ليس فقط من أجل الكفاءة التشغيلية ولكن أيضًا لتقدم البحث في بروتوكولات تصحيح الأخطاء الكمومية. يقوم فك الشيفرة باستخدام المطابقة المثالية ذات الوزن الأدنى (MWPM)، وهي طريقة مستخدمة على نطاق واسع، بتعيين مشكلة فك الشيفرة على إطار عمل رسومي، مما يسمح بتصحيح الأخطاء بكفاءة من خلال خوارزميات مثل خوارزمية بلوسوم إدموندز. ومع ذلك، واجهت التطبيقات التقليدية لفك الشيفرة MWPM صعوبة في تلبية متطلبات السرعة للتطبيقات في الوقت الحقيقي.
يقدم المؤلفون تنفيذًا جديدًا لفك الشيفرة MWPM، يُطلق عليه “بلوسوم المتناثر”، والذي يتناول مباشرةً مشكلة فك الشيفرة على الرسم البياني للكاشف، متجاوزًا عدم الكفاءة في الطرق السابقة التي اعتمدت على خطوات متسلسلة. يعزز هذا الخوارزمية بشكل كبير من سرعة فك الشيفرة، محققًا أداءً يتماشى مع معدل توليد البيانات لمعالجات الكم فائقة التوصيل. يظهر تنفيذ بلوسوم المتناثر، المتاح في الإصدار 2 من حزمة PyMatching بايثون، القدرة على فك شيفرة كل من قواعد X و Z لدائرة رمز السطح ذات المسافة 17 في أقل من ميكروثانية لكل جولة. كما يناقش المؤلفون إمكانية تحسينات مستقبلية من خلال التوازي والتكامل مع تقنيات فك الشيفرة الأخرى، مما يبرز أهمية الحفاظ على معالجة فعالة في الوقت الحقيقي لمنع تراكم البيانات أثناء الحسابات.
النتائج
في هذا القسم، يقدم المؤلفون نتائج حسابية توضح كفاءة تنفيذهم لخوارزمية بلوسوم المتناثر، PyMatching v2، لفك شيفرة تجارب ذاكرة رموز السطح. قاموا بتقييم وقت التشغيل لـ PyMatching v2 مقارنةً بالإصدارات السابقة والتنفيذات البديلة، مما يكشف أنه يعالج كل من قواعد X و Z لدارات رموز السطح ذات المسافة 17 في أقل من ميكروثانية لكل جولة من استخراج المتلازمة بمعدل ضوضاء تفكيك على مستوى الدائرة يبلغ 0.1%. يتماشى هذا الأداء مع معدل توليد بيانات المتلازمة لأجهزة الكمبيوتر الكمومية فائقة التوصيل. من الجدير بالذكر أن PyMatching v2 يظهر تحسينًا تربيعيًا في التوسع مقارنةً بالإصدار السابق PyMatching v0.7 وتنفيذ NetworkX، خاصةً عند معدلات الأخطاء الفيزيائية المنخفضة.
كما يبرز المؤلفون أنه بالنسبة لمعدلات الأخطاء الفيزيائية التي تتراوح من 0.1% إلى 1% ولدارات رموز السطح ذات المسافة 29 وما فوق، فإن PyMatching v2 أسرع بأكثر من 100,000 مرة من التنفيذ النقي بلغة بايثون الذي يقلل المشكلة إلى المطابقة المثالية ذات الوزن الأدنى (MWPM). بالإضافة إلى ذلك، فإنه أسرع بحوالي 100 مرة من تقريب المطابقة المحلية لفك الشيفرة MWPM بالقرب من عتبة الخطأ وأسرع تقريبًا 1000 مرة تحتها. يُعزى تسريع الأداء إلى التعامل الأكثر كفاءة مع الرسم البياني للطريق في خوارزمية البلوسوم مقارنةً بالمطابقة المحلية، التي تبني رسم بياني للطريق أكثر اتساعًا مما هو ضروري. تشير تحليل أوقات التشغيل إلى متوسط قدره 0.62 ميكروثانية لكل جولة لدارات المسافة 17، مع إكمال 97.4% من اللقطات في أقل من ميكروثانية. في مقارنة عملية باستخدام بيانات تجريبية، تفوق PyMatching v2 بشكل كبير على PyMatching v0.7، حيث أكمل فك الشيفرة لـ 7 ملايين لقطة في 71 ثانية فقط مقارنةً بـ 3 ساعات و43 دقيقة للإصدار الأخير.
نقاش
في هذا القسم، يناقش المؤلفون الإطار لتحليل دوائر تصحيح الأخطاء الكمومية من خلال عدسة قياسات الكاشف والملاحظات. يتم تحديد نتيجة الكاشف من خلال توازن بتات القياس، حيث تظهر الأخطاء كاختلافات بين النتائج المتوقعة والملاحظة. يقدم المؤلفون نموذج خطأ مستقل يتميز بمجموعة من آليات الخطأ، كل منها يؤثر على كواشف وملاحظات معينة، ممثلة بواسطة مصفوفات فحص التوازن الثنائية. يسمح هذا النموذج بتحليل الأخطاء بكفاءة وبناء ملاحظات منطقية، والتي تعتبر ضرورية لفك شيفرة الأخطاء في الدوائر الكمومية.
ثم يتحول التركيز إلى نماذج الأخطاء الشبيهة بالرسم البياني، حيث تقلب كل آلية خطأ في أقصى حد اثنين من الكواشف. هذه النماذج ذات صلة خاصة لمجموعة متنوعة من رموز تصحيح الأخطاء الكمومية، بما في ذلك رموز السطح ورموز الألوان. يحدد المؤلفون رسمًا بيانيًا للكاشف يلتقط العلاقات بين الكواشف وآليات الخطأ، مما يسهل تنفيذ فك الشيفرة باستخدام المطابقة المثالية ذات الوزن الأدنى (MWPM). يهدف هذا الفك إلى تحديد الخطأ الفيزيائي الأكثر احتمالًا المتسق مع المتلازمة الملاحظة، مستفيدًا من خصائص الرسم البياني للكاشف لتحسين عملية فك الشيفرة. يختتم القسم بإقامة صلة بين المطابقة المثالية ذات الوزن الأدنى والمطابقة المدمجة، مما يبرز الكفاءة الحسابية لاستراتيجيات فك الشيفرة المقترحة وأهميتها لتطبيقات تصحيح الأخطاء الكمومية العملية.
DOI: https://doi.org/10.22331/q-2025-01-20-1600
Publication Date: 2025-01-20
Author(s): Oscar Higgott et al.
Primary Topic: Quantum Computing Algorithms and Architecture
Overview
In this research, the authors present a novel implementation of the minimum-weight perfect matching (MWPM) decoder, termed “sparse blossom,” which is specifically designed for quantum error correction, particularly for surface codes. This algorithm enhances the traditional blossom algorithm by eliminating the need for all-to-all Dijkstra searches, which are computationally intensive. Sparse blossom demonstrates impressive performance, processing syndrome data for both X and Z bases of distance-17 surface code circuits in under one microsecond per round of syndrome extraction, aligning with the data generation rate of superconducting quantum computers. The implementation is open-source and available in version 2 of the PyMatching library.
The authors also introduce techniques such as compressed tracking, which simplifies the union-find decoder by focusing on predicting logical observables rather than physical errors. This approach allows for a more efficient representation of paths in the detector graph, significantly improving the performance of the decoder. While the current throughput of sparse blossom is approximately 3.5 times slower than the desired rate for real-time decoding, the authors suggest that future work could involve parallelizing the implementation or adapting it to account for correlated errors in realistic noise models. Overall, the sparse blossom decoder represents a significant advancement in the field of quantum error correction, with potential applications extending to other decoding strategies.
Introduction
The introduction outlines the challenges associated with real-time decoding in superconducting quantum computers, particularly those utilizing surface codes with a million physical qubits generating measurement data at a rate of approximately 1 terabit per second. Fast decoders are essential not only for operational efficiency but also for advancing research in quantum error correction protocols. The minimum-weight perfect matching (MWPM) decoder, a widely used method, maps the decoding problem onto a graphical framework, allowing for efficient error correction through algorithms like Edmonds’ blossom algorithm. However, traditional implementations of the MWPM decoder have struggled to meet the speed requirements for real-time applications.
The authors present a novel implementation of the MWPM decoder, termed “sparse blossom,” which directly addresses the decoding problem on the detector graph, circumventing the inefficiencies of previous methods that relied on sequential steps. This new algorithm significantly enhances decoding speed, achieving performance that matches the data generation rate of superconducting quantum processors. The sparse blossom implementation, available in version 2 of the PyMatching Python package, demonstrates the capability to decode both X and Z bases of a distance-17 surface code circuit in under one microsecond per round. The authors also discuss the potential for future improvements through parallelization and integration with other decoding techniques, highlighting the importance of maintaining efficient real-time processing to prevent data backlog during computations.
Results
In this section, the authors present computational results demonstrating the efficiency of their implementation of the sparse blossom algorithm, PyMatching v2, for decoding surface code memory experiments. They benchmarked the running time of PyMatching v2 against previous versions and alternative implementations, revealing that it processes both X and Z bases of distance-17 surface code circuits in under one microsecond per round of syndrome extraction at a circuit-level depolarizing noise rate of 0.1%. This performance aligns with the syndrome data generation rate of superconducting quantum computers. Notably, PyMatching v2 exhibits a quadratic improvement in scaling compared to the earlier PyMatching v0.7 and a NetworkX implementation, particularly at low physical error rates.
The authors further highlight that for physical error rates ranging from 0.1% to 1% and for distance-29 surface code circuits and larger, PyMatching v2 is over 100,000 times faster than the pure Python implementation that reduces the problem to minimum weight perfect matching (MWPM). Additionally, it is approximately 100 times faster than the local matching approximation of the MWPM decoder near the error threshold and nearly 1000 times faster below it. The speedup is attributed to the more efficient handling of the path graph in the blossom algorithm compared to local matching, which constructs a more extensive path graph than necessary. The analysis of running times indicates a mean of 0.62 microseconds per round for distance-17 circuits, with 97.4% of the shots completed in under one microsecond. In a practical comparison using experimental data, PyMatching v2 significantly outperformed PyMatching v0.7, completing the decoding of 7 million shots in just 71 seconds compared to 3 hours and 43 minutes for the latter.
Discussion
In this section, the authors discuss the framework for analyzing quantum error correction circuits through the lens of detector and observable measurements. A detector’s outcome is determined by the parity of measurement bits, with errors manifesting as discrepancies between expected and observed outcomes. The authors introduce an independent error model characterized by a set of error mechanisms, each affecting specific detectors and observables, represented by binary parity check matrices. This model allows for efficient error analysis and the construction of logical observables, which are essential for decoding errors in quantum circuits.
The focus then shifts to graphlike error models, where each error mechanism flips at most two detectors. These models are particularly relevant for various quantum error correction codes, including surface codes and color codes. The authors define a detector graph that captures the relationships between detectors and error mechanisms, facilitating the implementation of a minimum-weight perfect matching (MWPM) decoder. This decoder aims to identify the most probable physical error consistent with the observed syndrome, leveraging the properties of the detector graph to optimize the decoding process. The section concludes by establishing a connection between minimum-weight perfect matching and embedded matching, highlighting the computational efficiency of the proposed decoding strategies and their relevance to practical quantum error correction applications.