Separating Non-Interactive Classical Verification of Quantum Computation from Falsifiable Assumptions

यहाँ शोध पत्र "Separating Non-Interactive Classical Verification of Quantum Computation from Falsifiable Assumptions" (Barhoush, Morimae, Nishimaki, और Yamakawa द्वारा) का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र क्वांटम क्रिप्टोग्राफी की एक मौलिक खुली समस्या को संबोधित करता है: क्या QMA जटिलता वर्ग (complexity class) के लिए नॉन-इंटरैक्टिव क्लासिकल वेरिफिकेशन ऑफ क्वांटम कम्प्यूटेशन (NI-CVQC) को मानक फाल्सिफिएबल (falsifiable) क्रिप्टोग्राफिक धारणाओं पर आधारित किया जा सकता है?

• संदर्भ: महादेव (2022) ने पहला प्रोटोकॉल पेश किया जिसने एक क्लासिकल वेरीफायर को क्वांटम प्रूवर के कम्प्यूटेशन को सत्यापित करने की अनुमति दी, लेकिन इसके लिए 4 संदेशों (messages) के इंटरैक्शन की आवश्यकता थी और यह लर्निंग-विथ-एरर्स (LWE) धारणा पर आधारित था।
• अंतराल (The Gap): जबकि बाद के कार्यों ने क्वांटम रैंडम ऑरेकल मॉडल (QROM) में गैर-इंटरैक्टिविटी (1 संदेश) प्राप्त की, प्लेन मॉडल (रैंडम ऑरेकल के बिना) में इसे प्राप्त करना एक खुली चुनौती बनी हुई है।
• प्रश्न: क्या प्लेन मॉडल में फाल्सिफिएबल धारणाओं (जैसे LWE, वन-वे फंक्शन्स, आदि) के आधार पर QMA के लिए NI-CVQC प्रोटोकॉल का निर्माण करना संभव है?
• परिभाषाएँ:
  • NI-CVQC: एक ऐसा प्रोटोकॉल जहाँ वेरीफायर एक पब्लिक की (पब्लिक की जो इंस्टेंस से स्वतंत्र हो) भेजता है, और प्रूवर एक एकल क्लासिकल प्रूफ भेजता है।
  • फाल्सिफिएबल धारणा (Falsifiable Assumption): एक ऐसी धारणा जिसे एक कुशल इंटरैक्टिव गेम के रूप में प्रस्तुत किया जा सकता है जहाँ एक चैलेंजर यह सत्यापित कर सकता है कि क्या कोई एडवरसरी जीत गया है (जैसे LWE को तोड़ना)।
  • QMA बनाम QCMA: QMA क्वांटम विटनेस (witnesses) की अनुमति देता है; QCMA क्लासिकल विटनेस की अनुमति देता है। शोध पत्र एक ऐसे "गैप" के अस्तित्व को मानता है जहाँ QMA समस्याएँ उन एडवर्सरीज के लिए भी कठिन होती हैं जिनके पास QCMA ऑरेकल तक पहुँच होती है।

2. मुख्य योगदान (Key Contributions)

लेखक एक मजबूत नकारात्मक परिणाम (strong negative result) सिद्ध करते हैं: यदि एक विशिष्ट जटिलता-सैद्धांतिक स्थिति लागू होती है, तो किसी भी फाल्सिफिएबल धारणा से NI-CVQC प्रोटोकॉल की साउंडनेस (soundness) को निकालने के लिए कोई क्वांटम ब्लैक-बॉक्स रिडक्शन मौजूद नहीं है।

मुख्य प्रमेय (अनौपचारिक):
यह मानते हुए कि एक सब-एक्सपोनेंशियल QMA-QCMA गैप समस्या मौजूद है, NI-CVQC प्रोटोकॉल की साउंडनेस को किसी फाल्सिफिएबल धारणा से प्राप्त करने वाला कोई क्वांटम ब्लैक-बॉक्स रिडक्शन मौजूद नहीं है।

उपप्रमेय (Corollary):
यह मानते हुए कि LWE और एक सब-एक्सपोनेंशियल QMA-QCMA गैप समस्या मौजूद है, महादेव के 4-संदेश वाले CVQC प्रोटोकॉल से NI-CVQC का कोई क्वांटम ब्लैक-बॉक्स रिडक्शन नहीं है। इसका तात्पर्य है कि 4 संदेशों से 1 संदेश (नॉन-इंटरैक्टिव) तक जाने के लिए संभवतः मानक फाल्सिफिएबल धारणाओं से अधिक मजबूत धारणाओं (या गैर-फाल्सिफिएबल धारणाओं) की आवश्यकता होगी।

3. कार्यप्रणाली और तकनीकी दृष्टिकोण (Methodology and Technical Approach)

प्रमाण एक "ब्लैक-बॉक्स सेपरेशन" ढांचे का अनुसरण करता है जो Gentry-Wichs के प्रसिद्ध SNARG सेपरेशन के समान है, लेकिन इसे क्वांटम सेटिंग और QMA के लिए अनुकूलित किया गया है। कार्यप्रणाली में तीन प्रमुख तकनीकी घटक शामिल हैं:

