Stratified Sampling for Quasi-Probability Decompositions

إليك ملخص تقني مفصل للورقة البحثية بعنوان "التحليل الطبقي لأخذ العينات في تفكيكات الاحتمالية شبه الكلية" (Stratified Sampling for Quasi-Probability Decompositions) للباحثين جوشوا دب و بالينت كوتزور.

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

تُعد تفكيكات الاحتمالية شبه الكلية (QPDs) أدوات أساسية في الحوسبة الكمومية لمحاكاة العمليات الكمومية الصعبة، وتخفيف الأخطاء (مثل إلغاء الخطأ الاحتمالي، PEC)، وإجراء التوليف الاحتمالي. يقوم الـ QPD باستبدال قناة وحدوية مستهدفة بمجموعة من القنوات التي يسهل تنفيذها، مع وزنها باحتمالات شبه كلية (والتي يمكن أن تكون سالبة).

بينما تسمح الـ QPDs بالتقدير غير المنحاز للملاحظات، إلا أنها تفرض عبئاً إضافياً كبيراً: تباين التكوين (configuration variance).

• المشكلة: تستخدم بروتوكولات QPD القياسية "أخذ عينات ساذج" (naïve sampling)، حيث يتم سحب تكوينات الدوائر بشكل مستقل ومتماثل التوزيع (i.i.d.) من توزيع حاصل ضرب. يؤدي هذا إلى إدخال مكون تباين كلاسيكي (تباين التكوين) بالإضافة إلى ضجيج "قاعدة بورن" الكمي المتأصل (ضجيج Shot noise).
• النتيجة: للوصول إلى دقة مستهدفة، يجب أن يتناسب العدد الإجمالي لتنفيذات الدائرة ($N$) مع مربع المعيار الأول للـ QPD ($\|g\|_1^2$). هذا التوسع الأسي غالباً ما يجعل طرق QPD غير عملية للدوائر العميقة.
• الفجوة: يركز العمل الحالي على تحسين تصميم الـ QPD لتقليل $\|g\|_1$. ومع ذلك، بالنسبة لـ QPD ثابت، لم يتم تحسين كفاءة استراتيجية أخذ العينات نفسها بشكل منهجي لتقليل الثوابت المسبقة للتباين.

2. المنهجية

يقترح المؤلفون إطار عمل يعتمد على أخذ العينات الطبقي (Stratified Sampling)، وهي تقنية من الإحصاء الكلاسيكي، تم تكييفها لتفكيكات QPD ذات شكل الضرب (product-form QPDs).

أ. تفكيك التباين

يصنف المؤلفون مُقدّر الـ QPD كعملية مونت كارلو ذات مستويين:

1. مستوى التكوين: أخذ عينة من متغير الدائرة $\ell$ من التوزيع $p(\ell)$.
2. مستوى الطلقات (Shot Level): تكرار القياس $R$ من المرات لكل $\ell$ لمتوسط ضجيج قاعدة بورن.

باستخدام قانون التباين الكلي، يقومون بتفكيك التباين الإجمالي للمُقدّر:
$$\text{Var}(Y) = \underbrace{\mathbb{E}[\text{Var}(Y|\ell)]}_{\text{ضجيج قاعدة بورن}} + \underbrace{\text{Var}(\mathbb{E}[Y|\ell])}_{\text{تباين التكوين}}$$
يستهدف أخذ العينات الطبقي المصطلح الثاني (تباين التكوين) دون تغيير التوقع المستهدف أو ضجيج قاعدة بورن.

ب. استراتيجية أخذ العينات الطبقي

بدلاً من سحب التكوينات بشكل i.i.d.، يقسم المؤلفون فضاء التكوين إلى طبقات (strata) بناءً على إحصائية حتمية $S(\ell)$.

• التخصيص النسبي (Proportional Allocation): يخصصون عدداً ثابتاً من العينات $K_s$ لكل طبقة $s$ بما يتناسب مع كتلة احتمالها $w_s$ (أي $K_s \approx K \cdot w_s$).
• الضمان النظري: يثبتون النظرية 1: في ظل التخصيص النسبي المثالي، يكون تباين المُقدّر الطبقي أبداً ليس أسوأ من أخذ العينات الساذج. التناقص في التباين يساوي تماماً "التباين بين الطبقات" (تباين متوسطات الطبقات).
  $$\text{Var}_{\text{naïve}} - \text{Var}_{\text{strat}} = \frac{1}{K} \sum_s w_s (\mu_s - \bar{\mu})^2 \geq 0$$

ج. متجه العدات (Counts-Vector Stratification)

لجعل هذه الخوارزمية صريحة خوارزمياً بالنسبة لـ product-form QPDs، قدموا إحصائية محددة: متجه العدات (Counts Vector).

• التعريف: لدائرة بعمق $\nu$ وعرض محلي $d$، يكون التكوين عبارة عن سلسلة $\ell = (\ell_1, \dots, \ell_\nu)$. يسجل متجه العدات $M = (M_1, \dots, M_d)$ تكرار كل فهرس أولي محلي، متجاهلاً الترتيب (الثبات تحت التبديل).
• الكفاءة: بينما يكون العدد الإجمالي للتكوينات هو $O(d^\nu)$، فإن عدد متجهات العدات المتميزة (الطبقات) هو فقط $O(\nu^{d-1})$، وهو متعدد الحدود في العمق بالنسبة لعرض ثابت.
• البرمجة الديناميكية (DP):
  • المسار الأمامي (Forward Pass): يحسب أوزان الاحتمال الدقيقة ($w_m$) لكل متجه عدات باستخدام توزيع Poisson-Multinomial. التعقيد: $O(d \nu^d)$.
  • المسار الخلفي (Backward Pass): يتيح أخذ عينات شرطية دقيقة لتكوين $\ell$ بناءً على متجه عدات مستهدف $M=m$. التعقيد: $O(\nu d)$ لكل عينة.
