क्यूएमए

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

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

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

परिलैंग्वेज

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

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

यह अज्ञात है कि इनमें से कोई भी समावेशन बिना नियम सख्त है, क्योंकि यह भी ज्ञात नहीं है कि क्या पी पूर्ण रूप से पीस्पेस में समाहित है या पी = पीस्पेस में है। चूँकि, क्यूएमए पर वर्तमान में सबसे उचित ज्ञात ऊपरी सीमाएँ हैं:^[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]

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

क्यूएमए

Namespaces

More

Page actions

Contents

परिलैंग्वेज

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

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

संबंधित वर्ग

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

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

क्यूएमए

परिलैंग्वेज

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

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

संबंधित वर्ग

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

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories