1क्वांटम आर्टिफिशियल इंटेलिजेंस लेबोरेटरी (QuAIL), NASA एम्स रिसर्च सेंटर, मोफेट फील्ड, CA
2यूएसआरए रिसर्च इंस्टीट्यूट फॉर एडवांस्ड कंप्यूटर साइंस (आरआईएसीएस), माउंटेन व्यू, सीए
3क्वांटम सूचना और संगणना के लिए बर्कले केंद्र, कैलिफोर्निया विश्वविद्यालय, बर्कले, CA
4कंप्यूटर विज्ञान विभाग, शिकागो विश्वविद्यालय, शिकागो, IL
इस पेपर को दिलचस्प खोजें या चर्चा करना चाहते हैं? Scate या SciRate पर एक टिप्पणी छोड़ दें.
सार
हम लगभग अधिकतम $k$XOR को हल करने के लिए स्थानीय एल्गोरिदम की शक्ति पर विचार करते हैं, जो पहले शास्त्रीय और क्वांटम एल्गोरिदम (MaxCut और Max E3LIN2) के साथ अध्ययन की गई दो बाधा संतुष्टि समस्याओं का एक सामान्यीकरण है। मैक्स $k$XOR में प्रत्येक बाधा बिल्कुल $k$ चर और एक समता बिट का XOR है। यादृच्छिक संकेतों (समानता) या कोई अतिव्यापी खंड और प्रति चर $D+1$ खंड वाले उदाहरणों पर, हम फरही एट अल [arXiv: 1] से गहराई -1411.4028 क्यूएओए के अपेक्षित संतोषजनक अंश की गणना करते हैं और इसके सामान्यीकरण के साथ तुलना करते हैं Hirvonen et al [arXiv:1402.2543] से स्थानीय दहलीज एल्गोरिथ्म। विशेष रूप से, क्वांटम एल्गोरिथ्म $k$$gt$$4$ के लिए थ्रेशोल्ड एल्गोरिथम से बेहतर प्रदर्शन करता है।
दूसरी ओर, हम इस समस्या पर कम्प्यूटेशनल क्वांटम लाभ प्राप्त करने के लिए क्यूएओए के लिए संभावित कठिनाइयों को उजागर करते हैं। हम पहले लगभग सभी बड़े यादृच्छिक नियमित अधिकतम $k$XOR उदाहरणों के अधिकतम संतोषजनक अंश पर एक तंग ऊपरी सीमा की गणना करते हैं, जो कि एक माध्य-क्षेत्र $k$-स्पिन ग्लास के जमीनी राज्य ऊर्जा घनत्व $P(k)$ की संख्यात्मक गणना करके करते हैं। arXiv:1606.02365]. दोनों एक-स्थानीय एल्गोरिदम के प्रदर्शन की तुलना में ऊपरी सीमा $k$ के साथ बहुत तेजी से बढ़ती है। हम कम-गहराई वाले क्वांटम सर्किट (QAOA सहित) के लिए एक नए अवरोध परिणाम की पहचान करते हैं, जब $k=3$, जब $k=1910.08980$ होता है, तो Bravyi et al [arXiv:2] के परिणाम को सामान्य किया जाता है। हम अनुमान लगाते हैं कि सभी $k$ के लिए एक समान बाधा मौजूद है।
विशेष रुप से प्रदर्शित छवि: थ्रेशोल्ड एल्गोरिथ्म के संतोषजनक अंश (प्रदर्शन) की तुलना और मैक्स kXOR के लिए गहराई -1 QAOA बड़े $D$ (और $D gg k$) पर। QAOA के लिए निरंतर $C_k$ थ्रेशोल्ड एल्गोरिथम की तुलना में $k$ के साथ अधिक तेज़ी से बढ़ता है। हालांकि थ्रेशोल्ड एल्गोरिथम {1}$ में $k के लिए डेप्थ-2,3,4 QAOA से बेहतर प्रदर्शन करता है, अन्य सभी k पर, QAOA बेहतर एल्गोरिथम है।
[एम्बेडेड सामग्री]
► BibTeX डेटा
► संदर्भ
[1] A. औफिंगर और W.-K. चेन। पेरिस उपायों के गुणों पर। arXiv:1303.3573, doi:10.1007/s00440-014-0563-y.
https: / / doi.org/ 10.1007 / s00440-014-0563-y
arXiv: 1303.3573
[2] A. औफिंगर और W.-K. चेन। पेरिसी फॉर्मूले में एक अद्वितीय मिनिमाइज़र है। गणितीय भौतिकी में संचार, 335(3):1429-1444, नवंबर 2014। arXiv:1402.5132, doi:10.1007/S00220-014-2254-z।
https: / / doi.org/ 10.1007 / s00220-014-2254-z
arXiv: 1402.5132
[3] A. औफिंगर और W.-K. चेन। मिश्रित पी-स्पिन मॉडल में ग्राउंड स्टेट एनर्जी के लिए पेरिस फॉर्मूला। arXiv:1606.05335, doi:10.1214/16-aop1173.
https:///doi.org/10.1214/16-aop1173
arXiv: 1606.05335
[4] एई अलाउई और ए मोंटानारी। माध्य क्षेत्र स्पिन चश्मे में एल्गोरिथम थ्रेसहोल्ड। arXiv: 2009.11481।
arXiv: 2009.11481
[5] एई अलाउई, ए। मोंटानारी, और एम। सेल्के। मीन-फील्ड स्पिन ग्लास का अनुकूलन। arXiv:2001.00904, doi:10.1214/21-aop1519.
https:///doi.org/10.1214/21-aop1519
arXiv: 2001.00904
[6] एस. ब्रावी, ए. क्लीश, आर. कोएनिग, और ई. तांग। समरूपता संरक्षण से राज्य की तैयारी और परिवर्तनशील अनुकूलन में बाधाएं। arXiv प्रीप्रिंट, 2019। arXiv:1910.08980।
https: / / doi.org/ 10.1103 / PhysRevLett.125.260505
arXiv: 1910.08980
[7] बी. बराक और के. मारवाह। उच्च परिधि वाले ग्राफ़ पर अधिकतम कटौती के लिए शास्त्रीय एल्गोरिदम और क्वांटम सीमाएं। arXiv:2106.05900, doi:10.4230/LIPics.ITCS.2022.14.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2022.14
arXiv: 2106.05900
[8] बी. बराक, ए. मोइत्रा, आर. ओ'डोनेल, एट अल। बाउंड डिग्री की बाधा संतुष्टि समस्याओं पर रैंडम असाइनमेंट को हराना। arXiv: 1505.03424।
arXiv: 1505.03424
[9] डब्ल्यू.-के. चेन, डी. गामार्निक, डी. पंचेंको, और एम. रहमान। अधिकतम-कट समस्याओं के एक वर्ग के लिए स्थानीय एल्गोरिदम की उप-अनुकूलता। द एनल्स ऑफ़ प्रोबेबिलिटी, 47(3), मई 2019। arXiv:1707.05386, doi:10.1214/18-aop1291।
https:///doi.org/10.1214/18-aop1291
arXiv: 1707.05386
[10] सी.-एन. चाउ, पीजे लव, जेएस संधू, और जे. शी। रैंडम मैक्स-के-एक्सओआर और परे पर स्थानीय क्वांटम एल्गोरिदम की सीमाएं। arXiv:2108.06049।
arXiv: 2108.06049
[11] ए. क्रिसंती और टी. रिज़ो। शेरिंगटन-किर्कपैट्रिक मॉडल के $infty$-प्रतिकृति समरूपता तोड़ने वाले समाधान का विश्लेषण। फिजिकल रिव्यू ई, 65(4), अप्रैल 2002. arXiv:cond-mat/0111037, doi:10.1103/physreve.65.046137.
https: / / doi.org/ 10.1103 / physreve.65.046137
arXiv: cond चटाई / 0111037
[12] बी डेरिडा। यादृच्छिक-ऊर्जा मॉडल: अव्यवस्थित प्रणालियों का बिल्कुल हल करने योग्य मॉडल। भौतिक. रेव. बी, 24:2613-2626, सितंबर 1981।
https: / / doi.org/ 10.1103 / PhysRevB.24.2613
[13] ए। डेम्बो, ए। मोंटानारी, और एस। सेन। विरल यादृच्छिक रेखांकन के चरम कटौती। संभावना के इतिहास, 45(2):1190-1217, 2017. arXiv:1503.03923, doi:10.1214/15-aop1084।
https:///doi.org/10.1214/15-aop1084
arXiv: 1503.03923
[14] एल एल्डर और एडब्ल्यू हैरो। स्थानीय हैमिल्टन जिनके जमीनी राज्य अनुमानित हैं। 2017 IEEE 58वां वार्षिक संगोष्ठी ऑन फाउंडेशन ऑफ कंप्यूटर साइंस (FOCS), अक्टूबर 2017.
https: / / doi.org/ 10.1109 / focs.2017.46
arXiv: 1510.02082
[15] ई. फरही, जे. गोल्डस्टोन, और एस. गुटमैन। एक क्वांटम अनुमानित अनुकूलन एल्गोरिथ्म। arXiv:1411.4028.
arXiv: 1411.4028
[16] ई. फरही, जे. गोल्डस्टोन, और एस. गुटमैन। एक क्वांटम अनुमानित अनुकूलन एल्गोरिथ्म एक बाध्य घटना बाधा समस्या पर लागू होता है। arXiv:1412.6062।
arXiv: 1412.6062
[17] ई. फरही, डी. गमार्निक, और एस. गुटमैन। क्वांटम अनुमानित अनुकूलन एल्गोरिथ्म को पूरे ग्राफ को देखने की जरूरत है: एक विशिष्ट मामला। आर्क्सिव: 2004.09002।
arXiv: 2004.09002
[18] जे फ्राइडमैन। एलोन के दूसरे स्वदेशी अनुमान और संबंधित समस्याओं का प्रमाण। arXiv:cs/0405020, doi:10.1090/memo/0910.
https://doi.org/10.1090/memo/0910
arXiv: सीएस / 0405020
[19] एस. हैडफ़ील्ड. वैज्ञानिक कंप्यूटिंग और अनुमानित अनुकूलन के लिए क्वांटम एल्गोरिदम। कोलंबिया विश्वविद्यालय, 2018, arXiv: 1805.03265।
arXiv: 1805.03265
[20] जे हस्ताद। कुछ इष्टतम अनुपयुक्तता परिणाम। जर्नल ऑफ़ द एसीएम (JACM), 48(4):798–859, 2001. doi:10.1145/258533.258536, URL http://www.cs.umd.edu/gasarch/BLOGPAPERS/max3satl। पीडीएफ।
https: / / doi.org/ 10.1145 / १.१३,९४,२०८
http://www.cs.umd.edu/~gasarch/BLOGPAPERS/max3satl.pdf
[21] एमबी हेस्टिंग्स। हैमिल्टनियन आने के लिए तुच्छ कम ऊर्जा राज्य, और क्वांटम पीसीपी अनुमान। क्वांटम सूचना और संगणना, 13, 2013. arXiv:1201.3387, doi:10.26421/qic13.5-6-3।
https: / / doi.org/ 10.26421 / qic13.5-6-3
arXiv: 1201.3387
[22] एमबी हेस्टिंग्स। शास्त्रीय और क्वांटम बाध्य गहराई सन्निकटन एल्गोरिदम। arXiv:1905.07047, doi:10.26421/qic19.13-14-3.
https: / / doi.org/ 10.26421 / qic19.13-14-3
arXiv: 1905.07047
[23] WW Ho और TH Hsieh। गैर-तुच्छ क्वांटम राज्यों का कुशल परिवर्तनशील अनुकरण। arXiv:1803.00026, doi:10.21468/Scipostphys.6.3.029।
https: / / doi.org/ 10.21468 / scipostphys.6.3.029
arXiv: 1803.00026
[24] जे। हिरवोनन, जे। रयबिकी, एस। श्मिड, और जे। सुमेला। त्रिभुज-मुक्त ग्राफ़ पर स्थानीय एल्गोरिदम के साथ बड़े कट। कॉम्बिनेटरिक्स का इलेक्ट्रॉनिक जर्नल, पृष्ठ P4–21, 2017. arXiv:1402.2543, doi:10.37236/6862।
https: / / doi.org/ 10.37236 / १.१३,९४,२०८
arXiv: 1402.2543
[25] सीवाई-वाई। लिन और वाई झू। बाध्य डिग्री के साथ बाधा संतुष्टि समस्याओं के विशिष्ट उदाहरणों पर क्यूएओए का प्रदर्शन। arXiv:1601.01744।
arXiv: 1601.01744
[26] के मारवाह। स्थानीय शास्त्रीय MAX-CUT एल्गोरिथम उच्च परिधि वाले नियमित ग्राफ़ पर $p=2$ QAOA से बेहतर प्रदर्शन करता है। क्वांटम, 5:437, अप्रैल 2021। arXiv:2101.05513, doi:10.22331/q-2021-04-20-437।
https://doi.org/10.22331/q-2021-04-20-437
arXiv: 2101.05513
[27] ए मोंटानारी। शेरिंगटन-किर्कपैट्रिक हैमिल्टनियन का अनुकूलन। arXiv:1812.10897, doi:10.1109/फ़ॉक्स.2019.00087।
https: / / doi.org/ 10.1109 / focs.2019.00087
arXiv: 1812.10897
[28] पी. ओब्ज़ार्स्की और ए. जस्त्र्ज़ब्स्की। 3-वर्दी हाइपरग्राफ का एज-कलरिंग। असतत अनुप्रयुक्त गणित, 217:48-52, 2017, संयुक्त अनुकूलन: सिद्धांत, संगणना, और अनुप्रयोग। डोई:10.1016/जे.डैम.2016.06.009।
https: / / doi.org/ 10.1016 / j.dam.2016.06.009
[29] डी पंचेंको। एसके मॉडल का परिचय। arXiv:1412.0170, doi:10.4310/cdm.2014.v2014.n1.a4।
https://doi.org/10.4310/cdm.2014.v2014.n1.a4
arXiv: 1412.0170
[30] डी पंचेंको। $k$-sat मॉडल पर बड़ी संख्या में खंड हैं। arXiv:1608.06256, doi:10.1002/rsa.20748.
https: / / doi.org/ 10.1002 / rsa.20748
arXiv: 1608.06256
[31] जी पेरिस। स्पिन ग्लास के लिए SK मॉडल के अनुमानित समाधानों का एक क्रम। जर्नल ऑफ फिजिक्स ए: मैथमैटिकल एंड जनरल, 13(4):L115–L121, अप्रैल 1980। doi:10.1088/0305-4470/13/4/009।
https://doi.org/10.1088/0305-4470/13/4/009
[32] दुर्लभ यादृच्छिक हाइपरग्राफ और स्पिन चश्मे पर एस सेन अनुकूलन। arXiv:1606.02365, doi:10.1002/rsa.20774।
https: / / doi.org/ 10.1002 / rsa.20774
arXiv: 1606.02365
[33] आर। शायदुलिन, एस। हैडफील्ड, टी। हॉग, और आई। सफ्रो। शास्त्रीय समरूपता और क्वांटम अनुमानित अनुकूलन एल्गोरिथ्म। क्वांटम सूचना प्रसंस्करण, 20(11):1–28, 2021. arXiv:2012.04713, doi:10.1007/s11128-021-03298-4.
https://doi.org/10.1007/s11128-021-03298-4
arXiv: 2012.04713
[34] एम तालाग्रांड। पेरिस सूत्र। एनल्स ऑफ़ मैथमेटिक्स, 163:221–263, 2006। doi:10.4007/साल.2006.163.221, यूआरएल https://annals.math.princeton.edu/wp-content/uploads/annals-v163 -n1-p04.pdf।
https: / / doi.org/ 10.4007 / annals.2006.163.221
https://annals.math.princeton.edu/wp-content/uploads/annals-v163-n1-p04.pdf
[35] जेड वांग, एस। हैडफील्ड, जेड जियांग, और ईजी रिफेल। मैक्सकट के लिए क्वांटम अनुमानित अनुकूलन एल्गोरिथ्म: एक फर्मोनिक दृश्य। भौतिक. रेव. ए, 97:022304, फरवरी 2018।
https: / / doi.org/ 10.1103 / PhysRevA.97.022304
arXiv: 1706.02998
द्वारा उद्धृत
[1] जोआओ बस्सो, एडवर्ड फरही, कुणाल मारवाह, बेंजामिन विलालोंगा, और लियो झोउ, "लार्ज-गिर्थ रेगुलर ग्राफ़ और शेरिंगटन-किर्कपैट्रिक मॉडल पर मैक्सकट के लिए उच्च गहराई पर क्वांटम अनुमानित अनुकूलन एल्गोरिथ्म", arXiv: 2110.14206.
[2] निकोलस पीडी सवाया, अल्बर्ट टी शमित्ज़, और स्टुअर्ट हैडफ़ील्ड, "असतत अनुकूलन के लिए क्वांटम एल्गोरिदम में ट्रेड-ऑफ़ और डिज़ाइन टूलकिट एन्कोडिंग: रंग, रूटिंग, शेड्यूलिंग, और अन्य समस्याएं", arXiv: 2203.14432.
[3] यश जे. पटेल, सोफीने जेर्बी, थॉमस बैक, और वेड्रान डंजको, "रीइन्फोर्समेंट लर्निंग असिस्टेड रिकर्सिव क्यूएओए", arXiv: 2207.06294.
उपरोक्त उद्धरण से हैं SAO / NASA ADS (अंतिम अद्यतन सफलतापूर्वक 2022-07-26 13:36:03)। सूची अधूरी हो सकती है क्योंकि सभी प्रकाशक उपयुक्त और पूर्ण उद्धरण डेटा प्रदान नहीं करते हैं।
On Crossref की उद्धृत सेवा द्वारा कार्यों का हवाला देते हुए कोई डेटा नहीं मिला (अंतिम प्रयास 2022-07-26 13:36:00)।
यह पत्र क्वांटम में प्रकाशित हुआ है क्रिएटिव कॉमन्स एट्रिब्यूशन 4.0 इंटरनेशनल (CC बाय 4.0) लाइसेंस। कॉपीराइट मूल कॉपीराइट धारकों जैसे लेखकों या उनकी संस्थाओं के पास रहता है।
