क्यूएमए: Difference between revisions

Revision as of 23:45, 4 August 2023

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

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

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

परिभाषा

भाषा L में है ${\mathsf {QMA}}(c,s)$ यदि बहुपद समय क्वांटम सत्यापनकर्ता V और बहुपद मौजूद है $p(x)$ ऐसा है कि:^[1]^[2]^[3]

$\forall x\in L$ , वहाँ क्वांटम अवस्था मौजूद है $|\psi \rangle$ ऐसी संभावना है कि V इनपुट स्वीकार करता है $(|x\rangle ,|\psi \rangle )$ से बड़ा है $c$ .
$\forall x\notin L$ , सभी क्वांटम अवस्थाओं के लिए $|\psi \rangle$ , संभावना है कि V इनपुट स्वीकार करता है $(|x\rangle ,|\psi \rangle )$ मै रुक जाना $s$ .

कहाँ $|\psi \rangle$ सभी क्वांटम अवस्थाओं में अधिकतम सीमा होती है $p(|x|)$ qubits.

जटिलता वर्ग ${\mathsf {QMA}}$ के बराबर परिभाषित किया गया है ${\mathsf {QMA}}({2}/{3},1/3)$ . हालाँकि, स्थिरांक बहुत महत्वपूर्ण नहीं हैं क्योंकि वर्ग अपरिवर्तित रहता है $c$ और $s$ को ऐसे किसी भी स्थिरांक पर सेट किया जाता है $c$ से बड़ा है $s$ . इसके अलावा, किसी भी बहुपद के लिए $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)})

.

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

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

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

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

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

$H=\sum _{i=1}^{m}H_{i}$ सामान्य k-स्थानीय हैमिल्टनियन समस्या, k-स्थानीय हैमिल्टनियन दी गई है $H$ , सबसे छोटा eigenvalue खोजने के लिए $\lambda$ का $H$ .^[4] $\lambda$ इसे हैमिल्टनियन की जमीनी अवस्था ऊर्जा भी कहा जाता है।

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

स्थानीय हैमिल्टनियन समस्या अधिकतम संतुष्टि समस्या|MAX-SAT का क्वांटम एनालॉग है। k-स्थानीय हैमिल्टनियन समस्या k ≥ 2 के लिए QMA-पूर्ण है।^[5] क्वैबिट के द्वि-आयामी ग्रिड पर कार्य करने के लिए प्रतिबंधित 2-स्थानीय हैमिल्टनियन समस्या भी QMA-पूर्ण है।^[6] यह दिखाया गया है कि के-स्थानीय हैमिल्टनियन समस्या अभी भी क्यूएमए-कठिन है, यहां तक कि हैमिल्टनियनों के लिए भी जो प्रति कण 12 राज्यों के साथ निकटतम-पड़ोसी इंटरैक्शन के साथ कणों की 1-आयामी रेखा का प्रतिनिधित्व करते हैं।^[7] यदि सिस्टम अनुवादात्मक रूप से-अपरिवर्तनीय है, तो इसकी स्थानीय हैमिल्टनियन समस्या QMA बन जाती है_EXP-पूर्ण (चूंकि समस्या इनपुट सिस्टम आकार में एन्कोड किया गया है, सत्यापनकर्ता के पास अब समान वादे के अंतर को बनाए रखते हुए घातीय रनटाइम है)।^[8]^[9] QMA-कठोरता परिणाम ZX हैमिल्टनियन जैसे क्वैबिट के सरल जाली मॉडल के लिए जाने जाते हैं ^[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}$ . ऐसे मॉडल सार्वभौमिक रुद्धोष्म क्वांटम गणना पर लागू होते हैं।

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

Classical	Quantum	Notes
Constraint Satisfaction Problem	Hamiltonian
Variable	Qubit
Constraint	Hamiltonian Term
Variable Assignment	Quantum state
Number of constraints satisfied	Hamiltonian's energy term
Optimal Solution	Hamiltonian's ground state	The most possible constraints satisfied

अन्य क्यूएमए-पूर्ण समस्याएं

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

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

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

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

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

