An Initialization-free Quantum Algorithm for General Abelian Hidden Subgroup Problem

ملخص تقني: خوارزمية كمومية خالية من التهيئة لمسألة الزمرة الفرعية المخفية الأبيلية العامة

بيان المسألة
تُعد مسألة الزمرة الفرعية المخفية (HSP) إطاراً جوهرياً في الحوسبة الكمومية، حيث تسعى لتحديد زمرة فرعية مجهولة $H$ من زمرة $G$ بمعلومية دالة $f$ تكون ثابتة على فصول (cosets) $H$ ومتميزة في الفصول المختلفة. وبينما توجد خوارزميات كمومية فعالة ذات زمن حدودي لمسألة الزمرة الفرعية المخفية الأبيلية (AHSP) حيث تكون $G$ زمرة أبيلية منتهية، إلا أن التنفيذات القياسية تواجه أعباءً تشغيلية عملية. وتحديداً، تتطلب الخوارق التقليدية تهيئة السجل المساعد إلى حالة نقية محددة (عادةً $|0\rangle$) في بداية كل تكرار. وفي السيناريوهات التي يتم فيها تنفيذ الإجراءات الكمومية الفرعية بشكل متكرر أو عند ضرورة إعادة استخدام الحالات الوسيطة، يخلق شرط التهيئة هذا عائقاً تجريبياً لا يستهان به ويحد من كفاءة المساحة.

المنهجية
يقترح المؤلفون خوارزمية كمومية لخوارلة الـ AHSP خالية من التهيئة، تعمل دون اشتراط تهيئة السجل المساعد في حالة نقية محددة. وتتضمن المنهجية الجوهرية ما يلي:

1. مدخل حالة مختلطة عشوائية: تقبل الخوارزمية حالة مختلطة مجهولة عشوائية $\rho_B = \sum_{y \in Y} \lambda_y |y\rangle_B\langle y|$ كالسجل المساعد، بدلاً من الحالة الثابتة $|0\rangle_B$.
2. استعلامات الأوراكل القياسية: تستخدم الخوارزمية أوراكل كمومي قياسي $U_f$ لترميز قيم الدالة.
3. المؤثر الوحدوي $S_z$: يكمن الابتكار الرئيسي في تقديم مؤثر وحدوي $S_z = F_M T_z^\dagger F_M$، حيث $F_M$ هو تحويل فورييه الكمومي (QFT) لزمرة دورية من الرتبة $M$ و $T_z$ هو مؤثر إزاحة. يُطبق هذا المؤثر مرتين ضمن كل تكرار:
   • أولاً، لترميز قيم الدالة $f(x)$ في طور (phase) السجل الرئيسي مع تحويل حالة السجل المساعد.
   • ثانياً، لـ "إلغاء الحساب" (uncompute) للسجل المساعد، مما يعكس التحويل الذي طُبق عليه فعلياً.
4. استعادة الحالة: من خلال تطبيق $S_z$ والاستعلام عن الأوراكل مرة ثانية، تضمن الخوارزمية عودة السجل المساعد إلى حالته الأصلية $|y\rangle_B$ (وبالتالي الحالة المختلطة $\rho_B$) في نهاية الحوسبة، بغض النظر عن نتيجة القياس في السجل الرئيسي.
5. العشوائية: لضمان مطابقة توزيع الاحتمالات لنتائج القياس مع الخوارزمية القياسية، يتم تطبيق المؤثر $S_z$ بمعامل $z \in Y$ مختار عشوائياً.

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

• التعميم ليشمل كافة الحالات المختلطة العشوائية: بخلاف الأعمال السابقة الخالية من التهيئة والمقتصرة على مسائل محددة (مثل مسألتي Deutsch-Jozsa و Simon)، تعمل هذه الخوارزمية على توسيع الإطار ليشمل جميع الزمر الأبيلية المنتهية.
• استعادة الحالة: تضمن الخوارزمية استعادة السجل المساعد إلى شكله الأصلي بعد الحوسبة. وهذا يسمح بإعادة استخدام نفس السجل الفيزيائي للتكرارات اللاحقة دون الحاجة لإعادة التهيئة.
• الحفاظ على التعقيد: يوضح المؤلفون أن العمليات الإضافية المطلوبة لاستعادة الحالة (تطبيقان لـ $S_z واستعلام واحد إضافي للأوراكل في كل تكرار) لا تزيد من التكلفة الحسابية التقاربية.

النتائج
تثبت الورقة النتائج النظرية التالية:

• تعقيد الاستعلام والزمن: تتطلب الخوارزمية الخالية من التهيئة $O(\log |G|)$ من استعلامات الأوراكل و $O(\log^3 |G|)$ من العمليات الأولية. وهذا يطابق تعقيد الخوارزمية الكمومية ذات الزمن الحدودي القياسية لـ AHSP.
• توزيع الاحتمالات: الاحتمال المتوقع للحصول على عينة $g$ من المبدد (annihilator) $H^\perp$ هو نفسه كما في الخوارزمية القياسية ($|H|/|G|$). وبناءً على ذلك، يظل عدد التكرارات اللازمة لتوليد مجموعة مولدة لـ $H$ هو $O(\log |G|)$.
• الخطية: نظراً لخطية العمليات الوحدوية، فإن استعادة الحالة تنطبق على أي حالة مختلطة مجهولة، وليس فقط الحالات النقية.

الأهمية والادعاءات
يزعم المؤلفون أن هذا العمل يوفر اتجاهاً واعداً لتحسين كفاءة الخوارزميات الكمومية من خلال تقليل الوقت التشغيلي المرتبط بتهيئة الحالة. ومن خلال إلغاء الحاجة لإعادة ضبط السجل المساعد إلى حالة نقية، تقوم الخوارزمية بـ:

1. تقليل الأعباء: تخفيف عبء تهيئة الحالة، وهو أمر ذو أهمية خاصة في الأجهزة الكمومية ذات المقياس المتوسط المشوبة بالضجيج (NISQ).
2. تعزيز كفاءة المساحة: تمكين إعادة استخدام الحالات الكمومية الوسيطة كسجلات مساعدة، مما قد يقلل العدد الإجمالي للكيوبتات المطلوبة للإجراءات التكرارية.
3. شمولية التطبيق الواسعة: بما أن العديد من خوارزميات التسريع الأسي (بما في ذلك خوارزميات Simon و Shor) يمكن صياغتها ضمن إطار AHSP، فإن تقنية الخلو من التهيئة هذه قابلة للتطبيق على فئة واسعة من المسائل الحسابية.

تخلص الورقة إلى أنه بينما تقدم الخوارزمية عمليات وحدوية إضافية، إلا أنها تحقق نفس تعقيد الاستعلام والزمن مثل الطرق القياسية مع تقديم مزايا عملية كبيرة من حيث تهيئة الحالة وإعادة استخدام الموارد.