2025-11-22T00:19:16.677522

Quantum Computing for Partition Function Estimation of a Markov Random Field in a Radar Anomaly Detection Problem

Presles, Enderli, Burel et al.

In probability theory, the partition function is a factor used to reduce any probability function to a density function with total probability of one. Among other statistical models used to represent joint distribution, Markov random fields (MRF) can be used to efficiently represent statistical dependencies between variables. As the number of terms in the partition function scales exponentially with the number of variables, the potential of each configuration cannot be computed exactly in a reasonable time for large instances. In this paper, we aim to take advantage of the exponential scalability of quantum computing to speed up the estimation of the partition function of a MRF representing the dependencies between operating variables of an airborne radar. For that purpose, we implement a quantum algorithm for partition function estimation in the one clean qubit model. After proposing suitable formulations, we discuss the performances and scalability of our approach in comparison to the theoretical performances of the algorithm.

academic

রাডার অ্যানোমালি ডিটেকশন সমস্যায় মার্কভ র্যান্ডম ফিল্ডের পার্টিশন ফাংশন অনুমানের জন্য কোয়ান্টাম কম্পিউটিং

মৌলিক তথ্য

পেপার আইডি: 2501.01154
শিরোনাম: Quantum Computing for Partition Function Estimation of a Markov Random Field in a Radar Anomaly Detection Problem
লেখক: Timothé Presles (Thales Defense Mission Systems), Cyrille Enderli (Thales Defense Mission Systems), Gilles Burel (Lab-STICC, CNRS, Univ. Brest), El Houssaın Baghious (Lab-STICC, CNRS, Univ. Brest)
শ্রেণীবিভাগ: cs.ET (উদীয়মান প্রযুক্তি), quant-ph (কোয়ান্টাম পদার্থবিজ্ঞান)
প্রকাশনার সময়: ২০২৫ সালের ২ জানুয়ারি
পেপার লিংক: https://arxiv.org/abs/2501.01154

সারসংক্ষেপ

এই পেপারটি সম্ভাব্যতা তত্ত্বে পার্টিশন ফাংশন অনুমানের সমস্যার জন্য কোয়ান্টাম কম্পিউটিং-ভিত্তিক সমাধান প্রস্তাব করে। পার্টিশন ফাংশন হল সম্ভাব্যতা ফাংশনকে মোট সম্ভাব্যতা ১-এ স্বাভাবিক করার জন্য একটি মূল উপাদান। মার্কভ র্যান্ডম ফিল্ড (MRF) ভেরিয়েবলগুলির মধ্যে পরিসংখ্যানগত নির্ভরতা প্রতিনিধিত্ব করার জন্য একটি কার্যকর মডেল হিসাবে কাজ করে, তবে এর পার্টিশন ফাংশনের পদ সংখ্যা ভেরিয়েবল সংখ্যার সাথে সূচকীয়ভাবে বৃদ্ধি পায়, যা বড় আকারের উদাহরণগুলিকে যুক্তিসঙ্গত সময়ের মধ্যে সঠিকভাবে গণনা করা অসম্ভব করে তোলে। এই পেপারটি কোয়ান্টাম কম্পিউটিংয়ের সূচকীয় স্কেলেবিলিটির সুবিধা ব্যবহার করে, বিমান-ভিত্তিক রাডার অপারেশনাল ভেরিয়েবলগুলির মধ্যে নির্ভরতা প্রতিনিধিত্বকারী MRF পার্টিশন ফাংশন অনুমানকে ত্বরান্বিত করে এবং খাঁটি কিউবিট মডেলে পার্টিশন ফাংশন অনুমানের একটি কোয়ান্টাম অ্যালগরিদম বাস্তবায়ন করে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার পটভূমি