• التعامل مع البواقي (Residual Handling): بما أن أعداد العينات يجب أن تكون أعداداً صحيحة، استخدم المؤلفون نظام "توزيع هاميلتون مراعٍ للبواقي" (Residual-Aware Hamilton Apportionment). يضمن هذا عدم الانحياز بدقة حتى عندما لا يكون النصيب النسبي المثالي عدداً صحيحاً، وذلك عبر تجميع "الطبقات المتبقية" في سلة بواقي.

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

1. الإطار النظري: وضع إطار عمل لكون أخذ العينات الطبقي أداة غير منحازة ومقللة للتباين لـ QPDs، مع إثبات صارم بأنها ليست أسوأ من أخذ العينات السيدي.
2. البناء الخوارزمي: تطوير عملية طبقية عالمية وثابتة تحت التبديل باستخدام متجهات العدات، مدعومة بخوارزمية برمجة ديناميكية فعالة لحساب الوزن وأخذ العينات الشرطي.
3. التنفيذ العملي: توفير بديل "جاهز للاستبدال" (drop-in replacement) لأخذ عينات QPD الساذج، والذي لا يتطلب موارد كمية إضافية، بل فقط معالجة مسبقة ولاحقة كلاسيكية.
4. تحليل تقليل التباين: إظهار أن الطريقة تقلل بفعالية "التباين المفسر" لفضاء التكوين، خاصة في الأنظمة التي يتم فيها كبح ضجيج الـ shot.

- النتائج الرقمية

قام المؤلفون باختبار طريقتهم على دوائر نموذج آيزينج في مجال عرضي (TFIM) باستخدام اثنين من مخططات QPD القياسية:

• التدريج الزاوي الاحتمالي (PAI): تقريب الدورات المستمرة باستخدام زوايا الأجهزة المتقطعة.
• إلغاء الخطأ الاحتمالي (PEC): تخفيف الضجيج المزيل للاستقطاب (depolarizing noise).

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

• نظام الأوراكل (عند كبح ضجيج الـ shot، $R \to \infty$): حقق أخذ العينات الطبقي تقليلاً هائلاً في التباين بنسبة 60-80%. يشير هذا إلى أن متجه العدات يلتقط جزءاً كبيراً من التباين بين التكوين في مخرجات الدائرة المثالية.
• نظام الطلقة الواحدة ($R=1$): في وجود ضجيج قاعدة بورن المهيمن، كانت التراجعات متواضعة ولكن قوية، حوالي 10%.
• القابلية للتوسع: تظل الطريقة عملية للأعماق المتوسطة (مثلاً $\nu \approx 100$) والعروض المحلية الصغيرة ($d=3$ لـ PAI، $d=4$ لـ PEC). التكلفة المسبقة هي متعددة حدود، وتكلفة توليد كل عينة تطابق أخذ العينات الساذج حتى عامل ثابت.

5. الأهمية والتأثير

• توفير الموارد: من خلال تقليل الثابت المسبق في التباين، تقلل هذه الطريقة فعلياً من إجمالي عدد تنفيذات الدائرة المطلوبة للوصول إلى دقة مستهدفة. وهذا يمدد الفائدة العملية لـ QPDs في الأجهزة القريبة من الكمية والآمنة من الأخطاء في مراحلها الأولى حيث تكون ميزانيات الـ shots محدودة.
• الاستقلالية عن تصميم QPD: يتكامل هذا النهج مع العمل الحالي لتصميم QPDs أفضل (تقليل $\|g\|_1$). فهو يعمل على أي QPD ذي شكل ضرب ثابت، ويقدم تقليلاً "مجانيّاً" للتباين دون تغيير الدائرة الكمية الأساسية أو نموذج الضجيج.
• القابلية للتعميم: رغم التركيز على QPDs ذات شكل الضرب، فإن الإطار المفاهيمي (فصل تباين التكوين عن ضجيج الـ shot واستخدام التدرج) ينطبق على نطاق واسع على خوارزميات كمية عشوائية أخرى، مثل التجميع العشوائي (randomized compiling)، والتدوير (twirling)، والظلال الكلاسيكية (classical shadows).
• القابلية للتطبيق الفوري: لا تتطلب الطريقة قدرات جديدة في الأجهزة الكمية؛ فهي مجرد تحسين كلاسيكي لبروتوكول أخذ العينات، مما يجعلها قابلة للنشر الفوري في مجموعات البرامج الكمية الحالية.

باخت اختصار، تقدم الورقة حلاً خوارزمياً صارماً لعنق الزجاجة المتمثل في "تباين التكوين" في الـ QPDs، مثبتة أن التصميم الذكي لأخذ العينات يمكن أن يحقق وفورات كبيرة ومثبتة في الموارد اللازمة لتخفيف الأخطاء الكمية والمحاكاة.