क्वांटम अनुकूलन एल्गोरिदम

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

क्वांटम आंकड़े फिटिंग

वक्र फिटिंग गणितीय कार्य के निर्माण की प्रक्रिया है जो आंकड़े बिंदुओं के चुनाव के लिए सबसे उपयुक्त है। उचित की गुणवत्ता को कुछ मानदंडों द्वारा मापा जाता है जो सामान्यतः कार्य और आंकड़े बिंदुओं के मध्य की दूरी द्वारा मापा जाता है।

क्वांटम कम से कम वर्ग फिटिंग

आंकड़े फिटिंग के सबसे सामान्य प्रकारों में से कम से कम वर्गों की समस्या को हल करता है, आंकड़े बिंदुओं और उचित किए गए कार्य के मध्य अंतर के वर्गों के योग को कम करता है।

जो एल्गोरिथ्म इनपुट के रूप में दिया गया है $N$ आंकड़े अंक $(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N})$ और $M$ निरंतर कार्य $f_{1},f_{2},...,f_{M}$. एल्गोरिदम आउटपुट के रूप में सतत कार्य प्राप्त करता है और $f_{\vec {\lambda }}$ देता है यह $f_{j}$ का रैखिक संयोजन है।

$f_{\vec {\lambda }}(x)=\sum _{j=1}^{M}f_{j}(x)\lambda _{j}$

दूसरे शब्दों में कह सकते है कि, एल्गोरिथ्म सम्मिश्र संख्या गुणांक $\lambda _{j}$ प्राप्त करता है और इस प्रकार वेक्टर ${\vec {\lambda }}=(\lambda _{1},\lambda _{2},...,\lambda _{M})$ प्राप्त करता है।

एल्गोरिथ्म का उद्देश्य त्रुटि को कम करना है, जो इस प्रकार दिया गया है।

$E=\sum _{i=1}^{N}\left\vert f_{\vec {\lambda }}(x_{i})-y_{i}\right\vert ^{2}=\sum _{i=1}^{N}\left\vert \sum _{j=1}^{M}f_{j}(x_{i})\lambda _{j}-y_{i}\right\vert ^{2}=\left\vert F{\vec {\lambda }}-{\vec {y}}\right\vert ^{2}$ जहां हम परिभाषित करते हैं $F$ निम्नलिखित मैट्रिक्स होने के लिए,

${F}={\begin{pmatrix}f_{1}(x_{1})&\cdots &f_{M}(x_{1})\\f_{1}(x_{2})&\cdots &f_{M}(x_{2})\\\vdots &\ddots &\vdots \\f_{1}(x_{N})&\cdots &f_{M}(x_{N})\\\end{pmatrix}}$

क्वांटम कम से कम वर्ग फिटिंग एल्गोरिथम समीकरणों की रैखिक प्रणालियों के लिए हैरो, हासिडिम और लॉयड (HHL) के क्वांटम एल्गोरिथम के संस्करण का उपयोग करता है और गुणांकों $\lambda _{j}$ को आउटपुट करता है और उचित गुणवत्ता का अनुमान $E$. इसमें तीन सबरूटीन्स होते हैं, सूडो-मैट्रिक्स उलटा ऑपरेशन करने के लिए एल्गोरिथम, उचित गुणवाता के आकलन के लिए नियमित और उचित पैरामीटर्स सीखने के लिए एल्गोरिथम का प्रयोग करता है।

जिससे कि क्वांटम एल्गोरिथम मुख्य रूप से हैरो, हासिडिम और लॉयड (HHL) एल्गोरिथम पर आधारित है, यह घातीय सुधार का सुझाव देता है। स्थितियों में जहां $F$ विरल मैट्रिक्स है और दोनों की स्थिति संख्या (अर्थात्, सबसे बड़े और सबसे छोटे eigenvalues ​​​​के मध्य का अनुपात) $FF^{\dagger }$ और $F^{\dagger }F$ छोटा होता है।

क्वांटम अर्ध निश्चित कार्यक्रम