यह अज्ञात है कि इनमें से कोई भी समावेशन बिना शर्त सख्त है, क्योंकि यह भी ज्ञात नहीं है कि क्या P पूरी तरह से PSPACE में समाहित है या P = PSPACE में। हालाँकि, QMA पर वर्तमान में सबसे अच्छी ज्ञात ऊपरी सीमाएँ हैं ^[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|the mathematical theory|the coaxial RF connector|QMA and QN connector}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, क्यूएमए, जो क्वांटम आर्थर-मर्लिन प्रोटोकॉल के लिए खड़ा है, भाषाओं का समूह है, जिसके लिए, जब एक स्ट्रिंग भाषा में होती है, तो एक बहुपद-आकार का क्वांटम प्रमाण (एक क्वांटम स्थिति) होता है जो एक बहुपद समय क्वांटम सत्यापनकर्ता ([[ एक कंप्यूटर जितना ]] पर चलने वाले) को उच्च संभावना के साथ इस तथ्य के बारे में आश्वस्त करता है। इसके अलावा, जब स्ट्रिंग भाषा में नहीं होती है, तो प्रत्येक बहुपद-आकार की क्वांटम स्थिति को सत्यापनकर्ता द्वारा उच्च संभावना के साथ खारिज कर दिया जाता है।
+[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, क्यूएमए, जो क्वांटम आर्थर-मर्लिन प्रोटोकॉल के लिए खड़ा है, भाषाओं का समूह है, जिसके लिए, जब  स्ट्रिंग भाषा में होती है, तो  बहुपद-आकार का क्वांटम प्रमाण ( क्वांटम स्थिति) होता है जो  बहुपद समय क्वांटम सत्यापनकर्ता ([[ एक कंप्यूटर जितना |  कंप्यूटर जितना]] पर चलने वाले) को उच्च संभावना के साथ इस तथ्य के बारे में आश्वस्त करता है। इसके अलावा, जब स्ट्रिंग भाषा में नहीं होती है, तो प्रत्येक बहुपद-आकार की क्वांटम स्थिति को सत्यापनकर्ता द्वारा उच्च संभावना के साथ खारिज कर दिया जाता है।
 क्यूएमए और [[बीक्यूपी]] के बीच संबंध [[जटिलता वर्ग]]ों [[एन[[पी (जटिलता)]]]] और पी (जटिलता) के बीच संबंध के अनुरूप है।{{cn|date=November 2022}}. यह संभाव्य जटिलता वर्ग आर्थर-मर्लिन प्रोटोकॉल और [[बीपीपी (जटिलता)]] के बीच संबंध के अनुरूप भी है।{{cn|date=November 2022}}.
-QAM एक संबंधित जटिलता वर्ग है, जिसमें काल्पनिक एजेंट आर्थर और मर्लिन अनुक्रम को अंजाम देते हैं: आर्थर एक यादृच्छिक स्ट्रिंग उत्पन्न करता है, मर्लिन एक क्वांटम [[प्रमाणपत्र (जटिलता)]] के साथ उत्तर देता है और आर्थर इसे BQP मशीन के रूप में सत्यापित करता है।
+QAM  संबंधित जटिलता वर्ग है, जिसमें काल्पनिक एजेंट आर्थर और मर्लिन अनुक्रम को अंजाम देते हैं: आर्थर  यादृच्छिक स्ट्रिंग उत्पन्न करता है, मर्लिन  क्वांटम [[प्रमाणपत्र (जटिलता)]] के साथ उत्तर देता है और आर्थर इसे BQP मशीन के रूप में सत्यापित करता है।
 == परिभाषा ==
-एक भाषा 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>|\psi\rangle</math> सभी क्वांटम अवस्थाओं में अधिकतम सीमा होती है <math>p(|x|)</math> qubits.
@@ Line 22: / Line 22: @@
 चूंकि क्यूएमए में कई दिलचस्प वर्ग शामिल हैं, जैसे पी, बीक्यूपी और एनपी, उन वर्गों की सभी समस्याएं भी क्यूएमए में हैं। हालाँकि, ऐसी समस्याएँ हैं जो QMA में हैं लेकिन NP या BQP में नहीं हैं। ऐसी कुछ प्रसिद्ध समस्याओं पर नीचे चर्चा की गई है।
-एक समस्या को क्यूएमए-हार्ड कहा जाता है, जो [[ एनपी कठिन ]] के समान है, यदि क्यूएमए में प्रत्येक समस्या इसमें [[कमी (जटिलता)]] हो सकती है। किसी समस्या को QMA-[[पूर्ण (जटिलता)]] कहा जाता है यदि वह QMA-हार्ड है और QMA में है।
+समस्या को क्यूएमए-हार्ड कहा जाता है, जो [[ एनपी कठिन ]] के समान है, यदि क्यूएमए में प्रत्येक समस्या इसमें [[कमी (जटिलता)]] हो सकती है। किसी समस्या को QMA-[[पूर्ण (जटिलता)]] कहा जाता है यदि वह QMA-हार्ड है और QMA में है।
 === स्थानीय हैमिल्टनियन समस्या ===
-एक के-स्थानीय [[हैमिल्टनियन (क्वांटम यांत्रिकी)]] <math>H</math> एक [[हर्मिटियन मैट्रिक्स]] है जो n क्वैबिट पर कार्य करता है जिसे इसके योग के रूप में दर्शाया जा सकता है <math>m</math> हैमिल्टनियन शर्तें अधिकतम पर कार्य करती हैं <math>k</math> प्रत्येक को क्वैबिट करता है।
+के-स्थानीय [[हैमिल्टनियन (क्वांटम यांत्रिकी)]] <math>H</math>  [[हर्मिटियन मैट्रिक्स]] है जो n क्वैबिट पर कार्य करता है जिसे इसके योग के रूप में दर्शाया जा सकता है <math>m</math> हैमिल्टनियन शर्तें अधिकतम पर कार्य करती हैं <math>k</math> प्रत्येक को क्वैबिट करता है।
 <math>H = \sum_{i=1}^m H_i</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
@@ Line 94: / Line 94: @@
 |}