১. রাডার অ্যানোমালি ডিটেকশনের প্রয়োজনীয়তা: আধুনিক বিমান-ভিত্তিক রাডার সিস্টেম (যেমন RBE2, RDY) অসংখ্য উপাদান নিয়ে গঠিত এবং অত্যন্ত উচ্চ ফ্লাইট নির্ভরযোগ্যতার প্রয়োজন। অন্তর্নির্মিত পরীক্ষা সরঞ্জাম বিশাল পরিমাণে অপারেশনাল ডেটা সংগ্রহ করে, কিন্তু বিমান-ভিত্তিক কম্পিউটিং ক্ষমতার সীমাবদ্ধতার কারণে, শুধুমাত্র প্রধান ত্রুটিগুলি প্রক্রিয়া করা যায়, যা সিস্টেম ক্র্যাশ না করে এমন অ্যানোমালিগুলি উপেক্ষা করে।

२. পার্টিশন ফাংশন গণনার চ্যালেঞ্জ: সম্ভাব্যতামূলক গ্রাফিক্যাল মডেলে, পার্টিশন ফাংশন Z_Ω সংজ্ঞায়িত করা হয়:

p_Ω(x) = (1/Z_Ω) · φ₁(D₁) · φ₂(D₂) · ... · φₖ(Dₖ)

এর গণনার জটিলতা ভেরিয়েবল সংখ্যা n এর সাথে সূচকীয়ভাবে বৃদ্ধি পায়, বড় আকারের উদাহরণগুলি গণনা করা যায় না।

३. বিদ্যমান পদ্ধতির সীমাবদ্ধতা:

স্যাম্পলিং পদ্ধতির জন্য ১০⁵টি মধ্যবর্তী পদক্ষেপ এবং কয়েক ঘন্টার গণনা প্রয়োজন
পরিবর্তনশীল পদ্ধতির কর্মক্ষমতা বিতরণের বৈশিষ্ট্যের সাথে ঘনিষ্ঠভাবে সম্পর্কিত, সম্ভাব্যতা ফাংশন মান বৃদ্ধির সাথে জটিলতা বৃদ্ধি পায়
বিশ্বাস প্রচার পদ্ধতির কর্মক্ষমতা গ্রাফ কাঠামোর উপর নির্ভর করে
সমস্ত পদ্ধতি নির্ভুলতা এবং গণনা সময়ের মধ্যে ট্রেড-অফের মুখোমুখি হয়

গবেষণার প্রেরণা

কোয়ান্টাম কম্পিউটিংয়ের সূচকীয় স্কেলেবিলিটির সুবিধা ব্যবহার করে, পার্টিশন ফাংশন অনুমানে ক্লাসিক্যাল কম্পিউটিংয়ের বাধা অতিক্রম করা এবং রাডার অ্যানোমালি ডিটেকশনের জন্য আরও দক্ষ সমাধান প্রদান করা।

মূল অবদান

१. কোয়ান্টাম অ্যালগরিদম অভিযোজন: খাঁটি কিউবিট মডেলে পার্টিশন ফাংশন অনুমান অ্যালগরিদমকে রাডার অ্যানোমালি ডিটেকশনের মার্কভ র্যান্ডম ফিল্ড সমস্যায় অভিযোজিত করা

२. দ্বিঘাত হ্যামিলটোনিয়ান নির্মাণ: দ্বিঘাত বাইনারি ফর্ম সমস্যাকে কোয়ান্টাম হ্যামিলটোনিয়ানে রূপান্তরিত করার পদ্ধতি প্রস্তাব করা, যেখানে এর eigenvalues সম্ভাব্যতা কনফিগারেশনের সাথে সামঞ্জস্যপূর্ণ

३. পরীক্ষামূলক যাচাইকরণ এবং বিশ্লেষণ: IBM Qiskit সিমুলেশনের মাধ্যমে অ্যালগরিদম কর্মক্ষমতা যাচাই করা এবং তাত্ত্বিক ফলাফলের সাথে তুলনা বিশ্লেষণ করা

