⚛️ quantum physics

A Computational Tsirelson's Theorem for the Value of Compiled XOR Games

यह शोध पत्र यह सिद्ध करता है कि कलई एवं अन्य द्वारा प्रस्तावित संकलन विधि (compilation method) किसी भी दो-खिलाड़ी XOR गेम के लिए सुदृढ़ है, यह प्रदर्शित करते हुए कि क्वांटम मान पर सेमीडेफिनेट प्रोग्रामिंग ऊपरी सीमा संकलित गेम के लिए एक नगण्य त्रुटि तक बनी रहती है, जिससे विशिष्ट CHSH मामले से पिछले परिणामों का सामान्य XOR गेम्स में विस्तार होता है और समानांतर पुनरावृत्तियों (parallel repetitions), ऑपरेटर सेल्फ-टेस्टिंग और सम-ऑफ-स्क्वायरज़ प्रमाणों (sum-of-squares certificates) पर सटीक सीमाएँ संभव हो पाती हैं।

मूल लेखक: David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, Tina Zhang

प्रकाशित 2026-01-28

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, Tina Zhang

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि एक हाई-स्टेक्स गेम शो चल रहा है जहाँ दो प्रतियोगी, एलिस और बॉब, अलग-अलग कमरों में बंद हैं। वे एक-दूसरे से बात नहीं कर सकते, लेकिन वे एक रहस्यमय, अदृश्य संबंध साझा करते हैं (जैसे कि जोड़ी जादुable पासे जो हमेशा मिलान वाले नंबरों पर आते हैं, चाहे वे एक-दूसरे से कितनी भी दूर क्यों न हों)। एक रेफरी उनसे सवाल पूछता है, और उन्हें जवाब देना होता है। यदि उनके उत्तर एक विशिष्ट पैटर्न का पालन करते हैं, तो वे जीत जाते हैं।

क्वांटम भौतिकी की दुनिया में, इसे नॉनलोकल गेम (Nonlocal Game) कहा जाता है। यह "जादुई" संबंध एंटैंगलमेंट (Entanglement) है। वैज्ञानिक लंबे समय से जानते हैं कि यदि एलिस और बॉब क्वांटम एंटैंगलमेंट का उपयोग करते हैं, तो वे साधारण, बिना जादू वाली रणनीतियों की तुलना में इन खेलों को अधिक बार जीत सकते हैं।

समस्या: एक खिलाड़ी बनाम सिस्टम

आमतौर पर, यह साबित करने के लिए कि एलिस और बॉब इस "जादू" का उपयोग कर रहे हैं, आपको दो अलग-अलग लोगों की आवश्यकता होती है जो बात न कर सकें। लेकिन क्या होगा यदि आपके पास केवल एक व्यक्ति (एक सिंगल क्वांटम कंप्यूटर) हो और आप यह परीक्षण करना चाहते हैं कि क्या वह उसी "जादुई" करतब को कर रहा है?

2023 में, शोधकर्ताओं की एक टीम (कलई एट अल.) ने एक चतुर तकनीक निकाली जिसे कंपाइलर (Compiler) कहा जाता है। इस कंपाइलर को एक "समय-यात्रा करने वाला अनुवादक" समझें। यह दो-खिलाड़ी वाले खेल को लेता है और एकल खिलाड़ी को बारी-बारी से एलिस और बॉब दोनों की भूमिका निभाने के लिए मजबूर करता है।

रेफरी एलिस के सवाल को एन्क्रिप्ट करता है (उसे एक डिजिटल तिजोरी में छिपा देता है)।
खिलाड़ी एलिस के रूप में कार्य करता है, तिजोरी खोलता है, अपनी "जादुई" अवस्था (state) को मापता है, और एक एन्क्रिप्टेड उत्तर वापस भेजता है।
इसके बाद रेफरी बॉब का सवाल प्रकट करता है (अनएन्क्रिप्टेड)।
खिलाड़ी बॉब के रूप में कार्य करता है, फिर से मापता है, और उत्तर देता है।

