Learning quantum Hamiltonians at any temperature in polynomial time

ملخص تقني: تعلم الهاميلتونيّات الكمومية عند أي درجة حرارة في وقت حدودي

بيان المشكلة
تتناول الورقة مشكلة تعلم الهاميلتوني (Hamiltonian learning) للأنظمة الكمومية المحلية. يُعطى نظام من $n$ من الكيوبتات (qubits) موصوف بهاميلتوني محلي $H = \sum_{a=1}^m \lambda_a E_a$، حيث تكون حدود التفاعل $E_a$ معروفة، ومتميزة، وغير متطابقة (non-identity)، وهي مؤثرات باولي محلية ذات حدود في الموضع (bounded locality)، بينما تكون المعاملات $\lambda_a$ هي قوى التفاعل المجهولة في النطاق $[-1, 1]$. الهدف هو تقدير قيم $\lambda_a$ باستخدام خوارزمية. تمتلك الخوارزمية إمكانية الوصول إلى نسخ من حالة جيبس (Gibbs state) $\rho = e^{-\beta H} / \text{tr}(e^{-\beta H})$ عند درجة حرارة عكسية معلومة $\beta > 0$. والهدف هو إخراج تقديرات $\hat{\lambda}_a$ بحيث يكون $|\hat{\lambda}_a - \lambda_a| \leq \epsilon$ لجميع القيم $a$، باستخدام عدد من العينات ووقت تشغيل حدودي في حجم النظام $n$ (وكذلك عدد الحدود $m$) وفي $1/\epsilon$.

قبل هذا العمل، كانت معروفة حدود التعقيد في عدد العينات (polynomial sample complexity) [AAKS20]، إلا أن الخوارزميات الحسابية المقابلة لها كانت غير فعالة (تستغرق وقتاً أسياً) لأنظمة درجات الحرارة المنخفضة العامة. كانت توجد خوارزميات فعالة فقط لدرجات الحرارة العالية ($\beta$ صغيرة) [HKT22] أو للهاميلتونيّات ذات الحدود المتبادلة (commuting terms) [AAKS21]. كان السؤال المفتوح المركزي هو ما إذا كان تعلم الهاميلتوني عند درجات الحرارة المنخفضة ( $\beta$ كبيرة) يمكن حله في وقت حدودي في $n$.

المنهجية
يقترح المؤلفون خوارزمية فعالة حسابياً تعتمد على تسلسل مجموع المربعات (Sum-of-Squares - SoS). وتتضمن الاستراتيجية التقنية الجوهرية ثلاث مكونات رئيسية:

1. صياغة نظام قيود متعدد الحدودات:
   بدلاً من عكس الخريطة من المعاملات إلى الهوامش المحلية (local marginals) بشكل مباشر (وهو أمر صعب حسابياً)، يحدد المؤلفون نظاماً من القيود التي يجب أن تحققها المعاملات الحقيقية. يتضمن هذا النظام:

• قيود على المعاملات: $-1 \leq \lambda'_a \leq 1$.
• قيود التبادل (Commutator constraints): ضمان أن الهاميلتوني المرشح $H'$ يتبادل مع حالة جيبس $\rho$ (أي $[H', \rho] \approx 0$).
• قيود متعددات الحدود "المسطحة" (Flat polynomial constraints): استبدال الأس المصفوفي $e^{-\beta H'}$ بتقريب متعدد حدود من درجة منخفضة $p(H' | P)$ يعمل على الملاحظات المحلية. وتحديداً، يفرضون أنه بالنسبة لمؤثرات باولي المحلية $P, Q$، فإن القيمة المتوقعة $\text{tr}(Q e^{-\beta H'} P e^{\beta H'} \rho)$ تكون قريبة من $\text{tr}(PQ\rho)$.

2. التقريب المسطح للأس متعدد الحدودات:
   تتمثل العقبة التقنية الرئيسية في أن تقريبات سلسلة تايلور القياسية لـ $e^{-\beta x}$ تنمو بسرعة كبيرة خارج نطاق التقريب، مما يجعلها غير مناسبة لدرجات الحرارة المنخفضة حيث تكون فروق القيم الذاتية كبيرة. يبني المؤلفون تقريباً جديداً لمتعدد الحدود "المسطح" $p(x)$ الذي:

• يقرب $e^{-\beta x}$ جيداً على الفترة $[-1, 1]$.
• ينمو بمعدل أسي متحكم فيه وبطيء ($e^{\eta \beta |x|}$) خارج هذه الفترة.
  هذا البناء مستوحى من تقنيات "التقشير" (peeling) التكرارية المستخدمة في حدود ليب-روبنسون (Lieb-Robinson bounds). وهذا يسمح باستبدال الأس المصفوف في القيود بمتعدد حدود من درجة منخفضة في المجاهيل $\lambda'_a$.

3. الترجمة بين متعددات الحدود والمبدلات المتداخلة (Nested Commutators):
   يضع المؤلفون ترجمة رسمية بين متعددات الحدود القياسية متعددة المتغيرات والمبدلات المتداخلة للمؤثرات. باستخدام صيغة هادامارد (Hadamard formula)، يوضحون أن حدوداً مثل $e^{-\beta H'} P e^{\beta H'}$ يمكن التعبير عنها كمتعددات حدود في القيم الذاتية لـ $H'$، والتي تقابل المبدلات المتداخلة $[H', P]_\ell$. ويثبتون أن المتطابقات متعددة الحدود في المجال القياسي تترجم إلى متطابقات تتضمن مبدلات متداخلة مع حدود خطأ صغيرة، بشرط أن تكون المؤثرات محلية.

