क्यूएमए

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

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

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

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

परिभाषा

भाषा 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 हैमिल्टनियन जैसे क्वैबिट के सरल जाली मॉडल के लिए जाने जाते हैं