बड़ा सवाल यह था: क्या यह एकल-खिलाड़ी, एन्क्रिप्टेड गेम मूल दो-खिलाड़ी गेम के समान जीतने की संभावना को बनाए रखता है?

हम जानते थे कि यह क्लासिकल खिलाड़ियों (बिना जादू के) के लिए काम करता है।
हम जानते थे कि यह सबसे सरल क्वांटम गेम (CHSH) के लिए काम करता है।
लेकिन हम नहीं जानते थे कि क्या यह सभी एक निश्चित प्रकार के क्वांटम गेम्स के लिए काम करता है।

सफलता: "XOR" गेम्स

यह पेपर, कुई, मालावोल्टा, मेहता और अन्य द्वारा, कहता है हाँ। वे सिद्ध करते हैं कि XOR गेम्स के एक विशाल परिवार के लिए, कंपाइलर पूरी तरह से काम करता है।

XOR गेम क्या है?
कल्पना कीजिए कि जीतने की शर्त सरल है: "आप जीतते हैं यदि आपके उत्तर समान हैं, या यदि वे प्रश्न के आधार पर भिन्न हैं।" यह "एक्सक्लूसिव ऑर" (XOR) लॉजिक पर आधारित एक खेल है। ये खेल क्वांटम भौतिकी के "ट्रेनिंग व्हील्स" (प्रशिक्षण पहिए) के समान हैं—वे गणित से हल करने के लिए पर्याप्त सरल हैं, लेकिन क्वांटम शक्ति दिखाने के लिए पर्याप्त जटिल भी हैं।

उन्होंने इसे कैसे सिद्ध किया: "सम ऑफ स्क्वायर्स" (Sum of Squares) ट्रिक

इस खेल की जीतने की संभावना को एक 'सम ऑफ स्क्वायर्स' (Sum of Squares - SOS) सर्टिफिकेट का उपयोग करके सिद्ध करने के लिए, लेखकों ने एक गणितीय उपकरण का उपयोग किया।

इस खेल की जीतने की संभावना को एक जटिल रेसिपी (नुस्खा) मान लीजिए। लेखकों ने इस रेसिपी को 'सम ऑफ स्क्वायर्स' (जैसे $x^2 + y^2 + z^2$ ) के रूप में फिर से लिखने का तरीका खोजा। गणित में, यदि आपके पास 'सम ऑफ स्क्वायर्स' है, तो आप जानते हैं कि यह ऋणात्मक (negative) नहीं हो सकता।

पुरानी समस्या: दो-खिलाड़ी वाले खेल में, अलगाव का "जादू" (एलिस और बॉब का अलग-अलग कमरों में होना) यह सुनिश्चित करता है कि कुछ गणितीय शब्द पूरी तरह से एक-दूसरे को काट देते हैं।
नई चुनौती: एकल-खिलाड़ी वाले खेल में, कोई भौतिक अलगाव नहीं है। "कैलकुलेशन" का यह 'कैंसिलेशन' भौतिकी द्वारा गारंटीकृत नहीं है; इसे क्रिप्टोग्राफी (डिजिटल तिजोरी की सुरक्षा) द्वारा गारंटीकृत किया जाना चाहिए।
समाधान: लेखकों ने दिखाया कि XOR गेम्स के लिए, गणित इतना "अच्छा" है कि भौतिक अलगाव के बिना भी, क्रिप्टोग्राफिक लॉक इतने मजबूत हैं कि वे एकल खिलाड़ी को बिल्कुल वैसा ही व्यवहार करने के लिए मजबूर करते हैं जैसा कि वे दो अलग-अलग लोगों के रूप में करते। "चीटिंग" का लाभ इतना छोटा (नगण्य) है कि वह व्यावहारिक रूप से शून्य है।

इसका क्या अर्थ है (यह क्यों महत्वपूर्ण है?)