अर्ध निश्चित प्रोग्रामिंग (SDP) विश्राम उप क्षेत्र है जो रेखीय उद्देश्य कार्य ( उपयोगकर्ता-निर्दिष्ट कार्य कोन न्यूनतम या अधिकतम करने के लिए) के अनुकूलन के साथ कार्य करता है, सकारात्मक स्थान के साथ सकारात्मक अर्ध-निश्चित मैट्रिक्स के शंकु के चौराहे पर। उद्देश्य कार्य मैट्रिक्स का आंतरिक उत्पाद है $C$ (इनपुट के रूप में दिया गया) चर के साथ $X$. द्वारा निरूपित करें $\mathbb {S} ^{n}$ सभी का स्थान $n\times n$ सममित मैट्रिक्स। चर $X$ सकारात्मक अर्ध निश्चित सममित आव्यूहों के (बंद उत्तल) शंकु में होना चाहिए $\mathbb {S} _{+}^{n}$. दो मैट्रिसेस के आंतरिक उत्पाद को इस प्रकार परिभाषित किया गया है।

$\langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\sum _{i=1,j=1}^{n}A_{ij}B_{ij}.$

समस्या में अतिरिक्त बाधाएँ हो सकती हैं (इनपुट के रूप में दी गई), सामान्यतः आंतरिक उत्पादों के रूप में भी तैयार की जाती हैं। प्रत्येक बाधा मेट्रिसेस के आंतरिक उत्पाद $A_{k}$ (इनपुट के रूप में दिया गया) को बाध्य करती है। अनुकूलन चर के साथ $X$ निर्दिष्ट मान $b_{k}$ (इनपुट के रूप में दिया गया) से छोटा होता है। अंत में,अर्ध निश्चित कार्यक्रम (SDP) समस्या को इस प्रकार लिखा जा सकता है।

${\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0\end{array}}$

बहुपद के समय में बिना परिस्थिति चलने के लिए सबसे उचित मौलिक एल्गोरिदम ज्ञात नहीं होता है। इसी व्यवहार्यता समस्या को या तो जटिलता वर्ग एनपी और सह-एनपी के संघ के बाहर या एनपी और सह-एनपी के चौराहे पर जाना जाता है।

क्वांटम एल्गोरिथ्म

एल्गोरिदम इनपुट $A_{1}...A_{m},C,b_{1}...b_{m}$ हैं और समाधान के ट्रेस वर्ग, त्रुटिहीन और इष्टतम मान (इष्टतम बिंदु पर उद्देश्य कार्य का मान) के बारे में पैरामीटर होता है।

क्वांटम एल्गोरिथ्म कई पुनरावृत्तियों के होते हैं। प्रत्येक पुनरावृत्ति में, यह गणितीय अनुकूलन के द्वारा व्यवहार्यता समस्या को हल करता है, अर्थात्, निम्नलिखित स्थितियों को संतुष्ट करने वाला कोई भी समाधान ढूंढता है (सीमा देकर $t$):

${\begin{array}{lr}\langle C,X\rangle _{\mathbb {S} ^{n}}\leq t\\\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\X\succeq 0\end{array}}$

प्रत्येक पुनरावृत्ति में, अलग सीमा $t$ चुना जाता है और एल्गोरिथ्म या तो समाधान $X$ का उत्पादन करता है जिससे कि $\langle C,X\rangle _{\mathbb {S} ^{n}}\leq t$ (और अन्य बाधाएं भी संतुष्ट हैं) या संकेत है कि ऐसा कोई समाधान उपस्तिथ नहीं है। एल्गोरिदम न्यूनतम सीमा खोजने के लिए बाइनरी खोज करता है $t$ जिसके लिए समाधान $X$ अभी भी उपस्तिथ है यह अर्ध निश्चित कार्यक्रम (SDP) समस्या का न्यूनतम समाधान देता है।

क्वांटम एल्गोरिथ्म सामान्य स्थितियों में सर्वश्रेष्ठ मौलिक एल्गोरिथ्म पर द्विघात सुधार प्रदान करता है और घातीय सुधार जब इनपुट मैट्रिसेस निम्न रैंक (रैखिक बीजगणित) के होते हैं।

क्वांटम दहनशील अनुकूलन

संयोजन अनुकूलन समस्या का उद्देश्य वस्तुओं के सीमित चुनाव से इष्टतम वस्तु खोजना है। समस्या को ऑब्जेक्टिव कार्य के अधिकतमकरण के रूप में व्यक्त किया जा सकता है जो बूलियन फ़ंक्शंस का योग है। प्रत्येक बूलियन समारोह $\,C_{\alpha }\colon \lbrace {0,1\rbrace }^{n}\rightarrow \lbrace {0,1}\rbrace$ इनपुट के रूप में प्राप्त करता है $n$-बिट स्ट्रिंग $z=z_{1}z_{2}\ldots z_{n}$ और आउटपुट के रूप में बिट (0 या 1) देता है। कॉम्बिनेटरियल ऑप्टिमाइज़ेशन की समस्या $n$ बिट्स और $m$ खंड खोज रहा है $n$-बिट स्ट्रिंग $z$ जो कार्य को अधिकतम करता है

