क्यूएमए

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 हैमिल्टनियन जैसे क्वैबिट के सरल जाली मॉडल के लिए जाने जाते हैं $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}$. ऐसे मॉडल सार्वभौमिक रुद्धोष्म क्वांटम गणना पर लागू होते हैं।

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

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 पर पाई जा सकती है।

संबंधित वर्ग

QCMA (या MQA), जो क्वांटम क्लासिकल मर्लिन आर्थर (या मर्लिन क्वांटम आर्थर) के लिए है, क्यूएमए के समान है, लेकिन प्रमाण शास्त्रीय स्ट्रिंग होना चाहिए। यह ज्ञात नहीं है कि QMA, QCMA के बराबर है या नहीं, हालाँकि QCMA स्पष्ट रूप से QMA में निहित है।

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

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

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 पर वर्तमान में सबसे अच्छी ज्ञात ऊपरी सीमाएँ हैं

${\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