+'''अन्य क्यूएमए-पूर्ण समस्याएं'''
-===अन्य क्यूएमए-पूर्ण समस्याएं===
 ज्ञात QMA-पूर्ण समस्याओं की सूची https://arxiv.org/abs/1212.6312 पर पाई जा सकती है।
 == संबंधित वर्ग ==
-QCMA (या MQA<ref name="JW" />), जो क्वांटम क्लासिकल मर्लिन आर्थर (या मर्लिन क्वांटम आर्थर) के लिए है, क्यूएमए के समान है, लेकिन प्रमाण एक शास्त्रीय स्ट्रिंग होना चाहिए। यह ज्ञात नहीं है कि QMA, QCMA के बराबर है या नहीं, हालाँकि QCMA स्पष्ट रूप से QMA में निहित है।
+QCMA (या MQA<ref name="JW" />), जो क्वांटम क्लासिकल मर्लिन आर्थर (या मर्लिन क्वांटम आर्थर) के लिए है, क्यूएमए के समान है, लेकिन प्रमाण  शास्त्रीय स्ट्रिंग होना चाहिए। यह ज्ञात नहीं है कि QMA, QCMA के बराबर है या नहीं, हालाँकि QCMA स्पष्ट रूप से QMA में निहित है।
-QIP(k), जो [[क्वांटम इंटरैक्टिव बहुपद समय]] (k संदेश) के लिए है, QMA का एक सामान्यीकरण है जहां मर्लिन और आर्थर k राउंड के लिए बातचीत कर सकते हैं। क्यूएमए क्यूआईपी(1) है। QIP(2) को PSPACE में जाना जाता है।<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>
+QIP(k), जो [[क्वांटम इंटरैक्टिव बहुपद समय]] (k संदेश) के लिए है, QMA का  सामान्यीकरण है जहां मर्लिन और आर्थर k राउंड के लिए बातचीत कर सकते हैं। क्यूएमए क्यूआईपी(1) है। QIP(2) को PSPACE में जाना जाता है।<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>
 QIP (जटिलता) QIP(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>
 == अन्य वर्गों से संबंध ==
 QMA निम्नलिखित संबंधों द्वारा अन्य ज्ञात जटिलता वर्गों से संबंधित है:
 :<math>\mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{MA} \subseteq \mathsf{QCMA} \subseteq \mathsf{QMA}\subseteq \mathsf{PP} \subseteq \mathsf{PSPACE}</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 23:45, 4 August 2023

Contents

परिभाषा

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

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

संबंधित वर्ग

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

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

क्यूएमए: Difference between revisions

Revision as of 23:45, 4 August 2023

परिभाषा

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

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

संबंधित वर्ग

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

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories