2025-11-18T06:07:11.995553

Optimal learning of quantum Hamiltonians from high-temperature Gibbs states

Haah, Kothari, Tang
We study the problem of learning a Hamiltonian $H$ to precision $\varepsilon$, supposing we are given copies of its Gibbs state $ρ=\exp(-βH)/\operatorname{Tr}(\exp(-βH))$ at a known inverse temperature $β$. Anshu, Arunachalam, Kuwahara, and Soleimanifar (Nature Physics, 2021, arXiv:2004.07266) recently studied the sample complexity (number of copies of $ρ$ needed) of this problem for geometrically local $N$-qubit Hamiltonians. In the high-temperature (low $β$) regime, their algorithm has sample complexity poly$(N, 1/β,1/\varepsilon)$ and can be implemented with polynomial, but suboptimal, time complexity. In this paper, we study the same question for a more general class of Hamiltonians. We show how to learn the coefficients of a Hamiltonian to error $\varepsilon$ with sample complexity $S = O(\log N/(β\varepsilon)^{2})$ and time complexity linear in the sample size, $O(S N)$. Furthermore, we prove a matching lower bound showing that our algorithm's sample complexity is optimal, and hence our time complexity is also optimal. In the appendix, we show that virtually the same algorithm can be used to learn $H$ from a real-time evolution unitary $e^{-it H}$ in a small $t$ regime with similar sample and time complexity.
academic

التعلم الأمثل لهاميلتونيانات الكم من حالات جيبس عالية الحرارة

المعلومات الأساسية

  • معرّف الورقة: 2108.04842
  • العنوان: التعلم الأمثل لهاميلتونيانات الكم من حالات جيبس عالية الحرارة
  • المؤلفون: جيونجوان هاه (Microsoft Quantum)، روبن كوثاري (Microsoft Quantum)، إيوين تانج (جامعة واشنطن)
  • التصنيف: quant-ph cs.DS cs.LG
  • تاريخ النشر: 17 مارس 2023 (نسخة arXiv)
  • رابط الورقة: https://arxiv.org/abs/2108.04842

الملخص

تبحث هذه الورقة في مشكلة تعلم الهاميلتونيان H بدقة ε من نسخ متعددة من حالة جيبس ρ=exp(-βH)/Tr(exp(-βH)) بدرجة حرارة معكوسة معروفة β. في منطقة درجات الحرارة العالية (β منخفضة)، يقترح المؤلفون خوارزمية تعلم لفئة الهاميلتونيانات منخفضة التقاطع، محققة تعقيد عينة S=O(logN/(βε)²) وتعقيد زمني O(SN)، ويثبتون حدود سفلى متطابقة، مما يدل على أن الخوارزمية مثلى في تعقيد العينة والزمن معاً.

الخلفية البحثية والدافع

تعريف المشكلة

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

الأهمية البحثية

  1. الأهمية الفيزيائية: فهم الخصائص الأساسية للأنظمة الكمية والتنبؤ بسلوكها
  2. الأهمية الحسابية: هذا تعميم كمي لمشكلة تعلم حقول ماركوف العشوائية الكلاسيكية
  3. الأهمية النظرية: ربط نظرية المعلومات الكمية بنظرية التعلم الإحصائي

قيود الطرق الموجودة

  • عمل أنشو وآخرون (AAKS21) يتعامل مع الهاميلتونيانات المحلية هندسياً، مع تعقيد عينة O(2^{poly(β)}N²logN/(β^c ε²))، وهو غير محسّن في الاعتماد على β و N
  • الافتقار إلى تحليل وتحسين واضح لتعقيد الزمن
  • ينطبق فقط على فئة الهاميلتونيانات المحلية هندسياً

