Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations

هذا ملخص تقني مفصل للورقة البحثية بعنوان: "التحسين التقاربي والعملي للدوائر الكمومية التي تنفذ عمليات الضرب والقسمة في الحقول الثنائية $GF(2^m)$."

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

تعد حسابات حقل غالوا (Galois Field)، وتحديداً فوق $GF(2^m)$، لبنة أساسية لمختلف الخوارزميات الكمومية، بما في ذلك مشكلات اللوغاريتم المتقطع للمنحنيات الإهليلجية (ECDLP)، وإثباتات الكمية (proofs of quantumness)، وفك التشفير التداخلي الكمومي.

• عنق الزجاجة: تعاني الدوائر الكمومية الحالية لضرب $GF(2^m)$ التي لا تستخدم مساعدة (ancilla-free) (بناءً على خوارزمية Karatsuba) من تعقيد في عدد بوابات CNOT يصل إلى $O(m^2)$. ينشأ هذا التكلفة التربيعية بشكل أساسي من تنفيذ عملية الضرب في كثير الحدود الثابت $1 + x^{\lceil m/2 \rceil}$، وهي خطوة ضرورية في بناء Van Hoof [46].
• تعقيد القسمة: تعتمد عملية قسمة الحقل (الانعكاس) عادةً على خوارزمية Itoh-Tsujii، والتي تتضمن عمليات تربيع وضرب متكررة. عانت التنفيذات السابقة من تعقيد CNOT يبلغ $O(m^2 \log m)$ بسبب دوائر التربيع الخطية العكسية غير الفعالة.
• الهدف: يهدف المؤلفون إلى تقليل التعقيد التقاربي لهذه العمليات إلى $O(m \log_2 3)$ للضرب، وتحسين تعقيد القسمة، مع الحفاظ على قيود عدم استخدام مساعدة (أو استخدام قليل جداً منها) وضمان التحسينات العملية للأحجام الميدانية ذات الصلة بالتشفير (مثل $m=163, 256, 1024$).

2. المنهجية

تستخدم الورقة نهجاً متعدد الجوانب يجمع بين نظرية الأعداد الجبرية، وتحسين الجبر الخطي، وتقنيات تركيب الدوائر.

أ. تحسين الضرب في الثابت ($1 + x^{\lceil m/2 \rceil}$)

الابتكار الجوهري هو تقليل تكلفة الضرب في الثابت $1 + x^{\lceil m/2 \rceil}$ من $O(m^2)$ إلى $O(m)$.

• التمثيل المصفوفي: يُنظر إلى عملية الضرب كتحويل خطي عكسي (مصفوفة $m \times m$ فوق $GF(2)$).
• اختيار كثير الحدود غير القابل للاختزال: يثبت المؤلفون أنه لأي $m$، توجد كثيرات حدود غير قابلة للاختزال حيث تسمح بنية المصفوفة بتنفيذ دائرة CNOT عالية الكفاءة.
  • عندما يكون $m$ زوجياً: يستخدمون كثيرات الحدود الثلاثية ($x^m + x^l + 1$) أو كثيرات حدود عامة حيث تكون الفجوة بين أعلى وأدنى الحدود غير التافهة صغيرة ($l_1 - l_k \in O(1)$). ويقومون بتطوير الخوارزمية 1 و 2 لبناء دوائر CNOT بعدد بوابات $O(m)$.
  • عندما يكون $m$ فردياً: يقدمون فئة محددة من كثيرات الحدود والخوارزميات 5 و 6 لتحقيق تعقيد $O(m)$، حتى بالنسبة لـ $m$ الفردية، عن طريق تقليص المشكلة إلى تركيب مصفوفة دورية (circulant matrix) محددة.
• النتيجة: يؤدي هذا إلى إزالة عنق الزجاجة التربيعي، مما يسمح لعملية ضرب Karatsuba الإجمالية بتحقيق تعقيد CNOT يبلغ $O(m \log_2 3)$.

ب. تحسين قسمة الحقل

تتم عملية القسمة عبر $b^{-1} = b^{2^m-2}$ باستخدام مبرهنة فيرما الصغرى.

• سلاسل الجمع (Addition Chains): بدلاً من سلسلة الجمع القياسية لـ Itoh-Tsujii، يستخدم المؤلفون سلاسل جمع محسنة (بناءً على Dimitrov و Järvinen [12]) لتقليل عدد عمليات الضرب المطلوبة.
• التحسين المتزامن: يختارون كثيرات حدود غير قابلة للاختزال تعمل في آن واحد على تحسين:
  1. الضرب في الثابت (كما هو موضح أعلاه).
  2. تربيع الحقل: يصممون دوائر للتربيع ($a \to a^2$) تعمل أيضاً بتعقيد $O(m \log m)$.
• تقليل التعقيد: من خلال دمج التربيع المحسن مع سلاسل الجمع، ينخفض إجمالي تعقيد CNOT للقسمة من $O(m^2 \log m)$ إلى $O(m^2 \log \log m / \log m)$.

ج. تقليل بوابات Toffoli

• صيغ شبيهة بـ Karatsuba: يعمم المؤلفون خوارزمية Karatsuba باستخدام صيغ "شبيهة بـ Karatsuba" (تقسيم المدخلات إلى $k$ من الأجزاء) لتقليل عدد عمليات الضرب.
• Toffoli المتحكم به بالتكافؤ (PCTOF): يقدمون تقنية لتجميع بوابات Toffoli بناءً على ضوابط التكافؤ (parity controls)، مما يسمح بتقليل رتبة مصفوفة التحكم. وهذا يقلل عدد بوابات Toffoli بنسبة تصل إلى 5% للقيم غير القوى للعدد 2 لـ $m$.

