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

From Vigyanwiki
(Created page with "{{Short description|Optimization algorithms using quantum computing}} {{Use American English|date=January 2019}} क्वांटम अनुकूलन एल्गोर...")
 
No edit summary
 
(7 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Optimization algorithms using quantum computing}}
{{Short description|Optimization algorithms using quantum computing}}
{{Use American English|date=January 2019}}
'''क्वांटम अनुकूलन एल्गोरिद'''म को [[क्वांटम एल्गोरिदम|क्वांटम प्रारूप]] कहते हैं जिनका उपयोग अनुकूलन स्थितियो को हल करने के लिए किया जाता है।<ref>{{cite journal|last1=Moll|first1=Nikolaj|last2=Barkoutsos|first2=Panagiotis|last3=Bishop|first3=Lev S.|last4=Chow|first4=Jerry M.|last5=Cross|first5=Andrew|last6=Egger|first6=Daniel J.|last7=Filipp|first7=Stefan|last8=Fuhrer|first8=Andreas|last9=Gambetta|first9=Jay M.|last10=Ganzhorn|first10=Marc|last11=Kandala|first11=Abhinav|last12=Mezzacapo|first12=Antonio|last13=Müller|first13=Peter|last14=Riess|first14=Walter|last15=Salis|first15=Gian|last16=Smolin|first16=John|last17=Tavernelli|first17=Ivano|last18=Temme|first18=Kristan|title=Quantum optimization using variational algorithms on near-term quantum devices|journal=Quantum Science and Technology|date=2018|volume=3|issue=3|pages= 030503|doi=10.1088/2058-9565/aab822|arxiv=1710.01022|bibcode=2018QS&T....3c0503M|s2cid=56376912}}</ref> [[गणितीय अनुकूलन]] संभावित समाधानों के चुनाव से किसी स्थितिका सबसे सटीक समाधान (कुछ मानदंडों के अनुसार) खोजने से संबंधित है। अधिकतर अनुकूलन स्थितिको न्यूनतमकरण स्थितिके रूप में तैयार किया जाता है, जहां कोई त्रुटि को कम करने की कोशिश करता है जो समाधान पर निर्भर करता है। जिससे उत्तम समाधान में न्यूनतम त्रुटि होती है। [[यांत्रिकी]], [[अर्थशास्त्र]] और [[अभियांत्रिकी]] जैसे विभिन्न क्षेत्रों में विभिन्न अनुकूलन प्रविधि को प्रयुक्त किया जाता है और जैसे-जैसे आंकड़े की जटिलता और मात्रा बढ़ती है वैसे ही अनुकूलन स्थितियो को हल करने के अधिक कुशल प्रणाली की आवश्यकता होती है। [[क्वांटम कम्प्यूटिंग]] की क्षमता उन स्थितियो को हल करने की अनुमति दे सकती है जो मौलिक कंप्यूटरों पर व्यावहारिक रूप से व्यवहार नहीं हैं या सर्वोत्तम ज्ञात मौलिक एल्गोरिथ्म (कलन विधि) के संबंध में अधिक गति का प्रस्ताव दे सकती हैं।
क्वांटम अनुकूलन एल्गोरिदम [[क्वांटम एल्गोरिदम]] हैं जिनका उपयोग अनुकूलन समस्याओं को हल करने के लिए किया जाता है।<ref>{{cite journal|last1=Moll|first1=Nikolaj|last2=Barkoutsos|first2=Panagiotis|last3=Bishop|first3=Lev S.|last4=Chow|first4=Jerry M.|last5=Cross|first5=Andrew|last6=Egger|first6=Daniel J.|last7=Filipp|first7=Stefan|last8=Fuhrer|first8=Andreas|last9=Gambetta|first9=Jay M.|last10=Ganzhorn|first10=Marc|last11=Kandala|first11=Abhinav|last12=Mezzacapo|first12=Antonio|last13=Müller|first13=Peter|last14=Riess|first14=Walter|last15=Salis|first15=Gian|last16=Smolin|first16=John|last17=Tavernelli|first17=Ivano|last18=Temme|first18=Kristan|title=Quantum optimization using variational algorithms on near-term quantum devices|journal=Quantum Science and Technology|date=2018|volume=3|issue=3|pages= 030503|doi=10.1088/2058-9565/aab822|arxiv=1710.01022|bibcode=2018QS&T....3c0503M|s2cid=56376912}}</ref> [[गणितीय अनुकूलन]] संभावित समाधानों के एक सेट से किसी समस्या का सबसे अच्छा समाधान (कुछ मानदंडों के अनुसार) खोजने से संबंधित है। अधिकतर, अनुकूलन समस्या को एक न्यूनतमकरण समस्या के रूप में तैयार किया जाता है, जहां कोई त्रुटि को कम करने की कोशिश करता है जो समाधान पर निर्भर करता है: इष्टतम समाधान में न्यूनतम त्रुटि होती है। [[यांत्रिकी]], [[अर्थशास्त्र]] और [[अभियांत्रिकी]] जैसे विभिन्न क्षेत्रों में विभिन्न अनुकूलन तकनीकों को लागू किया जाता है, और जैसे-जैसे डेटा की जटिलता और मात्रा बढ़ती है, अनुकूलन समस्याओं को हल करने के अधिक कुशल तरीकों की आवश्यकता होती है। [[क्वांटम कम्प्यूटिंग]] की शक्ति उन समस्याओं को हल करने की अनुमति दे सकती है जो शास्त्रीय कंप्यूटरों पर व्यावहारिक रूप से व्यवहार्य नहीं हैं, या सर्वोत्तम ज्ञात क्लासिकल एल्गोरिदम के संबंध में काफी गति का सुझाव दे सकती हैं।


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


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


