क्यूएमए: Difference between revisions

Revision as of 16:54, 10 September 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)$ , इस प्रकार है:-

Q M A (\frac{2}{3}, \frac{1}{3}) = Q M A (\frac{1}{2} + \frac{1}{q (n)}, \frac{1}{2} - \frac{1}{q (n)}) = Q M A (1 - 2^{- r (n)}

[1]

[2]

[3]

@@ Line 8: / Line 8: @@
 क्यूएमए संबंधित समष्टिता वर्ग है, जिसमें काल्पनिक एजेंट आर्थर और मर्लिन अनुक्रम को प्रमाण प्रदान करते हैं: आर्थर यादृच्छिक स्ट्रिंग उत्पन्न करता है, मर्लिन क्वांटम [[प्रमाणपत्र (जटिलता)|प्रमाणपत्र (समष्टिता)]] के साथ उत्तर देता है और आर्थर इसे बीक्यूपी मशीन के रूप में सत्यापित करता है।
-== परिलैंग्वेज ==
+== डेफिनेशन ==
 लैंग्वेज 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>
@@ Line 18: / Line 18: @@
 :<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> प्रत्येक को क्वैबिट करता है।
 <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
 | first = Roberto
@@ Line 47: / Line 47: @@
 | arxiv = quant-ph/0504050
 | 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
 | volume = 287
@@ Line 58: / Line 58: @@
 | journal = [[Communications in Mathematical Physics]]
 | 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>
@@ Line 66: / Line 66: @@
 </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"
 |-
@@ Line 73: / Line 73: @@
 ! scope="col" | नोट्स
 |-
-| बाध्यता संतुष्टि समस्या
+| बाध्यता संतुष्टि प्रॉब्लम
 | हैमिल्टनियन
 |
@@ Line 98: / Line 98: @@
 |}
-'''अन्य क्यूएमए-पूर्ण समस्याएं'''
+'''अन्य क्यूएमए-पूर्ण प्रॉब्लम'''
 ज्ञात क्यूएमए-पूर्ण समस्याओं की सूची https://arxiv.org/abs/1212.6312 पर प्राप्त की जा सकती है।

Anonymous

Search

क्यूएमए: Difference between revisions

Namespaces

More

Page actions

Revision as of 16:54, 10 September 2023

Contents

डेफिनेशन