Counting anticommuting Pauli pairs in linear time

ملخص تقني: عدّ أزواج باولي غير التبادلية في زمن خطي

صياغة المشكلة
تتناول الورقة البحثية روتينًا فرعيًا كلاسيكيًا أساسيًا مطلوبًا في سير عمل الحوسبة الكمومية: معالجة قائمة من $m$ من سلاسل باولي المبعثرة (sparse) لـ $n$ من الكيوبتات، $P^{(1)}, \dots, P^{(m)}$، حيث لكل سلسلة وزن محدود (محلية) $k$ (أي أنها تعمل بشكل غير متطابق على $k$ من الكيوبتات كحد أقصى). الهدف هو تحديد خصائص التبادل الزوجي لهذه السلاسل. وتحديدًا، يجب أن يحقق الخوارزم تنفيذ أحد المهام الثلاث التالية:

1. العد الدقيق: حساب العدد الدقيق للأزواج غير المرتبة $\{i, j\}$ بحيث $P^{(i)}P^{(j)} = -P^{(j)}P^{(i)}$.
2. التحقق (Certification): التحقق مما إذا كانت جميع السلاسل في المجموعة تتبادل زوجيًا.
3. إيجاد الشاهد (Witness Finding): إذا لم تكن جميع السلاسل تتبادل فيما بينها، يتم تحديد زوج محدد $(i, j)$ لا يتبادل.

النهج القياسي يمثل سلاسل باولي في الصيغة الرمزية الثنائية (binary symplectic form) ويتحقق من كل زوج، مما يؤدي إلى تعقيد زمني قدره $O(m^2)$ (أو $O(m^2 k)$ للسلاسل المبعثرة). وبينما يتطلب سرد جميع الحواف غير التبادلية في رسم بياني كثيف بطبيعته زمنًا قدره $\Omega(m^2)$، يشير المؤلفون إلى أن العد الدقيق والتحقق غالبًا ما يتطلبان مخرجات ذات حجم ثابت أو لوغاريتمي، مما يشير إلى إمكانية تحسين دون التربيعي.

المنهجية: خوارزمية "المحلية-زيتا" (Locality-Zeta Algorithm)
يقترح المؤلفون خوارزمية تعمل في زمن $O(m)$ بالنسبة لـ $k$ ثابتة، حيث تنقل النموذج من المقارنة الزوجية إلى تجميع الأنماط. الجوهر في هذه الطريقة هو بنية بيانات تسمى بنية بيانات المحلية-زيتا (locality-zeta data structure)، والتي تحتفظ بأعداد الأنماط الفرعية الموسومة لسلاسل تم إدراجها مسبقًا.

1. تعريف النمط: النمط المسمى لباولي هو زوج $(A, a)$، حيث $A$ هي مجموعة جزئية من مواقع الكيوبت و $a$ يخصص حرف باولي غير محايد ($X, Y, Z$) لكل موقع في $A$.
2. الإدراج: عند إدراج سلسلة باولي جديدة $Q$، تقوم الخوارزمية بحصر جميع المجموعات الجزئية $A \subseteq \text{supp}(Q)$ وتزيد عدد الأنماط $(A, Q|_A)$ في قاموس. بالنسبة لسلسلة بوزن $w$، يتضمن ذلك $2^w$ من عمليات التحديث.
3. الاستعلام عبر هوية "مجموعة جزئية زيتا": للاستعلام عن سلسلة باولي $P$ مقابل مجموعة السلاسل المدرجة مسبقًا $G$، تحسب الخوارماج مجموعًا مرجحًا عبر جميع المجموعات الجزئية $A \subseteq \text{supp}(P)$.
   • تحسب $F_G(P, A)$، وهي عدد السلاسل في $G$ التي تتعارض مع $P$ في كل إحداثي في $A$.
   • تحسب "مجموع زيتا" $Z_G(P) = \sum_{A \subseteq \text{supp}(P)} (-2)^{|A|} F_G(P, A)$.
   • يتم اشتقاق عدد السلاسل غير التبادلية كـ $\text{anti}_G(P) = (|G| - Z_G(P)) / 2$.

تعتمد الصحة على مبدأ الإدراج والتحليل (تحديدًا هوية مجموعة جزئية زيتا) لعزل زوجية حجم مجموعة التعارض. إذا كان حجم مجموعة التعارض $|\text{conf}(P, Q)|$ فرديًا، فإن الحدود في المجموع تلغي بعضها البعض لتعطي $-1$؛ وإذا كان زوجيًا، فإنها تجمع لتكون$+1$.

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

• التعقيد الزمني الخطي: تقدم الورقة خوارزمية ذات تعقيد زمني متوقع قدره $O(\sum_{i=1}^m w_i 3^{w_i})$، حيث $w_i$ هو وزن السلسلة رقم $i$. في نظام المحلية المحدودة حيث $w_i \leq k$ لجميع $i$، يصبح التعقيد $O(m k 3^k)$. وبما أن $k$ تُعامل كثابت، فإن الخوارزمية تعمل في زمن خطي $O(m)$ بالنسبة لعدد السلاسل $m$.
• التعقيد المكاني: تتطلب الخوارزمية مساحة قدرها $O(\sum_{i=1}^m w_i 2^{w_i})$ لمفاتيح القاموس، وهو ما يتبسط إلى $O(m k 2^k)$ للمحلية المحدودة.
• المثالية (Optimality): يزعم المؤلفون أنه بالنسبة لـ $k$ ثابتة في نموذج المدخلات المبعثرة، فإن هذه الخوارزمية مثالية حتى عامل ثابت يعتمد على $k$.
• إيجاد الشاهد: يمكن توسيع الخوارزمية لإرجاع زوج شاهد محدد $(i, j)$ إذا وجد. وبينما تكون خطوات العد والتحقق خطية، فإن إيجاد الشاهد المحدد يتضمن مسحًا للسلاسل السابقة، مما يضيف تكلفة $O(mk)$، والتي تظل فعالة مقارنة بالأساس$O(m^2)$.

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

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