एल्गोरिथ्म इनपुट के रूप में दिया गया है <math> N </math> डेटा अंक <math> (x_1, y_1), (x_2, y_2), ... , (x_N, y_N)</math> और <math> M </math> [[निरंतर कार्य]] <math> f_{1}, f_{2}, ... , f_{M} </math>. एल्गोरिदम आउटपुट के रूप में एक सतत कार्य पाता है और देता है <math> f_{\vec{\lambda}} </math> यह का एक [[रैखिक संयोजन]] है <math> f_j</math>:
जो एल्गोरिथ्म (कलन विधि) इनपुट के रूप में दिया गया है <math> N </math> आंकड़े अंक <math> (x_1, y_1), (x_2, y_2), ... , (x_N, y_N)</math> और <math> M </math> [[निरंतर कार्य]] <math> f_{1}, f_{2}, ... , f_{M} </math>. प्रारूप आउटपुट के रूप में सतत कार्य प्राप्त करता है और <math> f_{\vec{\lambda}} </math> देता है यह <math> f_j</math> का [[रैखिक संयोजन]] है।


:<math>
:<math>
f_{\vec{\lambda}}(x) = \sum_{j=1}^M f_{j}(x)\lambda_{j}
f_{\vec{\lambda}}(x) = \sum_{j=1}^M f_{j}(x)\lambda_{j}
</math>
</math>
दूसरे शब्दों में, एल्गोरिथ्म सम्मिश्र संख्या गुणांक पाता है <math>\lambda_j </math>, और इस प्रकार वेक्टर पाता है <math> \vec{\lambda} = (\lambda_1, \lambda_2, ..., \lambda_M) </math>.
दूसरे शब्दों में कह सकते है कि, एल्गोरिथ्म (कलन विधि) सम्मिश्र संख्या गुणांक <math>\lambda_j </math> प्राप्त करता है और इस प्रकार दिष्‍ट <math> \vec{\lambda} = (\lambda_1, \lambda_2, ..., \lambda_M) </math> प्राप्त करता है।


एल्गोरिथ्म का उद्देश्य त्रुटि को कम करना है, जो इसके द्वारा दिया गया है:
एल्गोरिथ्म (कलन विधि) का उद्देश्य त्रुटि को कम करना है, जो इस प्रकार दिया गया है।
:<math>
:<math>
E=\sum_{i=1}^N  
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
\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_{j}(x_i)\lambda_{j}-y_i \right\vert^2 = \left\vert F\vec{\lambda}-\vec{y} \right\vert^2
</math> जहां हम परिभाषित करते हैं <math> F </math> निम्नलिखित मैट्रिक्स होने के लिए:
</math> जहां हम परिभाषित करते हैं निम्नलिखित मैट्रिक्स <math> F </math> होने के लिए,


:<math>{F} = \begin{pmatrix}
:<math>{F} = \begin{pmatrix}
Line 29: Line 28:
f_{1}(x_N) & \cdots & f_{M}(x_N) \\
f_{1}(x_N) & \cdots & f_{M}(x_N) \\
\end{pmatrix}</math>
\end{pmatrix}</math>
क्वांटम कम से कम वर्ग फिटिंग एल्गोरिथम<ref>{{cite journal|last1=Wiebe|first1=Nathan|last2=Braun|first2=Daniel|last3=Lloyd|first3=Seth|title=Quantum Algorithm for Data Fitting|journal=Physical Review Letters|date=2 August 2012|volume=109|issue=5|pages=050505|arxiv=1204.5242|doi=10.1103/PhysRevLett.109.050505|pmid=23006156|bibcode=2012PhRvL.109e0505W|s2cid=118439810 }}</ref> समीकरणों की रैखिक प्रणालियों (HHL) के लिए हैरो, हासिडिम और लॉयड के क्वांटम एल्गोरिथम के एक संस्करण का उपयोग करता है, और गुणांकों को आउटपुट करता है <math> \lambda_j </math> और फिट गुणवत्ता का अनुमान <math> E </math>. इसमें तीन सबरूटीन्स होते हैं: एक सूडो-[[मैट्रिक्स उलटा]] ऑपरेशन करने के लिए एक एल्गोरिद्म, फिट क्वालिटी के आकलन के लिए एक रूटीन और फिट पैरामीटर्स सीखने के लिए एक एल्गोरिद्म।
क्वांटम कम से कम वर्ग फिटिंग एल्गोरिथम<ref>{{cite journal|last1=Wiebe|first1=Nathan|last2=Braun|first2=Daniel|last3=Lloyd|first3=Seth|title=Quantum Algorithm for Data Fitting|journal=Physical Review Letters|date=2 August 2012|volume=109|issue=5|pages=050505|arxiv=1204.5242|doi=10.1103/PhysRevLett.109.050505|pmid=23006156|bibcode=2012PhRvL.109e0505W|s2cid=118439810 }}</ref> समीकरणों की रैखिक प्रणालियों के लिए हैरो, हासिडिम और लॉयड (HHL) के क्वांटम एल्गोरिथम के संस्करण का उपयोग करता है और गुणांकों <math> \lambda_j </math> को आउटपुट करता है और उचित गुणवत्ता का अनुमान <math> E </math>. इसमें तीन उप-दैनिकि होते हैं, सूडो-[[मैट्रिक्स उलटा]] ऑपरेशन करने के लिए एल्गोरिथम, उचित गुणवाता के आकलन के लिए नियमित और उचित पैरामीटर्स सीखने के लिए एल्गोरिथम का प्रयोग करता है।