المساهمات الأساسية

  1. خوارزمية مثلى: اقتراح خوارزمية مثلى لتعلم الهاميلتونيانات منخفضة التقاطع في منطقة درجات الحرارة العالية، مع تعقيد عينة O(logN/(βε)²) وتعقيد زمني O(N logN/(βε)²)
  2. حدود سفلى متطابقة: إثبات حد سفلى متطابق لتعقيد العينة Ω(exp(β)logN/(β²ε²))، محقق الأمثلية في منطقة درجات الحرارة العالية
  3. فئة هاميلتونيانات أوسع: التوسع إلى الهاميلتونيانات منخفضة التقاطع، وهي أكثر عمومية من الهاميلتونيانات المحلية هندسياً
  4. تحليل نظري: تحسين تحليل التحدب القوي لدالة التقسيم اللوغاريتمية، مع تحسين معامل التحدب القوي إلى β²/2
  5. توسيع التطور الزمني الفعلي: إثبات أن نفس الخوارزمية يمكن استخدامها لتعلم الهاميلتونيان من عوامل يونيتاري للتطور الزمني الفعلي e^{-itH}

شرح الطريقة

تعريف المهمة

اعتبر هاميلتونيان نظام N كيوبت H = Σ_^M λ_a E_a، حيث:

  • E_a هي عوامل باولي غير متطابقة معروفة ومختلفة
  • λ_a ∈ -1,1 هي المعاملات المراد تعلمها
  • الهاميلتونيان منخفض التقاطع: كل عامل يعمل على عدد ثابت من الكيوبتات، وكل عامل له تقاطع غير تافه مع عدد ثابت فقط من العوامل الأخرى

الهدف: تعلم المعاملات {λ_a} من نسخ حالة جيبس ρ = exp(-βH)/Tr(exp(-βH)) بخطأ إضافي ε.

الإطار التقني الأساسي

1. توسيع العناقيد (Cluster Expansion)

استخدام تقنية توسيع العناقيد من الفيزياء الإحصائية، لتوسيع القيمة المتوقعة ⟨E_a⟩ كسلسلة تايلور في β:

⟨E_a⟩(x) = β p₁^{(a)}(x) + β² p₂^{(a)}(x) + β³ p₃^{(a)}(x) + ...

حيث p_m^{(a)} هي متعددة حدود متجانسة من الدرجة m، و p₁^{(a)}(x) = -x_a.

2. تدفق الخوارزمية

الخطوة 1: تقدير القيم المتوقعة

  • لكل عامل باولي E_a، قدّر ⟨E_a⟩ بدقة βε
  • استخدم تلوين الرسم البياني للتفاعل الثنائي، وقس العوامل غير المتداخلة بالتوازي
  • تعقيد العينة: O(d/(β²ε²)log(M/δ))

الخطوة 2: طريقة نيوتن-رافسون عرّف الدالة F_a(x) = Σ_^m β^k p_k^{(a)}(x) - Ê_a، والهدف هو إيجاد x بحيث يكون F(x) صغيراً بما يكفي.

استخدم تكرار نيوتن-رافسون المعدل:

x^{(t+1)} = Proj_{[-1,1]^M}[x^{(t)} + β^{-1} Σ_{k=0}^{K-1} (I + β^{-1}J(x^{(t)}))^k F(x^{(t)})]

3. الابتكارات التقنية الرئيسية

حساب مشتقات العناقيد:

  • تصميم خوارزمية لحساب مشتقات العناقيد D_W L بدقة
  • تعقيد زمني: (8m + L)poly(m)
  • استخدام الخصائص الصحيحة لمصفوفات باولي لتحقيق الحسابات الدقيقة

تحليل مصفوفة جاكوبيان:

  • إثبات أن مصفوفة جاكوبيان J لها خاصية "قطرية النطاق"
  • إذا كانت المسافة بين b و a هي k، فإن J_ بحجم β^{k+1}
  • هذا يجعل J قريبة من -βI، وبالتالي يسهل تقريب J^{-1}

تحليل التقارب

شرط درجة الحرارة الحرجة

تعمل الخوارزمية عند β < β_c، حيث β_c = (25e^6(d+1)^{10})^{-1} يعتمد فقط على درجة الرسم البياني للتفاعل الثنائي d.

