क्यूएमए: Difference between revisions

Revision as of 20:37, 6 August 2023

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

क्यूएमए और बीक्यूपी के मध्य संबंध समष्टिता वर्गों [[एनपी (समष्टिता)]] और P (समष्टिता) के मध्य संबंध के अनुरूप होता है। यह संभाव्य समष्टिता वर्ग आर्थर-मर्लिन प्रोटोकॉल और बीपीपी (समष्टिता) के मध्य संबंध के अनुरूप भी होता है।

क्यूएमए संबंधित समष्टिता वर्ग है, जिसमें काल्पनिक एजेंट आर्थर और मर्लिन अनुक्रम को प्रमाण प्रदान करते हैं: आर्थर यादृच्छिक स्ट्रिंग उत्पन्न करता है, मर्लिन क्वांटम प्रमाणपत्र (समष्टिता) के साथ उत्तर देता है और आर्थर इसे बीक्यूपी मशीन के रूप में सत्यापित करता है।

परिलैंग्वेज

लैंग्वेज L में है, ${\mathsf {QMA}}(c,s)$ यदि बहुपद समय क्वांटम सत्यापनकर्ता V और बहुपद उपस्थित है, तो $p(x)$ ऐसा है कि:^[1]^[2]^[3]

$\forall x\in L$ , जहाँ क्वांटम अवस्था उपस्थित है I $|\psi \rangle$ ऐसी संभावना है कि V इनपुट स्वीकार करता है, $(|x\rangle ,|\psi \rangle )$ $c$ से बड़ा है I
$\forall x\notin L$ , सभी क्वांटम अवस्थाओं के लिए $|\psi \rangle$ , संभावना है कि V इनपुट स्वीकार करता है $(|x\rangle ,|\psi \rangle )$ $s$ से कम है I

जहाँ $|\psi \rangle$ सभी क्वांटम अवस्थाओं अवस्थाओं $p(|x|)$ क्वैबिट्स पर निर्भर करता है I

समष्टिता वर्ग ${\mathsf {QMA}}$ , ${\mathsf {QMA}}({2}/{3},1/3)$ के बराबर परिभाषित किया गया है I चूँकि, स्थिरांक बहुत महत्वपूर्ण नहीं हैं क्योंकि वर्ग अपरिवर्तित रहता है, $c$ और $s$ को ऐसे किसी भी स्थिरांक पर सेट किया जाता है, $c$ से $s$ बड़ा है I इसके अतिरिक्त, किसी भी बहुपद के लिए $q(n)$ और $r(n)$ , इस प्रकार है:-

{\mathsf {QMA}}\left({\frac {2}{3}},{\frac {1}{3}}\right)={\mathsf {QMA}}\left({\frac {1}{2}}+{\frac {1}{q(n)}},{\frac {1}{2}}-{\frac {1}{q(n)}}\right)={\mathsf {QMA}}(1-2^{-r(n)},2^{-r(n)})

क्यूएमए में समस्याएं

चूंकि क्यूएमए में कई वर्ग सम्मिलित हैं, जैसे P, BQP और NP, उन वर्गों की सभी समस्याएं भी क्यूएमए में हैं। चूँकि, ऐसी समस्याएँ हैं जो क्यूएमए में हैं, किन्तु NP या BQP में नहीं हैं। ऐसी कुछ प्रसिद्ध समस्याओं पर नीचे चर्चा की गई है।

समस्या को क्यूएमए-हार्ड कहा जाता है, जो एनपी हार्ड के समान है, यदि क्यूएमए में प्रत्येक समस्या इसमें कमी (समष्टिता) हो सकती है। किसी समस्या को क्यूएमए-पूर्ण (समष्टिता) कहा जाता है यदि वह क्यूएमए हार्ड और क्यूएमए में है।

स्थानीय हैमिल्टनियन समस्या