४. প্যারামিটার অপ্টিমাইজেশন কৌশল: তাত্ত্বিক মানের চেয়ে উন্নত প্যারামিটার সেটিংস আবিষ্কার করা, নির্ভুলতা নিশ্চিত করার সাথে সাথে গণনা ওভারহেড হ্রাস করা

পদ্ধতির বিস্তারিত বর্ণনা

কাজের সংজ্ঞা

ইনপুট: বাইনারি মার্কভ র্যান্ডম ফিল্ডের প্যারামিটার ম্যাট্রিক্স Θ, যেখানে F_C(x_C) = x_C^T Θ x_C আউটপুট: পার্টিশন ফাংশন Z_C = Σ_{x_C∈{0,1}^n} exp(F_C(x_C)) এর অনুমান মূল্য সীমাবদ্ধতা: বহুপদী সময়ে সূচকীয় ত্বরণ অর্জনের জন্য কোয়ান্টাম কম্পিউটিং ব্যবহার করা

মডেল আর্কিটেকচার

१. খাঁটি কিউবিট মডেল

প্রাথমিক অবস্থা একটি খাঁটি অবস্থা কিউবিট |0⟩ এবং q সম্পূর্ণ মিশ্র অবস্থা কিউবিট নিয়ে গঠিত:

ρ = |0⟩⟨0| ⊗ (I_q/2^q)

নিয়ন্ত্রিত ইউনিটারি অপারেটর U এর গেট অপারেশনের মাধ্যমে, সহায়ক কিউবিট পরিমাপ করে সম্ভাব্যতা p₀ পাওয়া যায়:

p₀ = 1/2 + Re(Tr(U))/2^{q+1}

२. ইউনিটারি অপারেটরের ব্লক এনকোডিং

হ্যামিলটোনিয়ান H কে ইউনিটারি অপারেটরের রৈখিক সমন্বয় (LCU) হিসাবে প্রকাশ করা:

H = Σ_{l=1}^L α_l H_l

"প্রস্তুতি" কোয়ান্টাম ওরাকেল P এবং "নির্বাচন" কোয়ান্টাম ওরাকেল S সংজ্ঞায়িত করা:

P|0⟩_m = Σ_{l=1}^L √α_l |l⟩_m
S = Σ_{l=1}^L H_l ⊗ |l⟩⟨l|_m

३. চেবিশেভ বহুপদ অনুমান

সূচক অপারেটর সম্প্রসারণের জন্য চেবিশেভ অনুমান ব্যবহার করা:

e^{-βH} = Σ_{k=-∞}^∞ (-1)^k I_k(β) T_k(H)

হাঁটার অপারেটর W_H এর k বার ক্রমাগত প্রয়োগের মাধ্যমে k-তম চেবিশেভ বহুপদ উৎপন্ন করা:

T_k(H) = ⟨0|(I_n ⊗ P')(W_H)^k (I_n ⊗ P'†)|0⟩_{n+m'}

প্রযুক্তিগত উদ্ভাবনী পয়েন্ট

१. বাইনারি অপারেটর সংজ্ঞা: B = (I-Z)/2 অপারেটর সৃজনশীলভাবে সংজ্ঞায়িত করা, বাইনারি দ্বিঘাত ফর্মকে সরাসরি কোয়ান্টাম অপারেটর স্থানে ম্যাপ করা

२. হ্যামিলটোনিয়ান নির্মাণ: হ্যামিলটোনিয়ান H_C নির্মাণ করা:

H_C = Σ_{i=1}^n θ_{i,i}B_i + Σ_{i≠j} θ_{i,j}B_{i,j}

এর eigenvalues ঠিক {P_C(x_C)}_{x_C∈{0,1}^n} এর সাথে সামঞ্জস্যপূর্ণ

३. প্যারামিটার অপ্টিমাইজেশন: K=3 এবং ε_abs=0.1 প্যারামিটার সেটিং আবিষ্কার করা যা নির্ভুলতা নিশ্চিত করার সাথে সাথে কোয়ান্টাম গেটের সংখ্যা উল্লেখযোগ্যভাবে হ্রাস করে

পরীক্ষামূলক সেটআপ

ডেটাসেট

গ্রাফ স্কেল: n ∈ {2,3,4} ছোট আকারের বাইনারি মার্কভ র্যান্ডম ফিল্ড
গ্রাফ কাঠামো: রাডার সিস্টেমে ভেরিয়েবলগুলির মধ্যে নির্ভরতা সম্পর্ক অনুকরণ করা, সন্নিহিত ম্যাট্রিক্স ব্যবহার করে প্রতিনিধিত্ব করা
উদাহরণ ম্যাট্রিক্স: ৫-নোড গ্রাফের Θ ম্যাট্রিক্স কর্ণ উপাদান এবং অ-কর্ণ উপাদান অন্তর্ভুক্ত করে, Σ|θ_{i,j}| = 1 স্বাভাবিকীকরণ শর্ত পূরণ করে

মূল্যায়ন সূচক

আপেক্ষিক ত্রুটি: |অনুমান মূল্য - প্রকৃত মূল্য|/প্রকৃত মূল্য × ১০০%
তাত্ত্বিক নমুনা সংখ্যা: Q = ⌈2^{2(n+m')+1} log(2K/δ)/(ε_abs/2e)^2⌉
তাত্ত্বিক চেবিশেভ ক্রম: K = ⌈m + e + log₂(1/ε_abs) + 2⌉

তুলনা পদ্ধতি

তাত্ত্বিক পূর্বাভাস মূল্য (সাহিত্য 9 এর তাত্ত্বিক বিশ্লেষণের উপর ভিত্তি করে)
সঠিক গণনা দ্বারা প্রকৃত পার্টিশন ফাংশন মূল্য

বাস্তবায়ন বিবরণ

কোয়ান্টাম সিমুলেটর: IBM Qiskit লাইব্রেরি
প্যারামিটার সেটিংস: K=3, ε_abs=0.1, δ=0.1
অনুমান শর্ত: m'=n+1 (সর্বোচ্চ ক্ষেত্রে, সম্পূর্ণ গ্রাফের সাথে সামঞ্জস্যপূর্ণ)

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

নমুনা সংখ্যার প্রভাব বিশ্লেষণ

সমস্যা স্কেল n	তাত্ত্বিক নমুনা সংখ্যা Q_th	10³	10⁴	10⁵	10⁶	10⁷
2	10,763,353	48.90%	5.82%	1.49%	0.80%	0.47%
3	172,213,657	68.56%	7.34%	2.48%	1.16%	0.72%
4	2,755,418,514	97.85%	9.17%	3.66%	1.59%	1.39%

চেবিশেভ ক্রমের প্রভাব বিশ্লেষণ

সমস্যা স্কেল n	তাত্ত্বিক ক্রম K_th	K=1	K=2	K=3	K=4	K=5
2	10	9.98%	3.41%	1.49%	1.49%	1.49%
3	11	17.91%	4.64%	2.48%	2.47%	2.47%
4	12	33.57%	8.16%	3.66%	3.65%	3.65%

মূল আবিষ্কার

१. নমুনা দক্ষতা উন্নতি: n=4 এর ক্ষেত্রে, মাত্র ১০⁴টি নমুনা দিয়ে প্রায় ১০% ত্রুটি অর্জন করা যায়, যখন তাত্ত্বিক পূর্বাভাস প্রায় ১০⁹টি নমুনার প্রয়োজন

२. চেবিশেভ ক্রম অপ্টিমাইজেশন: K=3 এ অ্যালগরিদম কর্মক্ষমতা স্থিতিশীল হয়ে যায়, K মূল্য আরও বৃদ্ধি করলে নির্ভুলতা উল্লেখযোগ্যভাবে উন্নত হয় না, কিন্তু কোয়ান্টাম গেটের সংখ্যা বৃদ্ধি পায়

३. স্কেলেবিলিটি বিশ্লেষণ:

IBM Condor (১১२१ ফিজিক্যাল কিউবিট) সর্বাধিক ১८६-নোড বাইনারি MRF সমর্থন করতে পারে (প্রায় ১০⁵⁶ পার্টিশন ফাংশন পদের সাথে সামঞ্জস্যপূর্ণ)
সর্বাধিক মিশ্র অবস্থা প্রস্তুত করতে পারে এমন কোয়ান্টাম কম্পিউটারে ३७३-নোড সমর্থন করা যায় (প্রায় ১०¹¹२ পার্টিশন ফাংশন পদের সাথে সামঞ্জস্যপূর্ণ)

উপসংহার এবং আলোচনা

প্রধান উপসংহার

१. কোয়ান্টাম পার্টিশন ফাংশন অনুমান অ্যালগরিদমকে সফলভাবে রাডার অ্যানোমালি ডিটেকশনের মার্কভ র্যান্ডম ফিল্ড সমস্যায় অভিযোজিত করা २. পরীক্ষামূলক ফলাফল দেখায় যে অ্যালগরিদম কর্মক্ষমতা তাত্ত্বিক পূর্বাভাসের চেয়ে উন্নত, কম নমুনা সংখ্যা এবং কম চেবিশেভ ক্রমে সন্তোষজনক নির্ভুলতা অর্জন করা যায় ३. কোয়ান্টাম পদ্ধতি বড় আকারের পার্টিশন ফাংশন গণনা পরিচালনার জন্য নতুন সম্ভাবনা প্রদান করে

সীমাবদ্ধতা

१. NISQ যুগের সীমাবদ্ধতা: বর্তমান কোয়ান্টাম হার্ডওয়্যারের শব্দ এবং ত্রুটির হার ব্যবহারিক প্রয়োগকে সীমাবদ্ধ করে २. ফিজিক্যাল কিউবিট প্রয়োজনীয়তা: লজিক্যাল কিউবিট নির্মাণের জন্য একাধিক ফিজিক্যাল কিউবিট প্রয়োজন, প্রকৃত ব্যবহারযোগ্য স্কেল সীমাবদ্ধ ३. ক্রমাগত ভেরিয়েবল সম্প্রসারণ: বর্তমান পদ্ধতি শুধুমাত্র বাইনারি ভেরিয়েবলের জন্য প্রযোজ্য, ক্রমাগত ভেরিয়েবলে আরও সম্প্রসারণের প্রয়োজন

ভবিষ্যত দিকনির্দেশনা

१. মিশ্র গ্রাফ মডেল: ক্রমাগত ভেরিয়েবল সহ সম্পূর্ণ অ্যানোমালি ডিটেকশন মডেলে সম্প্রসারণ २. কোয়ান্টাম গেট অপ্টিমাইজেশন: সার্কিট বাস্তবায়ন অপ্টিমাইজ করা কোয়ান্টাম গেটের সংখ্যা হ্রাস করতে ३. হার্ডওয়্যার অভিযোজন: নির্দিষ্ট কোয়ান্টাম হার্ডওয়্যার আর্কিটেকচার এবং গেট খরচ বিবেচনা করে প্যারামিটার অপ্টিমাইজেশন

গভীর মূল্যায়ন

শক্তি

१. সমস্যা নির্বাচন: ব্যবহারিক প্রয়োগ মূল্য সহ রাডার অ্যানোমালি ডিটেকশন সমস্যা নির্বাচন করা, কোয়ান্টাম কম্পিউটিংয়ের ব্যবহারিকতা প্রদর্শন করা २. শক্ত তত্ত্ব: পরিপক্ক খাঁটি কিউবিট মডেল তত্ত্বের উপর ভিত্তি করে, অ্যালগরিদম ডিজাইন কঠোর ३. প্যারামিটার বিশ্লেষণ: নমুনা সংখ্যা এবং চেবিশেভ ক্রমের কর্মক্ষমতার উপর প্রভাব গভীরভাবে বিশ্লেষণ করা, তাত্ত্বিক মানের চেয়ে উন্নত প্যারামিটার সেটিংস আবিষ্কার করা ४. স্কেলেবিলিটি আলোচনা: বর্তমান এবং ভবিষ্যত কোয়ান্টাম হার্ডওয়্যারের প্রয়োগ সম্ভাবনা উদ্দেশ্যমূলকভাবে বিশ্লেষণ করা

অপূর্ণতা

१. পরীক্ষামূলক স্কেল: শুধুমাত্র ছোট আকারের সমস্যায় (n≤4) সিমুলেশন যাচাইকরণ পরিচালিত হয়েছে, বড় আকারের উদাহরণের যাচাইকরণের অভাব २. শব্দের প্রভাব: কোয়ান্টাম হার্ডওয়্যার শব্দ অ্যালগরিদম কর্মক্ষমতার উপর প্রভাব বিবেচনা করা হয়নি ३. তুলনা মানদণ্ড: অন্যান্য ক্লাসিক্যাল পার্টিশন ফাংশন অনুমান পদ্ধতির সাথে সরাসরি কর্মক্ষমতা তুলনার অভাব ४. ব্যবহারিক স্থাপনা: প্রকৃত কোয়ান্টাম হার্ডওয়্যারে অ্যালগরিদম কর্মক্ষমতা যাচাই করা হয়নি

প্রভাব

१. একাডেমিক অবদান: সম্ভাব্যতামূলক গ্রাফিক্যাল মডেলে কোয়ান্টাম কম্পিউটিং প্রয়োগের জন্য নতুন চিন্তাভাবনা প্রদান করা २. ব্যবহারিক মূল্য: রাডার সিস্টেম অ্যানোমালি ডিটেকশন এবং অন্যান্য ব্যবহারিক সমস্যা সমাধানের জন্য কোয়ান্টাম সমাধান প্রদান করা ३. প্রযুক্তি উত্তরাধিকার: পরবর্তী কোয়ান্টাম মেশিন লার্নিং অ্যালগরিদম উন্নয়নের জন্য ভিত্তি স্থাপন করা

প্রযোজ্য পরিস্থিতি

१. বড় আকারের সম্ভাব্যতামূলক গ্রাফিক্যাল মডেল: বিশাল সংখ্যক ভেরিয়েবল সহ মার্কভ র্যান্ডম ফিল্ডের পার্টিশন ফাংশন অনুমানের জন্য প্রযোজ্য २. রিয়েল-টাইম অ্যানোমালি ডিটেকশন: দ্রুত প্রতিক্রিয়ার প্রয়োজন এমন অ্যানোমালি ডিটেকশন সিস্টেমে প্রয়োগ করা যায় ३. কোয়ান্টাম সুবিধা যাচাইকরণ: কোয়ান্টাম কম্পিউটিংয়ের ক্লাসিক্যাল কম্পিউটিংয়ের তুলনায় সুবিধা প্রদর্শনের একটি সাধারণ ক্ষেত্র হিসাবে কাজ করা

সংদর্ভ

এই পেপারটি ২१টি গুরুত্বপূর্ণ সংদর্ভ উদ্ধৃত করে, যা কোয়ান্টাম কম্পিউটিং মৌলিক তত্ত্ব, হ্যামিলটোনিয়ান সিমুলেশন, পার্টিশন ফাংশন অনুমান এবং অন্যান্য মূল ক্ষেত্র কভার করে, গবেষণার জন্য একটি শক্ত তাত্ত্বিক ভিত্তি প্রদান করে।