انتشار الخطأ

تحليل انتشار الخطأ من خلال نظرية القيمة المتوسطة متعددة المتغيرات:

|x_a - λ_a| ≤ ||J^{-1}||_{∞→∞}(||F(x)||_∞ + ||F(λ)||_∞) ≤ 4ε

الإعداد التجريبي

التحقق النظري

الورقة عمل نظرية بشكل أساسي، تتحقق من صحة الخوارزمية والأمثلية من خلال الإثبات الرياضي، وليس من خلال التجارب التجريبية.

تحليل التعقيد

  • تعقيد العينة: O(logN/(βε)²) (خطأ ℓ_∞)، O(N/(βε)²) (خطأ ℓ_2)
  • التعقيد الزمني: O(N logN/(βε)²) (ℓ_∞)، O(N²/(βε)²) (ℓ_2)
  • وقت المعالجة المسبقة: O(LMd log d) لبناء الرسم البياني للتفاعل الثنائي

النتائج التجريبية

النتائج النظرية الرئيسية

نظرية الحد الأعلى (Theorem 1.1)

للهاميلتونيانات منخفضة التقاطع، تحت الشرط β < β_c:

  • خطأ ℓ_∞ ε: تعقيد عينة O(1/(β²ε²) log(N/δ))
  • خطأ ℓ_2 ε: تعقيد عينة O(N/(β²ε²) log(N/δ))
  • التعقيد الزمني هو تعقيد العينة مضروباً في N

نظرية الحد الأسفل (Theorem 1.2)

توجد هاميلتونيانات ثنائية محلية بحيث:

  • خطأ ℓ_∞: تعقيد عينة Ω(exp(β)/(β²ε²) log(N/δ))
  • خطأ ℓ_2: تعقيد عينة Ω(exp(β)N/(β²ε²))

المقارنة مع الأعمال السابقة

الطريقةتعقيد العينةالتعقيد الزمنينطاق التطبيق
AAKS21O(N²logN/(β^c ε²))O(N³logN/(β^c ε²))محلي هندسياً
هذه الورقةO(logN/(β²ε²))O(N logN/(β²ε²))منخفض التقاطع
الحالة الكلاسيكيةO(logN/(β²ε²))O(N logN/(β²ε²))-

تحسين التحدب القوي

تحسين معامل التحدب القوي لدالة التقسيم اللوغاريتمية من Ω(β^c/N) إلى Ω(β²)، وهذا يتوافق مع تحسين الحد الأدنى لتباين الكميات الماكروسكوبية القابلة للملاحظة.

الأعمال ذات الصلة

تعلم هاميلتونيان الكم

  • بايري وآخرون (2019): أول من اقترح تعلم الهاميلتونيان من الحالة المستقرة، لكن بدون تحليل الحالة الأسوأ
  • AAKS21: إنشاء حدود عليا صارمة لتعقيد العينة، لكن غير محسّنة في عدة معاملات
  • الحالة الكلاسيكية: تعلم معاملات حقول ماركوف العشوائية له خوارزميات قريبة من الأمثلية

الروابط التقنية

  • توسيع العناقيد: الاستفادة من تقنية التوسيع عالي الحرارة في الفيزياء الإحصائية
  • طريقة نيوتن: تطبيق طريقة التحسين الكلاسيكية في الإعداد الكمي
  • الحدود السفلى النظرية للمعلومات: استخدام ليما فانو لإنشاء حدود سفلى نظرية للمعلومات

الخلاصة والنقاش

الاستنتاجات الرئيسية

  1. في منطقة درجات الحرارة العالية، يمكن لتعلم هاميلتونيان الكم أن يحقق نفس التعقيد الأمثل للحالة الكلاسيكية
  2. الخوارزمية المقترحة مثلى في تعقيد العينة والزمن
  3. فئة الهاميلتونيانات منخفضة التقاطع أكثر عمومية من المحلية هندسياً، لكن لا تزال قابلة للتعلم بكفاءة

