क्यूएमए: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 2: | Line 2: | ||
{{about|गणितीय सिद्धांत|समाक्षीय आरएफ कनेक्टर|क्यूएमए और क्यूएन कनेक्टर}} | {{about|गणितीय सिद्धांत|समाक्षीय आरएफ कनेक्टर|क्यूएमए और क्यूएन कनेक्टर}} | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल | [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कम्प्लेक्सिटी थ्योरी]] में, '''क्यूएमए''', जो क्वांटम आर्थर-मर्लिन प्रोटोकॉल के लिए स्थित है, लैंग्वेज का समूह होता है, जिसके लिए, जब स्ट्रिंग लैंग्वेज में होती है, तो पॉलीनोमिअल-साइज का क्वांटम प्रूफ (क्वांटम स्थिति) होता है जो पॉलीनोमिअल टाइम क्वांटम वेरिफायर[[ एक कंप्यूटर जितना | (क्वांटम कंप्यूटर]] पर चलने वाले) को हाई प्रोबेबिलिटी के साथ इस तथ्य के सम्बन्ध में कन्फर्म करता है। इसके अतिरिक्त, जब स्ट्रिंग लैंग्वेज में नहीं होती है, तो प्रत्येक पॉलीनोमिअल-साइज की क्वांटम स्थिति को वेरिफायर द्वारा हाई प्रोबेबिलिटी के साथ रिजेक्ट कर दिया जाता है। | ||
क्यूएमए और [[बीक्यूपी]] के मध्य संबंध [[जटिलता वर्ग| | क्यूएमए और [[बीक्यूपी]] के मध्य संबंध [[जटिलता वर्ग|कम्प्लेक्सिटी वर्गों]] [[एन[[पी (जटिलता)|पी (कम्प्लेक्सिटी)]]]] और P (कम्प्लेक्सिटी) के मध्य संबंध के अनुरूप होता है। यह संभाव्य कम्प्लेक्सिटी वर्ग आर्थर-मर्लिन प्रोटोकॉल और [[बीपीपी (जटिलता)|बीपीपी (कम्प्लेक्सिटी)]] के मध्य संबंध के अनुरूप भी होता है। | ||
क्यूएमए संबंधित | क्यूएमए संबंधित कम्प्लेक्सिटी वर्ग है, जिसमें काल्पनिक एजेंट आर्थर और मर्लिन अनुक्रम को प्रूफ प्रदान करते हैं: आर्थर यादृच्छिक स्ट्रिंग उत्पन्न करता है, मर्लिन क्वांटम [[प्रमाणपत्र (जटिलता)|प्रमाणपत्र (कम्प्लेक्सिटी)]] के साथ उत्तर देता है और आर्थर इसे बीक्यूपी मशीन के रूप में सत्यापित करता है। | ||
== डेफिनेशन == | == डेफिनेशन == | ||
लैंग्वेज L में है, <math>\mathsf{QMA}(c,s)</math> यदि | लैंग्वेज L में है, <math>\mathsf{QMA}(c,s)</math> यदि पॉलीनोमिअल टाइम क्वांटम वेरिफायर V और पॉलीनोमिअल उपस्थित है, तो {{tmath|p(x)}}ऐसा है कि:<ref>{{cite arXiv|eprint=quant-ph/0210077v1|first1=Dorit|last1=Aharonov|author1-link= Dorit Aharonov|first2=Tomer|last2=Naveh|title=Quantum NP – A Survey|year=2002}}</ref><ref name="JW">{{cite book|arxiv=0804.3401|first=John|last=Watrous|author-link=John Watrous (computer scientist)|chapter=Quantum Computational Complexity|year=2009|title=जटिलता और सिस्टम विज्ञान का विश्वकोश|pages=7174–7201|doi=10.1007/978-0-387-30440-3_428|editor-first=Robert A.|editor-last=Meyers}}</ref><ref>{{cite journal |last1=Gharibian |first1=Sevag |last2=Huang |first2=Yichen |last3=Landau |first3=Zeph |last4=Shin |first4=Seung Woo |title=क्वांटम हैमिल्टनियन जटिलता|journal=Foundations and Trends in Theoretical Computer Science |date=2015 |volume=10 |issue=3 |pages=159–282 |doi=10.1561/0400000066|arxiv=1401.3916 }}</ref> | ||
*<math>\forall x \in L</math>, जहाँ क्वांटम अवस्था उपस्थित है I <math>|\psi\rangle</math> ऐसी संभावना है कि V इनपुट स्वीकार करता है, <math>(|x\rangle, |\psi\rangle)</math> {{mvar|c}} से बड़ा है I | *<math>\forall x \in L</math>, जहाँ क्वांटम अवस्था उपस्थित है I <math>|\psi\rangle</math> ऐसी संभावना है कि V इनपुट स्वीकार करता है, <math>(|x\rangle, |\psi\rangle)</math> {{mvar|c}} से बड़ा है I | ||
*<math>\forall x \notin L</math>, सभी क्वांटम अवस्थाओं के लिए <math>|\psi\rangle</math>, संभावना है कि V इनपुट स्वीकार करता है <math>(|x\rangle, |\psi\rangle)</math> {{mvar|s}} से कम है I | *<math>\forall x \notin L</math>, सभी क्वांटम अवस्थाओं के लिए <math>|\psi\rangle</math>, संभावना है कि V इनपुट स्वीकार करता है <math>(|x\rangle, |\psi\rangle)</math> {{mvar|s}} से कम है I | ||
जहाँ <math>|\psi\rangle</math> सभी क्वांटम अवस्थाओं <math>p(|x|)</math> क्वैबिट्स पर निर्भर करता है I | जहाँ <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}\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> | :<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 में नहीं हैं। ऐसी कुछ प्रसिद्ध समस्याओं पर नीचे वर्णन किया गया है। | चूंकि क्यूएमए में कई वर्ग सम्मिलित हैं, जैसे P, BQP और NP, उन वर्गों की सभी प्रॉब्लम भी क्यूएमए में हैं। चूँकि, ऐसी समस्याएँ हैं जो क्यूएमए में हैं, किन्तु NP या BQP में नहीं हैं। ऐसी कुछ प्रसिद्ध समस्याओं पर नीचे वर्णन किया गया है। | ||
प्रॉब्लम को क्यूएमए-हार्ड कहा जाता है, जो [[ एनपी कठिन |एनपी हार्ड]] के समान है, यदि क्यूएमए में प्रत्येक प्रॉब्लम को इसमें [[कमी (जटिलता)|कम]] [[कमी (जटिलता)|( | प्रॉब्लम को क्यूएमए-हार्ड कहा जाता है, जो [[ एनपी कठिन |एनपी हार्ड]] के समान है, यदि क्यूएमए में प्रत्येक प्रॉब्लम को इसमें [[कमी (जटिलता)|कम]] [[कमी (जटिलता)|(कम्प्लेक्सिटी)]] किया जा सकता है। किसी प्रॉब्लम को क्यूएमए-[[पूर्ण (जटिलता)|पूर्ण (कम्प्लेक्सिटी)]] कहा जाता है यदि वह क्यूएमए हार्ड और क्यूएमए में है। | ||
=== स्थानीय हैमिल्टनियन प्रॉब्लम === | === स्थानीय हैमिल्टनियन प्रॉब्लम === | ||
| Line 58: | Line 58: | ||
| journal = [[Communications in Mathematical Physics]] | | journal = [[Communications in Mathematical Physics]] | ||
| year = 2009 | bibcode=2009CMaPh.287...41A | | year = 2009 | bibcode=2009CMaPh.287...41A | ||
| arxiv= 0705.4077}}</ref> यदि सिस्टम अनुवादात्मक रूप से-अपरिवर्तनीय है, तो इसकी स्थानीय हैमिल्टनियन प्रॉब्लम QMA<sub>EXP</sub>-पूर्ण बन जाती है (चूंकि प्रॉब्लम इनपुट सिस्टम आकार में एन्कोड किया गया है, | | arxiv= 0705.4077}}</ref> यदि सिस्टम अनुवादात्मक रूप से-अपरिवर्तनीय है, तो इसकी स्थानीय हैमिल्टनियन प्रॉब्लम QMA<sub>EXP</sub>-पूर्ण बन जाती है (चूंकि प्रॉब्लम इनपुट सिस्टम आकार में एन्कोड किया गया है, वेरिफायर के पास अब समान प्रॉमिस के अंतर को बनाए रखते हुए घातीय रनटाइम है)।<ref>{{cite journal |last1=Aharonov |first1=Dorit |last2=Gottesman |first2=Daniel |last3=Irani |first3=Sandy |last4=Kempe |first4=Julia |title=एक लाइन पर क्वांटम सिस्टम की शक्ति|journal=Communications in Mathematical Physics |date=1 April 2009 |volume=287 |issue=1 |pages=41–65 |doi=10.1007/s00220-008-0710-3}}</ref><ref>{{cite journal |last1=Bausch |first1=Johannes |last2=Cubitt |first2=Toby |last3=Ozols |first3=Maris |title=कम स्थानीय आयाम के साथ अनुवादात्मक रूप से अपरिवर्तनीय स्पिन श्रृंखलाओं की जटिलता|journal=Annales Henri Poincaré |date=November 2017 |volume=18 |issue=11 |pages=3449–3513 |doi=10.1007/s00023-017-0609-7|doi-access=free }}</ref> | ||
क्यूएमए-हार्ड परिणाम ZX हैमिल्टनियन जैसे क्वैबिट के सरल [[जाली मॉडल|लैटिस प्रारूप]] के लिए जाने जाते हैं I <ref>{{Cite journal | last1=Biamonte | first1=Jacob | last2=Love | first2=Peter | title=सार्वभौमिक रुद्धोष्म क्वांटम कंप्यूटरों के लिए साकार करने योग्य हैमिल्टनियन| journal=[[Physical Review A]] | year=2008 | volume=78 | issue=1 | pages=012352 | arxiv=0704.1287 | doi=10.1103/PhysRevA.78.012352 | bibcode=2008PhRvA..78a2352B}}.</ref> | क्यूएमए-हार्ड परिणाम ZX हैमिल्टनियन जैसे क्वैबिट के सरल [[जाली मॉडल|लैटिस प्रारूप]] के लिए जाने जाते हैं I <ref>{{Cite journal | last1=Biamonte | first1=Jacob | last2=Love | first2=Peter | title=सार्वभौमिक रुद्धोष्म क्वांटम कंप्यूटरों के लिए साकार करने योग्य हैमिल्टनियन| journal=[[Physical Review A]] | year=2008 | volume=78 | issue=1 | pages=012352 | arxiv=0704.1287 | doi=10.1103/PhysRevA.78.012352 | bibcode=2008PhRvA..78a2352B}}.</ref> | ||
| Line 104: | Line 104: | ||
== संबंधित वर्ग == | == संबंधित वर्ग == | ||
क्यूसीएमए (या एमक्यूए<ref name="JW" />), जो क्वांटम क्लासिकल मर्लिन आर्थर (या मर्लिन क्वांटम आर्थर) के लिए है, क्यूएमए के समान है, किन्तु | क्यूसीएमए (या एमक्यूए<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 संदेश) के लिए है, क्यूएमए का सामान्यीकरण है जहां मर्लिन और आर्थर 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> | </ref> | ||
== अन्य वर्गों से संबंध == | == अन्य वर्गों से संबंध == | ||
क्यूएमए निम्नलिखित संबंधों द्वारा अन्य ज्ञात | क्यूएमए निम्नलिखित संबंधों द्वारा अन्य ज्ञात कम्प्लेक्सिटी वर्गों से संबंधित है: | ||
:<math>\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}\subseteq \mathsf{PP} \subseteq \mathsf{PSPACE}</math> | :<math>\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}\subseteq \mathsf{PP} \subseteq \mathsf{PSPACE}</math> | ||
प्रथम | प्रथम इन्क्लूसन एनपी (कम्प्लेक्सिटी) की लैंग्वेज से होता है। दो इन्क्लूसन इस तथ्य से निकलते हैं कि प्रत्येक विषय में वेरिफायर को अधिक पावरफुल बनाया जा रहा है। क्यूसीएमए, क्यूएमए में कॉन्टैनेड है क्योंकि वेरिफायर प्रूफ प्राप्त होते ही प्रूफ को मापकर प्रतिष्ठित प्रूफ प्रेक्षित करने के लिए बाध्य कर सकता है। तथ्य यह है कि क्यूएमए [[पीपी (जटिलता)|पीपी (कम्प्लेक्सिटी)]] में कॉन्टैनेड है, [[एलेक्सी किताएव]] और [[जॉन वॉटरस (कंप्यूटर वैज्ञानिक)|जॉन वॉटरस (कंप्यूटर साइंटिस्ट)]] द्वारा प्रदर्शित किया गया था। पीपी को पीस्पेस में भी सरलता से प्रदर्शित किया जाता है। | ||
यह अज्ञात है कि इनमें से कोई भी | यह अज्ञात है कि इनमें से कोई भी इन्क्लूसन बिना नियम दृढ़ है, क्योंकि यह भी ज्ञात नहीं है कि क्या P पूर्ण रूप से पीस्पेस में कॉन्टैनेड है या P = PSPACE में है। चूँकि, क्यूएमए पर वर्तमान में सबसे उचित ज्ञात ऊपरी लिमिट हैं:<ref>{{cite journal | ||
| last = Vyalyi | | last = Vyalyi | ||
| first = Mikhail N. | | first = Mikhail N. | ||
| Line 135: | Line 135: | ||
}}</ref> | }}</ref> | ||
:<math>\mathsf{QMA}\subseteq\mathsf{A_0PP}</math> और <math>\mathsf{QMA}\subseteq\mathsf{P^{QMA[log]}}</math>, | :<math>\mathsf{QMA}\subseteq\mathsf{A_0PP}</math> और <math>\mathsf{QMA}\subseteq\mathsf{P^{QMA[log]}}</math>, | ||
दोनों जहाँ <math>\mathsf{A_0PP}</math> और <math>\mathsf{P^{QMA[log]}}</math> <math>\mathsf{PP}</math> में | दोनों जहाँ <math>\mathsf{A_0PP}</math> और <math>\mathsf{P^{QMA[log]}}</math> <math>\mathsf{PP}</math> में कॉन्टैनेड हैं। यह संभावना नहीं है कि <math>\mathsf{QMA}</math> <math>\mathsf{P^{QMA[log]}}</math> के समान होता है, जैसा कि इसका तात्पर्य <math>\mathsf{QMA}=\mathsf{co}</math>-<math>\mathsf{QMA}</math> होता है। यह अज्ञात है या नहीं <math>\mathsf{P^{QMA[log]}}\subseteq\mathsf{A_0PP}</math> या इसके विपरीत है। | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 17:23, 10 September 2023
कम्प्यूटेशनल कम्प्लेक्सिटी थ्योरी में, क्यूएमए, जो क्वांटम आर्थर-मर्लिन प्रोटोकॉल के लिए स्थित है, लैंग्वेज का समूह होता है, जिसके लिए, जब स्ट्रिंग लैंग्वेज में होती है, तो पॉलीनोमिअल-साइज का क्वांटम प्रूफ (क्वांटम स्थिति) होता है जो पॉलीनोमिअल टाइम क्वांटम वेरिफायर (क्वांटम कंप्यूटर पर चलने वाले) को हाई प्रोबेबिलिटी के साथ इस तथ्य के सम्बन्ध में कन्फर्म करता है। इसके अतिरिक्त, जब स्ट्रिंग लैंग्वेज में नहीं होती है, तो प्रत्येक पॉलीनोमिअल-साइज की क्वांटम स्थिति को वेरिफायर द्वारा हाई प्रोबेबिलिटी के साथ रिजेक्ट कर दिया जाता है।
क्यूएमए और बीक्यूपी के मध्य संबंध कम्प्लेक्सिटी वर्गों [[एनपी (कम्प्लेक्सिटी)]] और P (कम्प्लेक्सिटी) के मध्य संबंध के अनुरूप होता है। यह संभाव्य कम्प्लेक्सिटी वर्ग आर्थर-मर्लिन प्रोटोकॉल और बीपीपी (कम्प्लेक्सिटी) के मध्य संबंध के अनुरूप भी होता है।
क्यूएमए संबंधित कम्प्लेक्सिटी वर्ग है, जिसमें काल्पनिक एजेंट आर्थर और मर्लिन अनुक्रम को प्रूफ प्रदान करते हैं: आर्थर यादृच्छिक स्ट्रिंग उत्पन्न करता है, मर्लिन क्वांटम प्रमाणपत्र (कम्प्लेक्सिटी) के साथ उत्तर देता है और आर्थर इसे बीक्यूपी मशीन के रूप में सत्यापित करता है।
डेफिनेशन
लैंग्वेज L में है, यदि पॉलीनोमिअल टाइम क्वांटम वेरिफायर V और पॉलीनोमिअल उपस्थित है, तो ऐसा है कि:[1][2][3]
- , जहाँ क्वांटम अवस्था उपस्थित है I ऐसी संभावना है कि V इनपुट स्वीकार करता है, c से बड़ा है I
- , सभी क्वांटम अवस्थाओं के लिए , संभावना है कि V इनपुट स्वीकार करता है s से कम है I
जहाँ सभी क्वांटम अवस्थाओं क्वैबिट्स पर निर्भर करता है I
कम्प्लेक्सिटी वर्ग , के समान परिभाषित किया गया है I चूँकि, स्थिरांक अधिक महत्वपूर्ण नहीं हैं, क्योंकि वर्ग अपरिवर्तित रहता है, c और s को ऐसे किसी भी स्थिरांक पर सेट किया जाता है, c से s बड़ा है I इसके अतिरिक्त, किसी भी पॉलीनोमिअल के लिए और , इस प्रकार है:-