Fanout Complexity of Symmetric Boolean Functions in $\mathsf{QAC}^0$

तकनीकी सारांश: सममित बूलियन फलनों (Symmetric Boolean Functions) की फैनआउट जटिलता $\mathsf{QAC}^0$ में

समस्या विवरण
$\mathsf{QAC}^0$ (स्थिर-गहराई, बहुपद-आकार वाले क्वांटम सर्किट जिनमें मनमाने सिंगल-क्विबिट गेट्स और मल्टी-कंट्रोल्ड टोफ़ोली गेट्स होते हैं) की केंद्रीय खुली समस्या यह है कि क्या यह $\mathsf{FANOUT}_n$ ऑपरेशन को लागू कर सकता है। शास्त्रीय सर्किट में, फैनआउट निःशुल्क होता है; क्वांटम सर्किट में, शास्त्रीय सूचना को एक क्वबिट से $n$ लक्ष्यों तक कॉपी करना एक गैर-तुच्छ संसाधन है। चूंकि $\mathsf{FANOUT}_n$, हैडामार्ड कंजुगेशन (Hadamard conjugation) के तहत $\mathsf{PARITY}_n$ फलन के समतुल्य है, इसलिए यह निर्धारित करना कि $\mathsf{QAC}^0 = \mathsf{QAC}^0_f$ (जहाँ $\mathsf{QAC}^0_f := \mathsf{QAC}^0[\mathsf{FANOUT}_n]$) $\mathsf{PARITY}_n \in \mathsf{QAC}^0$ निर्धारित करने के समान है।

जबकि सामान्य मामला खुला है, डिक (Dicke)-स्टेट तैयारी पर हालिया कार्य ने एक सूक्ष्म दृष्टिकोण का सुझाव दिया है: सममित फलन को कंप्यूट करने की कठिनाई, आवश्यक फैनआउट गेट के आकार से सह-संबंधित हो सकती है। यह शोध पत्र इस सामान्य प्रश्न को संबोधित करता है: किसी भी सममित बूलियन फलन $f$ के लिए, $\mathsf{QAC}^0$ के भीतर उसे कंप्यूट करने के लिए आवश्यक फैनआउट आकार क्या है?

कार्यप्रणाली
लेखक सममित फलनों के लिए एक संरचनात्मक पैरामीटर पेश करते हैं जिसे ट्रांजिशन रेडियस (transition radius) कहा जाता है, जिसे $\rho(f)$ द्वारा दर्शाया गया है। एक सममित फलन $f$ के लिए, $\Delta f$ उन इंडेक्सों का सेट है जहाँ फलन का मान हैमिंग वेट (Hamming weight) $i$ और $i+1$ के बीच बदल जाता है। ट्रांजिशन रेडियस को इस प्रकार परिभाषित किया गया है:
$$\rho(f) := \max_{i \in \Delta f} \min\{i + 1, n - i\}$$
सहज रूप से, $\rho(f)$ हैमिंग वेट अंतराल के निकटतम छोर से "आंतरिकतम" ट्रांजिशन की दूरी को मापता है।

यह शोध पत्र $\mathsf{QAC}^0$ रिडक्शन के तहत किसी सममित फलन $f$ को कंप्यूट करने और $\mathsf{FANOUT}_{\rho(f)}$ को लागू करने के बीच एक सटीक समानता स्थापित करता है। प्रमाण दो दिशाओं में आगे बढ़ता है:

1. फैनआउट से सममित फलनों तक:
   लेखक दिखाते हैं कि $\rho(f) = k$ वाले किसी भी सममित फलन को कंप्यूट करने के लिए $\mathsf{FANOUT}_k$ पर्याप्त है। चूंकि ऐसे फलन के सभी ट्रांजिशन पहले $k$ या अंतिम $k$ हैमिंग वेट लेयर्स के भीतर होते हैं, इसलिए फलन को अधिकतम $2k$ "एक्ज़ैक्ट वेट" (exact weight) प्रेडिकेट्स ($\mathsf{EXACT}_j$) के डिसजंक्शन (OR) के रूप में व्यक्त किया जा सकता है। $\mathsf{FANOUT}_k$ का उपयोग करके, सर्किट इनपुट की $2k$ प्रतियां समानांतर में उत्पन्न कर सकता है, आवश्यक $\mathsf{EXACT}_j$ प्रेडिकेट्स का मूल्यांकन कर सकता है (जो ज्ञात है कि $\mathsf{QAC}^0[\mathsf{FANOUT}_k]$ में हैं), और उन्हें एक एकल OR गेट के साथ जोड़ सकता है।

2. सममित फलनों से फैनआउट तक:
   इसके विपरीत, लेखक प्रदर्शित करते हैं कि यदि एक $\mathsf{QAC}^0$ सर्किट एक सममित फलन $f$ को $\rho(f) = k$ के साथ, कम से कम $1/2 + 1/\text{polylog}(n)$ की वर्स्ट-केस प्रायिकता के साथ कंप्यूट करता है, तो $\mathsf{FANOUT}_k$ को लागू किया जा सकता है।

