का नतीजा $MIP^\ast=RE$ क्वांटम एल्गोरिदम के बारे में
(लंबित-पीयर समीक्षा) का प्रमाण $MIP^\ast=RE$में इस पूर्व-प्रिंट एक महत्वपूर्ण सफलता के रूप में स्वागत किया गया है। इस परिणाम का महत्व हेनरी यूएन (लेखकों में से एक) ने इस ब्लॉग पोस्ट में संबोधित किया है । स्कॉट आरोनसन भी इस ब्लॉग पोस्ट में कुछ प्रमुख निहितार्थों को सूचीबद्ध करता है ।
एक गैर-स्थानीय खेल के लिए ($G$), गैर-सापेक्षतावादी टेनर उत्पाद रणनीतियों के लिए सफलता की संभावनाओं के वर्चस्व को परिभाषित करें $\omega^\ast(G)$, और एक relativistic कम्यूटिंग ऑपरेटर (QFT) रणनीति के लिए सफलता की संभावनाओं का वर्चस्व $\omega^{co}(G)$। चूंकि गैर-सापेक्षतावादी क्यूएम क्यूएफटी का एक विशेष मामला है, इसलिए यह स्पष्ट है कि एक इष्टतम कम्यूटिंग ऑपरेटर-आधारित रणनीति कम से कम एक इष्टतम टेंसर उत्पाद-आधारित रणनीति के रूप में अच्छी है,$\omega^\ast(G) \le \omega^{co}(G)$।
यूएन की पोस्ट के बारे में मेरी समझ यह है कि इसका एक परिणाम है $MIP^\ast=RE$ क्या वह गैर-स्थानीय खेल मौजूद है जिसके लिए $\omega^\ast(G) < \omega^{co}(G)$। विशेष रूप से, वह कहते हैं
एक खेल होना चाहिए $G$, तब, जिसके लिए क्वांटम मान कम्यूटिंग ऑपरेटर मूल्य से अलग है। लेकिन इसका मतलब है कि Tsirelson की समस्या का एक नकारात्मक जवाब है, और इसलिए कॉन्स का एम्बेडिंग अनुमान गलत है।
मैं इसका मतलब यह समझता हूं कि समस्याओं का एक वर्ग है जिसके लिए QFT (संचार ऑपरेटरों) से तकनीकों का उपयोग करने वाले एल्गोरिदम गैर-सापेक्ष क्यूएम (टेन्सर उत्पादों, क्वांटम सर्किट औपचारिकता) से तकनीकों का उपयोग करके एल्गोरिदम की तुलना में अधिक सफलता की संभावनाएं हैं।
मेरे प्रश्न का पहला भाग है, इस प्रमाण को मानते हुए :
- कर देता है $MIP^\ast=RE$ इसका मतलब यह है कि गैर-सापेक्ष क्यूएम औपचारिकता (पारंपरिक क्वांटम सर्किट) के बजाय क्यूएफटी (कम्यूटिंग ऑपरेटर) के गणितीय औपचारिकता को नियोजित करके अधिक कुशलता से हल किया जा सकता है?
जब तक मैं गलत नहीं समझ रहा हूँ, यह सीधे यूएन के बयानों से लगता है। यदि ऐसा है, तो क्या यह संभव है कि गैर-स्थानीय खेलों का एक सेट मौजूद हो$\omega^\ast(G) < 0.5$ तथा $\omega^{co}(G) > 0.5$? विशेष रूप से, मेरे प्रश्न का दूसरा भाग है:
- कर देता है $MIP^\ast=RE$ इसका मतलब है कि वहाँ (या हो सकता है) समस्याओं का एक सेट है जो कि कम्यूटिंग सर्किट का उपयोग करके हल नहीं किया जा सकता है, जो कम्यूटिंग सर्किट का उपयोग करके हल नहीं किया जा सकता है या क्या क्वांटम सर्किट मॉडल की सार्वभौमिकता से इसकी संभावना है?
EDIT: हेनरी यूएन ने इस जटिलता वर्ग या the को बेहतर ढंग से समझने के इच्छुक लोगों के लिए एक MIP * Wiki बनाया है$MIP^\ast = RE$ परिणाम।
जवाब
मुझे नहीं पता कि एमआईपी * = आरई परिणाम, और विशेष रूप से दावा है कि एक गैर-खेल मौजूद है $G$ कहां है $\omega^*(G) \neq \omega^{co}(G)$, क्वांटम कंप्यूटर के लिए कोई एल्गोरिथम निहितार्थ है। यहाँ कहने के लिए कुछ चीज़ें हैं।
MIP * = RE परिणाम इस बात के बारे में है कि गैर-संगणक खेलों का उपयोग करके क्या कम्प्यूटेशनल समस्याओं को सत्यापित किया जा सकता है , गैर-खेल द्वारा हल किया जा सकता है (मुझे यकीन नहीं है कि इसका क्या मतलब होगा, किसी भी तरह!)। सत्यापन और समाधान के बीच का अंतर निम्न में से है: एक गैर-खेल में, हम मानते हैं कि ऐलिस और बॉब जादुई रूप से समस्या का उत्तर जानते हैं (इसलिए हम मानते हैं कि वे किसी भी कम्प्यूटेशनल समस्या को तुरंत हल कर सकते हैं)। उनकी चुनौती इसे हल करना नहीं है, बल्कि साबित करना हैएक बहुपद-कालिक शास्त्रीय सत्यापनकर्ता के लिए वे उत्तर जानते हैं। किसी चीज़ का उत्तर जानने का मतलब यह नहीं है कि आप उत्तर के किसी और को समझाने में सक्षम हैं। क्या एलिस और बॉब टेंसर उत्पाद ढांचे से सहसंबंधों का उपयोग कर सकते हैं या कम्यूटिंग ऑपरेटर फ्रेमवर्क प्रभावित करते हैं जो वे सत्यापनकर्ता को साबित करने में सक्षम हैं। एमआईपी * = आरई दिखाता है कि, टेंसर उत्पाद सहसंबंधों के साथ, ऐलिस और बॉब यह साबित कर सकते हैं कि वे ट्यूरिंग मशीन को जानते हैं और अंततः रुक जाते हैं। यह कुछ ऐसा है जो अगर नहीं किया जा सकता है, तो ऐलिस और बॉब शेयरिंग ऑपरेटर सहसंबंध; इसलिए कम्यूटिंग ऑपरेटर मॉडल टेंसर उत्पाद मॉडल से भिन्न होता है।
दूसरी बात जिसका मैं उल्लेख करना चाहता था, अलग से, यह एक दिलचस्प सवाल है कि क्या कोई क्वांटम गणना के मॉडल को परिभाषित कर सकता है जो संचालक और अनंत आयामी प्रणालियों के बारे में बात करता है। ऐसा प्रतीत होता है कि क्लेव, एट अल ने इसके लिए एक मॉडल के साथ आने की कोशिश की है, कुछ वे सी * -सर्किट मॉडल कहते हैं:https://arxiv.org/pdf/1811.12575.pdf। आपको यह दिलचस्प लग सकता है।