সর্বোচ্চ সম্প্রসারণযোগ্য পণ্য কোড ভাল কোবাউন্ডারি সম্প্রসারক

মৌলিক তথ্য

• পেপার আইডি: 2501.01411
• শিরোনাম: সর্বোচ্চ সম্প্রসারণযোগ্য পণ্য কোড ভাল কোবাউন্ডারি সম্প্রসারক
• লেখক: গ্লেব কালাচেভ, পাভেল প্যান্টেলিভ (মস্কো স্টেট ইউনিভার্সিটি)
• শ্রেণীবিভাগ: cs.IT math.IT quant-ph
• প্রকাশনার সময়/সম্মেলন: IEEE Symposium on Foundations of Computer Science (FOCS 2025)-এ প্রকাশনার জন্য গৃহীত
• পেপার লিঙ্ক: https://arxiv.org/abs/2501.01411

সারসংক্ষেপ

এই পেপারটি টেনসর পণ্য কোডের কোবাউন্ডারি সম্প্রসারণ বৈশিষ্ট্য (পণ্য সম্প্রসারণ নামে পরিচিত) অধ্যয়ন করে, যা সম্প্রতি ভাল কোয়ান্টাম LDPC কোড এবং ক্লাসিক্যাল স্থানীয় পরীক্ষাযোগ্য কোড নির্মাণে গুরুত্বপূর্ণ ভূমিকা পালন করে। পূর্ববর্তী গবেষণা দেখিয়েছে যে দুটি রৈখিক দূরত্ব সহ কোডের পণ্যের জন্য, এই বৈশিষ্ট্যটি সামঞ্জস্যপূর্ণ পরীক্ষাযোগ্যতা এবং শক্তিশালী পরীক্ষাযোগ্যতার সমতুল্য। তবে দুটির বেশি কোডের পণ্যের জন্য, পণ্য সম্প্রসারণ একটি কঠোরভাবে শক্তিশালী বৈশিষ্ট্য। এই পেপারটি প্রমাণ করে যে যথেষ্ট বড় ক্ষেত্রে র‍্যান্ডম কোডের সংগ্রহ ভাল পণ্য সম্প্রসারণ বৈশিষ্ট্য রাখে। লেখকরা বিশ্বাস করেন যে চারটি কোডের ক্ষেত্রে, এই ধারণাগুলি ভাল কোয়ান্টাম স্থানীয় পরীক্ষাযোগ্য কোড নির্মাণে ব্যবহার করা যেতে পারে, যা বর্তমানে শুধুমাত্র দুটি কোডের পণ্য ব্যবহার করে।

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

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

1. উচ্চ-মাত্রিক সম্প্রসারকদের গুরুত্ব: উচ্চ-মাত্রিক সম্প্রসারক (HDXs) ক্লাসিক্যাল স্থানীয় পরীক্ষাযোগ্য কোড (LTCs) এবং কোয়ান্টাম নিম্ন-ঘনত্ব প্যারিটি-চেক কোড (qLDPC) নির্মাণে গুরুত্বপূর্ণ ভূমিকা পালন করে।
2. পণ্য সম্প্রসারণের সীমাবদ্ধতা:
   • দুটি কোডের পণ্যের জন্য, পণ্য সম্প্রসারণ সামঞ্জস্যপূর্ণ পরীক্ষাযোগ্যতা এবং শক্তিশালী পরীক্ষাযোগ্যতার সমতুল্য
   • কিন্তু দুটির বেশি কোডের পণ্যের জন্য, পণ্য সম্প্রসারণ একটি কঠোরভাবে শক্তিশালী বৈশিষ্ট্য
   • বিদ্যমান নির্মাণগুলি প্রধানত দুটি কোডের পণ্যের উপর ভিত্তি করে, যা প্রয়োগের পরিধি সীমিত করে
