Halving the cost of QROM

ملخص تقني: خفض تكلفة الـ QROM إلى النصف

بيان المشكلة

تُعد ذاكرة القراءة فقط الكمومية (QROM) روتيناً فرعياً أساسياً في الخوارزميات الكمومية المقاومة للأخطاء، حيث تُمكّن من تحميل البيانات الكلاسيكية بشكل متماسك في حالة التراكب. وهي تمثل مصدراً رئيسياً للعبء الحسابي الخوارزمي في تطبيقات مثل محاكاة الهاملتوني، وتحضير الحالة، وتخليق الوحدة (unitary synthesis)، والمحللات الكمومية للمعادلات التفاضلية والخطية.

المهمة الجوهرية لـ QROM هي تنفيذ التحويل:
$$\sum_{x=0}^{N-1} \psi_x |x\rangle|0\rangle \to \sum_{x=0}^{N-1} \psi_x |x\rangle|f(x)\rangle$$
حيث $N$ هو عدد مدخلات البيانات، و $b$ هو طول البت لكل مدخل، و $f(x)$ هي دالة كلاسيكية محسوبة مسبقاً.

تاريخياً، كانت تكلفة البوابات غير الكليفوردية (وتحديداً عدد بوابات Toffoli) في QROM تشكل عائقاً. وبينما قللت الطرق المبكرة باستخدام التكرار أحادي الوحدة (unary iteration) التكلفة إلى $N$، فإن إدخال تقنيات "SelectSwap" التي تستخدم الكيوبتات المساعدة أتاح تحسيناً أكبر. كانت أحدث التقنيات قبل هذا العمل، والتي وضعها Berry وآخرون، تستخدم $b(\lambda-1)$ من الكيوبتات المساعدة "المتسخة" (غير النقية) لتحقيق تكلفة Toffoli قدرها:
$$2\frac{N}{\lambda} + 4b(\lambda-1)$$
حيث $\lambda$ هو معامل يحدد المقايضة بين عدد الكيوبتات المساعدة وتعداد Toffoli. هذا البناء تسبب في عامل ضرب قدره 2 على الحد المهيمن $N/\lambda$ بسبب استخدام الكيوبتات المساعدة المتسخة، وهو قيد استمر لأكثر من سبع سنوات.

المنهجية

يقترح المؤلفون بناءً جديداً لـ QROM يعمل بفعالية على خفض تكلفة التنفيذ في النطاقات العملية. تسير المنهجية في مرحلتين:

1. من SelectSwap إلى SelectCopy

التحسين الأول يستبدل بنية "SelectSwap" ببنية "SelectCopy".

• النهج السابق (SelectSwap): لتحميل البيانات باستخدام الكيوبتات المساعدة المتسخة، تقوم الخوارزمية بتبديل السجل المتسخ رقم $r$ مع سجل صفر بناءً على حالة العنوان $|r\rangle$، ثم نسخ السجل صفر إلى سجل نظيف، ثم التبديل مرة أخرى. يتطلب هذا التسلسل عمليات تبديل متعددة الإرسال وبوابات CNOT.
• النهج الجديد (SelectCopy): لاحظ المؤلفون أن تسلسل التبديل، النسخ، والتبديل العكسي يكافئ رياضياً عملية نسخ متعددة الإرسال مباشرة للسجل رقم $r$ إلى السجل النظيف بناءً على $|r\rangle$.
  • عملية النسخ المباشر هذه تقلل من تكلفة Toffoli للعمليات متعددة الإرسال إلى النصف مقارنة بنهج التبديل (swap-based).
  • علاوة على ذلك، من خلال تعديل استراتيجية التحميل لتحميل $f(q, 0)$ مباشرة في السجل النظيف و $f(q, r) \oplus f(q, 0)$ في السجلات المتسخة (لـ $r > 0$)، قلل المؤلفون من متطلبات الكيوبتات المساعدة المتسخة من $b\lambda$ إلى $b(\lambda-1)$ مع تحسين الثوابت الإضافية بشكل أكبر.
  • التكلفة الناتجة: $2\frac{N}{\lambda} + 2b(\lambda-1) + 2\lambda - 6$.

2. حزم البتات المتتالية (التحسين البارامتري)

يعالج التحسين الثاني النطاق المقيد بالكيوبتات حيث يهيمن حد $N/\lambda$. يقدم المؤلفون طريقة لمعاملة QROM واحد بطول $b$ بت كـ $\alpha$ من عمليات QROM متتالية، كل منها يحمل $b/\alpha$ من البتات.

