The power of constant-depth quantum circuits of unbounded size

ملخص تقني: قوة الدوائر الكمومية ذات العمق الثابت والحجم غير المحدود

بيان المشكلة
تتقصى الورقة البحثية القدرة الحسابية للدوائر الكمومية عند إزالة القيود المفروضة على حجم الدائرة والمساحة المساعدة (ancillary space). في التعقيد الكلاسيكي، لا تستطيع فئة $AC^0$ (الدوائر ذات العمق الثابت مع بوابات AND/OR ذات المدخلات غير المحدودة) حساب التكافؤ (parity). ومع ذلك، إذا رُفعت قيود الحجم متعدد الحدود، يمكن حساب كل دالة بولينية في عمق ثابت عبر إنشاءات الصيغة الطبيعية المشتملة (DNF). يتساءل المؤلفون عما إذا كانت ظاهرة مماثلة تنطبق على الدوائر الكمومية المبنية من بوابات أحادية الكيوبت (single-qubit gates) عشوائية وبوابات Toffoli المعممة ($QAC^0$). وتحديداً، هل يمكن تنفيذ أي عملية وحدوية (unitary operation) بدقة في عمق ثابت إذا كان حجم الدائرة وعدد الكيوبتات المساعدة غير مقيدين؟

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

1. حساب العضوية في أي مجموعة $L \subseteq \{0, 1\}^n$.
2. تنفيذ أي تبديل (permutation) لحالات القاعدة الحسابية.
3. تحضير أي حالة كمومية نقية.
4. تنفيذ أي عملية وحدوية عشوائية على كل حالة مدخلة.

المنهجية
يستخدم المؤلفون مزيجاً من إنشاءات الدوائر الكلاسيكية القابلة للانعكاس، والتقنيات الكلاسيكية الاحتمالية المكيفة للمجال الكمومي، وبروتوكولات النقل الآني الكمومي (quantum teleportation).

• الإنشاءات الكلاسيكية القابلة للانعكاس: يثبت المؤلفون أولاً أن التبديلات الكلاسيكية العشوائية لسلاسل البتات يمكن تنفيذها في عمق ثابت باستخدام بوابات Toffoli وfanout. ويتم تحقيق ذلك عبر مخطط "ترميز المؤشر" (indicator encoding): حيث يتم رسم الخرائط للمدخل إلى متجه مؤشر ذي أبعاد $2^n$ (حيث يوجد عنصر واحد فقط قيمته 1)، ثم معالجته، ثم فك ترميزه للعودة إلى السلسلة الأصلية. يسمح هذا بالتقييم المتوازي لجميع المدخلات الممكنة.
• التكيف الاحتمالي إلى الكمومي: لتحضير التوزيعات الاحتمالية النقية وحالات الحالة النقية، يكيف المؤلفون إنشاءً كلاسيكياً احتمالياً. يتضمن ذلك أخذ عينات من البتات بشكل مستقل لترميز توزيع بناءً على موقع أول '1'. وفي السياق الكمومي، يتم جعل هذه العملية متماسكة (coherent) عبر تطبيق دورات عكسية (inverse rotations) على الكيوبتات التي تلي أول '1' لإعادتها إلى الحالة $|0\rangle$ دون تدمير التراكب (superposition).
• توسيع مجموعة البوابات: بينما تشمل مجموعة البوابات الأساسية بوابات أحادية الكيوبت وبوابات Toffoli المعممة، يستخدم المؤلفون بوابات fanout كأداة مفاهيمية. ويستشهدون بنتائج Grier وMorris وWu [GMW26] وRosenthal [Ros20] لإظهار أن fanout يمكن تنفيذه بدقة في عمق ثابت باستخدام مجموعة البوابات الأساسية فقط، وإن كان ذلك قد يتطلب زيادة في حجم الدائرة إلى حدود أسية مزدوجة.
• الاختزال للعمليات الوحدوية: بالنسبة لتنفيذ العمليات الوحدوية العشوائية، لا يقدم المؤلفون إنشاءً مباشراً. بدلاً من ذلك، يقدمون عدة صياغات واختزالات متكافئة. وتشمل هذه اختزال تنفيذ العمليات الوحدوية إلى:
  • استنساخ ناقلات (vectors) لقاعدة متعامدة محددة.
  • تبديل قوائم من ناقلات القاعدة.
  • فك ترميز تسميات القاعدة.
  • تنفيذ عمليات وحدوية ذات مجموع صف وعمود وحدة (عبر صيغة Idel-Wolf normal form).
  • تنفيذ عمليات وحدوية متناظرة (involutions) عديمة الأثر (traceless) (باستخدام كيوبت نظيف إضافي واحد).