3. কোয়ান্টাম LTC অনুমান: ভাল কোয়ান্টাম স্থানীয় পরীক্ষাযোগ্য কোড (qLTCs) নির্মাণের জন্য চার-মাত্রিক অনুরূপ সম্প্রসারক LP কোড প্রয়োজন, যার জন্য চারটি কোডের পণ্য ভাল পণ্য সম্প্রসারণ বৈশিষ্ট্য রাখা প্রয়োজন।

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

• বিদ্যমান তত্ত্বকে যেকোনো সংখ্যক কোডের পণ্যে প্রসারিত করা
• কোয়ান্টাম LTC অনুমানের জন্য তাত্ত্বিক ভিত্তি প্রদান করা
• র‍্যান্ডম কোডগুলি ভাল পণ্য সম্প্রসারণ রাখে তা প্রতিষ্ঠা করা

মূল অবদান

1. প্রধান তাত্ত্বিক ফলাফল: প্রমাণ করে যে যথেষ্ট বড় ক্ষেত্রে, যেকোনো সংখ্যক র‍্যান্ডম কোডের সংগ্রহ উচ্চ সম্ভাবনায় ভাল পণ্য সম্প্রসারণ বৈশিষ্ট্য রাখে।
2. সর্বোচ্চ সম্প্রসারণযোগ্য পণ্য কোড ধারণা: সর্বোচ্চ সম্প্রসারণযোগ্য পণ্য কোডের ধারণা প্রবর্তন করে, যা অন্য সমস্ত একই প্যারামিটার পণ্য কোডের সম্প্রসারণযোগ্যতা বৈশিষ্ট্য উত্তরাধিকার করে।
3. পণ্য সম্প্রসারণের পুনর্বিবৃতি: পণ্য সম্প্রসারণ বৈশিষ্ট্যকে দ্বৈত কোড পণ্যে সম্প্রসারণযোগ্য উপসেটের মাধ্যমে পুনর্বিবৃত করে, উচ্চ-মাত্রিক বিশ্লেষণ সরল করে।
4. LTCs-এর পণ্য সম্প্রসারণ: প্রমাণ করে যে স্থানীয় পরীক্ষাযোগ্য কোড (LTCs) সংগ্রহ পণ্য সম্প্রসারণযোগ্য।
5. নির্বিচারে দৈর্ঘ্যের LTCs নির্মাণ: প্রমাণ করে যে নির্বিচারে দৈর্ঘ্য এবং 1-এর কাছাকাছি কোড হার সহ LTCs বিদ্যমান।

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

কাজের সংজ্ঞা

রৈখিক কোডের সংগ্রহ $C = (C_i)_{i \in [D]}$ দেওয়া, যেখানে $C_i \subseteq \mathbb{F}_q^n$, পণ্য কোড সংজ্ঞায়িত করুন:

$C_1 \otimes \cdots \otimes C_D := \{c \in \mathbb{F}_{[n]^D} | \forall i \in [D], \forall \ell \in L_i : c|_\ell \in C_i\}$

যেখানে $L_i$ হল $i$-অক্ষের সমান্তরাল রেখার সংগ্রহ।

পণ্য সম্প্রসারণের সংজ্ঞা: কোড সংগ্রহ $C$ হল $\rho$-পণ্য সম্প্রসারণযোগ্য, যদি প্রতিটি কোডওয়ার্ড $c \in C_1 \boxplus \cdots \boxplus C_D$ কে $c = \sum_{i \in [D]} a_i$ হিসাবে প্রকাশ করা যায়, যেখানে $a_i \in C^{(i)}$, এবং সন্তুষ্ট করে:

$\rho \sum_{i \in [D]} \|a_i\|_i \leq \|c\|$

মূল প্রযুক্তিগত কাঠামো

1. সম্প্রসারণযোগ্য সেট তত্ত্ব

