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
- শিরোনাম: উচ্চ-তাপমাত্রা গিবস অবস্থা থেকে কোয়ান্টাম হ্যামিলটোনিয়ানের সর্বোত্তম শিক্ষা
- লেখক: জিওংওয়ান হা (মাইক্রোসফট কোয়ান্টাম), রবিন কোথারি (মাইক্রোসফট কোয়ান্টাম), ইউইন ট্যাং (ওয়াশিংটন বিশ্ববিদ্যালয়)
- শ্রেণীবিভাগ: quant-ph cs.DS cs.LG
- প্রকাশনার সময়: ১৭ মার্চ, ২০২৩ (arXiv সংস্করণ)
- পেপার লিঙ্ক: https://arxiv.org/abs/2108.04842
সারসংক্ষেপ
এই পেপারটি পরিচিত বিপরীত তাপমাত্রা β সহ গিবস অবস্থা ρ=exp(-βH)/Tr(exp(-βH)) এর অনুলিপি থেকে নির্ভুলতা ε পর্যন্ত হ্যামিলটোনিয়ান H শিখার সমস্যা অধ্যয়ন করে। উচ্চ-তাপমাত্রা (নিম্ন β) অঞ্চলে, লেখকরা নিম্ন-ছেদ হ্যামিলটোনিয়ান শ্রেণীর জন্য একটি শিক্ষা অ্যালগরিদম প্রস্তাব করেন, যা নমুনা জটিলতা S=O(logN/(βε)²) এবং সময় জটিলতা O(SN) অর্জন করে এবং মিলিত নিম্ন সীমা প্রমাণ করে, যা নমুনা এবং সময় জটিলতা উভয় ক্ষেত্রেই অ্যালগরিদম সর্বোত্তম তা প্রদর্শন করে।
গবেষণা পটভূমি এবং প্রেরণা
সমস্যার সংজ্ঞা
হ্যামিলটোনিয়ান শিক্ষা সমস্যা কোয়ান্টাম বহু-শরীর পদার্থবিজ্ঞান এবং মেশিন লার্নিং এর ছেদ ক্ষেত্রে একটি গুরুত্বপূর্ণ সমস্যা। একটি অজানা হ্যামিলটোনিয়ান H এর তাপীয় সমতা অবস্থা (গিবস অবস্থা) এর একাধিক অনুলিপি দেওয়া হলে, লক্ষ্য হ্যামিলটোনিয়ানের সহগুণক শিখা। এই সমস্যার পদার্থবিজ্ঞানে সরাসরি প্রেরণা রয়েছে: হ্যামিলটোনিয়ান কোয়ান্টাম সিস্টেমের পারস্পরিক ক্রিয়া এবং সময় বিবর্তন বর্ণনা করে, যখন গিবস অবস্থা প্রদত্ত তাপমাত্রায় পরিবেশের সাথে তাপীয় সমতায় থাকা সিস্টেমের অবস্থা।
গবেষণার তাৎপর্য
- পদার্থবিজ্ঞানগত অর্থ: কোয়ান্টাম সিস্টেমের মৌলিক বৈশিষ্ট্য বোঝা, এর আচরণ পূর্বাভাস দেওয়া
- গণনামূলক অর্থ: এটি ধ্রুপদী মার্কভ র্যান্ডম ক্ষেত্র শিক্ষা সমস্যার কোয়ান্টাম সম্প্রসারণ
- তাত্ত্বিক অর্থ: কোয়ান্টাম তথ্য তত্ত্ব এবং পরিসংখ্যানগত শিক্ষা তত্ত্ব সংযোগ করা
বিদ্যমান পদ্ধতির সীমাবদ্ধতা
- আনশু এবং অন্যান্য (AAKS21) এর কাজ জ্যামিতিক স্থানীয় হ্যামিলটোনিয়ানের জন্য, নমুনা জটিলতা O(2^{poly(β)}N²logN/(β^c ε²)), β এবং N এর নির্ভরশীলতায় অপ্টিমাইজ করা যথেষ্ট নয়
- সময় জটিলতার দিক থেকে স্পষ্ট বিশ্লেষণ এবং অপ্টিমাইজেশনের অভাব
- শুধুমাত্র জ্যামিতিক স্থানীয় হ্যামিলটোনিয়ান শ্রেণীতে প্রযোজ্য
মূল অবদান
- সর্বোত্তম অ্যালগরিদম: উচ্চ-তাপমাত্রা অঞ্চলে নিম্ন-ছেদ হ্যামিলটোনিয়ান শিখার জন্য সর্বোত্তম অ্যালগরিদম প্রস্তাব করা, নমুনা জটিলতা O(logN/(βε)²), সময় জটিলতা O(N logN/(βε)²)
- মিলিত নিম্ন সীমা: নমুনা জটিলতার মিলিত নিম্ন সীমা Ω(exp(β)logN/(β²ε²)) প্রমাণ করা, উচ্চ-তাপমাত্রা অঞ্চলে সর্বোত্তমতা অর্জন করা
- আরও বিস্তৃত হ্যামিলটোনিয়ান শ্রেণী: নিম্ন-ছেদ হ্যামিলটোনিয়ানে সম্প্রসারণ, যা জ্যামিতিক স্থানীয় হ্যামিলটোনিয়ানের চেয়ে আরও সাধারণ
- তাত্ত্বিক বিশ্লেষণ: লগারিদমিক বিভাজন ফাংশনের শক্তিশালী উত্তলতা বিশ্লেষণ উন্নত করা, শক্তিশালী উত্তলতা পরামিতি β²/2 এ উন্নত করা
- রিয়েল-টাইম বিবর্তন সম্প্রসারণ: একই অ্যালগরিদম রিয়েল-টাইম বিবর্তন ইউনিটারি অপারেটর e^{-itH} থেকে হ্যামিলটোনিয়ান শিখতে ব্যবহার করা যায় তা প্রমাণ করা
পদ্ধতির বিস্তারিত বিবরণ
কাজের সংজ্ঞা
N কোয়ান্টাম বিট সিস্টেমের হ্যামিলটোনিয়ান H = Σ_^M λ_a E_a বিবেচনা করুন, যেখানে:
- E_a পরিচিত বিভিন্ন অ-পরিচয় পাউলি অপারেটর
- λ_a ∈ -1,1 শিখার জন্য সহগুণক
- হ্যামিলটোনিয়ান নিম্ন-ছেদ: প্রতিটি অপারেটর ধ্রুবক সংখ্যক কোয়ান্টাম বিটে কাজ করে, এবং প্রতিটি অপারেটর শুধুমাত্র ধ্রুবক সংখ্যক অন্যান্য অপারেটরের সমর্থনের সাথে অ-তুচ্ছ ছেদ রয়েছে
লক্ষ্য: গিবস অবস্থা ρ = exp(-βH)/Tr(exp(-βH)) এর অনুলিপি থেকে সহগুণক {λ_a} যোজক ত্রুটি ε পর্যন্ত শিখা।
মূল প্রযুক্তিগত কাঠামো
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 সংজ্ঞায়িত করুন, লক্ষ্য F(x) যথেষ্ট ছোট 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)
2-স্থানীয় হ্যামিলটোনিয়ান বিদ্যমান যা:
- ℓ_∞ ত্রুটি: নমুনা জটিলতা Ω(exp(β)/(β²ε²) log(N/δ))
- ℓ_2 ত্রুটি: নমুনা জটিলতা Ω(exp(β)N/(β²ε²))
পূর্ববর্তী কাজের সাথে তুলনা
| পদ্ধতি | নমুনা জটিলতা | সময় জটিলতা | প্রযোজ্য পরিসর |
|---|---|---|---|
| AAKS21 | O(N²logN/(β^c ε²)) | O(N³logN/(β^c ε²)) | জ্যামিতিক স্থানীয় |
| এই পেপার | O(logN/(β²ε²)) | O(N logN/(β²ε²)) | নিম্ন-ছেদ |
| ধ্রুপদী ক্ষেত্রে | O(logN/(β²ε²)) | O(N logN/(β²ε²)) | - |
শক্তিশালী উত্তলতা উন্নতি
লগারিদমিক বিভাজন ফাংশনের শক্তিশালী উত্তলতা পরামিতি Ω(β^c/N) থেকে Ω(β²) এ উন্নত করা, যা ম্যাক্রোস্কোপিক পর্যবেক্ষণযোগ্য পরিমাণের বৈচিত্র্যের নিম্ন সীমা উন্নতির সাথে সামঞ্জস্যপূর্ণ।
সম্পর্কিত কাজ
কোয়ান্টাম হ্যামিলটোনিয়ান শিক্ষা
- বাইরে এবং অন্যান্য (2019): স্থিতিশীল অবস্থা থেকে হ্যামিলটোনিয়ান শিখা প্রথম প্রস্তাব করেন, কিন্তু সর্বনিম্ন ক্ষেত্রে বিশ্লেষণের অভাব
- AAKS21: কঠোর নমুনা জটিলতা উপরের সীমা প্রতিষ্ঠা করেন, কিন্তু একাধিক পরামিতিতে অপ্টিমাইজ করা যথেষ্ট নয়
- ধ্রুপদী ক্ষেত্রে: মার্কভ র্যান্ডম ক্ষেত্রের পরামিতি শিক্ষা ইতিমধ্যে কাছাকাছি-সর্বোত্তম অ্যালগরিদম রয়েছে
প্রযুক্তিগত সংযোগ
- ক্লাস্টার সম্প্রসারণ: পরিসংখ্যানগত বলবিজ্ঞানে উচ্চ-তাপমাত্রা সম্প্রসারণ কৌশল থেকে ধার করা
- নিউটন পদ্ধতি: ধ্রুপদী অপ্টিমাইজেশন পদ্ধতি কোয়ান্টাম সেটিংয়ে প্রয়োগ
- তথ্য-তাত্ত্বিক নিম্ন সীমা: ফানো লেমা ব্যবহার করে তথ্য-তাত্ত্বিক নিম্ন সীমা প্রতিষ্ঠা করা
সিদ্ধান্ত এবং আলোচনা
প্রধান সিদ্ধান্ত
- উচ্চ-তাপমাত্রা অঞ্চলে, কোয়ান্টাম হ্যামিলটোনিয়ান শিক্ষা ধ্রুপদী ক্ষেত্রের মতো একই সর্বোত্তম জটিলতা অর্জন করতে পারে
- প্রস্তাবিত অ্যালগরিদম নমুনা এবং সময় জটিলতা উভয় ক্ষেত্রেই সর্বোত্তম
- নিম্ন-ছেদ হ্যামিলটোনিয়ান শ্রেণী জ্যামিতিক স্থানীয়ের চেয়ে আরও সাধারণ, কিন্তু এখনও দক্ষতার সাথে শেখা যায়
সীমাবদ্ধতা
- তাপমাত্রা সীমাবদ্ধতা: অ্যালগরিদম শুধুমাত্র উচ্চ-তাপমাত্রা অঞ্চলে কাজ করে, সমালোচনামূলক তাপমাত্রা দ্বৈত গ্রাফ ডিগ্রির উপর নির্ভর করে
- ডিগ্রি নির্ভরশীলতা: যদিও স্থির ডিগ্রির জন্য সর্বোত্তম, সমালোচনামূলক তাপমাত্রা ডিগ্রির সাথে দ্রুত হ্রাস পায়
- নিম্ন-তাপমাত্রা অঞ্চল: নিম্ন-তাপমাত্রা অঞ্চলের শিক্ষা সমস্যা এখনও খোলা
ভবিষ্যত দিকনির্দেশনা
- তাপমাত্রা পরিসীমা প্রসারিত করা: আরও বিস্তৃত তাপমাত্রা পরিসরে কাজ করে এমন অ্যালগরিদম খুঁজে বের করা
- সাধারণ স্থানীয় হ্যামিলটোনিয়ান: ডিগ্রি ধ্রুবক নয় এমন ক্ষেত্রে সম্প্রসারণ
- নিম্ন-তাপমাত্রা অ্যালগরিদম: নিম্ন-তাপমাত্রা অঞ্চলের জন্য কার্যকর শিক্ষা অ্যালগরিদম বিকাশ করা
- পরীক্ষামূলক যাচাইকরণ: প্রকৃত কোয়ান্টাম সিস্টেমে অ্যালগরিদম কর্মক্ষমতা যাচাই করা
গভীর মূল্যায়ন
সুবিধা
- তাত্ত্বিক সম্পূর্ণতা: সম্পূর্ণ উপরের সীমা এবং মিলিত নিম্ন সীমা বিশ্লেষণ প্রদান করা
- প্রযুক্তিগত উদ্ভাবন: ক্লাস্টার সম্প্রসারণ এবং নিউটন পদ্ধতি চতুরভাবে একত্রিত করা
- সর্বোত্তমতা: একাধিক পরামিতিতে একযোগে সর্বোত্তমতা অর্জন করা
- সাধারণতা: পূর্ববর্তী কাজের চেয়ে আরও বিস্তৃত হ্যামিলটোনিয়ান শ্রেণীতে সম্প্রসারণ
- অ্যালগরিদম ব্যবহারযোগ্যতা: নির্দিষ্ট বাস্তবায়নযোগ্য অ্যালগরিদম এবং জটিলতা বিশ্লেষণ প্রদান করা
অপূর্ণতা
- প্রয়োগের পরিসীমা সীমাবদ্ধতা: শুধুমাত্র উচ্চ-তাপমাত্রা অঞ্চলে প্রযোজ্য
- ডিগ্রি সংবেদনশীলতা: সমালোচনামূলক তাপমাত্রা ডিগ্রির উপর শক্তিশালী নির্ভরশীলতা
- পরীক্ষামূলক অভাব: বিশুদ্ধ তাত্ত্বিক কাজ, সংখ্যাগত যাচাইকরণের অভাব
- অস্পষ্ট কোয়ান্টাম সুবিধা: অধ্যয়নকৃত সেটিংয়ে, কোয়ান্টাম ক্ষেত্রে জটিলতা ধ্রুপদী ক্ষেত্রের মতো
প্রভাব
- তাত্ত্বিক অবদান: কোয়ান্টাম হ্যামিলটোনিয়ান শিক্ষার জন্য মানদণ্ড প্রতিষ্ঠা করা
- পদ্ধতিগত মূল্য: ধ্রুপদী কৌশলের কোয়ান্টাম সেটিংয়ে কার্যকর প্রয়োগ প্রদর্শন করা
- পরবর্তী গবেষণা: নিম্ন-তাপমাত্রা অঞ্চল এবং আরও সাধারণ সেটিংয়ের গবেষণার ভিত্তি স্থাপন করা
- ব্যবহারিক সম্ভাবনা: কোয়ান্টাম সিস্টেমের পরীক্ষামূলক প্রকাশের জন্য তাত্ত্বিক নির্দেশনা প্রদান করা
প্রযোজ্য পরিস্থিতি
- কোয়ান্টাম সিমুলেশন: কোয়ান্টাম সিমুলেটরের নির্ভুলতা যাচাই করা
- উপকরণ বিজ্ঞান: ঘনীভূত অবস্থা সিস্টেমের কার্যকর হ্যামিলটোনিয়ান শিখা
- কোয়ান্টাম কম্পিউটিং: কোয়ান্টাম প্রসেসরের ক্যালিব্রেশন এবং যাচাইকরণ
- মৌলিক গবেষণা: কোয়ান্টাম বহু-শরীর সিস্টেমের বৈশিষ্ট্য বোঝা
তথ্যসূত্র
- Anshu, A., Arunachalam, S., Kuwahara, T., & Soleimanifar, M. (2021). Sample-efficient learning of interacting quantum systems. Nature Physics.
- Kuwahara, T., Kato, K., & Brandão, F. G. (2020). Clustering of conditional mutual information for quantum Gibbs states above a threshold temperature. Physical Review Letters.
- Bresler, G. (2015). Efficiently learning Ising models on arbitrary graphs. STOC.
- Klivans, A., & Meka, R. (2017). Learning graphical models using multiplicative weights. FOCS.