• प्रमाण हैमिंग वेट स्पेक्ट्रम के केंद्र में एक ट्रांजिशन को अलग करने के लिए सर्किट को $m = 2k-1$ इनपुट बिट्स तक सीमित करता है।
• यह प्रतिबंधित सर्किट के संबद्ध वास्तविक-मान फलन $g$ का विश्लेषण करता है। सर्किट द्वारा $f$ को उच्च प्रायिकता के साथ कंप्यूट करने की स्थिति, आसन्न हैमिंग वेट वाले इनपुट $x, y$ के लिए $|g(x) - g(y)|$ के अंतर पर एक निचली सीमा (lower bound) लगाती है।
• यह अंतर फलन के कुल प्रभाव (total influence) पर एक निचली सीमा में अनुवादित होता है, जो पार्सवल की पहचान (Parseval's identity) और फैक्ट 6 के माध्यम से, एक महत्वपूर्ण "फोरियर टेल" (Fourier tail - उच्च डिग्री पर द्रव्यमान) को दर्शाता है।
• लेखक Gretta, Gupta, और Joshi [GGJ26a] के फोरियर-टेल रिडक्शन परिणाम का उपयोग करते हैं, जो कहता है कि पर्याप्त उच्च-डिग्री फोरियर द्रव्यमान वाले सर्किट को $\mathsf{FANOUT}_\ell$ सर्किट में बदला जा सकता है।
• अंत में, वे दिखाते हैं कि व्युत्पन्न फैनआउट आकार $\ell$, एक कॉन्स्टेंट-डेप्थ ट्री के माध्यम से $\mathsf{FANOUT}_k$ का निर्माण करने के लिए पर्याप्त है।

मुख्य परिणाम
मुख्य प्रमेय किसी भी सममित बूलियन फलन $f$ के लिए निम्नलिखित समानता स्थापित करता है:
$$f \in \mathsf{QAC}^0 \iff \mathsf{FANOUT}_{\rho(f)} \in \mathsf{QAC}^0$$
अधिक सटीक रूप से:

1. यदि $f$ को $1/2 + 1/\log^c n$ की प्रायिकता के साथ $\mathsf{QAC}^0$ सर्किट द्वारा कंप्यूट किया जा सकता है, तो $\mathsf{FANOUT}_{\rho(f)}$ को $\mathsf{QAC}^0$ सर्किट द्वारा लागू किया जा सकता है।
2. यदि $\mathsf{FANOUT}_{\rho(f)}$ को $\mathsf{QAC}^0$ सर्किट द्वारा लागू किया जा सकता है, तो $f$ को $\mathsf{QAC}^0$ सर्किट द्वारा सटीक रूप से कंप्यूट किया जा सकता है।

उपलब्धियाँ और निहितार्थ

• बड़े ट्रांजिशन रेडियस के लिए पूर्णता (Completeness): यदि $\rho(f) \ge n^\delta$ किसी स्थिरांक $\delta > 0$ के लिए है, तो $f$ को कंप्यूट करना $\mathsf{QAC}^0_f$-पूर्ण है। ऐसा इसलिए है क्योंकि $\mathsf{FANOUT}_{\rho(f)}$ को $\mathsf{FANOUT}_n$ को लागू करने के लिए एक कॉन्स्टेंट-डेप्थ ट्री में दोहराया जा सकता है। यह परिणाम $\mathsf{PARITY}$, $\mathsf{MAJORITY}$, $\mathsf{THRESHOLD}$, और $\mathsf{MOD}_q$ के पिछले पूर्णता परिणामों को एकीकृत और सामान्य करता है।
• अनुमानित डिग्री (Approximate Degree) और समरूपता: पटूरी (Paturi) के अनुमानित डिग्री ($\widetilde{\deg}(f) = \Theta(\sqrt{n\rho(f)})$) के प्रमेय के साथ संयोजन करते हुए, लेखक $\mathsf{QAC}^0$ में फलनों पर एक प्रतिबंध प्राप्त करते हैं। विशेष रूप से, यदि $\mathsf{PARITY}_n \notin \mathsf{QAC}^0$ है, तो $\Omega(n^{1/2+\eta})$ अनुमानित डिग्री वाला $\mathsf{QAC}^0$ में कोई भी फलन असममित (nonsymmetric) होना चाहिए। ऐसा इसलिए है क्योंकि इतनी डिग्री वाला एक सममित फलन, पॉलिनोमियल रूप से बड़ा ट्रांजिशन रेडियस रखेगा, जिससे वह $\mathsf{QAC}^0_f$-पूर्ण (और इस प्रकार $\mathsf{PARITY}_n$ के समतुल्य) हो जाएगा।

महत्व
यह शोध पत्र $\mathsf{QAC}^0$ के भीतर संपूर्ण सममित बूलियन फलनों के वर्ग के लिए फैनआउट जटिलता का पूर्ण लक्षण वर्णन प्रदान करता है। यह ट्रांजिशन रेडियस को सटीक थ्रेशोल्ड के रूप में पहचानकर सममित फलनों के लिए फैनआउट प्रश्न की "ऑल-ऑर-नथिंग" (all-or-nothing) प्रकृति को हल करता है। यह कार्य विशिष्ट फलनों (जैसे $\mathsf{PARITY}$ और $\mathsf{MAJORITY}$) के लिए ज्ञात परिणामों को विशेष मामलों के रूप में पुनः प्राप्त करता है और यह दिखाकर पिछले परिणामों को मजबूत करता है कि बड़े ट्रांजिशन रेडियस वाले फलनों के लिए $\mathsf{FANOUT}_k$ की पूर्णता को ट्रिगर करने के लिए अनुमानित गणना (प्रायिकता $1/2 + 1/\text{polylog}(n)$ के साथ) ही पर्याप्त है। इसके अतिरिक्त, यह $\mathsf{QAC}^0$ की सीमाओं के संबंध में एक नया दृष्टिकोण प्रदान करता है, जो उच्च-डिग्री सममित फलनों के $\mathsf{PARITY}$ के प्रश्न को सीधे जोड़ता है।