• অভ্যন্তরীণভাবে উৎপাদিত সেট: সেট $M \subseteq [n]^D$ কোড $C_1 \boxplus \cdots \boxplus C_D$-এর জন্য অভ্যন্তরীণভাবে উৎপাদিত, যদি এর $M$-এ সমর্থিত প্রতিটি কোডওয়ার্ড $M$-এর মধ্যে রেখায় সমর্থিত কোডওয়ার্ডের যোগফল হিসাবে প্রকাশ করা যায়।
• সম্প্রসারণযোগ্য সেট: সেট $M$ কোড $C_1 \otimes \cdots \otimes C_D$-এর জন্য সম্প্রসারণযোগ্য, যদি $M$-এ স্থানীয় সীমাবদ্ধতা সন্তুষ্ট করে এমন প্রতিটি স্থানীয় কোডওয়ার্ড বৈশ্বিক কোডওয়ার্ডে প্রসারিত হতে পারে।

2. সর্বোচ্চ সম্প্রসারণযোগ্যতা

সংজ্ঞা: পণ্য কোড $C = \bigotimes_{i \in [D]} C_i$ সর্বোচ্চ সম্প্রসারণযোগ্য, যদি একই মাত্রার অন্য যেকোনো পণ্য কোড $C'$-এর জন্য, যখন সেট $M$ $C'$-এ সম্প্রসারণযোগ্য হয়, তখন এটি $C$-এও সম্প্রসারণযোগ্য।

3. মূল লেম্মা শৃঙ্খল

• লেম্মা 17: $\rho$-পণ্য সম্প্রসারণ সমস্ত $\rho$-বন্ধ সেট অভ্যন্তরীণভাবে উৎপাদিত হওয়া নির্দেশ করে
• লেম্মা 19: যদি সমস্ত $\varepsilon$-বন্ধ সেট অভ্যন্তরীণভাবে উৎপাদিত হয়, তাহলে $\rho(C_1, \ldots, C_D) \geq \gamma(\varepsilon, D)$
• লেম্মা 20: সর্বোচ্চ সম্প্রসারণযোগ্য কোড LTCs-এর পণ্য সম্প্রসারণ বৈশিষ্ট্য উত্তরাধিকার করে

প্রমাণ কৌশল

প্রথম পদক্ষেপ: LTCs-এর পণ্য সম্প্রসারণ

স্থানীয় পরীক্ষাযোগ্য কোড সংগ্রহ পণ্য সম্প্রসারণ বৈশিষ্ট্য রাখে তা প্রমাণ করুন:

লেম্মা 14: ন্যূনতম দূরত্ব কমপক্ষে $\delta n$ এবং শব্দ পরিসীমা $(\alpha_l, \alpha_h)$ সহ কোড $C_1, \ldots, C_D$-এর জন্য, একটি ধনাত্মক ফাংশন $f(D, \alpha_l, \alpha_h, \delta)$ বিদ্যমান যাতে $\rho(C_1, \ldots, C_D) \geq f(D, \alpha_l, \alpha_h, \delta)$।

দ্বিতীয় পদক্ষেপ: কোড হার অভিযোজন

উপকোড নির্মাণের মাধ্যমে নির্বিচারে কোড হার অর্জন করুন:

লেম্মা 10: উপকোড $C'_1 \subseteq C_1$-এর জন্য, আমাদের আছে: $\rho(C'_1, C_2, \ldots, C_D) \geq \frac{\rho(C_1, C_2, \ldots, C_D)}{1 + \rho(C_2, \ldots, C_D)^{-1}}$

তৃতীয় পদক্ষেপ: র‍্যান্ডম কোডের সর্বোচ্চ সম্প্রসারণযোগ্যতা

লেম্মা 21: $\text{Gr}_{2^t}(n, k_1) \times \cdots \times \text{Gr}_{2^t}(n, k_D)$ থেকে সমানভাবে র‍্যান্ডমভাবে নির্বাচিত কোড উপাদান, যার পণ্য কোড সম্ভাবনা কমপক্ষে $1 - n^D 2^{n^D - t + 1}$ সহ সর্বোচ্চ সম্প্রসারণযোগ্য।

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

