ملخص تقني: الترميز الدوراني للدوال الهدفية للتحسين الكمي

بيان المشكلة

توفر خوارزميات البحث الكمي، مثل خوارزمية غروفر (Grover's algorithm)، مزايا حوسبية لمسائل إرضاء القيود (CSPs) والتحسين التوليفي. ومع ذلك، فإن قابليتها للتطبيق العملي مقيدة بشدة بتكلفة بناء "الأوراكل" (oracles) الخاصة بالمسألة. في النهج التقليدية للتحسين، تعتمد الأوراكل على المنطق البولياني (Boolean-based) وتعتمد على سجلات متعددة الكيوبتات لتخزين قيم الدوال الهدفية صراحةً كأرقام ثنائية. ثم يتم مقارنة هذه القيم بعتبة يتم تحديثها ديناميكياً باستخدام مؤثرات حسابية (مثل العدادات ذات التحكم - controlled-incrementers) والمقارنات.

تتسبب هذه الطريقة التقليدية في أعباء كبيرة:

1. كثافة الموارد: تتطلب سجلات متعددة الكيوبتات (واحد لقيمة الدالة الهدفية، وآخر للعتبة) والعديد من الكيوبتات المساعدة (ancilla qubits).
2. عمق الدائرة والتكلفة: تُبنى دوائر الحساب والمقارنة من عدد كبير من البوابات القابلة للعكس، مما يؤدي إلى أعداد عالية من البوابات، ودوائر عميقة، وزيادة التعرض لفك الترابط (decoherence).
3. التنفيذ التكراري: نظرًا لأن الأوراكل البوليانية لا يمكنها بطبيعتها ترتيب الحلول الصالحة حسب التكلفة، فإن التحسين يتطلب تشغيل خوارزمية البحث بشكل متكرر مع تحديث العتبة باستمرار، مما يزيد من وقت التنفيذ.

يعالج هذا البحث الحاجة إلى تمثيل بديل يدمج معلومات الدالة الهدفية مباشرة في العمليات الكمية لتقليل هذه التكاليف.

المنهجية: العداد الدوراني الزاوي (ARC)

قدم المؤلفون العداد الدوراني الزاوي (Angular Rotational Counter - ARC)، وهو تصميم للدائرة يقوم بترميز الدوال الهدفية كجموع تراكمي للدورات الكمية على سجل أحادي الكيوبت، بدلاً من قيمة ثنائية على سجل متعدد الكيوبتات.

الآلية الجوهرية

تم تصميم ARC للدوال الهدفية $C(x)$ التي يمكن تفكيكها إلى مجموع موزون من الدوال البوليانية:
$$C(x) = \sum_{i=1}^{m} w_i f_i(x)$$
حيث $w_i \geq 0$ هي الأوزان و $f_i(x)$ هي دوال بوليانية.

تعمل الدائرة كما يلي:

1. المدخلات: تتم معالجة حل مرشح $x$.
2. التقييم البولياني: يتم حساب كل حد $f_i(x)$ على كيوبت تحكم.
3. الترميز الدوراني: إذا كانت $f_i(x) = 1$، يقوم بوابة دوران متحكم بها (تحديداً $RX$) بتطبيق دوران بزاوية $\frac{\pi}{K} w_i$ على كيوبت المخرج. وإذا كانت $f_i(x) = 0$، فلا يحدث دوران.
4. التراكم: الزاوية الدورانية الإجمالية المطبقة على كيوبت المخرج تتناسب مع القيمة الهدفية: $\theta = \frac{\pi}{K} C(x)$.

الخصائص الرياضية

يثبت البحث أن احتمالية قياس كيوبت المخرج ترتبط ارتباطاً رتيبياً بالقيمة الهدفية $C(x)$:

• التعظيم (Maximization): إذا تم تهيئة كيوبت المخرج إلى الحالة $|0\rangle$، فإن احتمال قياس الحالة $|1\rangle$ يزداد مع زيادة $C(x)$ (ضمن الفترة $(0, K)$).
• التقليل (Minimization): إذا تم تهيئة الكيوبت إلى الحالة $|1\rangle$، فإن احتمال قياس الحالة $|1\rangle$ ينخفض مع زيادة $C(x)$.
• القيد: يجب ضبط الثابت $K$ ليكون أكبر من أو يساوي أقصى قيمة ممكنة للهدف لضمان الرتابة ضمن النطاق ذي الصلة.

التطبيق: تخصيص الحالة (State Assignment)

طبق المؤلفون ARC على مسألة تخصيص الحالة للآلات ذات الحالات المحدودة (finite automata)، وهي مسألة أساسية في تركيب الآلات الهيكلية. الهدف هو تخصيص ترميزات ثنائية متميزة للحالات لتقليل دالة التكلفة.

• دالة التكلفة: مسافة هامينج (Hamming distance) موزونة بأسلوب استدلالي، وهي حالة خاصة من مسألة التخصيص التربيعي.
• بناء الأوراكل: يتضمن الأوراكل فاحصاً للترميز (لضمان تميز الحالات) وحاسب تكلفة يعتمد على ARC. يستبدل ARC العداد الحسابي والمقارن التقليدي.
• الخوارزمية: يتم دمج ARC في خوارزمية البحث لغروفر. تنفذ الخوارزمية بحث غروفر مرة واحدة باستخدام الأوراكل الذي تم بناؤه. ثم يتم قياس الكيوبتات المدخلة، ويتم اختيار $r \geq 1$ من الحلول بناءً على أعلى احتمالات القياس. ومن المهم ملاحظة أن هذه الحلول المختارة يجب أن تخضع أيضاً للفحص للتحقق من صحتها وأمثلتها، حيث أن احتمالات القياس تشير إلى اتجاهات التكلفة ولكنها لا تضمن حلاً صالحاً في جولة واحدة دون عملية تحقق لاحقة.

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

1. إطار الترميز الدوراني: تقديم ARC كوسيلة لتمثيل الدوال الهدفية القابلة للتفكيك عبر الدورات الكمية المتراكمة على كيوبت واحد، على النقييد مع الترميز الثنائي الصريح.
2. الصياغة الرياضية: إثبات أن ARC يقوم بترميز الدالة الهدفية دورانياً، وأن احتمالية قياس كيوبت المخرج تعتمد رتيبياً على القيمة الهدفية، مما يسمح بالتحسين المباشر دون الحاجة لتحديثات العتبة التكرارية.
3. تصميم أوراكل لتخصيص الحالة: بناء أوراكل محدد لمسألة تخصيص الحالة باستخدام دالة تكلفة مسافة هامينج موزونة، مما يوضح قابلية تطبيق ARC على مسائل التحسين التوليفية الهامة.
4. التقييم الشامل: تحليل مقارن لأوراكل القائم على ARC مقابل الأوراكل القائم على المنطق البولياني عبر 26 اختباراً معيارياً.

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

قام المؤلفون بتقييم أوراكل ARC مقابل نظائره القائمة على المنطق البولياني في 26 اختباراً معيارياً من مكتبة LGSynth'91. تم تحويل الدوائر باستخدام Qiskit (مستوى التحسين 3) إلى البوابات الأصلية (CZ, RX, RZ, $\sqrt{X}$, X).

مقاييس الأداء (متوسط الانخفاضات الحسابية):

• عدد الكيوبتات: انخفض بنسبة 20.8% (تتراوح بين 3.9% و 45.2%). ويعزى ذلك إلى استبدال السجلات متعددة الكيوبتات للتكلفة والعتبة بسجل أحادي الكيوبت.
• عدد البوابات: انخفض بنسبة 89.3% (تتراوح بين 63.8% و 99.5%).
• عمق الدائرة: انخفض بنسبة 92.4% (تتراوح بين 72.8% و 99.7%).
• تكلفة التجميع الكمي (TQC): انخفضت بنسبة 90.6% (تتراوح بين 67.4% و 99.6%).

تنتج الانخفاضات الكبيرة في عدد البوابات وعمق الدائرة بشكل أساسي من إلغاء بوابات العدادات ذات التحكم والمقارنات المكلفة، واستبدالها ببوابات الدوران المتحكم بها في تصميم ARC.

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

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

• كفاءة الموارد: يقلل هذا النهج بشكل كبير من متطلبات الكيوبتات والبوابات والعمق، وهو أمر حيوي للأجهزة الكمية القريبة من العصر الحالي ذات الترابط والتماسك المحدود.
• البنية الخوارزمية: يتيح التحسين ضمن تنفيذ واحد لخوارزمية البحث من خلال ترميز التكلفة مباشرة في سعات الاحتمال، مما يلغي الحاجة لتحديثات العتبة التكرارية المطلوبة من الأوراكل البولياني. تختار الخوارزمية الحلول المرشحة بناءً على احتمالات القياس، تليها خطوة تحقق لتأكيد الصلاحية.
• القابلية للتوسع: يشير التحليل النظري إلى أن حاسب التكلفة في ARC لديه تعقيد زمني قدره $O(n^2 \log n)$، وهو أقل بكثير من التوسع الأسي الملاحظ في الطرق البوليانية السابقة لتخصيص الحالة.

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