Efficient Synthesis of Multi-Controlled Toffoli Gates with Ternary Clifford$+P_9$ Gates

ملخص تقني: التخليق الفعال لبوابات Toffoli متعددة التحكم باستخدام بوابات Clifford+P9 الثلاثية

بيان المشكلة
تُعد بوابات Toffoli متعددة التحكم (MCT) وحدات أساسية في تصميم الدوائر الكمومية، وهي ضرورية للحسابات العكسية، وبناء الأوراكل (oracle)، وتضخيم السعة. ومع ذلك، يصبح تفكيك هذه البوابات مكلفًا بشكل متزايد مع زيادة عدد الكيوبتات المتحكم بها. في البنى القابلة لتصحيح الأخطاء (fault-tolerant)، تتطلب العمليات غير الكليفوردية (مثل بوابات Toffoli) إعداد حالات موارد وتدفق حقن مكلف. عادةً ما تقوم المنهجيات الثنائية فقط بتفكيك بوابات MCT إلى بوابات Toffoli أصغر، ثم إلى مجموعات Clifford+T، مما يؤدي إلى مقايضة بين تكلفة بوابة T، ومتطلبات الكيوبتات المساعدة، وعمق الدائرة. وبينما تحقق البناءات الثنائية الحديثة التي تستخدم مساعدات نظيفة مشروطة عمقًا لوغاريتميًا، إلا أنها تعتمد على فك الحساب بمساعدة القياس والتغذية الراجعة الكلاسيكية، مما يسبب أعباءً تتعلق بزمن انتقال القياس والجدولة المتماسكة. بدلًا من ذلك، توجد طرق تخليق تقريبية لكنها لا توفر بناءات دقيقة. تعالج هذه الورقة الحاجة إلى تخليق دقيق وفعال للموارد لبوابات MCT يتجنب أعباء القياس مع تحسين العمق ومتطلبات الكيوبتات المساعدة في بيئة قابلة لتصحيح الأخطاء.

المنهجية
يقترح المؤلفون تفكيكًا دقيقًا لبوابات MCT ذات مدخلات ومخرجات في الفضاء الجزئي الثنائي باستخدام إطار عمل Clifford+P9 الثلاثي. يستفيد هذا النهج من الإشغال المؤقت لمستوى الكوتريت (qutrit) غير الحسابي $|2\rangle$ كفضاء عمل، مع إبقاء الحالات المنطقية مشفرة في الفضاء الجزئي الثنائي $H_{bin} = \text{span}\{|0\rangle, |1\rangle\}$.

تتضمن المنههجية الجوهرية تفكيكًا شجريًا هرميًا:

1. العمليات الأولية: يستخدم البناء ثلاث عمليات أساسية: بوابة SUM الثلاثية (Clifford)، وعملية زيادة محكومة انتقائية للحالة $C_2(\text{INC})$ (غير كليفوردية)، وعملية تبديل صارمة محكومة للهدف الثنائي $C_2(X_{01})$ (غير كليفوردية). تُقاس تكلفة الموارد بعدد حقن P9 المنطقية المطلوبة لتنفيذ البوابات غير الكليفوردية.
2. هيكل الشجرة: بدلًا من التمديد العودي المتسلسل، يتم تقييم عناصر التحكم عبر شجرة متوازنة.
   • كتل الأوراق (Leaf Blocks): يتم فحص مجموعات من ثلاثة عناصر تحكم ثنائية بالتوازي. تستخدم كتلة الورقة بوابة SUM وعملية $C_2(\text{INC})$ لتمييز كوتريت تحكم مؤقت بالحالة $|2\rangle$ إذا وفقط إذا كانت جميع المدخلات هي $|1\rangle$.
   • كتل الدمج (Merge Blocks): تدمج العقد الداخلية النتائج من شجرتين فرعيتين وعنصر تحكم إضافي واحد. يستخدم هذا النوع كوتريت مساعدًا نظيفًا (مُهيأ للحالة $|0\rangle$) وثلاث عمليات $C_2(\text{INC})$. إذا كان كلا العلامتين في الأشجار الفرعية هما $|2\rangle$ وكان عنصر التحكم الأوسط هو $|1\rangle$، فإن الكوتريت المساعد يصل إلى الحالة $|2\rangle$، مما يؤدي بدوره إلى وصول عنصر التحكم الأوسط إلى الحالة $|2\rangle$.
   • عملية الجذر (Root Operation): بمجرد وصول علامة الجذر إلى $|2\rangle$ (مما يشير إلى أن جميع عناصر التحكم نشطة)، تقوم عملية تبديل صارمة واحدة $C_2(X_{01})$ بقلب الكيوبت المستهدف.
   • فك الحساب (Uncomputation): يتم عكس الدائرة لاستعادة جميع العلامات المؤقتة والكوتريتات المساعدة إلى الحالة $|0\rangle$.

