क्यूएमए: Difference between revisions

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

{\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 क्वैबिट पर कार्य करता है जिसे योग के रूप में प्रदर्शित किया जा सकता है, $m$ हैमिल्टनियन नियम अधिकतम पर कार्य करती हैं I $k$ प्रत्येक को क्वैबिट करता है।

$H=\sum _{i=1}^{m}H_{i}$

सामान्य k-स्थानीय हैमिल्टनियन प्रॉब्लम, k-स्थानीय हैमिल्टनियन दी गई है I $H$ , सबसे छोटा ईजीएनमूल्य परिक्षण के लिए $\lambda$ का $H$ है I^[4] $\lambda$ इसे हैमिल्टनियन की आधार अवस्था ऊर्जा भी कहा जाता है।

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

स्थानीय हैमिल्टनियन प्रॉब्लम अधिकतम संतुष्टि प्रॉब्लम MAX-SAT का क्वांटम एनालॉग है। k-स्थानीय हैमिल्टनियन प्रॉब्लम k ≥ 2 के लिए क्यूएमए-पूर्ण है।^[5]

क्वैबिट के द्वि-आयामी ग्रिड पर कार्य करने के लिए प्रतिबंधित 2-स्थानीय हैमिल्टनियन प्रॉब्लम भी क्यूएमए-पूर्ण है।^[6] यह प्रदर्शित किया गया है कि k-स्थानीय हैमिल्टनियन प्रॉब्लम अभी भी क्यूएमए-हार्ड है, यहां तक कि हैमिल्टनियनों के लिए भी जो प्रति कण 12 स्टेट के साथ निकटतम इंटरैक्शन के साथ कणों की 1-आयामी रेखा का प्रतिनिधित्व करते हैं।^[7] यदि सिस्टम अनुवादात्मक रूप से-अपरिवर्तनीय है, तो इसकी स्थानीय हैमिल्टनियन प्रॉब्लम QMA_EXP-पूर्ण बन जाती है (चूंकि प्रॉब्लम इनपुट सिस्टम आकार में एन्कोड किया गया है, वेरिफायर के पास अब समान प्रॉमिस के अंतर को बनाए रखते हुए घातीय रनटाइम है)।^[8]^[9]

क्यूएमए-हार्ड परिणाम ZX हैमिल्टनियन जैसे क्वैबिट के सरल लैटिस प्रारूप के लिए जाने जाते हैं I ^[10]

$H_{ZX}=\sum _{i}h_{i}Z_{i}+\sum _{i}\Delta _{i}X_{i}+\sum _{i<j}J^{ij}Z_{i}Z_{j}+\sum _{i<j}K^{ij}X_{i}X_{j}$ जहाँ $Z,X$ पॉल के आव्यूह $\sigma _{z},\sigma _{x}$ का प्रतिनिधित्व करते है, ऐसे मॉडल सार्वभौमिक एडियाबेटिक क्वांटम गणना पर प्रस्तावित होते हैं।

k-स्थानीय हैमिल्टनियन प्रॉब्लम प्रतिष्ठित बाधा संतुष्टि समस्याओं के अनुरूप हैं।^[11] निम्नलिखित तालिका प्रतिष्ठित सीएसपी और हैमिल्टनियन के मध्य अनुरूप गैजेट को प्रदर्शित करती है।

क्लासिकल	क्वांटम	नोट्स
बाध्यता संतुष्टि प्रॉब्लम	हैमिल्टनियन
चर	क्यूबिट
बाध्यता	हैमिल्टनियन शब्द
परिवर्तनीय असाइनमेंट	क्वांटम अवस्था
संतुष्ट बाधाओं की संख्या	हैमिल्टनियन का ऊर्जा शब्द
सर्वोतम उपाय	हैमिल्टनियन की भूमिगत स्थिति	सबसे संभावित बाधाओं को पूर्ण किया गया

अन्य क्यूएमए-पूर्ण प्रॉब्लम

ज्ञात क्यूएमए-पूर्ण समस्याओं की सूची https://arxiv.org/abs/1212.6312 पर प्राप्त की जा सकती है।

अन्य वर्गों से संबंध

क्यूएमए निम्नलिखित संबंधों द्वारा अन्य ज्ञात कम्प्लेक्सिटी वर्गों से संबंधित है:

{\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {MA}}\subseteq {\mathsf {QCMA}}\subseteq {\mathsf {QMA}}\subseteq {\mathsf {PP}}\subseteq {\mathsf {PSPACE}}

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

यह अज्ञात है कि इनमें से कोई भी इन्क्लूसन बिना नियम दृढ़ है, क्योंकि यह भी ज्ञात नहीं है कि क्या P पूर्ण रूप से पीस्पेस में कॉन्टैनेड है या P = PSPACE में है। चूँकि, क्यूएमए पर वर्तमान में सबसे उचित ज्ञात ऊपरी लिमिट हैं:^[15]^[16]

{\mathsf {QMA}}\subseteq {\mathsf {A_{0}PP}}

और

{\mathsf {QMA}}\subseteq {\mathsf {P^{QMA[log]}}}

,

दोनों जहाँ ${\mathsf {A_{0}PP}}$ और ${\mathsf {P^{QMA[log]}}}$ ${\mathsf {PP}}$ में कॉन्टैनेड हैं। यह संभावना नहीं है कि ${\mathsf {QMA}}$ ${\mathsf {P^{QMA[log]}}}$ के समान होता है, जैसा कि इसका तात्पर्य ${\mathsf {QMA}}={\mathsf {co}}$ - ${\mathsf {QMA}}$ होता है। यह अज्ञात है या नहीं ${\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}$ या इसके विपरीत है।

संदर्भ

↑ Aharonov, Dorit; Naveh, Tomer (2002). "Quantum NP – A Survey". arXiv:quant-ph/0210077v1.
↑ ^2.0 ^2.1 Watrous, John (2009). "Quantum Computational Complexity". In Meyers, Robert A. (ed.). जटिलता और सिस्टम विज्ञान का विश्वकोश. pp. 7174–7201. arXiv:0804.3401. doi:10.1007/978-0-387-30440-3_428.
↑ Gharibian, Sevag; Huang, Yichen; Landau, Zeph; Shin, Seung Woo (2015). "क्वांटम हैमिल्टनियन जटिलता". Foundations and Trends in Theoretical Computer Science. 10 (3): 159–282. arXiv:1401.3916. doi:10.1561/0400000066.
↑ O'Donnel, Ryan. "Lecture 24: QMA: Quantum Merlin Arthur" (PDF). Retrieved 18 April 2021.
↑ Kempe, Julia; Kitaev, Alexei; Regev, Oded (2006). "स्थानीय हैमिल्टनियन समस्या की जटिलता". SIAM Journal on Computing. 35 (5): 1070–1097. arXiv:quant-ph/0406180v2. doi:10.1137/S0097539704445226..
↑ Oliveira, Roberto; Terhal, Barbara M. (2008). "The complexity of quantum spin systems on a two-dimensional square lattice". Quantum Information and Computation. 8 (10): 900–924. arXiv:quant-ph/0504050. Bibcode:2005quant.ph..4050O.
↑ Aharonov, Dorit; Gottesman, Daniel; Irani, Sandy; Kempe, Julia (2009). "The power of quantum systems on a line". Communications in Mathematical Physics. 287 (1): 41–65. arXiv:0705.4077. Bibcode:2009CMaPh.287...41A. doi:10.1007/s00220-008-0710-3.
↑ Aharonov, Dorit; Gottesman, Daniel; Irani, Sandy; Kempe, Julia (1 April 2009). "एक लाइन पर क्वांटम सिस्टम की शक्ति". Communications in Mathematical Physics. 287 (1): 41–65. doi:10.1007/s00220-008-0710-3.
↑ Bausch, Johannes; Cubitt, Toby; Ozols, Maris (November 2017). "कम स्थानीय आयाम के साथ अनुवादात्मक रूप से अपरिवर्तनीय स्पिन श्रृंखलाओं की जटिलता". Annales Henri Poincaré. 18 (11): 3449–3513. doi:10.1007/s00023-017-0609-7.
↑ Biamonte, Jacob; Love, Peter (2008). "सार्वभौमिक रुद्धोष्म क्वांटम कंप्यूटरों के लिए साकार करने योग्य हैमिल्टनियन". Physical Review A. 78 (1): 012352. arXiv:0704.1287. Bibcode:2008PhRvA..78a2352B. doi:10.1103/PhysRevA.78.012352..
↑ Yuen, Henry. "उलझाव की जटिलता" (PDF). henryyuen.net. Retrieved 20 April 2021.
↑ Jain, Rahul; Upadhyay, Sarvagya; Watrous, John (2009). "Two-message quantum interactive proofs are in PSPACE". Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS '09). IEEE Computer Society. pp. 534–543. doi:10.1109/FOCS.2009.30. ISBN 978-0-7695-3850-1.
↑ Watrous, John (2003). "पीएसपीएसीई में निरंतर-गोल क्वांटम इंटरैक्टिव प्रूफ सिस्टम हैं". Theoretical Computer Science. 292 (3): 575–588. doi:10.1016/S0304-3975(01)00375-9.
↑ Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John (2011). "QIP = PSPACE". Journal of the ACM. 58 (6): A30. doi:10.1145/2049697.2049704.
↑ Vyalyi, Mikhail N. (2003). "QMA = PP implies that PP contains PH". Electronic Colloquium on Computational Complexity.
↑ Gharibian, Sevag; Yirka, Justin (2019). "The complexity of simulating local measurements on quantum systems". Quantum. 3: 189. doi:10.22331/q-2019-09-30-189.

बाहरी संबंध

Aaronson, Scott. "PHYS771 Lecture 13: How Big are Quantum States?".
Gharibian, Sevag. "Lecture 5: Quantum Merlin Arthur (QMA) and strong error reduction" (PDF).
Complexity Zoo: QMA

[1] Aharonov, Dorit; Naveh, Tomer (2002). "Quantum NP – A Survey". arXiv:quant-ph/0210077v1.

[JW-2] 2.0 ^2.1 Watrous, John (2009). "Quantum Computational Complexity". In Meyers, Robert A. (ed.). जटिलता और सिस्टम विज्ञान का विश्वकोश. pp. 7174–7201. arXiv:0804.3401. doi:10.1007/978-0-387-30440-3_428.

[3] Gharibian, Sevag; Huang, Yichen; Landau, Zeph; Shin, Seung Woo (2015). "क्वांटम हैमिल्टनियन जटिलता". Foundations and Trends in Theoretical Computer Science. 10 (3): 159–282. arXiv:1401.3916. doi:10.1561/0400000066.

[4] O'Donnel, Ryan. "Lecture 24: QMA: Quantum Merlin Arthur" (PDF). Retrieved 18 April 2021.

[5] Kempe, Julia; Kitaev, Alexei; Regev, Oded (2006). "स्थानीय हैमिल्टनियन समस्या की जटिलता". SIAM Journal on Computing. 35 (5): 1070–1097. arXiv:quant-ph/0406180v2. doi:10.1137/S0097539704445226..

[6] Oliveira, Roberto; Terhal, Barbara M. (2008). "The complexity of quantum spin systems on a two-dimensional square lattice". Quantum Information and Computation. 8 (10): 900–924. arXiv:quant-ph/0504050. Bibcode:2005quant.ph..4050O.

[7] Aharonov, Dorit; Gottesman, Daniel; Irani, Sandy; Kempe, Julia (2009). "The power of quantum systems on a line". Communications in Mathematical Physics. 287 (1): 41–65. arXiv:0705.4077. Bibcode:2009CMaPh.287...41A. doi:10.1007/s00220-008-0710-3.

[8] Aharonov, Dorit; Gottesman, Daniel; Irani, Sandy; Kempe, Julia (1 April 2009). "एक लाइन पर क्वांटम सिस्टम की शक्ति". Communications in Mathematical Physics. 287 (1): 41–65. doi:10.1007/s00220-008-0710-3.

[9] Bausch, Johannes; Cubitt, Toby; Ozols, Maris (November 2017). "कम स्थानीय आयाम के साथ अनुवादात्मक रूप से अपरिवर्तनीय स्पिन श्रृंखलाओं की जटिलता". Annales Henri Poincaré. 18 (11): 3449–3513. doi:10.1007/s00023-017-0609-7.

[10] Biamonte, Jacob; Love, Peter (2008). "सार्वभौमिक रुद्धोष्म क्वांटम कंप्यूटरों के लिए साकार करने योग्य हैमिल्टनियन". Physical Review A. 78 (1): 012352. arXiv:0704.1287. Bibcode:2008PhRvA..78a2352B. doi:10.1103/PhysRevA.78.012352..

[11] Yuen, Henry. "उलझाव की जटिलता" (PDF). henryyuen.net. Retrieved 20 April 2021.

[12] Jain, Rahul; Upadhyay, Sarvagya; Watrous, John (2009). "Two-message quantum interactive proofs are in PSPACE". Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS '09). IEEE Computer Society. pp. 534–543. doi:10.1109/FOCS.2009.30. ISBN 978-0-7695-3850-1.

[13] Watrous, John (2003). "पीएसपीएसीई में निरंतर-गोल क्वांटम इंटरैक्टिव प्रूफ सिस्टम हैं". Theoretical Computer Science. 292 (3): 575–588. doi:10.1016/S0304-3975(01)00375-9.

[14] Jain, Rahul; Ji, Zhengfeng; Upadhyay, Sarvagya; Watrous, John (2011). "QIP = PSPACE". Journal of the ACM. 58 (6): A30. doi:10.1145/2049697.2049704.

[15] Vyalyi, Mikhail N. (2003). "QMA = PP implies that PP contains PH". Electronic Colloquium on Computational Complexity.

[16] Gharibian, Sevag; Yirka, Justin (2019). "The complexity of simulating local measurements on quantum systems". Quantum. 3: 189. doi:10.22331/q-2019-09-30-189.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

@@ Line 2: / Line 2: @@
 {{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 \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>\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 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 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>
 == अन्य वर्गों से संबंध ==
-क्यूएमए निम्नलिखित संबंधों द्वारा अन्य ज्ञात समष्टिता वर्गों से संबंधित है:
+क्यूएमए निम्नलिखित संबंधों द्वारा अन्य ज्ञात कम्प्लेक्सिटी वर्गों से संबंधित है:
 :<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
+यह अज्ञात है कि इनमें से कोई भी इन्क्लूसन बिना नियम दृढ़ है, क्योंकि यह भी ज्ञात नहीं है कि क्या P पूर्ण रूप से पीस्पेस में कॉन्टैनेड है या P = PSPACE में है। चूँकि, क्यूएमए पर वर्तमान में सबसे उचित ज्ञात ऊपरी लिमिट हैं:<ref>{{cite journal
 | last = Vyalyi
 | first = Mikhail N.
@@ Line 135: / Line 135: @@
 }}</ref>
 :<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> या इसके विपरीत है।
 ==संदर्भ==

v t e Important complexity classes (more)
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

Anonymous

Search

क्यूएमए: Difference between revisions

Namespaces

More

Page actions

Revision as of 17:23, 10 September 2023

Contents

डेफिनेशन

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

स्थानीय हैमिल्टनियन प्रॉब्लम

संबंधित वर्ग

अन्य वर्गों से संबंध

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

क्यूएमए: Difference between revisions

Revision as of 17:23, 10 September 2023

डेफिनेशन

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

स्थानीय हैमिल्टनियन प्रॉब्लम

संबंधित वर्ग

अन्य वर्गों से संबंध

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories