Shadow bootstrapping: Nearly minimal-setting pure-state tomography with shallow Clifford measurements

ملخص تقني: التمهيد الظلي لتقصي الحالة النقية في إعدادات شبه دنيا

بيان المشكلة
يهدف تقصي الحالة الكمية (QST) إلى إعادة بناء حالة كمية مجهولة من بيانات القياس. بالنسبة لحالة نقية $n$-كيوبت $|\psi\rangle$ في بُعد $d=2^n$، فإن تعقيد العينات الأمثل معروف بأنه $\Theta(d/\epsilon)$ نسخة لتحقيق عدم وفاء (infidelity) بمقدار $1 - |\langle \hat{\psi}|\psi\rangle|^2 \le \epsilon$. وبينما تم تحقيق هذا التعقيد في العينات بواسطة بروتوكولات متنوعة، لا تزال هناك عقبة كبيرة تتمثل في عدد إعدادات القياس المتميزة المطلوبة. تتطلب العديد من الطرق الحالية عدداً من الإعدادات ينمو حدودياً مع $1/\epsilon$ أو خطياً مع $d$، مما يؤدي إلى أعباء تجريبية كبيرة بسبب تجميع الدارات وتغييرات برنامج التحكم. علاوة على ذلك، فإن تخزين نتائج القياس الخام لعدد كبير من الطلقات (shots) يستهلك الذاكرة بكثافة. الهدف هو تحقيق تعقيد عينات أمثل باستخدام عدد شبه أدنى من إعدادات القياس (من الناحية المثالية يكون مستقلاً عن $d$ ولوغاريتمياً في $1/\epsilon$) مع الحفاظ على معالجة كلاسيكية فعالة من تمثيلات بيانات مدمجة.

المنهجية
يقترح البحث خوارزمية مكونة من مرحلتين تستخدم قياسات كليفورد أحادية النسخة ضحلة غير تكيفية، وتقنية مبتكرة تسمى التمهيد الظلي (Shadow Bootstrapping).

1. مجموعة القياس: يستخدم البروتوكول مجموعة كليفورد مكونة من طبقتين حيث تتكون الدارات من طبقات متناوبة من وحدات كليفورد المحلية التي تعمل على كتل مكونة من $k$-كيوبت (حيث $k = \Theta(\log n)$). يضمن هذا عمق دائرة قدره $O(\log n)$.
2. تمثيل البيانات: بدلاً من تخزين قوائم السلاسل الثنائية الخام، تقوم الخوارزمية بتجميع نتائج القياس في رسوم بيانية (histograms) لكل أساس. يقلل هذا من متطلبات الذاكرة ويعمل كمدخل للمعالجة الكلاسيكية اللاحقة.
3. التهيئة (إعادة بناء الشجرة):
   • تقوم الخوارزمية أولاً ببناء تقدير أولي $|\sigma_0\rangle$ بتداخل ثابت ($\ge 1/2$) مع الحالة المستهدفة $|\psi\rangle$.
   • يتم تحقيق ذلك عبر إطار إعادة بناء تكراري (مستوحى من [GGH+26]) يبني الحالة من أوراق شجرة ثنائية (تمثل الحالات الشرطية بعد قياس البوادئ/prefixes) صعوداً إلى الجذر.
   • عند كل عقدة، يتم تقدير "مصفوفة إعادة بناء" $2 \times 2$ باستخدام مقدرات الظل المستمدة من الرسوم البيانية. يوفر المتجه الذاتي العلوي لهذه المصفوفة المعاملات لدمج تقديرات الأبناء.
   • تستخدم هذه المرحلة $O(d)$ من النسخ و $O(n^3)$ من إعدادات القياس، مما يضمن أن التقدير الأولي دقيق بما يكفي لتمهيد المرحلة التالية.
