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

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

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

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

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

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

एल्गोरिथ्म इनपुट के रूप में दिया गया है $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$. इसमें तीन सबरूटीन्स होते हैं: एक सूडो-मैट्रिक्स उलटा ऑपरेशन करने के लिए एक एल्गोरिद्म, फिट क्वालिटी के आकलन के लिए एक रूटीन और फिट पैरामीटर्स सीखने के लिए एक एल्गोरिद्म।

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

क्वांटम सेमीडिफिनिट प्रोग्रामिंग

अर्ध निश्चित प्रोग्रामिंग (एसडीपी) एक ऑप्टिमाइज़ेशन सबफ़ील्ड है जो एक रेखीय उद्देश्य फ़ंक्शन (एक उपयोगकर्ता-निर्दिष्ट फ़ंक्शन कोन न्यूनतम या अधिकतम करने के लिए) के अनुकूलन के साथ काम करता है, एक सकारात्मक स्थान के साथ सकारात्मक अर्ध-निश्चित मैट्रिक्स के शंकु के चौराहे पर। उद्देश्य फ़ंक्शन मैट्रिक्स का एक आंतरिक उत्पाद है $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$ अभी भी मौजूद है: यह एसडीपी समस्या का न्यूनतम समाधान देता है।

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

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

संयोजन अनुकूलन समस्या का उद्देश्य वस्तुओं के सीमित सेट से एक इष्टतम वस्तु खोजना है। समस्या को ऑब्जेक्टिव फ़ंक्शन के अधिकतमकरण के रूप में व्यक्त किया जा सकता है जो बूलियन फ़ंक्शंस का योग है। प्रत्येक बूलियन समारोह $\,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) संक्षेप में किसी भी ज्ञात बहुपद समय शास्त्रीय एल्गोरिथ्म (एक निश्चित समस्या के लिए) की तुलना में बेहतर सन्निकटन अनुपात था, जब तक एक अधिक प्रभावी शास्त्रीय एल्गोरिथम प्रस्तावित नहीं किया गया था। क्वांटम एल्गोरिथम की सापेक्ष गति एक खुला शोध प्रश्न है।

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

2020 में, यह दिखाया गया था कि क्यूएओए एक समस्या की बाधा (गणित) के अनुपात पर चर (गणित) (समस्या घनत्व) के अनुपात पर एक मजबूत निर्भरता प्रदर्शित करता है, जो संबंधित हानि फ़ंक्शन को कम करने के लिए एल्गोरिथम की क्षमता पर सीमित प्रतिबंध लगाता है। जल्द ही यह मान लिया गया कि QAOA प्रक्रिया का एक सामान्यीकरण अनिवार्य रूप से एक अंतर्निहित ग्राफ पर एक निरंतर-समय क्वांटम वॉक का एक वैकल्पिक अनुप्रयोग है, जिसके बाद प्रत्येक समाधान स्थिति पर गुणवत्ता-निर्भर चरण बदलाव लागू होता है। इस सामान्यीकृत QAOA को QWOA (क्वांटम वॉक-बेस्ड ऑप्टिमाइज़ेशन एल्गोरिथम) कहा गया। कागज में arXiv को प्रस्तुत क्वांटम कम्प्यूटेशनल वर्चस्व के लिए कितने qubits की आवश्यकता है, लेखकों का निष्कर्ष है कि 420 qubits और 500 कांस्ट्रेंट (गणित) के साथ एक QAOA सर्किट को अत्याधुनिक सुपर कंप्यूटर पर चल रहे शास्त्रीय सिमुलेशन एल्गोरिदम का उपयोग करके अनुकरण करने के लिए कम से कम एक शताब्दी की आवश्यकता होगी ताकि आवश्यकता हो और पर्याप्तता # क्वांटम वर्चस्व के लिए पर्याप्तता।

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

यह भी देखें

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