चूंकि उन्होंने सिद्ध किया कि यह कंपाइलर सभी XOR गेम्स के लिए काम करता है, उन्होंने तीन नई महाशक्तियाँ अनलॉक कर दीं:

सेल्फ-टेस्टिंग (एक झूठ पकड़ने वाला यंत्र):
यदि कोई खिलाड़ी कंपाइल किए गए गेम में लगभग पूरी तरह से जीतता है, तो अब हम गणितीय रूप से यह सिद्ध कर सकते हैं कि उनकी क्वांटम मशीन वास्तव में अंदर क्या कर रही है। यह एक ब्लैक बॉक्स को देखने और यह कहने जैसा है, "मैं जानता हूँ कि आप एक विशिष्ट प्रकार का घूमता हुआ लट्टू पकड़े हुए हैं, और मैं जानता हूँ कि वह ठीक कैसे घूम रहा है।" इसे रिजिडिटी (Rigidity) कहा जाता है।
पैरेलल रिपिटिशन (एक मल्टीप्लायर):
यदि आप एक साथ कई बार खेल खेलते हैं (पैरेलल रिपिटेशन), तो एक धोखेबाज के जीतने की संभावना तेजी से घट जाती है। यह पेपर सिद्ध करता है कि यह कंपाइल किए गए, एकल-ख pemain सेटिंग में भी सच होता है। यह कहने जैसा है, "यदि आप एक टेस्ट में धोखाधड़ी करने की कोशिश करते हैं, तो आप भाग्यशाली हो सकते हैं। यदि आप एक साथ 100 टेस्ट में धोखाधड़ी करने की कोशिश करते हैं, तो आप निश्चित रूप से पकड़े जाएंगे।"
मैजिक स्क्वायर गेम:
उन्होंने मैजिक स्क्वायर गेम नामक एक प्रसिद्ध पहेली पर अपने तरीके को लागू किया। उन्होंने सिद्ध किया कि यहाँ तक कि इस कंपाइल किए गए संस्करण में भी, यदि कोई खिलाड़ी जीतता है, तो उनकी मशीन में दो विशिष्ट "विपरीत" बल (ऑपरेटर्स) होने चाहिए जो आपस में कम्यूट (commute) नहीं करते (वे आपस में तालमेल नहीं बिठाते)। यह पुष्टि करता है कि मशीन वास्तव में क्वांटम है।

निष्कर्ष

यह पेपर एक सेतु (bridge) है। यह एक जटिल, सैद्धांतिक उपकरण (कंपाइलर) को लेता है जो केवल सरल मामलों के लिए काम करने के लिए जाना जाता था और सिद्ध करता है कि यह महत्वपूर्ण क्वांटम गेम्स के एक पूरे वर्ग के लिए काम करता है। यह पुष्टि करता है कि हम एक एकल, एन्क्रिप्टेड क्वांटम कंप्यूटर पर उन कार्यों को करने के लिए भरोसा कर सकते हैं जिनके लिए आमतौर पर दो अलग-अलग, एंटैंगल्ड क्वांटम कंप्यूटरों की आवश्यकता होती है, बिना किसी "क्वांटम जादू" को खोए।

संक्षेप में: उन्होंने एक तरीका खोजा जिससे वे एक क्वांटम गेम को डिजिटल तिजोरी के अंदर बंद कर सकें, एक ही व्यक्ति को दोनों पक्षों को खेलने के लिए मजबूर कर सकें, और यह सिद्ध कर सकें कि तिजोरी के अंदर का खेल उतना ही निष्पक्ष और जादुई है जितना कि दो अलग-अलग कमरों में रहने वाले दो लोगों द्वारा खेला जाने वाला मूल खेल।