k-स्थानीय हैमिल्टनियन (क्वांटम यांत्रिकी) $H$ हर्मिटियन मैट्रिक्स है, जो n क्वैबिट पर कार्य करता है जिसे इसके योग के रूप में प्रदर्शित किया जा सकता है

[1]

[2]

[3]

@@ Line 2: / Line 2: @@
 {{about|गणितीय सिद्धांत|समाक्षीय आरएफ कनेक्टर|क्यूएमए और क्यूएन कनेक्टर}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, क्यूएमए, जो क्वांटम आर्थर-मर्लिन प्रोटोकॉल के लिए स्थित है, लैंग्वेज का समूह होता है, जिसके लिए, जब स्ट्रिंग लैंग्वेज में होती है, तो बहुपद-आकार का क्वांटम प्रमाण (क्वांटम स्थिति) होता है जो बहुपद समय क्वांटम सत्यापनकर्ता[[ एक कंप्यूटर जितना | (क्वांटम कंप्यूटर]] पर चलने वाले) को उच्च संभावना के साथ इस तथ्य के सम्बन्ध में आश्वस्त करता है। इसके अतिरिक्त, जब स्ट्रिंग लैंग्वेज में नहीं होती है, तो प्रत्येक बहुपद-आकार की क्वांटम स्थिति को सत्यापनकर्ता द्वारा उच्च संभावना के साथ रद्द कर दिया जाता है।
+[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल समष्टिता सिद्धांत]] में, क्यूएमए, जो क्वांटम आर्थर-मर्लिन प्रोटोकॉल के लिए स्थित है, लैंग्वेज का समूह होता है, जिसके लिए, जब स्ट्रिंग लैंग्वेज में होती है, तो बहुपद-आकार का क्वांटम प्रमाण (क्वांटम स्थिति) होता है जो बहुपद समय क्वांटम सत्यापनकर्ता[[ एक कंप्यूटर जितना | (क्वांटम कंप्यूटर]] पर चलने वाले) को उच्च संभावना के साथ इस तथ्य के सम्बन्ध में आश्वस्त करता है। इसके अतिरिक्त, जब स्ट्रिंग लैंग्वेज में नहीं होती है, तो प्रत्येक बहुपद-आकार की क्वांटम स्थिति को सत्यापनकर्ता द्वारा उच्च संभावना के साथ रद्द कर दिया जाता है।
-क्यूएमए और [[बीक्यूपी]] के मध्य संबंध [[जटिलता वर्ग|जटिलता वर्गों]] [[एन[[पी (जटिलता)]]]] और P (जटिलता) के मध्य संबंध के अनुरूप होता है।{{cn|date=November 2022}} यह संभाव्य जटिलता वर्ग आर्थर-मर्लिन प्रोटोकॉल और [[बीपीपी (जटिलता)]] के मध्य संबंध के अनुरूप भी होता है।
+क्यूएमए और [[बीक्यूपी]] के मध्य संबंध [[जटिलता वर्ग|समष्टिता वर्गों]] [[एन[[पी (जटिलता)|पी (समष्टिता)]]]] और P (समष्टिता) के मध्य संबंध के अनुरूप होता है। यह संभाव्य समष्टिता वर्ग आर्थर-मर्लिन प्रोटोकॉल और [[बीपीपी (जटिलता)|बीपीपी (समष्टिता)]] के मध्य संबंध के अनुरूप भी होता है।
-क्यूएमए संबंधित जटिलता वर्ग है, जिसमें काल्पनिक एजेंट आर्थर और मर्लिन अनुक्रम को प्रमाण प्रदान करते हैं: आर्थर यादृच्छिक स्ट्रिंग उत्पन्न करता है, मर्लिन क्वांटम [[प्रमाणपत्र (जटिलता)]] के साथ उत्तर देता है और आर्थर इसे बीक्यूपी मशीन के रूप में सत्यापित करता है।
+क्यूएमए संबंधित समष्टिता वर्ग है, जिसमें काल्पनिक एजेंट आर्थर और मर्लिन अनुक्रम को प्रमाण प्रदान करते हैं: आर्थर यादृच्छिक स्ट्रिंग उत्पन्न करता है, मर्लिन क्वांटम [[प्रमाणपत्र (जटिलता)|प्रमाणपत्र (समष्टिता)]] के साथ उत्तर देता है और आर्थर इसे बीक्यूपी मशीन के रूप में सत्यापित करता है।
 == परिलैंग्वेज ==
