DOI: https://doi.org/10.22331/q-2026-04-13-2061
تاريخ النشر: 2026-04-13
المؤلف: Kou Hamada وآخرون
الموضوع الرئيسي: خوارزميات وهندسة الحوسبة الكمومية
نظرة عامة
تقدم ورقة البحث خوارزمية جدولة جديدة لعمليات جراحة الشبكة في الحوسبة الكمومية المقاومة للأخطاء، والتي تعتبر ضرورية للتنفيذ الفعال لعمليات الكيوبت المنطقية المشفرة باستخدام رموز السطح. يقترح المؤلفون طريقة تعيد صياغة تحدي الجدولة كمشكلة رسم بياني تتضمن تضمين مسارات ثلاثية الأبعاد في شبكة ثلاثية الأبعاد. تتيح هذه الطريقة تطبيق خوارزميات البحث عن المسار، وبشكل خاص نوع متقدم من خوارزمية ديكسترا، لتعزيز إنتاجية عمليات جراحة الشبكة. تظهر التقييمات العددية تقليصًا كبيرًا في وقت التنفيذ—بمقدار 3.8—مقارنة بالخوارزميات الجشعة التقليدية.
في الخاتمة، يعترف المؤلفون بالحاجة إلى استكشاف مزيد من العمليات المنطقية بخلاف قياسات باولي-XX وZZ التي تم النظر فيها في تجاربهم. يبرزون أهمية دمج عمليات جراحة الشبكة متعددة الجسيمات ومعالجة القضايا المحتملة المتعلقة بالانسداد أثناء النقل السحري للحالة. تحدد الورقة اتجاهات البحث المستقبلية، بما في ذلك توسيع طرقهم لتشمل أطر تجميع أوسع، وتحسين وزن الفوكسل في البحث عن المسار، وتكييف نهجهم مع هياكل الحوسبة الكمومية المقاومة للأخطاء الموزعة. بشكل عام، تشير النتائج إلى أن خوارزميات الرسم البياني يمكن أن تعزز بشكل كبير كفاءة الجدولة في الحوسبة الكمومية المقاومة للأخطاء، مما يمهد الطريق لمزيد من الخوارزميات الكمومية العملية.
مقدمة
في المقدمة، يتناول المؤلفون التحديات المتعلقة بتحقيق ميزة كمومية عملية بسبب معدلات الخطأ العالية في الحوسبة الكمومية. يبرزون إمكانيات تقنيات تصحيح الأخطاء الكمومية، وخاصة رموز السطح، التي يمكن أن تخلق بفعالية كيوبتات منطقية بمعدلات خطأ منخفضة باستخدام كيوبتات ضوضائية متعددة مرتبة في شبكة ثنائية الأبعاد (2D). يتم التأكيد على جراحة الشبكة كتقنية حاسمة للحوسبة الكمومية المقاومة للأخطاء، مما يمكّن من قياسات باولي متعددة الكيوبتات بشكل متوازي من خلال ربط الكيوبتات المنطقية عبر مساحات مساعدة. ومع ذلك، فإن تحسين جدولة تعليمات جراحة الشبكة هو مشكلة صعبة من الدرجة NP، مما يتطلب تطوير استراتيجيات تقريب فعالة.
يقترح المؤلفون خوارزمية جدولة جديدة تحول مشكلة جدولة جراحة الشبكة من مشكلة توجيه ثنائية الأبعاد إلى مشكلة توجيه ثلاثية الأبعاد، مما يعزز من مرونة وأداء تنفيذ الخوارزميات الكمومية. طريقتهم، المسماة إسقاط ديكسترا المتقدم، تؤسس علاقة بين المسارات في شبكة ثلاثية الأبعاد وتسلسلات جراحة الشبكة القابلة للتنفيذ، مما يسمح بتطبيق تقنيات تحسين الرسم البياني. تظهر المحاكاة العددية أن هذه الخوارزمية تحقق تحسينًا في الإنتاجية بمقدار 3.8 مرة مقارنة بالحلول الساذجة في المعايير العملية، مع الحفاظ على أوقات تجميع معقولة. لا تعمل الطريقة المقترحة فقط على تحسين وقت التشغيل للخوارزميات الكمومية، بل تمتد أيضًا إلى تصاميم الحوسبة الكمومية المقاومة للأخطاء المتنوعة، مما يمهد الطريق لاستراتيجيات تجميع أكثر كفاءة في هذا المجال.
طرق
في هذا القسم، يقيم المؤلفون أداء أربع طرق مقترحة—BFS، BFS المتقدم، إسقاط ديكسترا، وإسقاط ديكسترا المتقدم—مقابل خوارزمية تجميع المسارات غير المتداخلة (EDPC). يتم إجراء التقييم تحت إعداد مشكلة محدد يتماشى مع متطلبات خوارزمية EDPC، باستخدام بوابات CNOT وبوابات T، مع تنفيذ بوابات T عبر النقل من مصنع حالة سحرية. تشير النتائج إلى أن SELECT 0 تطلبت حجم طائرة كيوبتات يبلغ 17 مع 37,856 تعليمات، بينما تطلبت SELECT 5 حجمًا قدره 30 مع 39,050 تعليمات. من الجدير بالذكر أن التكوينات التي تنتهك شرط الكينك تم وضع علامة عليها في النتائج، لكن المؤلفين يركزون على القيم الخام لتقييم كفاءة التوجيه، مما يشير إلى أن الأخذ في الاعتبار الجدوى من شأنه أن يعزز من ميزة الأداء لطرقهم.
يتم وضع أداء خوارزمية EDPC بين BFS وBFS المتقدم بسبب استراتيجيتها في إدارة تبعيات التعليمات من خلال الفرز الطوبولوجي، والذي، بينما يمكّن من التجميع المتوازي، يقدم حواجز جدولة قد تعيق الأداء. يبرز المؤلفون أن تقنية النظر المتقدم في التعليمات تضيق الفجوة في الأداء بين BFS المتقدم وإسقاط ديكسترا، حيث تحقق إسقاط ديكسترا المتقدم نتائج ملحوظة. على وجه التحديد، تظهر إسقاط ديكسترا تحسينًا بمقدار 1.8 مرة مقارنة بـ BFS المتقدم، وتظهر إسقاط ديكسترا المتقدم تحسينًا بمقدار 3.6 مرة. كما يشير المؤلفون إلى أن وقت تنفيذ خوارزمية EDPC قد يتأثر سلبًا بتنفيذها في جوليا والتكاليف الحسابية المرتبطة بالروتينات الفرعية لتدفق الحد الأقصى في النقل بوابة T، مما يتناقض مع تنفيذهم الخاص بلغة C++.
نقاش
في هذا القسم، يناقش المؤلفون تنفيذ وجدولة جراحة الشبكة ضمن إطار رموز السطح لتصحيح الأخطاء الكمومية. يتم تسليط الضوء على رموز السطح كوسائل فعالة لترميز الكيوبتات، مع تنفيذ العمليات المنطقية من خلال معالجة البيانات والخلايا المساعدة على طائرة كيوبت ثنائية الأبعاد. يؤكد المؤلفون على أهمية جدولة تعليمات جراحة الشبكة، والتي تعتبر ضرورية لربط خلايا الكيوبتات المنطقية وإجراء قياسات موثوقة للتحقق من التماثل. يقدمون مفهوم “نبضة الشيفرة” كوحدة زمنية لتنفيذ هذه التعليمات، مشيرين إلى أن جدولة مثل هذه العمليات معقدة حسابيًا وصعبة من الدرجة NP.
لمعالجة هذه التعقيدات، يقترح المؤلفون طريقة جدولة أساسية باستخدام البحث بالعرض (BFS) لتحديد أقصر المسارات لتعليمات جراحة الشبكة. كما يقدمون نهجًا معززًا يسمى “BFS المتقدم”، والذي يسمح بإعادة ترتيب التعليمات لتحسين كفاءة الجدولة. يستكشف المؤلفون أيضًا إمكانيات التوجيه ثلاثي الأبعاد لجراحة الشبكة، موضحين أن تقسيم تعليمات جراحة الشبكة يمكن أن يؤدي إلى استخدام أكثر كفاءة للموارد في شبكة الكيوبتات. يؤسسون نظرية تربط خصائص المسارات ثلاثية الأبعاد بتنفيذ العمليات المنطقية، مثل قياسات باولي وبوابات CNOT، مما يوفر طريقة منهجية لتحويل المسارات ثلاثية الأبعاد إلى دوائر كمومية. بشكل عام، يبرز هذا القسم أهمية الجدولة الفعالة في تعظيم أداء العمليات الحوسبية الكمومية المعتمدة على رموز السطح.
DOI: https://doi.org/10.22331/q-2026-04-13-2061
Publication Date: 2026-04-13
Author(s): Kou Hamada et al.
Primary Topic: Quantum Computing Algorithms and Architecture
Overview
The research paper presents a novel scheduling algorithm for lattice-surgery operations in fault-tolerant quantum computing, which is crucial for efficient execution of logical qubit operations encoded with surface codes. The authors propose a method that reformulates the scheduling challenge as a graph problem involving the embedding of 3D paths into a 3D lattice. This approach allows for the application of pathfinding algorithms, specifically a look-ahead variant of Dijkstra’s algorithm, to enhance the throughput of lattice-surgery operations. Numerical evaluations demonstrate a significant reduction in execution time—by a factor of 3.8—compared to traditional greedy algorithms.
In the conclusion, the authors acknowledge the need for further exploration of various logical operations beyond the Pauli-XX and ZZ measurements considered in their experiments. They highlight the importance of integrating many-body lattice-surgery operations and addressing potential blocking issues during magic-state teleportation. The paper outlines future research directions, including extending their methods to broader compilation frameworks, optimizing voxel weighting in pathfinding, and adapting their approach for distributed fault-tolerant quantum computing architectures. Overall, the findings suggest that graph algorithms can significantly enhance the efficiency of scheduling in fault-tolerant quantum computing, paving the way for more practical quantum algorithms.
Introduction
In the introduction, the authors address the challenges of achieving practical quantum advantage due to high error rates in quantum computing. They highlight the potential of quantum error-correction technologies, particularly surface codes, which can effectively create logical qubits with low error rates using multiple noisy qubits arranged in a two-dimensional (2D) grid. Lattice surgery is emphasized as a crucial technique for fault-tolerant quantum computation, enabling parallel multi-qubit Pauli measurements by connecting logical qubits through ancillary spaces. However, optimizing the scheduling of lattice-surgery instructions is NP-hard, necessitating the development of efficient approximation strategies.
The authors propose a novel scheduling algorithm that transforms the lattice-surgery scheduling problem from a 2D to a 3D routing problem, thereby enhancing the versatility and performance of quantum algorithm execution. Their method, termed the look-ahead Dijkstra projection, establishes a correspondence between paths in a 3D lattice and executable lattice-surgery sequences, allowing for the application of graph optimization techniques. Numerical simulations demonstrate that this algorithm achieves a throughput improvement of 3.8 times over naive solutions in practical benchmarks, while maintaining reasonable compilation times. The proposed approach not only optimizes runtime for quantum algorithms but also extends to various fault-tolerant quantum computing designs, thereby laying the groundwork for more efficient compilation strategies in the field.
Methods
In this section, the authors evaluate the performance of four proposed methods—BFS, look-ahead BFS, Dijkstra projection, and look-ahead Dijkstra projection—against the Edge-Disjoint Paths Compilation (EDPC) algorithm. The evaluation is conducted under a specific problem setting that adheres to the requirements of the EDPC algorithm, utilizing CNOT gates and T-gates, with T-gates implemented via teleportation from a magic state factory. The results indicate that SELECT 0 required a qubit plane size of 17 with 37,856 instructions, while SELECT 5 required a size of 30 with 39,050 instructions. Notably, configurations violating the kink condition are marked in the results, but the authors focus on raw values to assess routing efficiency, suggesting that accounting for feasibility would further enhance the performance advantage of their methods.
The performance of the EDPC algorithm is positioned between BFS and look-ahead BFS due to its strategy of managing instruction dependencies through topological sorting, which, while enabling parallel compilation, introduces scheduling barriers that may hinder performance. The authors highlight that the instruction look-ahead technique significantly narrows the performance gap between look-ahead BFS and Dijkstra projection, with the look-ahead Dijkstra projection achieving remarkable results. Specifically, the Dijkstra projection shows a 1.8-fold improvement over look-ahead BFS, and the look-ahead Dijkstra projection exhibits a 3.6-fold improvement. The authors also note that the execution time of the EDPC algorithm may be adversely affected by its implementation in Julia and the computational costs associated with maximum flow subroutines in T-gate teleportation, contrasting with their own C++ implementation.
Discussion
In this section, the authors discuss the implementation and scheduling of lattice surgery within the framework of surface codes for quantum error correction. Surface codes are highlighted as effective means to encode qubits, with logical operations performed through the manipulation of data and ancillary cells on a two-dimensional qubit plane. The authors emphasize the importance of scheduling lattice-surgery instructions, which are necessary for connecting logical qubit cells and performing reliable parity-check measurements. They introduce the concept of a “code beat” as a time unit for executing these instructions, noting that the scheduling of such operations is computationally complex and NP-hard.
To address this complexity, the authors propose a baseline scheduling method using breadth-first search (BFS) to identify the shortest paths for lattice-surgery instructions. They also introduce an enhanced approach called “look-ahead BFS,” which allows for the reordering of instructions to optimize scheduling efficiency. The authors further explore the potential of 3D routing for lattice surgery, demonstrating that splitting lattice-surgery instructions can lead to more efficient resource utilization in the qubit lattice. They establish a theorem linking the characteristics of 3D paths to the execution of logical operations, such as Pauli measurements and CNOT gates, thereby providing a systematic method for converting 3D paths into quantum circuits. Overall, the section underscores the significance of efficient scheduling in maximizing the performance of quantum computing operations based on surface codes.