क्यूएमए

This article is about the mathematical theory. For the coaxial RF connector, see QMA and QN connector.

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

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

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

परिभाषा

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

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

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

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