क्योंकि क्वांटम एल्गोरिथम मुख्य रूप से एचएचएल एल्गोरिथम पर आधारित है, यह एक घातीय सुधार का सुझाव देता है<ref>{{cite journal|last1=Montanaro|first1=Ashley|title=Quantum algorithms: an overview|journal=[[npj Quantum Information]] |date=12 January 2016|volume=2|pages=15023|arxiv=1511.04206|doi=10.1038/npjqi.2015.23|bibcode=2016npjQI...215023M|s2cid=2992738}}</ref> मामले में जहां <math> F</math> [[विरल मैट्रिक्स]] है और दोनों की स्थिति संख्या (अर्थात्, सबसे बड़े और सबसे छोटे [[eigenvalues]] ​​​​के बीच का अनुपात) <math> F F^\dagger </math> और <math> F^\dagger F </math> छोटा है।
जिससे कि क्वांटम एल्गोरिथम मुख्य रूप से हैरो, हासिडिम और लॉयड (HHL) एल्गोरिथम पर आधारित है, यह घातीय सुधार का सुझाव देता है।<ref>{{cite journal|last1=Montanaro|first1=Ashley|title=Quantum algorithms: an overview|journal=[[npj Quantum Information]] |date=12 January 2016|volume=2|pages=15023|arxiv=1511.04206|doi=10.1038/npjqi.2015.23|bibcode=2016npjQI...215023M|s2cid=2992738}}</ref> स्थितियों में जहां <math> F</math> [[विरल मैट्रिक्स]] है और दोनों की स्थिति संख्या (अर्थात्, सबसे बड़े और सबसे छोटे [[eigenvalues|एइगेन्वलुएस]] ​​​​के मध्य का अनुपात) <math> F F^\dagger </math> और <math> F^\dagger F </math> छोटा होता है।


== क्वांटम सेमीडिफिनिट प्रोग्रामिंग ==
== क्वांटम अर्ध निश्चित कार्यक्रम ==
[[अर्ध निश्चित प्रोग्रामिंग]] (एसडीपी) एक ऑप्टिमाइज़ेशन सबफ़ील्ड है जो एक रेखीय उद्देश्य फ़ंक्शन (एक उपयोगकर्ता-निर्दिष्ट फ़ंक्शन [[कोन]] न्यूनतम या अधिकतम करने के लिए) के अनुकूलन के साथ काम करता है, एक सकारात्मक स्थान के साथ सकारात्मक अर्ध-निश्चित मैट्रिक्स के शंकु के चौराहे पर। उद्देश्य फ़ंक्शन मैट्रिक्स का एक आंतरिक उत्पाद है <math> C </math> (इनपुट के रूप में दिया गया) चर के साथ <math> X </math>. द्वारा निरूपित करें <math>\mathbb{S}^n</math> सभी का स्थान <math>n \times n</math> सममित मैट्रिक्स। चर <math> X </math> सकारात्मक अर्ध निश्चित सममित आव्यूहों के (बंद उत्तल) शंकु में होना चाहिए <math>\mathbb{S}^{n}_+</math>. दो मैट्रिसेस के आंतरिक उत्पाद को इस प्रकार परिभाषित किया गया है:
[[अर्ध निश्चित प्रोग्रामिंग|अर्ध निश्चित कार्यक्रम]] (SDP) विश्राम वह उप क्षेत्र है जो रेखीय उद्देश्य कार्य ( उपयोगकर्ता-निर्दिष्ट कार्य [[कोन]] न्यूनतम या अधिकतम करने के लिए) के अनुकूलन के साथ कार्य करता है, सकारात्मक स्थान के साथ सकारात्मक अर्ध-निश्चित मैट्रिक्स के शंकु के प्रतिच्छेदन पर उद्देश्य कार्य मैट्रिक्स का आंतरिक उत्पाद है <math> C </math> (इनपुट के रूप में दिया गया) चर के साथ <math> X </math>. द्वारा निरूपित करें <math>\mathbb{S}^n</math> सभी का स्थान <math>n \times n</math> सममित मैट्रिक्स। चर <math> X </math> सकारात्मक अर्ध निश्चित सममित आव्यूहों के (बंद उत्तल) शंकु में होना चाहिए <math>\mathbb{S}^{n}_+</math>. दो मैट्रिसेस के आंतरिक उत्पाद को इस प्रकार परिभाषित किया गया है।


<math>
<math>
Line 40: Line 39:
   A_{ij}B_{ij}.
   A_{ij}B_{ij}.
</math>
</math>
समस्या में अतिरिक्त बाधाएँ हो सकती हैं (इनपुट के रूप में दी गई), आमतौर पर आंतरिक उत्पादों के रूप में भी तैयार की जाती हैं। प्रत्येक बाधा मेट्रिसेस के आंतरिक उत्पाद को बाध्य करती है <math> A_k </math> (इनपुट के रूप में दिया गया) अनुकूलन चर के साथ <math> X </math> एक निर्दिष्ट मान से छोटा होना <math> b_k </math> (इनपुट के रूप में दिया गया)अंत में, SDP समस्या को इस प्रकार लिखा जा सकता है:
 