المساهمات والنتائج الرئيسية
تقدم الورقة تحليلًا دقيقًا للموارد لعروض التحكم المتوازنة $n = 2^h - 1$ وتوسع البناء ليشمل العروض التعسفية.

• كفاءة الموارد للعروض المتوازنة ($n = 2^h - 1$):

  • عدد P9: يتطلب البناء $6n + 3$ من حقن P9 المنطقية. وهذا يطابق عدد P9 الدقيق للنموذج المرجعي (Baseline B) المستمد من Bocharov et al. [16] الذي يعتمد على التمديد العودي بدون مساعدة.
  • الكوتريتات المساعدة: يتطلب البناء $\frac{n-3}{4}$ من الكوتريتات المساعدة النظيفة. وهذا يمثل ربع المتطلبات التقريبية لـ Baseline B التي تتطلب $n-2$ من المساعدات.
  • عمق الدائرة: من خلال تقييم الأشجار الفرعية المستقلة بالتوازي، تم تقليل العمق من خطي $\Theta(n)$ إلى لوغاريثمي $\Theta(\log n)$.

• حد المقايضة (Trade-off Frontier):
  تحدد الورقة مقايضة بنائية بين مساحة العمل المساعدة وتكلفة العمليات غير الكليفوردية. من خلال إعادة استخدام الكوتريتات المساعدة (تقليل عدد الكوتريتات المساعدة النشطة في وقت واحد $A$)، تزداد عدد حقن P9. على وجه التحديد، استخدام كوتريت مساعد واحد معاد استخدامه ($A=1$) يؤدي إلى عدد P9 يبلغ $9n - 18$ وعمق $\Theta(n)$، بينما الاحتفاظ بـ $I(n)$ من المساعدات يقلل عدد P9 إلى $6n+3$.

• عروض التحكم التعسفية:
  بالنسبة لأي $n$، يوسع المؤلفون البناء عن طريق اختيار نواة متوازنة بعرض $m = 2^h - 1 \leq n$ وإلحاق عناصر التحكم المتبقية $n-m$ بالتسلسل. يحافظ هذا على عدد P9 البالغ $6n+3$ ولكنه يؤدي إلى عمق قدره $O(\log m + n - m)$. في الحالة الأسوأ (على سبيل المثال، $n = 2^{h+1}-2$)، يتدرج العمق خطيًا مع $n$.

الأهمية والادعاءات
تدعي الورقة أن التفكيك المقترح يوفر لبنة بناء عملية لتصميم وتجميع خوارزميات كمومية أكثر كفاءة في استهلاك الموارد في نظام قابل لتصحيح الأخطاء. تكمن أهميتها الأساسية في:

1. تقليل العمق: استبدال العمق الخطي للنماذج الثلاثية العودية بعمق لوغاريتمي للمدخلات المتوازنة دون الاعتماد على القياس أو التغذية الراجعة.
2. تقليل المساعدات: تقليل المتطلبات التقريبية للكوتريتات المساعدة النظيفة بمعامل قدره أربعة مقارلة بأفضل النماذج العودية الدقيقة الموجودة، مع الحفاظ على نفس تكلفة العمليات غير الكليفوردية (P9).
3. التخليق الدقيق: تقديم استراتيجية بناء دقيقة تدمج المعلومات الثنائية في أنظمة متعددة المستويات، وهو ما يختلف عن أنظمة التخليق التقريبي.

يشير المؤلفون إلى أنه بينما يوفر الجزء المتوازن عمقًا لوغاريتميًا، فإن العمق في الحالة الأسوأ للعروض التعسفية يظل خطيًا. ويقترحون أن العمل المستقبلي يمكن أن يستكشف نماذج تكلفة أكثر تفصيلًا لقابلية تصحيح الأخطاء (بما في ذلك تقطير الحالة السحرية "magic-state distillation" والتوجيه)، وإعدادات الكوتريت الوسيطة البديلة، والدمج في عمليات فرعية عكسية أكبر مثل دوائر الحساب.