القيود

  1. قيود درجة الحرارة: تعمل الخوارزمية فقط في منطقة درجات الحرارة العالية، والحرارة الحرجة تعتمد على درجة الرسم البياني الثنائي
  2. الاعتماد على الدرجة: على الرغم من الأمثلية للدرجة الثابتة، تنخفض درجة الحرارة الحرجة بسرعة مع الدرجة
  3. منطقة درجات الحرارة المنخفضة: مشكلة التعلم في منطقة درجات الحرارة المنخفضة لا تزال مفتوحة

الاتجاهات المستقبلية

  1. توسيع نطاق درجات الحرارة: البحث عن خوارزميات تعمل في نطاق درجات حرارة أوسع
  2. الهاميلتونيانات المحلية العامة: التوسع إلى الحالات التي لا تكون فيها الدرجة ثابتة
  3. خوارزميات درجات الحرارة المنخفضة: تطوير خوارزميات تعلم فعالة لمنطقة درجات الحرارة المنخفضة
  4. التحقق التجريبي: التحقق من أداء الخوارزمية في الأنظمة الكمية الفعلية

التقييم المتعمق

المزايا

  1. الاكتمال النظري: توفير تحليل كامل للحدود العليا والحدود السفلى المتطابقة
  2. الابتكار التقني: دمج ماهر لتوسيع العناقيد وطريقة نيوتن
  3. الأمثلية: تحقيق الأمثلية في عدة معاملات في نفس الوقت
  4. العمومية: التوسع إلى فئة هاميلتونيانات أوسع من الأعمال السابقة
  5. الجدوى العملية للخوارزمية: توفير خوارزمية محددة وقابلة للتنفيذ وتحليل التعقيد

أوجه القصور

  1. قيود نطاق التطبيق: ينطبق فقط على منطقة درجات الحرارة العالية
  2. حساسية الدرجة: اعتماد قوي لدرجة الحرارة الحرجة على الدرجة
  3. الافتقار إلى التجارب: عمل نظري بحت، يفتقر إلى التحقق العددي
  4. عدم وضوح الميزة الكمية: في الإعداد المدروس، التعقيد في الحالة الكمية هو نفسه في الحالة الكلاسيكية

التأثير

  1. المساهمة النظرية: إنشاء معيار لتعلم هاميلتونيان الكم
  2. القيمة المنهجية: إظهار التطبيق الفعال للتقنيات الكلاسيكية في الإعداد الكمي
  3. البحث اللاحق: وضع الأساس للبحث في منطقة درجات الحرارة المنخفضة والإعدادات الأكثر عمومية
  4. الإمكانات العملية: توفير إرشادات نظرية للتوصيف التجريبي للأنظمة الكمية

السيناريوهات المعمول بها

  1. محاكاة الكم: التحقق من دقة محاكيات الكم
  2. علم المواد: تعلم الهاميلتونيانات الفعالة لأنظمة الحالة المكثفة
  3. الحوسبة الكمية: معايرة والتحقق من معالجات الكم
  4. البحث الأساسي: فهم خصائص الأنظمة الكمية متعددة الأجسام

المراجع

  1. Anshu, A., Arunachalam, S., Kuwahara, T., & Soleimanifar, M. (2021). تعلم الأنظمة الكمية المتفاعلة بكفاءة العينة. Nature Physics.
  2. Kuwahara, T., Kato, K., & Brandão, F. G. (2020). تجميع المعلومات المتبادلة الشرطية لحالات جيبس الكمية فوق درجة حرارة حدية. Physical Review Letters.
  3. Bresler, G. (2015). تعلم نماذج Ising بكفاءة على الرسوم البيانية التعسفية. STOC.
  4. Klivans, A., & Meka, R. (2017). تعلم النماذج الرسومية باستخدام أوزان مضاعفة. FOCS.