क्यूएमए

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

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

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

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

डेफिनेशन

लैंग्वेज L में है, ${\mathsf {QMA}}(c,s)$ यदि पॉलीनोमिअल टाइम क्वांटम वेरिफायर V और पॉलीनोमिअल उपस्थित है, तो $p(x)$ऐसा है कि:

• $\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 $\lambda$ इसे हैमिल्टनियन की आधार अवस्था ऊर्जा भी कहा जाता है।

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

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

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

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

$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-स्थानीय हैमिल्टनियन प्रॉब्लम प्रतिष्ठित बाधा संतुष्टि समस्याओं के अनुरूप हैं। निम्नलिखित तालिका प्रतिष्ठित सीएसपी और हैमिल्टनियन के मध्य अनुरूप गैजेट को प्रदर्शित करती है।

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

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

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

संबंधित वर्ग

क्यूसीएमए (या एमक्यूए), जो क्वांटम क्लासिकल मर्लिन आर्थर (या मर्लिन क्वांटम आर्थर) के लिए है, क्यूएमए के समान है, किन्तु प्रूफ प्रतिष्ठित स्ट्रिंग होना चाहिए। यह ज्ञात नहीं है कि क्यूएमए, क्यूसीएमए के समान है या नहीं, चूँकि क्यूसीएमए स्पष्ट रूप से क्यूएमए में निहित है।

क्यूआईपी (k), जो क्वांटम इंटरैक्टिव पॉलीनोमिअल टाइम (k संदेश) के लिए है, क्यूएमए का सामान्यीकरण है जहां मर्लिन और आर्थर k राउंड के लिए वर्णन कर सकते हैं। क्यूएमए, क्यूआईपी(1) है। क्यूआईपी(2) को पीस्पेस में जाना जाता है। क्यूआईपी (कम्प्लेक्सिटी) क्यूआईपी (k) है, जहां k को क्वैबिट की संख्या में पॉलीनोमिअल होने की अनुमति है। यह ज्ञात है कि QIP(3) = QIP. यह भी ज्ञात है कि QIP = IP (कम्प्लेक्सिटी) = PSPACE।

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

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

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

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

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

${\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}}$ या इसके विपरीत है।

बाहरी संबंध

• 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