क्यूएमए: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 2: Line 2:
{{about|गणितीय सिद्धांत|समाक्षीय आरएफ कनेक्टर|क्यूएमए और क्यूएन कनेक्टर}}
{{about|गणितीय सिद्धांत|समाक्षीय आरएफ कनेक्टर|क्यूएमए और क्यूएन कनेक्टर}}


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


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


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


== परिभाषा ==
== परिलैंग्वेज ==


भाषा 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>, वहाँ क्वांटम अवस्था मौजूद है <math>|\psi\rangle</math> ऐसी संभावना है कि V इनपुट स्वीकार करता है <math>(|x\rangle, |\psi\rangle)</math> से बड़ा है {{mvar|c}}.
*<math>\forall x \in L</math>, वहाँ क्वांटम अवस्था उपस्थित है <math>|\psi\rangle</math> ऐसी संभावना है कि V इनपुट स्वीकार करता है <math>(|x\rangle, |\psi\rangle)</math> से बड़ा है {{mvar|c}}.
*<math>\forall x \notin L</math>, सभी क्वांटम अवस्थाओं के लिए <math>|\psi\rangle</math>, संभावना है कि V इनपुट स्वीकार करता है <math>(|x\rangle, |\psi\rangle)</math> मै रुक जाना {{mvar|s}}.
*<math>\forall x \notin L</math>, सभी क्वांटम अवस्थाओं के लिए <math>|\psi\rangle</math>, संभावना है कि V इनपुट स्वीकार करता है <math>(|x\rangle, |\psi\rangle)</math> मै रुक जाना {{mvar|s}}.
कहाँ <math>|\psi\rangle</math> सभी क्वांटम अवस्थाओं में अधिकतम सीमा होती है <math>p(|x|)</math> qubits.
कहाँ <math>|\psi\rangle</math> सभी क्वांटम अवस्थाओं में अधिकतम सीमा होती है <math>p(|x|)</math> qubits.
Line 30: Line 30:
सामान्य k-स्थानीय हैमिल्टनियन समस्या, k-स्थानीय हैमिल्टनियन दी गई है <math>H</math>, सबसे छोटा eigenvalue खोजने के लिए <math>\lambda</math> का <math>H</math>.<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>H</math>, सबसे छोटा eigenvalue खोजने के लिए <math>\lambda</math> का <math>H</math>.<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> इसे हैमिल्टनियन की जमीनी अवस्था ऊर्जा भी कहा जाता है।


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


स्थानीय हैमिल्टनियन समस्या अधिकतम संतुष्टि समस्या|MAX-SAT का क्वांटम एनालॉग है। k-स्थानीय हैमिल्टनियन समस्या k ≥ 2 के लिए QMA-पूर्ण है।<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-स्थानीय हैमिल्टनियन समस्या भी QMA-पूर्ण है।<ref>{{cite journal
स्थानीय हैमिल्टनियन समस्या अधिकतम संतुष्टि समस्या|MAX-SAT का क्वांटम एनालॉग है। k-स्थानीय हैमिल्टनियन समस्या k ≥ 2 के लिए QMA-पूर्ण है।<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-स्थानीय हैमिल्टनियन समस्या भी QMA-पूर्ण है।<ref>{{cite journal
Line 109: Line 109:
QMA निम्नलिखित संबंधों द्वारा अन्य ज्ञात जटिलता वर्गों से संबंधित है:
QMA निम्नलिखित संबंधों द्वारा अन्य ज्ञात जटिलता वर्गों से संबंधित है:
:<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>
पहला समावेशन एनपी (जटिलता) की परिभाषा से होता है। अगले दो निष्कर्ष इस तथ्य से निकलते हैं कि प्रत्येक मामले में सत्यापनकर्ता को अधिक शक्तिशाली बनाया जा रहा है। क्यूसीएमए क्यूएमए में समाहित है क्योंकि सत्यापनकर्ता प्रमाण प्राप्त होते ही प्रमाण को मापकर शास्त्रीय प्रमाण भेजने के लिए बाध्य कर सकता है। तथ्य यह है कि क्यूएमए [[पीपी (जटिलता)]] में निहित है, [[एलेक्सी किताएव]] और [[जॉन वॉटरस (कंप्यूटर वैज्ञानिक)]] द्वारा दिखाया गया था। पीपी को PSPACE में भी आसानी से दिखाया जाता है।
पहला समावेशन एनपी (जटिलता) की परिलैंग्वेज से होता है। अगले दो निष्कर्ष इस तथ्य से निकलते हैं कि प्रत्येक मामले में सत्यापनकर्ता को अधिक शक्तिशाली बनाया जा रहा है। क्यूसीएमए क्यूएमए में समाहित है क्योंकि सत्यापनकर्ता प्रमाण प्राप्त होते ही प्रमाण को मापकर शास्त्रीय प्रमाण भेजने के लिए बाध्य कर सकता है। तथ्य यह है कि क्यूएमए [[पीपी (जटिलता)]] में निहित है, [[एलेक्सी किताएव]] और [[जॉन वॉटरस (कंप्यूटर वैज्ञानिक)]] द्वारा दिखाया गया था। पीपी को PSPACE में भी आसानी से दिखाया जाता है।


यह अज्ञात है कि इनमें से कोई भी समावेशन बिना शर्त सख्त है, क्योंकि यह भी ज्ञात नहीं है कि क्या P पूरी तरह से PSPACE में समाहित है या P = PSPACE में। हालाँकि, QMA पर वर्तमान में सबसे अच्छी ज्ञात ऊपरी सीमाएँ हैं
यह अज्ञात है कि इनमें से कोई भी समावेशन बिना शर्त सख्त है, क्योंकि यह भी ज्ञात नहीं है कि क्या P पूरी तरह से PSPACE में समाहित है या P = PSPACE में। हालाँकि, QMA पर वर्तमान में सबसे अच्छी ज्ञात ऊपरी सीमाएँ हैं

Revision as of 19:34, 6 August 2023

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

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

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

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

परिलैंग्वेज

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

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

कहाँ सभी क्वांटम अवस्थाओं में अधिकतम सीमा होती है qubits.

जटिलता वर्ग के बराबर परिभाषित किया गया है . हालाँकि, स्थिरांक बहुत महत्वपूर्ण नहीं हैं क्योंकि वर्ग अपरिवर्तित रहता है c और s को ऐसे किसी भी स्थिरांक पर सेट किया जाता है c से बड़ा है s. इसके अलावा, किसी भी बहुपद के लिए और , अपने पास

.

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

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

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

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

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