তাত্ত্বিক যাচাইকরণ পদ্ধতি

এই পেপারটি প্রধানত তাত্ত্বিক কাজ, কঠোর গাণিতিক প্রমাণের মাধ্যমে ফলাফল যাচাই করে:

1. সম্ভাব্যতা বিশ্লেষণ: র‍্যান্ডম কোডের বৈশিষ্ট্য বিশ্লেষণ করতে Schwartz-Zippel লেম্মা ব্যবহার করুন
2. আনয়ন প্রমাণ: মাত্রা $D$-এর উপর আনয়ন দ্বারা পণ্য সম্প্রসারণ বৈশিষ্ট্য প্রমাণ করুন
3. গঠনমূলক প্রমাণ: স্পষ্ট নির্মাণের মাধ্যমে LTCs-এর অস্তিত্ব প্রমাণ করুন

প্যারামিটার সেটিং

• ক্ষেত্র আকার: $2^t$, যেখানে $t$ যথেষ্ট বড় যাতে $n^D 2^{n^D - t + 1} \to 0$
• কোড হার: $(R_1, \ldots, R_D) \in (0,1)^D$
• কোড দৈর্ঘ্য: নির্বিচারে $n \in \mathbb{N}$

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

প্রধান তাত্ত্বিক ফলাফল

উপপাদ্য 2: প্রতিটি কোড হার টুপল $(R_1, \ldots, R_D) \in (0,1)^D$-এর জন্য, একটি $\rho > 0$ বিদ্যমান যাতে প্রতিটি $n \in \mathbb{N}$-এর জন্য, $\text{Gr}_{2^t}(n, k_1) \times \cdots \times \text{Gr}_{2^t}(n, k_D)$ থেকে সমানভাবে র‍্যান্ডমভাবে নির্বাচিত কোড উপাদান (যেখানে $k_i \leq nR_i$) সম্ভাবনা কমপক্ষে $1 - n^D 2^{n^D - t + 1}$ সহ $\rho$-পণ্য সম্প্রসারণযোগ্য।

অনুসিদ্ধান্ত 3: যেকোনো ব্যবধান $I_1, \ldots, I_D \subseteq (0,1)$-এর জন্য, একটি $\rho > 0$ বিদ্যমান যাতে যথেষ্ট বড় $n$-এর জন্য, কোড $C_1, \ldots, C_D \subseteq \mathbb{F}_{2^{t_n}}^n$ বিদ্যমান (যেখানে $t_n = (n+1)^D$) সন্তুষ্ট করে:

• $\frac{1}{n} \dim C_i \in I_i$
• $\rho(C_1, \ldots, C_D) \geq \rho$
• $\rho(C_1^{\perp}, \ldots, C_D^{\perp}) \geq \rho$

মূল প্রযুক্তিগত ফলাফল

1. LTCs নির্মাণ (উপপাদ্য 4): প্রতিটি $R \in (0,1)$-এর জন্য, ধ্রুবক $s > 0, \Delta > 0, \delta > 0$ বিদ্যমান যাতে প্রতিটি $n \in \mathbb{N}$-এর জন্য, একটি $(\Delta, s)$-স্থানীয় পরীক্ষাযোগ্য $[n, k, d]$ কোড বিদ্যমান, যেখানে $k \geq Rn, d \geq \delta n$।
2. সম্প্রসারণ সংরক্ষণ: উপকোডের পণ্য সম্প্রসারণ ফ্যাক্টর মূল কোডের কমপক্ষে $2^{-D}(\rho)^{2^D}$।

সম্পর্কিত কাজ

উচ্চ-মাত্রিক সম্প্রসারক তত্ত্ব