@@ Line 15: / Line 15: @@
 जहाँ <math>|\psi\rangle</math> सभी क्वांटम अवस्थाओं अवस्थाओं <math>p(|x|)</math> क्वैबिट्स पर निर्भर करता है I
-जटिलता वर्ग <math>\mathsf{QMA}</math>, <math>\mathsf{QMA}({2}/{3},1/3)</math> के बराबर परिभाषित किया गया है I चूँकि, स्थिरांक बहुत महत्वपूर्ण नहीं हैं क्योंकि वर्ग अपरिवर्तित रहता है, {{mvar|c}} और {{mvar|s}} को ऐसे किसी भी स्थिरांक पर सेट किया जाता है, {{mvar|c}} से {{mvar|s}} बड़ा है I इसके अतिरिक्त, किसी भी बहुपद के लिए <math>q(n)</math> और <math>r(n)</math>, इस प्रकार है:-
+समष्टिता वर्ग <math>\mathsf{QMA}</math>, <math>\mathsf{QMA}({2}/{3},1/3)</math> के बराबर परिभाषित किया गया है I चूँकि, स्थिरांक बहुत महत्वपूर्ण नहीं हैं क्योंकि वर्ग अपरिवर्तित रहता है, {{mvar|c}} और {{mvar|s}} को ऐसे किसी भी स्थिरांक पर सेट किया जाता है, {{mvar|c}} से {{mvar|s}} बड़ा है I इसके अतिरिक्त, किसी भी बहुपद के लिए <math>q(n)</math> और <math>r(n)</math>, इस प्रकार है:-
 :<math>\mathsf{QMA}\left(\frac{2}{3},\frac{1}{3}\right) =\mathsf{QMA}\left(\frac{1}{2}+\frac{1}{q(n)},\frac{1}{2}-\frac{1}{q(n)}\right)=\mathsf{QMA}(1-2^{-r(n)},2^{-r(n)})</math>
@@ Line 22: / Line 22: @@
 चूंकि क्यूएमए में कई वर्ग सम्मिलित हैं, जैसे P, BQP और NP, उन वर्गों की सभी समस्याएं भी क्यूएमए में हैं। चूँकि, ऐसी समस्याएँ हैं जो क्यूएमए में हैं, किन्तु NP या BQP में नहीं हैं। ऐसी कुछ प्रसिद्ध समस्याओं पर नीचे चर्चा की गई है।
-समस्या को क्यूएमए-हार्ड कहा जाता है, जो [[ एनपी कठिन |एनपी हार्ड]] के समान है, यदि क्यूएमए में प्रत्येक समस्या इसमें [[कमी (जटिलता)]] हो सकती है। किसी समस्या को क्यूएमए-[[पूर्ण (जटिलता)]] कहा जाता है यदि वह क्यूएमए हार्ड और क्यूएमए में है।
+समस्या को क्यूएमए-हार्ड कहा जाता है, जो [[ एनपी कठिन |एनपी हार्ड]] के समान है, यदि क्यूएमए में प्रत्येक समस्या इसमें [[कमी (जटिलता)|कमी (समष्टिता)]] हो सकती है। किसी समस्या को क्यूएमए-[[पूर्ण (जटिलता)|पूर्ण (समष्टिता)]] कहा जाता है यदि वह क्यूएमए हार्ड और क्यूएमए में है।
 === स्थानीय हैमिल्टनियन समस्या ===
