क्यूएमए: Difference between revisions

From Vigyanwiki
No edit summary
m (14 revisions imported from alpha:क्यूएमए)
 
(6 intermediate revisions by 2 users not shown)
Line 2: Line 2:
{{about|गणितीय सिद्धांत|समाक्षीय आरएफ कनेक्टर|क्यूएमए और क्यूएन कनेक्टर}}
{{about|गणितीय सिद्धांत|समाक्षीय आरएफ कनेक्टर|क्यूएमए और क्यूएन कनेक्टर}}


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


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


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


== परिलैंग्वेज ==
== डेफिनेशन ==


लैंग्वेज 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>
लैंग्वेज 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}</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>


== क्यूएमए में समस्याएं ==
== क्यूएमए में प्रॉब्लम ==


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


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


=== स्थानीय हैमिल्टनियन समस्या ===
=== स्थानीय हैमिल्टनियन प्रॉब्लम ===
k-स्थानीय [[हैमिल्टनियन (क्वांटम यांत्रिकी)]] <math>H</math> [[हर्मिटियन मैट्रिक्स]] है, जो n क्वैबिट पर कार्य करता है जिसे इसके योग के रूप में प्रदर्शित किया जा सकता है, <math>m</math> हैमिल्टनियन नियम अधिकतम पर कार्य करती हैं I <math>k</math> प्रत्येक को क्वैबिट करता है।
k-स्थानीय [[हैमिल्टनियन (क्वांटम यांत्रिकी)]] <math>H</math> [[हर्मिटियन मैट्रिक्स]] है, जो n क्वैबिट पर कार्य करता है जिसे योग के रूप में प्रदर्शित किया जा सकता है, <math>m</math> हैमिल्टनियन नियम अधिकतम पर कार्य करती हैं I <math>k</math> प्रत्येक को क्वैबिट करता है।


<math>H = \sum_{i=1}^m H_i</math>
<math>H = \sum_{i=1}^m H_i</math>