तकनीकी सारांश: संकलित (Compiled) XOR गेम्स के मान के लिए एक कम्प्यूटेशनल ट्सिरेलसन का प्रमेय (Tsirelson's Theorem)

समस्या विवरण

नॉनलोकल गेम्स (Nonlocal games) एंटैंगलमेंट को समझने और कई स्थानिक रूप से अलग उपकरणों वाले क्वांटम प्रोटोकॉल बनाने के लिए मौलिक हैं। एक केंद्रीय चुनौती इन मल्टी-प्रोवर परिणामों को एक ऐसे मॉडल में अनुवादित करने की है जहाँ एक क्लासिकल वेरीफायर (verifier) एक एकल, कम्प्यूटेशनल रूप से सीमित क्वांटम प्रोवर के साथ इंटरैक्ट करता है। "नॉन-कम्युनिकेशन" (non-communication) धारणा को व्यवहार में लागू करना कठिन है।

इसे संबोधित करने के लिए, कालई एट अल. (STOC '23) ने एक जेनेरिक कंपाइलर प्रस्तावित किया जो किसी भी $k$ -प्लेयर वन-राउंड नॉनलोकल गेम को मल्टी-राउंड सिंगल-प्रोवर प्रोटोकॉल में बदलने के लिए क्वांटम होमोमोर्फिक एन्क्रिप्शन (QHE) का उपयोग करता है। जबकि उन्होंने यह सिद्ध किया कि कंपाइलर क्लासिकल मान को सुरक्षित रखता है, सामान्य गेम्स के लिए क्वांटम मान का संरक्षण एक खुला प्रश्न बना रहा। नटाराजन और झांग (FOCS '23) ने CHSH गेम के विशिष्ट मामले के लिए इसे हल किया, लेकिन दो-प्लेयर XOR गेम्स के व्यापक वर्ग के लिए यह प्रश्न बना रहा।

यह शोध पत्र इस प्रश्न को संबोधित करता है: क्या कालई एट अल. का कंपाइलर किसी भी दो-प्लेयर XOR गेम के लिए क्वांटम मान को सुरक्षित रखता है?

कार्यप्रणाली (Methodology)

लेखक संकलित गेम के क्वांटम मान को सीमित करने के लिए दो पूरक दृष्टिकोणों का उपयोग करते हैं, जो XOR गेम्स की विशिष्ट बीजगणितीय संरचना पर आधारित हैं।

1. सम-ऑफ-स्क्वायर्स (SOS) प्रमाण और स्यूडो-एक्सपेक्टेशन (Pseudo-Expectations)

एक नॉनलोकल गेम के क्वांटम मान को ऊपरी सीमा देने की मानक विधि में एक गेम को एक बहुपद $p$ के साथ जोड़ना और $\omega \mathbb{1} - p$ के लिए एक सम-ऑफ-स्क्वायर्स (SOS) अपघटन (decomposition) खोजना शामिल है। नॉनलोकल सेटिंग में, प्रोवर्स की स्थानिक पृथकता यह दर्शाती है कि मेजरमेंट ऑपरेटर्स कम्यूट करते हैं ( $[A_x, B_y] = 0$ ), जिससे एक "स्यूडो-एक्सपेक्टेशन" का निर्माण संभव होता है जो पॉजिटिव ऑपरेटर्स को पॉजिटिव नंबरों में मैप करता है।

संकलित (compiled) सेटिंग में, एकल प्रोवर क्रमिक रूप से कार्य करता है, इसलिए कम्यूटेटिविटी (commutativity) की बाधा समाप्त हो जाती है। लेखक इसे इस प्रकार हल करते हैं:

"सुंदर" (Nice) SOS प्रमाणों का निर्माण: स्लोफ्रा के कार्यों पर आधारित, वे दिखाते हैं कि प्रत्येक XOR गेम बायस बहुपद (bias polynomial) के लिए एक "सुंदर" SOS प्रमाण स्वीकार करता है। इन प्रमाणों में, अपघटन के पद डिग्री 1 के होते हैं और अधिकतम एक एलिस ऑब्जर्वेबल ( $A_x$ ) पर निर्भर करते हैं।
क्रिप्टोग्राफिक स्यूडो-एक्सपेक्टेशन को परिभाषित करना: वे एक डिग्री-2 स्यूडो-एक्सपेक्टेशन ऑपरेटर $\tilde{E}_S$ को परिभाषित करते हैं जो एक संकलित रणनीति द्वारा प्रेरित होता है। QHE स्कीम की सुरक्षा के कारण, यह ऑपरेटर आवश्यक पॉजिटिविटी गुणों को (नेग्लिजिबल एरर तक) संतुष्ट करता है, बशर्ते कि SOS प्रमाण में विशिष्ट "सुंदर" संरचना ( $A_x$ पर रैखिक निर्भरता) हो।
मान को सीमित करना: इस "सुंदर" SOS प्रमाण पर इस स्यूडो-एक्सपेक्टेशन को लागू करके, वे प्रदर्शित करते हैं कि किसी भी संकलित रणनीति की जीतने की प्रायिकता मूल गेम के इष्टतम क्वांटम बायस द्वारा (एक नेग्लिजिबल टर्म तक) सीमित होती है।

2. ट्सिरेलसन का पत्राचार (Tsirelson's Correspondence) और वेक्टर रणनीतियाँ

यह शोध पत्र ट्सिरेलसन के पत्राचार का उपयोग करते हुए एक वैकल्पिक प्रमाण की रूपरेखा भी प्रस्तुत करता है, जो वेक्टर रणनीतियों को क्वांटम रणनीतियों से जोड़ता है।

वे संकलित सेटिंग में बॉब ऑपरेटर्स पर जेन्सेन के असमानता (Jensen's inequality) को लागू करते हैं।
यह उन्हें संकलित XOR गेम के लिए किसी भी क्वांटम रणनीति के बायस को मूल नॉनलोकल XOR गेम की किसी वेक्टर रणनीति द्वारा प्राप्त बायस द्वारा सीमित करने की अनुमति देता है।
चूंकि ट्सिरलसन का प्रमेय स्थापित करता है कि इष्टतम वेक्टर बायस, इष्टतम क्वांटम बायस के बराबर होता है, यह संकलित मान पर एक ऊपरी सीमा प्रदान करता है।

मुख्य योगदान और परिणाम

1. मुख्य प्रमेय: XOR गेम्स के लिए साउंडनेस (Soundness)

प्राथमिक परिणाम (थ्योरम 1.1 और थ्योरम 3.1) यह स्थापित करता है कि किसी भी दो-प्लेयर XOR गेम $G$ के लिए, संकलित गेम $G_{comp}$ का क्वांटम मान एक नेग्लिजिबल एरर तक संरक्षित रहता है। विशेष रूप से, कोई भी पॉलीनोमियल-टाइम प्रोवर $G_{comp}$ को $\omega^*_q(G) + \text{negl}(\lambda)$ की प्रायिकता के साथ जीतता है, जहाँ $\omega^*_q(G)$ मूल गेम का इष्टतम क्वांटम मान है। यह नटाराजन और झांग द्वारा उठाए गए प्रश्न को हल करता है।

2. सभी XOR गेम्स के लिए सेल्फ-टेस्टिंग (Self-Testing)

SOS फ्रेमवर्क और स्लोफ्रा के परिणामों का उपयोग करते हुए, लेखक किसी भी संकलित XOR गेम के लिए एक सेल्फ-टेस्टिंग कथन व्युत्पन्न करते हैं (थ्योरम 4.3)।

परिणाम: संकलित XOR गेम में किसी भी निकट-इष्टतम (near-optimal) रणनीति के लिए, "बॉब" पार्टी के मेजरमेंट ऑपरेटर्स को अनुमानतः विशिष्ट बीजगणितीय संबंधों ("सॉल्यूशन अलजेब्रा") को संतुष्ट करना चाहिए।
महत्व: यह CHSH गेम में पाए जाने वाले एंटी-कम्यूटेशन के सेल्फ-टेस्ट को सभी XOR गेम्स के लिए सामान्यीकृत करता है, जिससे संकलित सेटिंग में रिजिडिटी (rigidity) प्राप्त होती है।

3. पैरेलल रिपिटिशन थ्योरम (Parallel Repetition Theorem)

यह शोध पत्र संकलित गेम्स के लिए पहला पैरेलल रिपिटिशन थ्योरम स्थापित करता है (थ्योरम 5.5)।

परिणाम: संकलित पैरेलल-रिपीटेड XOR गेम का क्वांटम मान पुनरावृत्तियों (repetitions) की संख्या के साथ पूर्णतः घातांकीय (exponentially) रूप से घटता है, जो अंतर्निहित नॉनलोकल गेम के व्यवहार से मेल खाता है।
विधि: इसे संकलित XOR गेम्स के योग (modulo 2) से संकलित गेम्स के पैरेलल रिपिटिशन को जोड़कर और मुख्य साउंडनेस परिणाम को लागू करके प्राप्त किया जाता है।

4. मैजिक स्क्वायर गेम के लिए सेल्फ-टेस्टिंग

यद्यपि मैजिक स्क्वायर गेम एक XOR गेम नहीं है, लेखक अपनी तकनीकों का विस्तार करके यह दिखाने के लिए इसका उपयोग करते हैं कि इसका संकलन एक जोड़ी एंटी-कम्यूटिंग ऑपरेटर्स के लिए एक सेल्फ-टेस्ट है (थ्योरम 6.7)। यह दो-प्रोवर सेटिंग में ज्ञात सेल्फ-टेस्टिंग गुणों को दर्शाता है।

महत्व

शोध पत्र का दावा है कि इसके परिणाम एक "कम्प्यूटेशनल ट्सिरलसन का प्रमेय" प्रदान करते हैं, जो XOR गेम्स के मानों के SDP (सेमीडेफिनेट प्रोग्रामिंग) के माध्यम से सटीक लक्षण वर्णन को संकलित, सिंगल-प्रोवर सेटिंग तक विस्तारित करता है।

सैद्धांतिक सेतु: यह XOR गेम्स के सुस्थापित सिद्धांत (जहाँ ट्सिरलसन का प्रमेय लागू होता है) और संकलित नॉनलोकल गेम्स के उभरते क्षेत्र के बीच के अंतर को पाटता है।
कंप्यूटेशन में रिजिडिटी: यह क्वांटम रणनीतियों की "रिजिडिटी" को प्रदर्शित करता है—जहाँ निकट-इष्टतम प्रदर्शन विशिष्ट ऑपरेटर संरचनाओं को मजबूर करता है—भले ही स्थानिक पृथकता को क्रिप्टोग्राफिक मान्यताओं द्वारा प्रतिस्थापित किया गया हो।
प्रोटोकॉल के लिए आधार: यह पुष्टि करके कि कंपाइलर XOR गेम्स के व्यापक वर्ग के लिए क्वांटम मानों को सुरक्षित रखता है, यह कार्य क्वांटम गणनाओं के कुशल डेलीगेशन और अन्य क्रिप्टोग्राफिक प्रोटोकॉल के उपयोग का समर्थन करता है जहाँ नॉन-कम्युनिकेशन धारणा को कम्प्यूटेशनल हार्डनेस (विशेष रूप से, लर्निंग विद एरर्स समस्या की कठिनाई) द्वारा प्रतिस्थापित किया जाता है।

लेखक नोट करते हैं कि जबकि उनकी तकनीकें वर्तमान में XOR गेम्स की विशिष्ट संरचना (विशेष रूप से "सुंदर" SOS प्रमाणों का अस्तित्व) पर निर्भर करती हैं, यह निर्धारित करना कि क्या समान तकनीकें सामान्य नॉनलोकल गेम्स तक विस्तारित होती हैं, भविष्य के अनुसंधान के लिए एक खुला विषय है।