• النقل الآني القائم على المنافذ (PBT): للتقرب من تنفيذ العمليات الوحدوية العشوائية دون الحاجة إلى تصحيحات وحدوية تعتمد على البوابة المحددة، يستخدم المؤلفون النقل الآني القائم على المنافذ (Port-Based Teleportation). يقومون بإنشاء دائرة وحدوية تقوم بـ PBT باستخدام حالات متشابكة قصوى (أو حالات Choi للعملية الوحدوية المستهدفة) وقياس مشترك، متبوعاً باختيار المنفذ.

المساهمات والنتائج الرئيسية

1. الإنشاءات ذات العمق الثابت الدقيق لمهام محددة:

   • التبديلات: يمكن تنفيذ أي تبديل لمتسلسلات البتات في عمق ثابت (العمق $\le 20$) باستخدام $O(n2^n)$ من البوابات والكيوبتات المساعدة.
   • العمليات الوحدوية القطرية: يمكن تنفيذ أي عمليات وحدوية قطرية في عمق ثابت (العمق 7) عبر حساب المؤشرات، وتطبيق الأطوار (phases) بالتوازي، ثم إلغاء الحساب (uncomputing).
   • تحضير الحالة: يمكن تحضير أي حالة كمومية نقية في عمق ثابت (العمق $\le 37$) باستخدام $O(4^n)$ من الكيوبتات و $O(n2^n)$ من البوابات. يتم إعادة جميع الكيوبتات المساعدة إلى الصفر.
   • تنفيذ Fanout: يمكن تنفيذ Fanout بدقة في عمق ثابت باستخدام بوابات أحادية الكيوبت وToffoli المعممة فقط، رغم أن هذا قد يتطلب حجماً أسياً مزدوجاً.

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

3. القياسات التكيفية ونقل البوابات (Gate Teleportation):
   يوضح المؤلفون أنه إذا سُمح بالقياسات البينية التكيفية، فيمكن تنفيذ أي بوابة في المستوى $\ell$ من تسلسل كليفورد (Clifford hierarchy) بعمق $O(\ell)$. علاوة على ذلك، يختزل تنفيذ العمليات الوحدوية العشوائية إلى تنفيذ التناظرات الوحدوية عديمة الأثر في هذا النموذج التكيفي.

4. تقريب النقل الآني القائم على المنافذ (PBT):
   ينشئ المؤلفون دائرة وحدوية لـ Port-Based Teleportation (PBT) لأبعاد مدخل $d$ و $M \ge d^2 - 1$ من المنافذ.

   • العمق: عمق الدائرة هو $O(\sqrt{d})$، وهو مستقل عن عدد المنافذ $M$.
   • الدقة (Fidelity): دقة التشابك (entanglement fidelity) محدودة بـ $F_e \ge (1 - \frac{d^2-1}{2M})^2$.
   • الدقة مقابل العمق: لأي بُعد مدخل $d$ ثابت، يمكن جعل التقريب دقيقاً بشكل تعسفي عن طريق زيادة $M$ دون زيادة عمق الدائرة. ومع ذلك، يظل الاعتماد على بُعد المدخل $d$ قائماً؛ وتظل المسألة مفتوحة حول ما إذا كان يمكن تحقيق حد للعمق مستقل عن $d$.
   • التنفيذ: تستخدم الدائرة فقط بوابات أحادية الكيوبت وToffoli المعممة ولا تتطلب قياسات بينية.

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

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

تتمثل المساهمة الرئيسية فيما يتعلق بالعمليات الوحدوية العامة في إنشاء PBT. يوضح المؤلفون أنه لأي بُعد مدخل ثابت، يمكن تقريب العمليات الوحدوية العشوائية بدقة تعسفية دون زيادة عمق الدائرة عبر زيادة عدد المنافذ. ومع ذلك، فإن عمق هذا الإنشاء يتناسب طردياً مع $O(\sqrt{d})$ مع بُعد المدخل $d$. ويذكر المؤلفون صراحةً أن مسألة ما إذا كان يمكن إزالة هذا الاعتماد على $d$ (أي تحقيق حد للعمق مستقل عن $d$) تظل سؤالاً مفتوحاً. تسلط الورقة الضوء على أن الصعوبة الجوهرية في تنفيذ العمليات الوحدوية في عمق ثابت لا تكمن في إنتاج مخرج عشوائي من مدخل ثابت، بل في فرض التأثير على كل حالة مدخلة في آن واحد مع الحفاظ على الوحدوية (unitarity).