4. التمهيد الظلي (الصقل التكراري):
   • الابتكار الجوهري هو عملية صقل تكرارية تقلل عدم الوفاء المستهدف إلى النصف في كل مرحلة باستخدام عدد ثابت فقط من إعدادات القياس الجديدة.
   • تقليل التباين: تتذبذب مقدرات الظل القياسية بسبب الاختيار العشوائي لقواعد القياس. يعمل التمهيد الظلي على التخفيف من حدة ذلك باستخدام التقدير الحالي $|\sigma_{t-1}\rangle$ كمرجع.
   • تقدير المتبقي (Residual Estimation): بالنسبة لدفعة جديدة من القياسات، تحسب الخوارزمية "مقدر المتبقي" المعرف كفرق بين مقدر الظل التجريبي والتنبؤ النظري بناءً على $|\sigma_{t-1}\rangle$.
   • نظرًا لأن الحالة المرجعية $|\sigma_{t-1}\rangle$ قريبة من الحالة الحقيقية، فإن التنبؤ يطابق الترددات المرصودة بدقة، مما يجعل تباين المتبقي يتناسب مع الخطأ الحالي بدلاً من البُعد الكامل.
   • تقوم الخوارزمية بتحديث التقدير بإضافة متوسط المتبقي إلى متجه الحالة السابق وتطبيعها (normalization).
   • تتكرر هذه العملية لـ $J = O(\log(1/\epsilon))$ مرحلة. يزداد عدد الطلقات لكل أساس أسياً ($S_t \propto 2^t$) لقمع ضوضاء الطلقات، بينما يظل عدد القواعد الجديدة لكل مرحلة ثابتاً ($N_t = O(1)$).
5. المعالجة الكلاسيكية اللاحقة:
   • تتجنب الخوارزمية تشكيل مصفوفات ظل كثيفة $d \times d$. بدلاً من ذلك، تستغل بنية مجموعة كليفورد وتحويل والش-هادامارد لتطبيق قناة الظل العكسية مباشرة على المتجهات.
   • يسمح هذا بمعالجة الرسوم البيانية وحساب التحديثات في زمن وذاكرة $\tilde{O}(d)$.

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

• التمهيد الظلي: تقنية تستخدم تقدير الحالة الحالي لتقليل تباين مقدرات المتبقي اللاحقة، مما يتيح إعادة بناء عالية الدقة باستخدام عدد ثابت من إعدادات القياس الجديدة لكل مرحلة صقل.
• إعدادات شبه دنيا: تحقق الخوارزمية تعقيد عينات أمثل $O(d/\epsilon)$ مع استخدام $\tilde{O}(1)$ من إعدادات القيال المتميزة (تحديداً $O(n^3 + \log(1/\epsilon))$)، وهو تحسن كبير عن الطرق السابقة حيث كانت الإعدادات تتناسب مع $1/\epsilon$ أو $d$.
• معالجة الرسوم البيانية الفعالة: توضح الطريقة كيفية إجراء معالجة كلاسيكية بزمن شبه خطي ($\tilde{O}(d)$) مباشرة من الرسوم البيانية للنتائج، متجاوزة بناء المصفوفات الكثيفة.
• دارات ضحلة: يستخدم البروتوكول قياسات كليفورد غير تكيفية بعمق $O(\log n)$، مما يجعله قابلاً للتطبيق على الأجهزة القريبة من العصر الكمي (near-term devices).

النتائج
يضع البحث ضمانات نظرية لحالة نقية $n$-كيوبت $|\psi\rangle$ وعدم وفاء مستهدف $\epsilon$:

• تعقيد العينات: $T = O(d \log(1/\delta) / \epsilon)$ نسخة، وهو أمثل حتى العوامل اللوغاريتمية.
• إعدادات القياس: $N = \tilde{O}(1)$ (تحديداً $O(n^3 + \log(1/\epsilon))$) من قواعد القياس المتميزة.
• عمق الدائرة: $O(\log n)$.
• وقت التشغيل الكلاسيكي: $\tilde{O}(d)$ زمن مع إعطاء الرسوم البيانية لكل أساس (مع تجاهل العوامل اللوغاريتمية لـ $d$ و $1/\epsilon$ و $1/\delta$).
• احتمالية النجاح: تخرج الخوارزمية حالة $|\hat{\psi}\rangle$ تحقق $1 - |\langle \hat{\psi}|\psi\rangle|^2 \le \epsilon$ باحتمالية لا تقل عن $1-\delta$.

الأهمية
يزعم المؤلفون أن هذا هو أول خوارزمية تحقق في آن واحد:

1. تعقيد عينات أمثل ($O(d/\epsilon)$).
2. عدد شبه أدنى من إعدادات القياس (مستقل عن $d$ ولوغاريتمي في $1/\epsilon$).
3. وقت معالجة كلاسيكية شبه خطي من بيانات الرسوم البيانية المدمجة.
4. دوائر قياس ضحلة ($O(\log n)$ عمق).

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