स्थितिमें अतिरिक्त बाधाएँ हो सकती हैं (इनपुट के रूप में दी गई), सामान्यतः आंतरिक उत्पादों के रूप में भी तैयार की जाती हैं। प्रत्येक बाधा मेट्रिसेस के आंतरिक उत्पाद <math> A_k </math> (इनपुट के रूप में दिया गया) को बाध्य करती है। अनुकूलन चर के साथ <math> X </math> निर्दिष्ट मान <math> b_k </math> (इनपुट के रूप में दिया गया) से छोटा होता है। अंत में,अर्ध निश्चित कार्यक्रम (SDP) स्थितिको इस प्रकार लिखा जा सकता है।
:<math>
:<math>
\begin{array}{rl}
\begin{array}{rl}
Line 48: Line 48:
\end{array}
\end{array}
</math>
</math>
बहुपद समय में बिना शर्त चलने के लिए सबसे अच्छा शास्त्रीय एल्गोरिदम ज्ञात नहीं है। इसी व्यवहार्यता समस्या को या तो जटिलता वर्ग एनपी और सह-एनपी के संघ के बाहर या एनपी और सह-एनपी के चौराहे पर जाना जाता है।<ref>{{Cite journal|url=https://doi.org/10.1007/BF02614433|doi = 10.1007/BF02614433|title = An exact duality theory for semidefinite programming and its complexity implications|year = 1997|last1 = Ramana|first1 = Motakuri V.|journal = Mathematical Programming|volume = 77|pages = 129–162|s2cid = 12886462}}</ref>
बहुपद के समय में बिना परिस्थिति चलने के लिए सबसे उचित मौलिक प्रारूप ज्ञात नहीं होता है। इसी व्यवहार्यता स्थितिको या तो जटिलता वर्ग एनपी और सह-एनपी के संघ के बाहर या एनपी और सह-एनपी के प्रतिच्छेदन पर जाना जाता है।<ref>{{Cite journal|url=https://doi.org/10.1007/BF02614433|doi = 10.1007/BF02614433|title = An exact duality theory for semidefinite programming and its complexity implications|year = 1997|last1 = Ramana|first1 = Motakuri V.|journal = Mathematical Programming|volume = 77|pages = 129–162|s2cid = 12886462}}</ref>
 
 
=== क्वांटम एल्गोरिथ्म ===
=== क्वांटम एल्गोरिथ्म ===
एल्गोरिदम इनपुट हैं <math> A_1 ... A_m, C , b_1 ... b_m</math> और समाधान के ट्रेस वर्ग, सटीक और इष्टतम मान (इष्टतम बिंदु पर उद्देश्य फ़ंक्शन का मान) के बारे में पैरामीटर।
प्रारूप इनपुट <math> A_1 ... A_m, C , b_1 ... b_m</math> हैं और समाधान के चिह्न वर्ग, त्रुटिहीन और उत्तम मान (उत्तम बिंदु पर उद्देश्य कार्य का मान) के बारे में पैरामीटर होता है।


क्वांटम एल्गोरिथ्म<ref>{{cite arXiv|last1=Brandao|first1=Fernando G. S. L.|last2=Svore|first2=Krysta|author2-link= Krysta Svore |title=Quantum Speed-ups for Semidefinite Programming|eprint=1609.05537|class=quant-ph|year=2016}}</ref> कई पुनरावृत्तियों के होते हैं। प्रत्येक पुनरावृत्ति में, यह एक गणितीय अनुकूलन # व्यवहार्यता समस्या को हल करता है, अर्थात्, निम्नलिखित स्थितियों को संतुष्ट करने वाला कोई भी समाधान ढूंढता है (दहलीज देकर <math>t</math>):
क्वांटम एल्गोरिथ्म<ref>{{cite arXiv|last1=Brandao|first1=Fernando G. S. L.|last2=Svore|first2=Krysta|author2-link= Krysta Svore |title=Quantum Speed-ups for Semidefinite Programming|eprint=1609.05537|class=quant-ph|year=2016}}</ref> कई पुनरावृत्तियों के होते हैं। प्रत्येक पुनरावृत्ति में, यह गणितीय अनुकूलन के द्वारा व्यवहार्यता स्थितिको हल करता है, अर्थात्, निम्नलिखित स्थितियों को संतुष्ट करने वाले कोई भी समाधान की खोज करता है (सीमा <math>t</math> देकर)


:<math>
:<math>
Line 63: Line 61:
\end{array}
\end{array}
</math>
</math>
प्रत्येक पुनरावृत्ति में, एक अलग दहलीज <math>t</math> चुना जाता है, और एल्गोरिथ्म या तो एक समाधान का उत्पादन करता है <math>X</math> ऐसा है कि <math> \langle C, X\rangle_{\mathbb{S}^n} \leq t</math> (और अन्य बाधाएं भी संतुष्ट हैं) या एक संकेत है कि ऐसा कोई समाधान मौजूद नहीं है। एल्गोरिदम न्यूनतम सीमा खोजने के लिए बाइनरी खोज करता है <math>t</math> जिसके लिए एक समाधान <math>X</math> अभी भी मौजूद है: यह एसडीपी समस्या का न्यूनतम समाधान देता है।
प्रत्येक पुनरावृत्ति में, अलग सीमा <math>t</math> को चुना जाता है और एल्गोरिथ्म (कलन विधि) या तो समाधान <math>X</math> का उत्पादन करता है जिससे कि <math> \langle C, X\rangle_{\mathbb{S}^n} \leq t</math> (और अन्य बाधाएं भी संतुष्ट हैं) इसका संकेत है कि ऐसा कोई समाधान उपस्तिथ नहीं है जो प्रारूप न्यूनतम सीमा <math>t</math> खोजने के लिए बाइनरी खोज करता है जिसके लिए समाधान <math>X</math> अभी भी उपस्तिथ है यह अर्ध निश्चित कार्यक्रम (SDP) स्थितिका न्यूनतम समाधान देता है।


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


== क्वांटम दहनशील अनुकूलन ==
== क्वांटम दहनशील अनुकूलन ==
[[संयोजन अनुकूलन]] समस्या का उद्देश्य वस्तुओं के सीमित सेट से एक इष्टतम वस्तु खोजना है। समस्या को ऑब्जेक्टिव फ़ंक्शन के अधिकतमकरण के रूप में व्यक्त किया जा सकता है जो बूलियन फ़ंक्शंस का योग है। प्रत्येक [[बूलियन समारोह]] <math>\,C_\alpha \colon \lbrace {0,1 \rbrace}^n \rightarrow \lbrace {0,1} \rbrace </math> इनपुट के रूप में प्राप्त करता है <math>n</math>-बिट स्ट्रिंग <math>z = z_1 z_2 \ldots z_n</math> और आउटपुट के रूप में एक बिट (0 या 1) देता है। कॉम्बिनेटरियल ऑप्टिमाइज़ेशन की समस्या <math>n</math> बिट्स और <math>m</math> खंड एक खोज रहा है <math>n</math>-बिट स्ट्रिंग <math>z</math> जो कार्य को अधिकतम करता है
[[संयोजन अनुकूलन]] स्थितिका उद्देश्य वस्तुओं के सीमित चुनाव से उत्तम वस्तु को खोजना है। स्थितिको ऑब्जेक्टिव कार्य के अधिकतमकरण के रूप में व्यक्त किया जा सकता है जो बूलियन कार्यो का योग है। प्रत्येक [[बूलियन समारोह]] <math>\,C_\alpha \colon \lbrace {0,1 \rbrace}^n \rightarrow \lbrace {0,1} \rbrace </math> इनपुट के रूप में प्राप्त करता है <math>n</math>-बिट शृंखला <math>z = z_1 z_2 \ldots z_n</math> और आउटपुट के रूप में बिट (0 या 1) देता है। संयोजन विश्राम की स्थिति<math>n</math> बिट्स और <math>m</math> खंड खोज रहा है <math>n</math>-बिट शृंखला <math>z</math> जो कार्य को अधिकतम करता है।
:<math>
:<math>
C(z) = \sum_{\alpha=1}^m C_\alpha(z)
C(z) = \sum_{\alpha=1}^m C_\alpha(z)
</math>
</math>
सन्निकटन एल्गोरिथम अनुकूलन समस्या का अनुमानित समाधान खोजने का एक तरीका है, जो अक्सर [[एनपी कठिन]] होता है। कॉम्बिनेटरियल ऑप्टिमाइज़ेशन समस्या का अनुमानित समाधान एक स्ट्रिंग है <math> z </math> जो अधिकतम करने के करीब है <math> C(z) </math>.
सन्निकटन एल्गोरिथम अनुकूलन स्थितिका अनुमानित समाधान खोजने की विधि है, जो अधिकांशतः [[एनपी कठिन]] होता है। संयोजन विश्राम स्थितिका अनुमानित समाधान शृंखला <math> z </math> है जो अधिकतम <math> C(z) </math> करने के समीप है।


=== क्वांटम अनुमानित अनुकूलन एल्गोरिदम ===
=== क्वांटम अनुमानित अनुकूलन प्रारूप ===
संयोजी अनुकूलन के लिए, क्वांटम अनुमानित अनुकूलन एल्गोरिथम (QAOA)<ref>{{cite arXiv|last1=Farhi|first1=Edward|last2=Goldstone|first2=Jeffrey|last3=Gutmann|first3=Sam|title=A Quantum Approximate Optimization Algorithm|eprint=1411.4028|class=quant-ph|year=2014}}</ref> संक्षेप में किसी भी ज्ञात बहुपद समय शास्त्रीय एल्गोरिथ्म (एक निश्चित समस्या के लिए) की तुलना में बेहतर सन्निकटन अनुपात था,<ref>{{cite arXiv|last1=Farhi|first1=Edward|last2=Goldstone|first2=Jeffrey|last3=Gutmann|first3=Sam|title=A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem|eprint=1412.6062|class=quant-ph|year=2014}}</ref> जब तक एक अधिक प्रभावी शास्त्रीय एल्गोरिथम प्रस्तावित नहीं किया गया था।<ref>{{cite arXiv|last1=Barak|first1=Boaz|last2=Moitra|first2=Ankur|last3=O'Donnell|first3=Ryan|last4=Raghavendra|first4=Prasad|last5=Regev|first5=Oded|last6=Steurer|first6=David|last7=Trevisan|first7=Luca|last8=Vijayaraghavan|first8=Aravindan|last9=Witmer|first9=David|last10=Wright|first10=John|title=Beating the random assignment on constraint satisfaction problems of bounded degree|eprint=1505.03424|class=cs.CC|year=2015}}</ref> क्वांटम एल्गोरिथम की सापेक्ष गति एक खुला शोध प्रश्न है।
संयोजी अनुकूलन के लिए, क्वांटम अनुमानित अनुकूलन एल्गोरिथम (क्यूएओए)<ref>{{cite arXiv|last1=Farhi|first1=Edward|last2=Goldstone|first2=Jeffrey|last3=Gutmann|first3=Sam|title=A Quantum Approximate Optimization Algorithm|eprint=1411.4028|class=quant-ph|year=2014}}</ref> संक्षेप में किसी भी ज्ञात बहुपद समय मौलिक एल्गोरिथ्म (कलन विधि) (निश्चित स्थितिके लिए) की तुलना में उत्तम सन्निकटन अनुपात होता था,<ref>{{cite arXiv|last1=Farhi|first1=Edward|last2=Goldstone|first2=Jeffrey|last3=Gutmann|first3=Sam|title=A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem|eprint=1412.6062|class=quant-ph|year=2014}}</ref> जब तक अधिक प्रभावी मौलिक एल्गोरिथम प्रस्तावित नहीं किया गया था।<ref>{{cite arXiv|last1=Barak|first1=Boaz|last2=Moitra|first2=Ankur|last3=O'Donnell|first3=Ryan|last4=Raghavendra|first4=Prasad|last5=Regev|first5=Oded|last6=Steurer|first6=David|last7=Trevisan|first7=Luca|last8=Vijayaraghavan|first8=Aravindan|last9=Witmer|first9=David|last10=Wright|first10=John|title=Beating the random assignment on constraint satisfaction problems of bounded degree|eprint=1505.03424|class=cs.CC|year=2015}}</ref> क्वांटम एल्गोरिथम की सापेक्ष गति का खुला शोध प्रश्न है।


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


2020 में, यह दिखाया गया था कि क्यूएओए एक समस्या की [[बाधा (गणित)]] के अनुपात पर [[चर (गणित)]] (समस्या घनत्व) के अनुपात पर एक मजबूत निर्भरता प्रदर्शित करता है, जो संबंधित हानि फ़ंक्शन को कम करने के लिए एल्गोरिथम की क्षमता पर सीमित प्रतिबंध लगाता है।<ref name=":0">{{Cite journal|last1=Akshay|first1=V.|last2=Philathong|first2=H.|last3=Morales|first3=M. E. S.|last4=Biamonte|first4=J. D.|date=2020-03-05|title=Reachability Deficits in Quantum Approximate Optimization|journal=Physical Review Letters|volume=124|issue=9|pages=090504|doi=10.1103/PhysRevLett.124.090504|pmid=32202873|arxiv=1906.11259|bibcode=2020PhRvL.124i0504A|s2cid=195699685}}</ref>
सन् 2020 में, यह दिखाया गया था कि क्वांटम अनुमानित अनुकूलन एल्गोरिथम (क्यूएओए) स्थितिकी [[बाधा (गणित)]] के अनुपात पर [[चर (गणित)]] (स्थितिघनत्व) के अनुपात पर मजबूत निर्भरता प्रदर्शित करता है, जो संबंधित हानि कार्य को कम करने के लिए एल्गोरिथम की क्षमता पर सीमित प्रतिबंध लगाता है।<ref name=":0">{{Cite journal|last1=Akshay|first1=V.|last2=Philathong|first2=H.|last3=Morales|first3=M. E. S.|last4=Biamonte|first4=J. D.|date=2020-03-05|title=Reachability Deficits in Quantum Approximate Optimization|journal=Physical Review Letters|volume=124|issue=9|pages=090504|doi=10.1103/PhysRevLett.124.090504|pmid=32202873|arxiv=1906.11259|bibcode=2020PhRvL.124i0504A|s2cid=195699685}}</ref>
जल्द ही यह मान लिया गया कि QAOA प्रक्रिया का एक सामान्यीकरण अनिवार्य रूप से एक अंतर्निहित ग्राफ पर एक निरंतर-समय क्वांटम वॉक का एक वैकल्पिक अनुप्रयोग है, जिसके बाद प्रत्येक समाधान स्थिति पर गुणवत्ता-निर्भर चरण बदलाव लागू होता है। इस सामान्यीकृत QAOA को QWOA (क्वांटम वॉक-बेस्ड ऑप्टिमाइज़ेशन एल्गोरिथम) कहा गया।<ref>{{Cite journal|last1=Marsh|first1=S.|last2=Wang|first2=J. B.|date=2020-06-08|title=Combinatorial optimization via highly efficient quantum walks|journal=Physical Review Research|volume=2|issue=2|pages=023302|doi=10.1103/PhysRevResearch.2.023302|arxiv=1912.07353 |bibcode=2020PhRvR...2b3302M|s2cid=216080740}}</ref>
कागज में arXiv को प्रस्तुत क्वांटम कम्प्यूटेशनल वर्चस्व के लिए कितने qubits की आवश्यकता है,<ref>{{Cite journal|last1=Dalzell|first1=Alexander M.|last2=Harrow|first2=Aram W.|last3=Koh|first3=Dax Enshan|last4=La Placa|first4=Rolando L.|date=2020-05-11|title=How many qubits are needed for quantum computational supremacy?|journal=Quantum|volume=4|pages=264|doi=10.22331/q-2020-05-11-264|arxiv=1805.05224|issn=2521-327X|doi-access=free}}</ref> लेखकों का निष्कर्ष है कि 420 [[qubits]] और 500 कांस्ट्रेंट (गणित) के साथ एक QAOA सर्किट को अत्याधुनिक [[सुपर कंप्यूटर]] पर चल रहे शास्त्रीय सिमुलेशन एल्गोरिदम का उपयोग करके अनुकरण करने के लिए कम से कम एक शताब्दी की आवश्यकता होगी ताकि आवश्यकता हो और पर्याप्तता # [[क्वांटम वर्चस्व]] के लिए पर्याप्तता।


शास्त्रीय एल्गोरिदम के साथ क्यूएओए की एक कठोर तुलना गहराई पर अनुमान दे सकती है <math> p </math> और क्वांटम लाभ के लिए आवश्यक qubits की संख्या। क्यूएओए और [[अधिकतम कट]] एल्गोरिद्म के अध्ययन से पता चलता है <math>p>11</math> स्केलेबल लाभ के लिए आवश्यक है।<ref name="Lykov Wurtz Poole Saffman p. ">{{cite arXiv | last1=Lykov | first1=Danylo | last2=Wurtz | first2=Jonathan | last3=Poole | first3=Cody | last4=Saffman | first4=Mark | last5=Noel | first5=Tom | last6=Alexeev | first6=Yuri | title=Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm | year=2022 | class=quant-ph | eprint=2206.03579 }}</ref>
जल्द ही यह मान लिया गया कि क्यूएओए प्रक्रिया का सामान्यीकरण अनिवार्य रूप से अंतर्निहित ग्राफ पर निरंतर-समय क्वांटम वॉक का वैकल्पिक अनुप्रयोग है, जिसके पश्चात् प्रत्येक समाधान स्थिति पर गुणवत्ता-निर्भर चरण बदलाव प्रायुक्त होता है। इस सामान्यीकृत क्यूएओए को QWOA (क्वांटम वॉक-बेस्ड ऑप्टिमाइज़ेशन एल्गोरिथम) कहा गया।<ref>{{Cite journal|last1=Marsh|first1=S.|last2=Wang|first2=J. B.|date=2020-06-08|title=Combinatorial optimization via highly efficient quantum walks|journal=Physical Review Research|volume=2|issue=2|pages=023302|doi=10.1103/PhysRevResearch.2.023302|arxiv=1912.07353 |bibcode=2020PhRvR...2b3302M|s2cid=216080740}}</ref>


कागज में arXiv को प्रस्तुत क्वांटम कम्प्यूटेशनल वर्चस्व के लिए कितने क्वांटम बिट (क्युबिट्स) की आवश्यकता होती है,<ref>{{Cite journal|last1=Dalzell|first1=Alexander M.|last2=Harrow|first2=Aram W.|last3=Koh|first3=Dax Enshan|last4=La Placa|first4=Rolando L.|date=2020-05-11|title=How many qubits are needed for quantum computational supremacy?|journal=Quantum|volume=4|pages=264|doi=10.22331/q-2020-05-11-264|arxiv=1805.05224|issn=2521-327X|doi-access=free}}</ref> लेखकों का निष्कर्ष है कि 420 [[qubits|क्वांटम बिट (क्युबिट्स)]] और 500 कांस्ट्रेंट (गणित) के साथ क्यूएओए विद्युत परिपथ को अत्याधुनिक [[सुपर कंप्यूटर]] पर चल रहे मौलिक सतत अनुकरण प्रारूप का उपयोग करके अनुकरण करने के लिए कम से कम शताब्दी की आवश्यकता होगी जिससे कि इसकी आवश्यकता हो और [[क्वांटम वर्चस्व]] के लिए पर्याप्त हो।


मौलिक प्रारूप के साथ क्वांटम अनुमानित अनुकूलन एल्गोरिथम (क्यूएओए) की कठोर तुलना गहराई पर अनुमान दे सकती है <math> p </math> और क्वांटम लाभ के लिए आवश्यक क्वांटम बिट की संख्या की आवश्यकता होती है। क्वांटम अनुमानित अनुकूलन एल्गोरिथम (क्यूएओए) और [[अधिकतम कट]] एल्गोरिथम के अध्ययन से पता चलता है <math>p>11</math> स्केलेबल लाभ के लिए आवश्यक है।<ref name="Lykov Wurtz Poole Saffman p.">{{cite arXiv | last1=Lykov | first1=Danylo | last2=Wurtz | first2=Jonathan | last3=Poole | first3=Cody | last4=Saffman | first4=Mark | last5=Noel | first5=Tom | last6=Alexeev | first6=Yuri | title=Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm | year=2022 | class=quant-ph | eprint=2206.03579 }}</ref>
== यह भी देखें ==
== यह भी देखें ==
* [[स्थिरोष्म क्वांटम संगणना]]
* [[स्थिरोष्म क्वांटम संगणना]]
Line 94: Line 92:


{{Quantum information}}
{{Quantum information}}
[[Category: क्वांटम एल्गोरिदम]]


[[Category: Machine Translated Page]]
[[Category:Collapse templates]]
[[Category:Created On 13/02/2023]]
[[Category:Created On 13/02/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:क्वांटम एल्गोरिदम]]

Latest revision as of 19:52, 20 February 2023

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

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

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

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

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

जो एल्गोरिथ्म (कलन विधि) इनपुट के रूप में दिया गया है आंकड़े अंक और निरंतर कार्य . प्रारूप आउटपुट के रूप में सतत कार्य प्राप्त करता है और देता है यह का रैखिक संयोजन है।

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

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

जहां हम परिभाषित करते हैं निम्नलिखित मैट्रिक्स होने के लिए,

क्वांटम कम से कम वर्ग फिटिंग एल्गोरिथम[2] समीकरणों की रैखिक प्रणालियों के लिए हैरो, हासिडिम और लॉयड (HHL) के क्वांटम एल्गोरिथम के संस्करण का उपयोग करता है और गुणांकों को आउटपुट करता है और उचित गुणवत्ता का अनुमान . इसमें तीन उप-दैनिकि होते हैं, सूडो-मैट्रिक्स उलटा ऑपरेशन करने के लिए एल्गोरिथम, उचित गुणवाता के आकलन के लिए नियमित और उचित पैरामीटर्स सीखने के लिए एल्गोरिथम का प्रयोग करता है।

जिससे कि क्वांटम एल्गोरिथम मुख्य रूप से हैरो, हासिडिम और लॉयड (HHL) एल्गोरिथम पर आधारित है, यह घातीय सुधार का सुझाव देता है।[3] स्थितियों में जहां विरल मैट्रिक्स है और दोनों की स्थिति संख्या (अर्थात्, सबसे बड़े और सबसे छोटे एइगेन्वलुएस ​​​​के मध्य का अनुपात) और छोटा होता है।

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

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

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

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

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

प्रारूप इनपुट हैं और समाधान के चिह्न वर्ग, त्रुटिहीन और उत्तम मान (उत्तम बिंदु पर उद्देश्य कार्य का मान) के बारे में पैरामीटर होता है।

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

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

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

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

संयोजन अनुकूलन स्थितिका उद्देश्य वस्तुओं के सीमित चुनाव से उत्तम वस्तु को खोजना है। स्थितिको ऑब्जेक्टिव कार्य के अधिकतमकरण के रूप में व्यक्त किया जा सकता है जो बूलियन कार्यो का योग है। प्रत्येक बूलियन समारोह इनपुट के रूप में प्राप्त करता है -बिट शृंखला और आउटपुट के रूप में बिट (0 या 1) देता है। संयोजन विश्राम की स्थिति बिट्स और खंड खोज रहा है -बिट शृंखला जो कार्य को अधिकतम करता है।

सन्निकटन एल्गोरिथम अनुकूलन स्थितिका अनुमानित समाधान खोजने की विधि है, जो अधिकांशतः एनपी कठिन होता है। संयोजन विश्राम स्थितिका अनुमानित समाधान शृंखला है जो अधिकतम करने के समीप है।

क्वांटम अनुमानित अनुकूलन प्रारूप

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

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

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

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

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

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

यह भी देखें

संदर्भ

  1. Moll, Nikolaj; Barkoutsos, Panagiotis; Bishop, Lev S.; Chow, Jerry M.; Cross, Andrew; Egger, Daniel J.; Filipp, Stefan; Fuhrer, Andreas; Gambetta, Jay M.; Ganzhorn, Marc; Kandala, Abhinav; Mezzacapo, Antonio; Müller, Peter; Riess, Walter; Salis, Gian; Smolin, John; Tavernelli, Ivano; Temme, Kristan (2018). "Quantum optimization using variational algorithms on near-term quantum devices". Quantum Science and Technology. 3 (3): 030503. arXiv:1710.01022. Bibcode:2018QS&T....3c0503M. doi:10.1088/2058-9565/aab822. S2CID 56376912.
  2. Wiebe, Nathan; Braun, Daniel; Lloyd, Seth (2 August 2012). "Quantum Algorithm for Data Fitting". Physical Review Letters. 109 (5): 050505. arXiv:1204.5242. Bibcode:2012PhRvL.109e0505W. doi:10.1103/PhysRevLett.109.050505. PMID 23006156. S2CID 118439810.
  3. Montanaro, Ashley (12 January 2016). "Quantum algorithms: an overview". npj Quantum Information. 2: 15023. arXiv:1511.04206. Bibcode:2016npjQI...215023M. doi:10.1038/npjqi.2015.23. S2CID 2992738.
  4. Ramana, Motakuri V. (1997). "An exact duality theory for semidefinite programming and its complexity implications". Mathematical Programming. 77: 129–162. doi:10.1007/BF02614433. S2CID 12886462.
  5. Brandao, Fernando G. S. L.; Svore, Krysta (2016). "Quantum Speed-ups for Semidefinite Programming". arXiv:1609.05537 [quant-ph].
  6. Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (2014). "A Quantum Approximate Optimization Algorithm". arXiv:1411.4028 [quant-ph].
  7. Farhi, Edward; Goldstone, Jeffrey; Gutmann, Sam (2014). "A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem". arXiv:1412.6062 [quant-ph].
  8. Barak, Boaz; Moitra, Ankur; O'Donnell, Ryan; Raghavendra, Prasad; Regev, Oded; Steurer, David; Trevisan, Luca; Vijayaraghavan, Aravindan; Witmer, David; Wright, John (2015). "Beating the random assignment on constraint satisfaction problems of bounded degree". arXiv:1505.03424 [cs.CC].
  9. Akshay, V.; Philathong, H.; Morales, M. E. S.; Biamonte, J. D. (2020-03-05). "Reachability Deficits in Quantum Approximate Optimization". Physical Review Letters. 124 (9): 090504. arXiv:1906.11259. Bibcode:2020PhRvL.124i0504A. doi:10.1103/PhysRevLett.124.090504. PMID 32202873. S2CID 195699685.
  10. Marsh, S.; Wang, J. B. (2020-06-08). "Combinatorial optimization via highly efficient quantum walks". Physical Review Research. 2 (2): 023302. arXiv:1912.07353. Bibcode:2020PhRvR...2b3302M. doi:10.1103/PhysRevResearch.2.023302. S2CID 216080740.
  11. Dalzell, Alexander M.; Harrow, Aram W.; Koh, Dax Enshan; La Placa, Rolando L. (2020-05-11). "How many qubits are needed for quantum computational supremacy?". Quantum. 4: 264. arXiv:1805.05224. doi:10.22331/q-2020-05-11-264. ISSN 2521-327X.
  12. Lykov, Danylo; Wurtz, Jonathan; Poole, Cody; Saffman, Mark; Noel, Tom; Alexeev, Yuri (2022). "Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm". arXiv:2206.03579 [quant-ph].