د. رؤية نظرية: الجذور التربيعية للوحدات (Unitaries)

تتضمن الورقة لِمّة (lemma) نظرية توضح أنه بالنسبة لبعض الوحدات الخطية العكسية $U$، فإن الجذر التربيعي $\sqrt{U}$ قد يتطلب دوائر أعمق تقاربياً ($\Omega(\log n)$) من $U$ نفسها (التي يمكن أن تكون ذات عمق ثابت)، حتى عندما يمكن تنفيذ كليهما باستخدام بوابات CNOT فقط.

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

1. التحسين التقاربي:
   • الضرب: تقليل تعقيد CNOT من $O(m^2)$ إلى $O(m \log_2 3)$.
   • القسمة: تقليل تعقيد CNOT من $O(m^2 \log m)$ إلى $O(m^2 \log \log m / \log m)$.
2. التحسين العملي:
   • طوروا خوارزميات بنائية (الخوارزميات 1-6) تضمن هذه الحدود لفئات محددة من كثيرات الحدود غير القابلة للاختزال.
   • أثبتوا وجود كثيرات حدود غير قابلة للاختزال مناسبة لجميع قيم $m$ حتى 10,000، مما يغطي جميع الأحجام التشفيرية ذات الصلة.
3. تقليل عدد البوابات:
   • حققوا تقليلاً يزيد عن 100 ضعف في أعداد CNOT لخطوة الضرب في الثابت (على سبيل المثال، لـ $m=6159$، انخفض العدد من ~2.2 مليون إلى ~6 آلاف بوابة).
   • تقليل إجمالي لـ CNOT بنسبة ~20.9% ولـ Toffoli بنسبة ~18% لعملية الضرب في الجدول I.
   • تقليل عدد بوابات القسمة بنسبة تصل إلى 28% لكل من CNOT و Toffoli (الجدول II).
4. قيد عدم استخدام المساعدة (Ancilla-Free): تم تحقيق جميع التحسينات دون استخدام كيوبتات مساعدة (ancillae) لعملية الضرب، ومع حد أدنى من التكاليف الإضافية للقسمة، مما يجعلها مناسبة للحواسيب الكمومية ذات القدرة على تصحيح الخطأ في مراحلها الأولى.

4. النتائج

يقدم المؤلفون نتائج عددية واسعة النطاق تقارن دوائرهم المحسنة مع أحدث التنفيذات (Van Hoof [46]، و Putranto et al. [37]، و Jang et al. [3]).

• الضرب (الجدول I):
  • لـ $m=163$ (حجم قياسي للمنحنيات الإهليلجية)، ينخفض عدد CNOT من 36,439 إلى 35,070، وعدد Toffoli من 4,387 إلى 3,605.
  • للقيم الأكبر (مثل $m=1024$)، ينخفض عدد CNOT من 591,942 إلى 525,140.
  • عامل التحسين يزدد مع زيادة $m$ بسبب أفضل مقياس تقاربي.
• القسمة (الجدول II):
  • لـ $m=64$، انخفض عدد CNOT من 169,272 إلى 121,120 (تقليل بنسبة ~28%).
  • لـ $m=1024$، انخفض عدد CNOT من 28.3 مليون إلى 22.9 مليون، وانخفض عدد Toffoli من 2.18 مليون إلى 1.59 مليون.
  • تم أيضاً تحسين استخدام سجل المساعدة (AR)، حيث تم تقليل العدد أحياناً بنسبة تصل إلى 22%.
• Toom-Cook (الملحق A): استكشف المؤلفون خوارزميات Toom-Cook لكنهم وجدوا أنها لا تتفوق على نهج Karatsuba-like المحسن في النطاق الذي تم اختباره بسبب الثوابت الرائدة العالية وتكاليف التكرار (recursion overhead).

5. الأهمية

• الأثر التشفيري: يترجم تقليل عدد البوابات مباشرة إلى متطلبات موارد أقل لكسر التشفير بالمفاتيح العامة (ECC) عبر خوارزمية Shor أو الهجمات الكمومية ذات الصلة. وهذا يدقق تقديرات الجداول الزمنية لـ "التفوق الكمي".
• الكفاءة الخوارزمية: يثبت هذا العمل أن "عنق الزجاجة" المتمثل في الضرب في الثابت في دوائر Karatsuba يمكن القضاء عليه، مما يجعل $O(m \log_2 3)$ حقيقة عملية وليس مجرد حد نظري.
• الملاءمة للأجهزة: من خلال التركيز على البناءات التي لا تستخدم مساعدة (ancilla-free) أو قليلة المساعدة، فإن النتائج قابلة للتطبيق فوراً على الحواسيب الكمومية في مراحل التصحيح الخطئي المبكرة حيث يكون عدد الكيوبتات هو القيد الأساسي.
• التوافق مع نموذج التكلفة: يستهدف التحسين دالة التكلفة $10 \times \text{Toffoli} + \text{CNOT}$، مما يعكس نماذج تصحيح الخطأ الحديثة حيث تكون بوابات Toffoli أغلى بكثير من بوابات CNOT، ولكن بوابات CNOT لم تعد مهملة أيضاً.

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