• Kaufman-Lubotzky: প্রথমে HDXs-কে LTCs নির্মাণে ব্যবহারের ধারণা প্রস্তাব করেন
• Dinur এবং অন্যরা: প্রথম ধ্রুবক কোড হার, দূরত্ব এবং স্থানীয়তা সহ LTCs নির্মাণ করেন
• Panteleev-Kalachev: সম্প্রসারক উত্তোলন পণ্য কোড প্রস্তাব করেন

পণ্য কোড তত্ত্ব

• Wolf, Chien-Ng: প্রাথমিক পণ্য কোড তত্ত্ব
• Tillich-Zémor: কোয়ান্টাম LDPC কোডে হাইপারগ্রাফ পণ্য কোড
• Leverrier-Zémor: কোয়ান্টাম Tanner কোড

কোয়ান্টাম এনকোডিং তত্ত্ব

• Hastings-Haah-O'Donnell: ফাইবার বান্ডেল কোড যুগান্তকারী
• Cross এবং অন্যরা: কোয়ান্টাম স্থানীয় পরীক্ষাযোগ্য কোডের সর্বশেষ অগ্রগতি

সিদ্ধান্ত এবং আলোচনা

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

1. অস্তিত্ব ফলাফল: প্রমাণ করে যে যেকোনো সংখ্যক র‍্যান্ডম কোডের সংগ্রহ যথেষ্ট বড় ক্ষেত্রে উচ্চ সম্ভাবনায় ভাল পণ্য সম্প্রসারণ রাখে।
2. সর্বজনীনতা: সর্বোচ্চ সম্প্রসারণযোগ্য পণ্য কোড একটি সর্বজনীন কাঠামো প্রদান করে, যা সমস্ত সম্ভাব্য সম্প্রসারণ বৈশিষ্ট্য উত্তরাধিকার করে।
3. প্রয়োগের সম্ভাবনা: চার-মাত্রিক কোয়ান্টাম LTCs নির্মাণের জন্য তাত্ত্বিক ভিত্তি প্রদান করে।

সীমাবদ্ধতা

1. ক্ষেত্র আকারের প্রয়োজনীয়তা: সূচকীয় আকারের ক্ষেত্র $\mathbb{F}_{2^{(n+1)^D}}$ প্রয়োজন, যা ব্যবহারিক প্রয়োগে সমস্যা হতে পারে।
2. ধ্রুবক অপ্টিমাইজেশন: যদিও অস্তিত্ব প্রমাণ করা হয়েছে, পণ্য সম্প্রসারণ ধ্রুবক সর্বোত্তম নাও হতে পারে।
3. নির্মাণ: প্রধানত অস্তিত্ব ফলাফল, বহুপদ সময় নির্মাণ অ্যালগরিদমের অভাব।

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

1. ক্ষেত্র আকার উন্নত করা: ছোট ক্ষেত্র প্রয়োজন এমন নির্মাণ পদ্ধতি খুঁজে বের করা।
2. স্পষ্ট নির্মাণ: বহুপদ সময় স্পষ্ট নির্মাণ অ্যালগরিদম বিকাশ করা।
3. কোয়ান্টাম LTC প্রয়োগ: তাত্ত্বিক ফলাফল নির্দিষ্ট কোয়ান্টাম LTC নির্মাণে প্রয়োগ করা।
4. ধ্রুবক অপ্টিমাইজেশন: পণ্য সম্প্রসারণ ধ্রুবকের সীমা উন্নত করা।

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

সুবিধা

1. তাত্ত্বিক যুগান্তকারী: প্রথমবার যেকোনো সংখ্যক কোডের পণ্য সম্প্রসারণ বৈশিষ্ট্য প্রমাণ করে, বিদ্যমান তত্ত্ব উল্লেখযোগ্যভাবে প্রসারিত করে।
2. প্রযুক্তিগত উদ্ভাবন:
   • সর্বোচ্চ সম্প্রসারণযোগ্যতা ধারণা নতুন বিশ্লেষণ কাঠামো প্রদান করে
   • পণ্য সম্প্রসারণকে সম্প্রসারণযোগ্য সেট সমস্যা হিসাবে পুনর্বিবৃত করে
   • LTCs তত্ত্ব এবং র‍্যান্ডম কোড বিশ্লেষণ দক্ষতার সাথে একত্রিত করে
