Quantum CORDIC -- Arcsine on a Budget

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

تتناول الورقة البحثية التحدي الحسابي المتمثل في حساب دالة الجيب العكسي ($\arcsin$) بكفاءة ضمن سياق الحوسبة الكمومية بدقة اختيارية. وتعد هذه الدالة متطلباً أساسياً لعدة خوارزميات كمومية جوهرية، منها:

• خوارزمية هارو-هاسيميد-لوي (HHL): لحل أنظمة المعادلات الخطية.
• المحول الرقمي-التناظري الكمومي (QDAC): لتحويل السلاسل الثنائية إلى سعات احتمالية (على سبيل المثال: $|x\rangle \to \sqrt{1-\Phi(x)}|0\rangle + \sqrt{\Phi(x)}|1\rangle$).
• طرق مونت كارلو الكمومية: لتسريع عمليات المحاكاة العشوائية.
• تقدير قيمة شابلي (Shapley value): للتخصيص العادل في نظرية الألعاب التعاونية.

تعتمد النهج الكمومية الحالية للدوال المثلثية العكسية غالباً على تقريبات متعددة الحدود المجزأة أو عمليات البحث الثنائي التكرارية. وتتطلب هذه الطرق عادةً موارد كبيرة، مثل الوصول إلى الذاكرة (qRAM)، أو الضرب المعقد، أو عمليات الجذر التربيعي، مما يجعل تنفيذها صعباً على الأجهزة الكمومية القريبة من العصر الحالي والمحدودة الموارد ("ذات الميزانية").

2. المنهجية

يقترح المؤلفون تكييف خوارزمية الحاسب الرقمي للتدوير الإحداثي (CORDIC)، وهي تقنية تكرارية كلاسيكية تعود إلى الخمسينيات صُممت للأجهزة ذات الإمكانيات الضعيفة، لتناسب المجال الكمومي.

التحديات والحلول الجوهرية

التحدي الرئيسي في خوارزمية CORDIC الكمومية هو القدرة على العكس (Reversibility). تستخدم خوارزمية CORDIC الكلاسيكية عمليات غير قابلة للعكس (مثل التبديل المشروط وكتابة المتغيرات فوق بعضها البعض) التي تدمر المعلومات الكمومية. ويفصل المؤلفون طريقة لجعل كل خطوة قابلة للعكس:

1. تمثيل النقطة الثابتة (Fixed-Point Representation): يتم تمثيل جميع المتغيرات ($\theta, x, y, t$) كأعداد ذات نقطة ثابتة بنظام المتمم الثنائي. وهذا يتجنب مشاكل تجاوز السعة ويسمح باستخدام عمليات إزاحة البتات البسيطة للضرب في قوى العدد 2.
2. بوابات المنطق القابلة للعكس:
   • كشف الإشارة: تحدد الخوارزمية اتجاه التدوير بناءً على بتات الإشارة. ويتم تنفيذ ذلك باستخدام بوابات Toffoli وCNOT لحساب بت التحكم $d_i$ دون تدمير الحالة المدخلة.
   • التدوير الزائف (Pseudo-Rotation): تتضمن خطوة التدوير الأساسية $x' = x - 2^{-i}y$ و $y' = y + 2^{-i}x$. وبما أن الحواسيب الكمومية لا يمكنها إجراء عمليات الضرب العشوائية بكفاءة، يستخدم المؤلفون خوارزمية ضرب قابلة للعكس (الخوارزمية 2) متخصصة تعتمد على متتاليات فيبوناتشي لتقريب عملية الضرب في $(1 + 2^{-k})$ باستخدام عمليات الجمع وإزاحة البتات فقط.
   • إلغاء الحساب (Uncomputation): للحفاظ على قابلية العكس، تقوم الخوارزمية بحساب النتيجة، ثم تطبيق التحويلات اللازمة، ثم عكس الحسابات المساعدة (uncomputing) لإعادة السجلات المساعدة إلى حالة $|0\rangle$، تاركةً فقط النتيجة المرغوبة.

عملية CORDIC الكمومية

تقوم الخوارزمية بتدوير المتجه $(x, y)$ تكرارياً نحو متجه مستهدف محدد بواسطة $t$.