• التفريغ المتتالي: من خلال ربط $m$ من تطبيقات QROM، يمكن دمج خطوة تفريغ التطبيق رقم $j$ مع خطوة تحميل التطبيق رقم $(j+1)$. هذا يقلل من عدد دورات التحميل/التفريغ الكاملة.
• خفض التكلفة: لـ $m$ من عمليات QROM المتتالية، يصبح معامل $N/\lambda$ هو $(m+1)$ بدلاً من $2m$.
• التطبيق على QROM واحد: يعامل المؤلفون QROM بطول $b$ بت كـ $\alpha$ من عمليات QROM المتتالية بحجم $b/\alpha$. هذا يسمح لعمق "SelectCopy" بالزيادة من $\lambda$ إلى $\alpha\lambda$.
• العائلة البارامترية: ينتج عن ذلك دالة تكلفة تعتمد على المعامل القابل للضبط $\alpha$:
  $$\left(1 + \frac{1}{\alpha}\right)\frac{N}{\lambda} + \left(b + \frac{b}{\alpha}\right)(\alpha\lambda - 1) + (\alpha + 1)(\alpha\lambda - 3)$$
  من خلال تغيير $\alpha$ من $1$إلى$b$، يمكن استكمال معامل حد$N/\lambda$المهيمن من$2$نزولاً إلى$(1 + 1/b)$.

النتائج الرئيسية

• النطاق الأمثل: في الحد الذي يكون فيه $N \gg b^2\lambda^2$ وعدد الكيوبتات المتسخة المتاحة محدوداً، يكون ضبط $\alpha = b$ (تحميل بت واحد في كل مرة بشكل متتالٍ) هو الأمثل.
• خفض التكلفة: تحت هذه الظروف، تنخفض تكلفة Toffoli الإجمالية لتصبح تقريباً:
  $$\left(1 + \frac{1}{b}\right)\frac{N}{\lambda}$$
• مكاسب الأداء: يمثل هذا انخفاضاً بنسبة 50% تقريباً في التكلفة مقارنة بأحدث ما توصل إليه العلم سابقاً ($2N/\lambda$).
• تكافؤ الكيوبتات النظيفة: أداء بناء الكيوبتات المتسخة هذا يطابق فعلياً أداء QROM الخاص بالكيوبتات النظيفة (والذي يحقق عادةً معاملاً قدره 1) للقيم العملية لـ $b$.
• التعميم: توفر الورقة عائلة بارامترية من الطرق التي تسمح للمستخدمين بالاستكمال بين تكلفة طريقة SelectCopy القياسية والطريقة المتتالية بالكامل بناءً على توافر الكيوبتات وقيود حجم المشكلة.

الأهمية والادعاءات

يزعم المؤلفون تقديم أول تحسين كبير لروتين QROM منذ أكثر من نصف عقد. تكمن الأهمية في:

1. خفض العبء الحسابي: بما أن QROM يشكل غالبية العبء الحسابي في معظم التطبيقات الكمومية العملية (مثل الكيمياء، والأنظمة الخطية)، فإن خفض تكلفته إلى النصف يترجم مباشرة إلى توفير كبير في الموارد عبر المجال.
2. العملية: يتم تحقيق التحسينات باستخدام الكيوبتات المساعدة "المتسخة"، وهي أسهل في التنفيذ في البنى المقاومة للأخطاء من الكيوبتات "النظيفة" (النقية)، دون التضحية بكفاءة المكاسب المرتبطة بالكيوبتات النظيفة.
3. المرونة: الطبيعة البارامترية للحل تسمح لمصممي الخوارزميات بتحسين التكلفة بناءً على قيود الأجهزة المحددة (ميزانية الكيوبت مقابل عمق البوابة) عن طريق ضبط المعامل $\alpha$.

يشير المؤلفون إلى أنه بينما يفترض البناء الحالي أن المعاملات هي قوى للرقم 2، فإن العمل المستقبلي يمكن أن يدمج تقنيات القسمة الصحيحة للاستفيد من ميزانيات الكيوبتات المتسخة المتاحة بالكامل عندما لا تتوافق مع قيد $2^k$، مما قد يوفر تخفيضات إضافية في نطاقات معينة. وقد تم تنفيذ البناء المقترح في مكتبة PennyLane.