3. প্রমাণ কৌশল: র‍্যান্ডম কোডের বহুপদ প্যারামিটারকরণ পরিচালনা করতে Schwartz-Zippel লেম্মা ব্যবহার করা প্রযুক্তিগত হাইলাইট।
4. প্রয়োগের মূল্য: কোয়ান্টাম LTC অনুমানের জন্য গুরুত্বপূর্ণ তাত্ত্বিক সহায়তা প্রদান করে।

অপূর্ণতা

1. ব্যবহারিক সীমাবদ্ধতা: সূচকীয় আকারের ক্ষেত্র প্রয়োজনীয়তা ব্যবহারিক প্রয়োগ সীমিত করে।
2. ধ্রুবক বিশ্লেষণ: পণ্য সম্প্রসারণ ধ্রুবকের নির্দিষ্ট মান এবং অপ্টিমাইজেশন ডিগ্রি যথেষ্ট স্পষ্ট নয়।
3. নির্মাণ জটিলতা: দক্ষ নির্মাণ অ্যালগরিদমের অভাব।

প্রভাব

1. তাত্ত্বিক অবদান: এনকোডিং তত্ত্ব এবং কোয়ান্টাম তথ্য ক্ষেত্রে গুরুত্বপূর্ণ তাত্ত্বিক মূল্য রয়েছে।
2. পদ্ধতিবিদ্যা: সর্বোচ্চ সম্প্রসারণযোগ্যতা ধারণা অন্যান্য সম্পর্কিত সমস্যার গবেষণা অনুপ্রাণিত করতে পারে।
3. কোয়ান্টাম কম্পিউটিং: কোয়ান্টাম ত্রুটি সংশোধন কোডের উন্নয়নে নতুন তাত্ত্বিক সরঞ্জাম প্রদান করে।

প্রযোজ্য দৃশ্য

1. তাত্ত্বিক গবেষণা: উচ্চ-মাত্রিক সম্প্রসারক এবং পণ্য কোড তত্ত্ব গবেষণা
2. কোয়ান্টাম এনকোডিং: কোয়ান্টাম LDPC কোড এবং কোয়ান্টাম LTC নির্মাণ
3. ক্লাসিক্যাল এনকোডিং: স্থানীয় পরীক্ষাযোগ্য কোডের তাত্ত্বিক বিশ্লেষণ

সংদর্ভ

মূল সংদর্ভগুলি অন্তর্ভুক্ত করে:

• Dinur এবং অন্যদের LTC নির্মাণ 1
• Panteleev-Kalachev-এর সম্প্রসারক LP কোড 2
• Kaufman-Lubotzky-এর HDX তত্ত্ব 3
• Hastings-Haah-O'Donnell-এর ফাইবার বান্ডেল কোড 6
• Leverrier-Zémor-এর কোয়ান্টাম Tanner কোড 23

এই পেপারটি পণ্য কোডের কোবাউন্ডারি সম্প্রসারণ তত্ত্বে গুরুত্বপূর্ণ যুগান্তকারী অর্জন করেছে, কোয়ান্টাম ত্রুটি সংশোধন কোডের উন্নয়নের জন্য নতুন তাত্ত্বিক ভিত্তি প্রদান করেছে। যদিও ব্যবহারিক দিক থেকে এখনও উন্নতির অবকাশ রয়েছে, তবে এর তাত্ত্বিক মূল্য এবং পদ্ধতিবিদ্যাগত অবদান উল্লেখযোগ্য।