• التهيئة: يتم تعيين $t$ إلى متجه.
• التكرار: لعدد $n$ من التكرارات (حيث $n$ هو عدد بتات الدقة):
  1. تحديد اتجاه التدوير ($d_i$) بناءً على إشارة $t - y$.
  2. تبديل $x$ و $y$ بشكل مشروط.
  3. إجراء التدوير الزائف (جمع/طرح مع إزاحة البتات).
  4. إلغاء التبديل إذا لزم الأمر.
  5. تعويض تمدد المتجه الناتج عن التدوير الزائف عن طريق تغيير مقياس الهدف $t$.
  6. تراكم الزاوية $\theta$ عن طريق إضافة حدود $\arctan(2^{-i})$ المحسوبة مسبقاً.
• المخرج: الزاوية المتراكمة $\theta$ تقرب القيمة $\arcsin(t)$.

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

• أول CORDIC كمومي قابل للعكس للجيب العكسي: توفر الورقة أول بناء مفصل لدائرة كمومية قابلة للعكس بالكامل لحساب $\arcsin$ باستخدام بنية CORDIC.
• تصميم كفء للموارد: تتجنب الطريقة العمليات المكلفة مثل الضرب الكامل أو الجذور التربيعية، معتمدة بدلاً من ذلك على إزاحة البتات والجمع، وهي عمليات أصلية في الأجهزة الكمومية.
• التكييف الخوارزمي: نجح المؤلفون في ترجمة منطق CORDIC الكلاسيكي (تحديداً نسخة Mazenc et al.) إلى دائرة كمومية، وحل مشكلة عدم قابلية العكس في عمليات التبديل المشروطة والتحديثات التكرارية.
• التطبيق على QDAC: يوضح المؤلفون سير عمل كاملاً لـ التحويل الرقمي-التناظري الكمومي، حيث يظهرون كيفية تشفير قيمة ثنائية $h_k$ في السعة الاحتمالية $\sqrt{h_k}$ للكيوبت باستخدام البدائية الكمومية لـ CORDIC.

4. النتائج وتحليل التعقيد

يقدم المؤلفون حدود التعقيد النظرية ونتائج المحاكاة (باستخدام Qiskit ومحاكيات كلاسيكية).

• تعقيد المساحة: $O(n)$ من الكيوبتات.
  • تتطلب حوالي $5n - 1$ من الكيوبتات لـ $n$ من بتات الدقة (سجلات لـ $x, y, t, d$، وسجل مساعد لعملية الضرب).
• تعقيد الوقت/العمق: $O(n \log n)$ من الطبقات.
  • عمق الدائرة تهيمن عليه عمليات الجمع المطلوبة لخطوات الضرب القابلة للعكس.
• عدد البوابات (CNOT): $O(n^2)$.
  • يتناسب عدد بوابات CNOT تربيعياً مع عدد بتات الدقة.
• الدقة:
  • تُظهر المحاكاة لـ $n=4, 5, 6$ (كمومي) وحتى $n=16$ (كلاسيكي) أن الخطأ يتناقص مع زيادة $n$.
  • الخطأ من رتبة $O(2^{-n})$، مما يسمح بدقة اختيارية عبر زيادة $n$.
• الأداء: أثبتت الطريقة فعاليتها العالية لتطبيقات الدقة المنخفضة إلى المتوسطة، وهي الأكثر صلة بأجهزة الحوسبة الكمومية المبكرة ذات القدرة على تصحيح الأخطاء.

5. الأهمية

هذا العمل مهم لعدة أسباب:

1. تمكين الخوارزميات الجوهرية: من خلال توفير طريقة فعالة ومنخفضة الموارد لحساب $\arcsin$، تزيل الورقة عقبة رئيسية أمام خوارزمية HHL، ومحاكاة مونت كارلو الكمومية، وتقدير قيمة شابلي.
2. التوافق مع الأجهزة: النهج "ذات الميزانية" (استخدام الإزاحة والجمع فقط) مثالي للحواسيب الكمومية المبكرة ذات القدرة على تصحيح الأخطاء حيث تكون أعداد البوابات وأوقات تماسك الكيوبت محدودة. فهي تتجنب الأعباء الثقيلة لـ qRAM أو وحدات الحساب المعقدة.
3. النمطية: يمكن توسيع وحدة CORDIC المقترحة لحساب دوال أساسية أخرى (مثل الدوال الزائدية، اللوغاريتمية، الأسية) ضمن نفس بنية الدائرة، مما قد يجعلها لبنة بناء قياسية للحساب الكمومي.
4. الواقعية: تجسر الورقة الفجوة بين تقنيات الحوسبة الكلاسيكية المدمجة (CORDIC) وتصميم الخوارزميات الكمومية الحديثة، مما يثبت أن الخوارزميات "القديمة" والفعالة يمكن إحياؤها للعصر الكمومي.

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