A Rigorous and Self--Contained Proof of the Grover--Rudolph State Preparation Algorithm

ملخص تقني لورقة "إثبات صارم وذاتي الاحتواء لخوارزمية تحضير حالة غروفر-رودولف"

بيان المشكلة
يُعد تحضير الحالات الكمومية حيث تُشفر السعات التوزيعات الاحتمالية الكلاسيكية عملية أولية أساسية، لا سيما في خوارط مونت كارلو الكمومية وتقدير السعة. خوارزمية غروفر-رودولف هي طريقة مشهودة على نطاق واسع لتحضير حالة مكونة من $n$ كيوبت $\sum_k \sqrt{p_k} |k\rangle$ من توزيع احتمالي $\{p_k\}$ مُعرَّف على شبكة ثنائية (dyadic grid). ومع ذلك، غالبًا ما تعرض الأدبيات الحالية هذه الإجراءات بمستوى عالٍ من التجريد، معتمدةً على تبريرات غير رسمية أو افتراضات ضمنية فيما يتعلق ببنية التنقيح الثنائي، وتعيين زوايا الدوران، ودلالات البوابات المتحكم بها. علاوة على ذلك، هناك نقص في التحليل الصارم حول كيفية انتقال الأخطاء الحتمية في تخليق الزوايا (بسبب الدقة المحدودة) إلى التوزيع النهائي، بشكل متميز عن الضجيج الإحصائي (shot noise).

المنهجية
يقدم المؤلفون معالجة رياضية كاملة وذاتية الاحتواء لبناء غروفر-رودولف، مهيكلة في ثلاث ركائز تحليلية رئيسية:

1. الصياغة الصارمة وإثبات الصحة:

   • يقوم البحث بصياغة شجرة الاحتمالات الثنائية وتعريف الاحتمالات المستهدفة $p_k$ كتكاملات لدالة كثافة $\varrho(x)$ عبر فترات ثنائية.
   • يستنتجون تحليلاً مثلثياً لهذه الاحتمالات، حيث يعبرون عن $p_k$ كحاصل ضرب مربعات دوال الجيب وجيب التمام للزوايا الشرطية $\theta_w$.
   • باستخدام الاستقراء العكسي، يثبت المؤلفون أن الدائرة، المبنية كمجموع لواحدات المراحل (stage unitaries $U_j$) (التي تتكون كل منها من دورات $R_y$ متعددة التحكم)، تُحضّر الحالة المستهدفة بدقة. يتتبع الإثبات صراحةً انتشار السعة عبر تسلسل الدورات المتحكم بها، مع عزل الطبيعة المتسلسلة للهويات المثلثية.

2. تحليل الاستقرار للزوايا غير المثالية:

   • يحلل المؤلفون حساسية التوزيع الناتج للارتباكات في زوايا الدوران. يقومون بنمذجة تنفيذ الزوايا كـ $\tilde{\theta}_w = \theta_w + \epsilon_w$.
   • من خلال بناء سلسلة من التوزيعات "الهجينة" التي تنتقل من الزوايا الدقيقة إلى المضطربة خطوة بخطوة، يستنتجون حداً كمياً لمسافة التباين الكلي (Total Variation distance) بين التوزيع المثالي والمضطرب.
   • يحلل هذا الجزء أخطاء التخليق الحتمية عن الأخطاء العشوائية الناتجة عن أخذ العينات.

3. الترجمة إلى الدوائر المنطقية (Transpilation):

   • يحدد البحث كل مرحلة من خوارزمية غروفر-رودولف كدوران $R_y$ متحكم به موحد (multiplexor).
   • يقدم البحث ترجمة صريحة، خالية من الكيوبتات المساعدة (ancilla-free)، لهذه المراحل إلى مجموعة البوابات الأساسية $\{R_y(\cdot), X, \text{CNOT}\}$.
   • يتم تحقيق ذلك عبر تفكيك سلم كود غراي (Gray-code ladder decomposition) مدمج مع تحويل زوايا "والش-هادامارد"، مما يحول قائمة الدورات المتحكم بها بالأنماط إلى تسلسل من $2^{j-1}$ من دورات الكيوبت الواحد و $2^{j-1}-1$ من بوابات CNOT.

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