4. تخفيف مجموع المربعات والقابلية للتمييز (Identifiability):
   النتيجة هي نظام من قيود متعددات الحدود من درجات منخفضة. يتم حل هذا النظام باستخدام تخفيف (relaxation) من نوع "مجموع المربعات" (SoS) من الدرجة $d$، والذي يمكن صياغته كبرنامج برمجة شبه محدد (SDP).

• القابلية للتحقق (Feasibility): يثبتون أن المعاملات الحقيقية تحقق النظام (مع مراعاة ضوضاء العينات).
• القابلية للتمييز (Identifiability): يقدمون برهاناً بنظام SoS مفاده أن أي حل للنظام يجب أن يكون قريباً من المعاملات الحقيقية. يعتمد هذا على فلسفة "البرهان إلى الخوارزميات". وتتمثل الخطوة الحاسمة في إظهار أن تباين المؤثرات المحلية تحت حالة جيبس بعيد عن الصفر (وهو نظير كمومي لخصائص النماذج الرسومية الكلاسيكية)، مما يضمن إمكانية تمييز المعاملات.
• الكفاءة: من خلال تحليل البنية المحددة لبرهانات SoS، يظهرون أن مجموعة فرعية متفرقة فقط من الحدود (monomials) مطلوبة، مما يسمح بحل الـ SDP في وقت حدودي في $m$ وفي $1/\epsilon$ (مع وجود اعتماد أسي على $\beta$ في الدرجة، ولكن حدودي في $n$).

النتائج الرئيسية
تقدم الورقة النظرية 1.1، والتي تنص على أنه لأي درجة حرارة عكسية ثابتة $\beta > 0$ (تحديداً $\beta \geq \beta_c$ لثابت عالمي ما)، توجد خوارزمية لتعلم معاملات الهاميلتوني بدقة $\epsilon$ باحتمالية $99/100$.

• تعقيد العينات: $n \geq \text{poly}(m, (1/\epsilon)^{2O(\beta)})$.
• وقت التشغيل: $n^{O(1)}$ (تحديداً $\text{poly}(m, \log(1/\delta)) \cdot (1/\epsilon)^{2O(\beta)}$).

تعمل الخوارزمية لـ "هاميلتونيّات منخفضة التقاطع" (low-intersection Hamiltonians)، وهي فئة تشمل الهاميلتونيّات المحلية هندسياً على الشبكات (lattices) وتلك المعرفة على رسوم بيانية موسعة (expander graphs).

الأهمية والادعاءات
يدعي المؤلفون أنهم حلوا بالكامل المشكلة المفتوحة المتعلقة بتعلم الهاميلتوني عند درجات الحرارة المنخفضة.

• حل الأسئلة المفتوحة: تقدم النتيجة إجابة إيجابية على السؤال حول إمكانية تعلم الهاملتوني في وقت حدودي عند درجات الحرارة المنخفضة [AAKS20; HKT22; Alh23; AA23]. كما تجيب سلبياً على الفرضية القائلة بأن حالات جيبس عند درجات الحرارة المنخفضة قد تكون عشوائية زائفة (pseudorandom) (السؤال 3 في [AA23]) وإيجابياً على السؤال حول إمكانية التعلم تحت شرط الاستقلال التقريبي (السؤال 2 في [AA23]).
• أداة خوارزمية: يوضح العمل كيف يمكن للأدوات المتطورة من نظرية الأمثلة، وتحديداً تسلسل مجموع المربعات (SoS)، التغلب على الحواجز في التعلم الكمومي متعدد الأجسام التي بدت سابقاً مستعصية بسبب صعوبة حساب دالات التجزئة (partition functions).
• الاستقلالية عن الحدود الكلاسيكية: يشير المؤلفون إلى أنه بينما يتطلب تعلم الهاميلتوني الكلاسيكي (تعلم النماذج الرسومية غير الموجهة) وقتاً أسياً في $\beta$، فإن الإطار الكمومي لا يرث بالضرورة هذه الصعوبة، رغم عدم التبادل وعدم الموضعية للأنظمة الكمومية.
• العملية: تقر الورقة بأنه على الرغم من أن الخوارزمية فعالة نظرياً (بعدد حدودي في $n$)، إلا أن الاعتماد على $\beta$ في الأس الخاص بوقت التشغيل وتعقيد العينات يعني أنها ليست عملية حالياً لدرجات الحرارة المنخفضة جداً أو الأنظمة الكبيرة جداً. ومع ذلك، فهي تثبت إمكانية نظرية حيث لم يكن موجوداً من قبل.

لا تقترح الورقة إعدادات تجريبية جديدة أو تطبيقات عملية فورية، بل تؤطر النتيجة كتقدم أساسي في فهم التعقيد الحسابي لتوصيف الأنظمة الكمومية، وهو أمر ذو صلة خاصة بالتحقق من صحة المحاكيات الكمومية التناظرية (analog quantum simulators) التي تعمل غالباً في درجات حرارة منخفضة.