सामान्य k-स्थानीय हैमिल्टनियन समस्या, k-स्थानीय हैमिल्टनियन दी गई है I <math>H</math>, सबसे छोटा ईजीएनमूल्य परिक्षण के लिए <math>\lambda</math> का <math>H</math> है I<ref>{{cite web |last1=O'Donnel |first1=Ryan |title=Lecture 24: QMA: Quantum Merlin Arthur |url=https://www.cs.cmu.edu/~odonnell/quantum15/lecture24.pdf |access-date=18 April 2021}}</ref> <math>\lambda</math> इसे हैमिल्टनियन की आधार अवस्था ऊर्जा भी कहा जाता है।
सामान्य k-स्थानीय हैमिल्टनियन प्रॉब्लम, k-स्थानीय हैमिल्टनियन दी गई है I <math>H</math>, सबसे छोटा ईजीएनमूल्य परिक्षण के लिए <math>\lambda</math> का <math>H</math> है I<ref>{{cite web |last1=O'Donnel |first1=Ryan |title=Lecture 24: QMA: Quantum Merlin Arthur |url=https://www.cs.cmu.edu/~odonnell/quantum15/lecture24.pdf |access-date=18 April 2021}}</ref> <math>\lambda</math> इसे हैमिल्टनियन की आधार अवस्था ऊर्जा भी कहा जाता है।


k-स्थानीय हैमिल्टनियन समस्या का निर्णय संस्करण प्रकार की [[वादा समस्या|प्रॉमिस समस्या]] है, और इसे k-स्थानीय हैमिल्टनियन के रूप में परिभाषित किया गया है, और <math>\alpha, \beta</math> जहाँ <math>\alpha > \beta</math>, यह तय करने के लिए कि क्या कोई क्वांटम ईजेनस्टेट उपस्थित है I <math>|\psi\rangle</math> का <math>H</math> संबद्ध ईजीएनमूल्य के साथ <math>\lambda</math>, ऐसा है कि <math>\lambda \leq \beta</math> या यदि<math>\lambda \geq \alpha</math> है I
k-स्थानीय हैमिल्टनियन प्रॉब्लम का निर्णय संस्करण प्रकार की [[वादा समस्या|प्रॉमिस प्रॉब्लम]] है, और इसे k-स्थानीय हैमिल्टनियन के रूप में परिभाषित किया गया है, और <math>\alpha, \beta</math> जहाँ <math>\alpha > \beta</math>, यह निर्धारित करने के लिए कि क्या कोई क्वांटम ईजेनस्टेट उपस्थित है I <math>|\psi\rangle</math> का <math>H</math> संबद्ध ईजीएनमूल्य के साथ <math>\lambda</math>, ऐसा है कि <math>\lambda \leq \beta</math> या यदि<math>\lambda \geq \alpha</math> है I


स्थानीय हैमिल्टनियन समस्या अधिकतम संतुष्टि समस्या MAX-SAT का क्वांटम एनालॉग है। k-स्थानीय हैमिल्टनियन समस्या k ≥ 2 के लिए क्यूएमए-पूर्ण है।<ref>{{Cite journal | last1=Kempe | first1=Julia | author1-link = Julia Kempe | last2=Kitaev | first2=Alexei |author2-link= Alexei Kitaev | last3=Regev | first3=Oded | author3-link= Oded Regev (computer scientist) | title=स्थानीय हैमिल्टनियन समस्या की जटिलता| year=2006 | journal=[[SIAM Journal on Computing]] | volume=35 | issue=5 | pages=1070–1097 | arxiv=quant-ph/0406180v2  | doi=10.1137/S0097539704445226}}.</ref>  
स्थानीय हैमिल्टनियन प्रॉब्लम अधिकतम संतुष्टि प्रॉब्लम MAX-SAT का क्वांटम एनालॉग है। k-स्थानीय हैमिल्टनियन प्रॉब्लम k ≥ 2 के लिए क्यूएमए-पूर्ण है।<ref>{{Cite journal | last1=Kempe | first1=Julia | author1-link = Julia Kempe | last2=Kitaev | first2=Alexei |author2-link= Alexei Kitaev | last3=Regev | first3=Oded | author3-link= Oded Regev (computer scientist) | title=स्थानीय हैमिल्टनियन समस्या की जटिलता| year=2006 | journal=[[SIAM Journal on Computing]] | volume=35 | issue=5 | pages=1070–1097 | arxiv=quant-ph/0406180v2  | doi=10.1137/S0097539704445226}}.</ref>  


क्वैबिट के द्वि-आयामी ग्रिड पर कार्य करने के लिए प्रतिबंधित 2-स्थानीय हैमिल्टनियन समस्या भी क्यूएमए-पूर्ण है।<ref>{{cite journal
क्वैबिट के द्वि-आयामी ग्रिड पर कार्य करने के लिए प्रतिबंधित 2-स्थानीय हैमिल्टनियन प्रॉब्लम भी क्यूएमए-पूर्ण है।<ref>{{cite journal
| last = Oliveira
| last = Oliveira
| first = Roberto
| first = Roberto
Line 47: Line 47:
| arxiv = quant-ph/0504050
| arxiv = quant-ph/0504050
| bibcode = 2005quant.ph..4050O
| bibcode = 2005quant.ph..4050O
}}</ref> यह प्रदर्शित किया गया है कि k-स्थानीय हैमिल्टनियन समस्या अभी भी क्यूएमए-हार्ड है, यहां तक ​​​​कि हैमिल्टनियनों के लिए भी जो प्रति कण 12 स्टेट के साथ निकटतम-पड़ोसी इंटरैक्शन के साथ कणों की 1-आयामी रेखा का प्रतिनिधित्व करते हैं।<ref>{{Cite journal
}}</ref> यह प्रदर्शित किया गया है कि k-स्थानीय हैमिल्टनियन प्रॉब्लम अभी भी क्यूएमए-हार्ड है, यहां तक ​​​​कि हैमिल्टनियनों के लिए भी जो प्रति कण 12 स्टेट के साथ निकटतम इंटरैक्शन के साथ कणों की 1-आयामी रेखा का प्रतिनिधित्व करते हैं।<ref>{{Cite journal
| doi = 10.1007/s00220-008-0710-3
| doi = 10.1007/s00220-008-0710-3
| volume = 287
| volume = 287
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>-पूर्ण बन जाती है (चूंकि समस्या इनपुट सिस्टम आकार में एन्कोड किया गया है, सत्यापनकर्ता के पास अब समान प्रॉमिस के अंतर को बनाए रखते हुए घातीय रनटाइम है)।<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>
| 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 64: Line 64:
<math>
<math>
H_{ZX} = \sum_{i}h_i Z_i + \sum_{i} \Delta_i X_i + \sum_{i<j}J^{ij}Z_iZ_j + \sum_{i<j}K^{ij}X_iX_j
H_{ZX} = \sum_{i}h_i Z_i + \sum_{i} \Delta_i X_i + \sum_{i<j}J^{ij}Z_iZ_j + \sum_{i<j}K^{ij}X_iX_j
</math> जहाँ <math>Z, X</math> [[पॉल के मैट्रिक्स]] <math>\sigma_z, \sigma_x</math>का प्रतिनिधित्व करते है, ऐसे मॉडल सार्वभौमिक [[रुद्धोष्म क्वांटम गणना|एडियाबेटिक क्वांटम गणना]] पर प्रस्तावित होते हैं।
</math> जहाँ <math>Z, X</math> [[पॉल के मैट्रिक्स|पॉल के आव्यूह]] <math>\sigma_z, \sigma_x</math>का प्रतिनिधित्व करते है, ऐसे मॉडल सार्वभौमिक [[रुद्धोष्म क्वांटम गणना|एडियाबेटिक क्वांटम गणना]] पर प्रस्तावित होते हैं।


k-स्थानीय हैमिल्टनियन समस्याएं प्रतिष्ठित बाधा संतुष्टि समस्याओं के अनुरूप हैं।<ref>{{cite web |last1=Yuen |first1=Henry |title=उलझाव की जटिलता|url=http://henryyuen.net/fall2020/complexity_of_entanglement_notes.pdf |website=henryyuen.net |access-date=20 April 2021}}</ref> निम्नलिखित तालिका प्रतिष्ठित सीएसपी और हैमिल्टनियन के मध्य अनुरूप गैजेट को प्रदर्शित करती है।
k-स्थानीय हैमिल्टनियन प्रॉब्लम प्रतिष्ठित बाधा संतुष्टि समस्याओं के अनुरूप हैं।<ref>{{cite web |last1=Yuen |first1=Henry |title=उलझाव की जटिलता|url=http://henryyuen.net/fall2020/complexity_of_entanglement_notes.pdf |website=henryyuen.net |access-date=20 April 2021}}</ref> निम्नलिखित तालिका प्रतिष्ठित सीएसपी और हैमिल्टनियन के मध्य अनुरूप गैजेट को प्रदर्शित करती है।
{| class="wikitable"
{| class="wikitable"
|-
|-
Line 73: Line 73:
! scope="col" | नोट्स
! scope="col" | नोट्स
|-
|-
| बाधा संतुष्टि समस्या
| बाध्यता संतुष्टि प्रॉब्लम
| हैमिल्टनियन
| हैमिल्टनियन
|  
|  
Line 81: Line 81:
|  
|  
|-
|-
| बाधा
| बाध्यता
| हैमिल्टनियन शब्द
| हैमिल्टनियन शब्द
|  
|  
Line 98: Line 98:
|}
|}


'''अन्य क्यूएमए-पूर्ण समस्याएं'''
'''अन्य क्यूएमए-पूर्ण प्रॉब्लम'''


ज्ञात क्यूएमए-पूर्ण समस्याओं की सूची https://arxiv.org/abs/1212.6312 पर प्राप्त की जा सकती है।
ज्ञात क्यूएमए-पूर्ण समस्याओं की सूची https://arxiv.org/abs/1212.6312 पर प्राप्त की जा सकती है।
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 को क्वैबिट की संख्या में बहुपद होने की अनुमति है। यह ज्ञात है कि 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>
</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>
प्रथम समावेशन एनपी (समष्टिता) की परिलैंग्वेज से होता है। अगले दो निष्कर्ष इस तथ्य से निकलते हैं कि प्रत्येक विषय में सत्यापनकर्ता को अधिक शक्तिशाली बनाया जा रहा है। क्यूसीएमए, क्यूएमए में समाहित है क्योंकि सत्यापनकर्ता प्रमाण प्राप्त होते ही प्रमाण को मापकर प्रतिष्ठित प्रमाण प्रेक्षित करने के लिए बाध्य कर सकता है। तथ्य यह है कि क्यूएमए [[पीपी (जटिलता)|पीपी (समष्टिता)]] में निहित है, [[एलेक्सी किताएव]] और [[जॉन वॉटरस (कंप्यूटर वैज्ञानिक)]] द्वारा प्रदर्शित किया गया था। पीपी को पीस्पेस में भी सरलता से प्रदर्शित किया जाता है।
प्रथम इन्क्लूसन एनपी (कम्प्लेक्सिटी) की लैंग्वेज से होता है। दो इन्क्लूसन इस तथ्य से निकलते हैं कि प्रत्येक विषय में वेरिफायर को अधिक पावरफुल बनाया जा रहा है। क्यूसीएमए, क्यूएमए में कॉन्टैनेड है क्योंकि वेरिफायर प्रूफ प्राप्त होते ही प्रूफ को मापकर प्रतिष्ठित प्रूफ प्रेक्षित करने के लिए बाध्य कर सकता है। तथ्य यह है कि क्यूएमए [[पीपी (जटिलता)|पीपी (कम्प्लेक्सिटी)]] में कॉन्टैनेड है, [[एलेक्सी किताएव]] और [[जॉन वॉटरस (कंप्यूटर वैज्ञानिक)|जॉन वॉटरस (कंप्यूटर साइंटिस्ट)]] द्वारा प्रदर्शित किया गया था। पीपी को पीस्पेस में भी सरलता से प्रदर्शित किया जाता है।


यह अज्ञात है कि इनमें से कोई भी समावेशन बिना नियम सख्त है, क्योंकि यह भी ज्ञात नहीं है कि क्या पी पूर्ण रूप से पीस्पेस में समाहित है या पी = पीस्पेस में है। चूँकि, क्यूएमए पर वर्तमान में सबसे उचित ज्ञात ऊपरी सीमाएँ हैं:<ref>{{cite journal
यह अज्ञात है कि इनमें से कोई भी इन्क्लूसन बिना नियम दृढ़ है, क्योंकि यह भी ज्ञात नहीं है कि क्या 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{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> या इसके विपरीत है।
दोनों जहाँ <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> या इसके विपरीत है।


==संदर्भ==
==संदर्भ==
Line 154: Line 154:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]
[[Category:Created On 25/07/2023]]
[[Category:Vigyan Ready]]

Latest revision as of 22:21, 2 February 2024

This article is about गणितीय सिद्धांत. For समाक्षीय आरएफ कनेक्टर, see क्यूएमए और क्यूएन कनेक्टर.

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

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

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

डेफिनेशन

लैंग्वेज L में है, यदि पॉलीनोमिअल टाइम क्वांटम वेरिफायर V और पॉलीनोमिअल उपस्थित है, तो ऐसा है कि:[1][2][3]

  • , जहाँ क्वांटम अवस्था उपस्थित है I ऐसी संभावना है कि V इनपुट स्वीकार करता है, c से बड़ा है I
  • , सभी क्वांटम अवस्थाओं के लिए