• الدقة الرياضية: يقدم البحث أول إثبات صريح وذاتي الاحتواء لنظرية غروفر-رودولف، موضحاً هويات التنقيح الثنائي وحجة السعة الاستقرائية التي غالباً ما تُترك ضمنية في الأعمال السابقة.
• نظرية الاستقرار الكمي: تثبت الورقة أنه إذا تم اضطراب كل زاوية دوران بمقدار $\eta$ على الأكثر، فإن التوزيع الناتج يتغير بمقدار $\min(1, n\eta)$ كحد أقصى في مسافة التباين الكلي. هذا الحد الخطي في العمق مستمد من بنية شجرة الاحتمال الشرطي بدلاً من تراكم معيار العامل (operator-norm) في أسوأ الحالات.
• قواعد تصميم صريحة: من خلال دمج نظرية الاستقرار مع حدود تركيز هوفدينغ (Hoefding concentration bounds)، يستنتج المؤلفون قاعدة تصميم مغلقة لتحقيق دقة مستهدفة $\epsilon$ بثقة $1-\delta$:
  • دقة الزاوية: $b \geq \log_2(2n\pi/\epsilon)$ بت.
  • عدد عمليات القياس (shots): $S \geq 2^{n+1} \log(2/\delta) / \epsilon^2$.
• التجميع الخالي من الكيوبتات المساعدة: يوفر البحث كوداً زائفاً (pseudo-code) ومخطط دائرة قابلاً للتنفيذ مباشرة للترجمة إلى قاموس بوابات قياسي دون استخدام كيوبتات مساعدة، باستخدام سلالم كود غراي.

النتائج

• الحدود النظرية: يؤكد حد الاستقرار المستنتج أن أخطاء الزاوية الحتمية تتناسب خطياً مع عدد الكيوبتات $n$ (تحديداً $n\eta$)، بينما يتناسب ضجيج أخذ العينات مع الجذر التربيعي لعدد النتائج ($\sqrt{2^n/S}$).
• التحقق العددي: أكدت المحاكاة لعدد كيوبتات $n \in \{2, 3, 4\}$ باستخدام كثافة احتمالية مثلثية التنبؤات النظرية.
  • دقة الزاوية: عند $b=8$ بت، بلغ خطأ التباين الكلي الناتج عن التكميم حوالي $3.5 \times 10^{-3}$. زيادة الدقة إلى 16 أو 32 بت تقلل هذا الخطأ بعدة مراتب عشرية ($< 10^{-5}$ و $< 10^{-9}$ على التوالي)، لكن الخطأ يظل مستقلاً إلى حد كبير عن $n$ عند ثبات عمق البت.
  • ضجيج أخذ العينات (Shot Noise): يتناسب خطأ التباين الكلي الناتج عن عدد المحاولات المحدود مع $O(\sqrt{2^n/S})$.
  • الهيمنة: أظهرت النتائج أنه بالنسبة لأعداد المحاولات العملية ($S \leq 4096$) والدقة المتوسطة ($b \geq 8$)، فإن ضجيج أخذ العينات هو الذي يهيمن على الخطأ الإجمالي. خطأ دقة الزاوية عند $b=8$ هو بالفعل ضئيل مقارنة بحد ضجيج أخذ العينات.

الأهمية والادعاءات
يدعي المؤلفون أن عملهم يوفر أساساً ضرورياً للتطبيق الصارم لخوارزمية غروفر-رودولف من خلال:

1. توضيح الصحة: إزالة الغموض بشأن التشغيل الدقيق للخوارزمية وإثبات صلاحيتها دون الاعتماد على الموروثات البرمجية (folklore) الخاصة بالتجميع.
2. فصل مصادر الخطأ: الفصل الصريح بين أخطاء التخليخ الحتمية والتقلبات الإحصائية الناتجة عن عدد المحاولات المحدود، وإظهار أن الأولى يمكن جعلها مهملة بدقة بت متوسطة ($b=8$ إلى $16$)، بينما يحدد الأخير مقياس الميزانية المطلوبة للقياس.
3. التنفيذ العملي: توفير مسار مباشر للتنفيذ على الأجهزة عبر تفكيك كود غراي الخالي من الكيوبتات المساعدة، مما يجعل الخوارزمية قابلة للتطبيق الفوري على المعالجات الكمومية الحالية ذات الاتصال المحدود والموارد المحدودة من الكيوبتات المساعدة.

تخلص الورقة إلى أنه بينما تعد الخوارزمية أنيقة مفاهيمياً، فإن فائدتها العملية مقيدة أساساً بميزانية المحاولات (shot budget) المطلوبة للتغلب على الضجيج الإحصائي، وليس بدقة تخليق الزوايا، بشرط استخدام عمق بت معقول (على سبيل المثال 8 بت).