@@ Line 106: / Line 106: @@
 क्यूसीएमए (या एमक्यूए<ref name="JW" />), जो क्वांटम क्लासिकल मर्लिन आर्थर (या मर्लिन क्वांटम आर्थर) के लिए है, क्यूएमए के समान है, किन्तु प्रमाण प्रतिष्ठित स्ट्रिंग होना चाहिए। यह ज्ञात नहीं है कि क्यूएमए, क्यूसीएमए के बराबर है या नहीं, चूँकि क्यूसीएमए स्पष्ट रूप से क्यूएमए में निहित है।
-क्यूआईपी(k), जो [[क्वांटम इंटरैक्टिव बहुपद समय]] (k संदेश) के लिए है, क्यूएमए का सामान्यीकरण है जहां मर्लिन और आर्थर k राउंड के लिए चर्चा कर सकते हैं। क्यूएमए, क्यूआईपी(1) है। क्यूआईपी(2) को पीस्पेस में जाना जाता है।<ref>{{Cite book | last1=Jain | first1=Rahul | last2=Upadhyay | first2=Sarvagya | last3=Watrous | first3=John | author3-link=John Watrous (computer scientist) | title=[[Symposium on Foundations of Computer Science|Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS '09)]] | publisher=IEEE Computer Society | isbn=978-0-7695-3850-1 | year=2009 | chapter=Two-message quantum interactive proofs are in PSPACE | doi = 10.1109/FOCS.2009.30 | pages=534–543}}</ref> क्यूआईपी (जटिलता) क्यूआईपी(k) है, जहां k को क्वैबिट की संख्या में बहुपद होने की अनुमति है। यह ज्ञात है कि QIP(3) = QIP.<ref>{{Cite journal | last1=Watrous | first1=John | author1-link=John Watrous (computer scientist) | title=पीएसपीएसीई में निरंतर-गोल क्वांटम इंटरैक्टिव प्रूफ सिस्टम हैं| year=2003 | journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume=292 | issue=3 | pages=575–588 | doi=10.1016/S0304-3975(01)00375-9 | doi-access=free }}</ref> यह भी ज्ञात है कि QIP = IP (जटिलता) = [[PSPACE]]।<ref>{{cite journal | last1=Jain | first1=Rahul | last2=Ji | first2=Zhengfeng | last3=Upadhyay | first3=Sarvagya | last4=Watrous | first4=John | author4-link=John Watrous (computer scientist) | journal = [[Journal of the ACM]] | year=2011 | title=QIP = PSPACE | volume = 58 | issue = 6 | page = A30 | doi = 10.1145/2049697.2049704}}
+क्यूआईपी(k), जो [[क्वांटम इंटरैक्टिव बहुपद समय]] (k संदेश) के लिए है, क्यूएमए का सामान्यीकरण है जहां मर्लिन और आर्थर k राउंड के लिए चर्चा कर सकते हैं। क्यूएमए, क्यूआईपी(1) है। क्यूआईपी(2) को पीस्पेस में जाना जाता है।<ref>{{Cite book | last1=Jain | first1=Rahul | last2=Upadhyay | first2=Sarvagya | last3=Watrous | first3=John | author3-link=John Watrous (computer scientist) | title=[[Symposium on Foundations of Computer Science|Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS '09)]] | publisher=IEEE Computer Society | isbn=978-0-7695-3850-1 | year=2009 | chapter=Two-message quantum interactive proofs are in PSPACE | doi = 10.1109/FOCS.2009.30 | pages=534–543}}</ref> क्यूआईपी (समष्टिता) क्यूआईपी(k) है, जहां k को क्वैबिट की संख्या में बहुपद होने की अनुमति है। यह ज्ञात है कि QIP(3) = QIP.<ref>{{Cite journal | last1=Watrous | first1=John | author1-link=John Watrous (computer scientist) | title=पीएसपीएसीई में निरंतर-गोल क्वांटम इंटरैक्टिव प्रूफ सिस्टम हैं| year=2003 | journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume=292 | issue=3 | pages=575–588 | doi=10.1016/S0304-3975(01)00375-9 | doi-access=free }}</ref> यह भी ज्ञात है कि QIP = IP (समष्टिता) = [[PSPACE]]।<ref>{{cite journal | last1=Jain | first1=Rahul | last2=Ji | first2=Zhengfeng | last3=Upadhyay | first3=Sarvagya | last4=Watrous | first4=John | author4-link=John Watrous (computer scientist) | journal = [[Journal of the ACM]] | year=2011 | title=QIP = PSPACE | volume = 58 | issue = 6 | page = A30 | doi = 10.1145/2049697.2049704}}
 </ref>
 == अन्य वर्गों से संबंध ==
-क्यूएमए निम्नलिखित संबंधों द्वारा अन्य ज्ञात जटिलता वर्गों से संबंधित है:
+क्यूएमए निम्नलिखित संबंधों द्वारा अन्य ज्ञात समष्टिता वर्गों से संबंधित है:
 :<math>\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}\subseteq \mathsf{PP} \subseteq \mathsf{PSPACE}</math>
-प्रथम समावेशन एनपी (जटिलता) की परिलैंग्वेज से होता है। अगले दो निष्कर्ष इस तथ्य से निकलते हैं कि प्रत्येक विषय में सत्यापनकर्ता को अधिक शक्तिशाली बनाया जा रहा है। क्यूसीएमए, क्यूएमए में समाहित है क्योंकि सत्यापनकर्ता प्रमाण प्राप्त होते ही प्रमाण को मापकर प्रतिष्ठित प्रमाण प्रेक्षित करने के लिए बाध्य कर सकता है। तथ्य यह है कि क्यूएमए [[पीपी (जटिलता)]] में निहित है, [[एलेक्सी किताएव]] और [[जॉन वॉटरस (कंप्यूटर वैज्ञानिक)]] द्वारा प्रदर्शित किया गया था। पीपी को पीस्पेस में भी सरलता से प्रदर्शित किया जाता है।
+प्रथम समावेशन एनपी (समष्टिता) की परिलैंग्वेज से होता है। अगले दो निष्कर्ष इस तथ्य से निकलते हैं कि प्रत्येक विषय में सत्यापनकर्ता को अधिक शक्तिशाली बनाया जा रहा है। क्यूसीएमए, क्यूएमए में समाहित है क्योंकि सत्यापनकर्ता प्रमाण प्राप्त होते ही प्रमाण को मापकर प्रतिष्ठित प्रमाण प्रेक्षित करने के लिए बाध्य कर सकता है। तथ्य यह है कि क्यूएमए [[पीपी (जटिलता)|पीपी (समष्टिता)]] में निहित है, [[एलेक्सी किताएव]] और [[जॉन वॉटरस (कंप्यूटर वैज्ञानिक)]] द्वारा प्रदर्शित किया गया था। पीपी को पीस्पेस में भी सरलता से प्रदर्शित किया जाता है।
 यह अज्ञात है कि इनमें से कोई भी समावेशन बिना नियम सख्त है, क्योंकि यह भी ज्ञात नहीं है कि क्या पी पूर्ण रूप से पीस्पेस में समाहित है या पी = पीस्पेस में है। चूँकि, क्यूएमए पर वर्तमान में सबसे उचित ज्ञात ऊपरी सीमाएँ हैं:<ref>{{cite journal

Anonymous

Search

क्यूएमए: Difference between revisions

Namespaces

More

Page actions

Revision as of 20:37, 6 August 2023

Contents

परिलैंग्वेज

क्यूएमए में समस्याएं

स्थानीय हैमिल्टनियन समस्या