$C(z)=\sum _{\alpha =1}^{m}C_{\alpha }(z)$

सन्निकटन एल्गोरिथम अनुकूलन समस्या का अनुमानित समाधान खोजने का विधि है, जो अधिकांशतःएनपी कठिन होता है। कॉम्बिनेटरियल ऑप्टिमाइज़ेशन समस्या का अनुमानित समाधान स्ट्रिंग है $z$ जो अधिकतम करने के करीब है $C(z)$.

क्वांटम अनुमानित अनुकूलन एल्गोरिदम

संयोजी अनुकूलन के लिए, क्वांटम अनुमानित अनुकूलन एल्गोरिथम (QAOA) संक्षेप में किसी भी ज्ञात बहुपद समय मौलिक एल्गोरिथ्म ( निश्चित समस्या के लिए) की तुलना में उत्तम सन्निकटन अनुपात था, जब तक अधिक प्रभावी मौलिक एल्गोरिथम प्रस्तावित नहीं किया गया था। क्वांटम एल्गोरिथम की सापेक्ष गति का खुला शोध प्रश्न है।

क्वांटम अनुमानित अनुकूलन एल्गोरिथम (QAOA) का केंद्र एकात्मक ऑपरेटरों के उपयोग पर निर्भर करता है $2p$ कोण, जंहा $p>1$ इनपुट पूर्णांक है। इन ऑपरेटरों को पुनरावृत्त रूप से राज्य पर प्रायुक्त किया जाता है जो कम्प्यूटेशनल आधार पर सभी संभावित राज्यों की समान भारित जितना अध्यारोपण है। प्रत्येक पुनरावृत्ति में, राज्य को कम्प्यूटेशनल आधार पर मापा जाता है और $C(z)$ अंदाजा है। कोणों को बढ़ाने के लिए मौलिक रूप से अद्यतन $C(z)$ किया जाता है। इस प्रक्रिया के बाद पर्याप्त संख्या को बार-बार दोहराया जाता है, जंहा $C(z)$ का मान लगभग इष्टतम मान के रूप में मापा जा रहा होता है, और यह स्थिति, भी इष्टतम होने के समीप होती है।

सन् 2020 में, यह दिखाया गया था कि क्वांटम अनुमानित अनुकूलन एल्गोरिथम (QAOA) समस्या की बाधा (गणित) के अनुपात पर चर (गणित) (समस्या घनत्व) के अनुपात पर मजबूत निर्भरता प्रदर्शित करता है, जो संबंधित हानि कार्य को कम करने के लिए एल्गोरिथम की क्षमता पर सीमित प्रतिबंध लगाता है।

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

कागज में arXiv को प्रस्तुत क्वांटम कम्प्यूटेशनल वर्चस्व के लिए कितने क्वांटम बिट (qubits) की आवश्यकता होती है, लेखकों का निष्कर्ष है कि 420 क्वांटम बिट (qubits) और 500 कांस्ट्रेंट (गणित) के साथ QAOA विद्युत परिपथ को अत्याधुनिक सुपर कंप्यूटर पर चल रहे मौलिक सतत अनुकरण एल्गोरिदम का उपयोग करके अनुकरण करने के लिए कम से कम शताब्दी की आवश्यकता होगी जिससे कि इसकीआवश्यकता हो और क्वांटम वर्चस्व के लिए पर्याप्त हो।

मौलिक एल्गोरिदम के साथ क्वांटम अनुमानित अनुकूलन एल्गोरिथम (QAOA) की कठोर तुलना गहराई पर अनुमान दे सकती है $p$ और क्वांटम लाभ के लिए आवश्यक क्वांटम बिट (qubits) की संख्या की आवश्यकता होती है। क्वांटम अनुमानित अनुकूलन एल्गोरिथम (QAOA) और अधिकतम कट एल्गोरिथम के अध्ययन से पता चलता है $p>11$ स्केलेबल लाभ के लिए आवश्यक है।

यह भी देखें

• स्थिरोष्म क्वांटम संगणना
• क्वांटम एनीलिंग