A. QMA-QCMA गैप समस्या

लेखक सेपरेशन को संचालित करने के लिए एक विशिष्ट प्रकार की समस्या पेश करते हैं। एक QMA-QCMA गैप समस्या में एक भाषा $L$ शामिल है जहाँ:

1. Yes instances को वैध क्वांटम विटनेस के साथ कुशलतापूर्वक सैंपल किया जा सकता है।
2. No instances को (संभवतः अक्षम रूप से) सैंपल किया जा सकता है।
3. अभेद्यता (Indistinguishability): एक QCMA ऑरेकल (एक ऑरेकल जो प्रॉमिस-QCMA समस्याओं को हल करता है) तक पहुँच रखने वाला कोई भी कुशल एडवरसरी Yes और No इंस्टेंस के बीच अंतर नहीं कर सकता है।

• महत्व: यह $QMA \neq QCMA$ से थोड़ा अधिक मजबूत है। यह आवश्यक बनाता है कि एक "क्लासिकल विटनेस सॉल्वर" (QCMA ऑरेकल) के साथ भी, समस्या की क्वांटम कठिनाई बनी रहे।

B. QCMA ऑरेकल के साथ संशोधित लीकेज लेम्मा (Modified Leakage Lemma)

क्लासिकल SNARG सेपरेशन (Gentry-Wichs) में, एक "लीकेज लेम्मा" कहता है कि यदि दो डिस्ट्रीब्यूशन अविभेद्य (indistinguishable) हैं, तो वे लघु सहायक स्ट्रिंग्स (auxiliary strings) के साथ भी अविभेद्य रहते हैं।

• चुनौती: NI-CVQC में, प्रमाण (proofs) अनिवार्य रूप से छोटे नहीं होते; संभावित प्रमाणों का स्थान घातीय (exponentially) रूप से बड़ा होता है, जिससे ब्रूट-फोर्स सर्च अव्यवहार्य हो जाता है।
• समाधान: लेखक एडवरसरी को एक QCMA ऑरेकल के साथ सुसज्जित करते हैं।
  • वे तर्क देते हैं कि सही सहायक जानकारी (दोषपूर्ण प्रमाण) खोजना एक क्लासिकल विटनेस खोजने के समान है, जो कि एक QCMA कार्य है।
  • वे एक संशोधित लीकेज लेम्मा सिद्ध करते हैं: भले ही सहायक जानकारी की लंबाई बहुपद (polynomial) हो, यदि अंतर्निहित समस्या एक QMA-QCMA गैप समस्या है, तो Yes/No डिस्ट्रीब्यूशन एडवरसरी के लिए अविभेद्य बने रहते हैं।

C. सैंपल अविभेद्यता से ऑरेकल अविभेद्यता तक

क्वांटम सेपरेशन में एक महत्वपूर्ण बाधा यह है कि NI-CVQC में ईमानदार प्रूवर एक क्वांटम एल्गोरिदम है।

• समस्या: मानक लीकेज लेम्मा दिखाते हैं कि "नकली" डिस्ट्रीब्यूशन से प्राप्त सैंपल्स ईमानदार डिस्ट्रीब्यूशन से अविभेद्य हैं। हालाँकि, एक क्वांटम रिडक्शन प्रूवर को एक यूनिटरी ऑरेकल के रूप में क्वेरी कर सकता है।
• समाधान: लेखक एक कुशल, स्टेटफुल सिम्युलेटर $S$ बनाने के लिए कंप्रेस्ड ऑरेकल तकनीक (Zhandry et al.) का उपयोग करते हैं। वे सिद्ध करते हैं कि $S$, वैध दिखने वाले प्रमाण उत्पन्न करने वाले अक्षम एडवरसरी $P$ से क्वांटम-ऑरेकल-अभेद्य (quantum-oracle-indistinguishable) है। यह रिडक्शन को यह विश्वास दिलाने में सक्षम बनाता है कि वह ईमानदार प्रूवर के साथ इंटरैक्ट कर रहा है, जबकि वास्तव में वह सिम्युलेटर के साथ इंटरैक्ट कर रहा होता है।

4. प्रमाण संरचना (Proof Structure)

असंभवता का प्रमाण विरोधाभास (contradiction) द्वारा चलता है:

1. धारणा: मान लें कि एक NI-CVQC प्रोटोकॉल $\Pi$ मौजूद है और यह एक फाल्सिफिएबल धारणा $(C, c)$ पर एक क्वांटम ब्लैक-बॉक्स रिडक्शन $\Sigma$ के माध्यम से आधारित है।
2. एडवरसरी का निर्माण: QMA-QCMA गैप समस्या का उपयोग करते हुए, लेखक एक अक्षम एडवरसरी $P$ का निर्माण करते हैं जो "No" इंस्टेंस के लिए वैध दिखने वाले प्रमाण उत्पन्न करता है (साउंडनेस को तोड़ता है)।
3. एडवरसरी का सिमुलेशन: वे एक कुशल सिम्युलेटर $S$ का निर्माण करते हैं जो $P$ के समान है, भले ही उसे क्वांटम ऑरेकल के रूप में एक्सेस किया जाए।
4. रिडक्शन को तोड़ना:
   • चूँकि $P$ साउंडनेस को तोड़ता है, इसलिए रिडक्शन $\Sigma^P$ फाल्सिफिएबल धारणा को तोड़ता है।
   • चूँकि $S$, $P$ के समान (indistinguishable) है, इसलिए $\Sigma^S$ को भी धारणा को तोड़ना चाहिए।
   • हालाँकि, $S$ कुशल है। यदि $\Sigma^S$ धारणा को तोड़ता है, तो इसका अर्थ है कि फाल्सिफिएबल धारणा के विरुद्ध एक कुशल हमला मौजूद है, जो धारणा की सत्यता का खंडन करता है।
5. निष्कर्ष: इसलिए, ऐसा कोई रिडक्शन $\Sigma$ मौजूद नहीं हो सकता।

5. सहायक निर्माण (Supporting Construction - Oracle Separation)

"QMA-QCMA गैप समस्या" की धारणा की संभावना को पुष्ट करने के लिए, लेखक एक क्वांटम यूनिटरी ऑरेकल के सापेक्ष एक निर्माण प्रदान करते हैं:

• वे एक ऐसी भाषा परिभाषित करते हैं जहाँ "Yes" इंस्टेंस विशिष्ट Haar-random स्टेट $|\psi_x\rangle$ के साथ इनपुट $x$ के युग्म के रूप में होते हैं।
• ऑरेकल $|x\rangle|\psi_x\rangle$ पर $x \in L$ होने पर एक फेज फ्लिप (phase flip) लगाता है।
• वे सिद्ध करते हैं कि इन इंस्टेंस को अलग करने के लिए विशिष्ट क्वांटम स्टेट $|\psi_x\rangle$ की आवश्यकता होती है।
• महत्वपूर्ण रूप से, वे दिखाते हैं कि QCMA ऑरेकल (जो क्लासिकल विटनेस खोज सकता है) तक पहुँच के साथ भी, एडवरसरी डिस्ट्रीब्यूशनों के बीच अंतर नहीं कर सकता है, जो आइडेंटिटी बनाम फेज-फ्लिप यूनिटरीज की अविभेद्यता के संबंध में आरोंसन (Aaronson) और कुपरबर्ग (Kuperberg) के परिणाम का लाभ उठाता है।

6. महत्व और निहितार्थ (Significance and Implications)

• फाल्सिफिएबल धारणाओं की सीमाएँ: यह परिणाम एक मौलिक बाधा स्थापित करता है। यह सुझाव देता है कि प्लेन मॉडल में सामान्य QMA समस्याओं के लिए नॉन-इंटरैक्टिव सत्यापन प्राप्त करना (LWE जैसी मानक क्रिप्टोग्राफिक धारणाओं का उपयोग करके) संभवतः असंभव है।
• जटिलता सिद्धांत (Complexity Theory): यह QMA और QCMA के बीच के संबंध की समझ को गहरा करता है, यह सुझाव देते हुए कि कुछ क्रिप्टोग्राफिक प्रिमिटिव्स के लिए उनके बीच का गैप आवश्यक है।
• भविष्य की दिशाएँ:
  • यह सेपरेशन एडेप्टिव साउंडनेस (जहाँ प्रूवर पब्लिक की देखने के बाद गलत स्टेटमेंट चुनता है) के लिए लागू होता है। शोध पत्र नोट करता है कि स्टैटिक साउंडनेस (जहाँ स्टेटमेंट की (key से पहले) चुनी जाती है) को कवर नहीं किया गया है, जो निर्माण के लिए एक संभावित मार्ग छोड़ता है।
  • यह परिणाम QMA के लिए लागू होता है। BQP के लिए (जहाँ विटनेस मामूली/trivial है), प्रिमिटिव स्वयं फाल्सिफिएबल है, इसलिए सेपरेशन सीधे लागू नहीं होता है, हालांकि लेखक विशिष्ट गैप धारणाओं के तहत BQP के लिए एक सशर्त असंभवता का सुझाव देते हैं।
  • व्यावहारिक प्रभाव: यह संकेत देता है कि यदि हम जटिल क्वांटम गणनाओं (QMA) के लिए नॉन-इंटरैक्टिव सत्यापन चाहते हैं, तो हमें या तो गैर-फाल्सिफिएबल धारणाओं (जैसे इंडिस्टिंग्विशेबिलिटी ऑब्फस्केशन का अस्तित्व) पर निर्भर रहना होगा या इंटरैक्शन (4+ संदेश) को स्वीकार करना होगा।

सारांश तालिका (Summary Table)