क्वांटम सपोर्ट वेक्टर मशीनों की जटिलता

क्वांटम सपोर्ट वेक्टर मशीनों की जटिलता

स्रोत नोड: 3057476

जियान जेन्टिनेटा1,2, अर्ने थॉमसन3,2, डेविड सुटर2, और स्टीफन वोर्नर2

1भौतिकी संस्थान, इकोले पॉलिटेक्निक फ़ेडेरेल डी लॉज़ेन
2आईबीएम क्वांटम, आईबीएम रिसर्च यूरोप - ज्यूरिख
3भौतिकी विभाग, ईटीएच ज्यूरिख

इस पेपर को दिलचस्प खोजें या चर्चा करना चाहते हैं? Scate या SciRate पर एक टिप्पणी छोड़ दें.

सार

क्वांटम सपोर्ट वेक्टर मशीनें कर्नेल फ़ंक्शन को परिभाषित करने के लिए क्वांटम सर्किट का उपयोग करती हैं। यह दिखाया गया है कि यह दृष्टिकोण कुछ डेटा सेटों के लिए किसी भी ज्ञात शास्त्रीय एल्गोरिदम की तुलना में एक सिद्ध घातीय गति प्रदान करता है। ऐसे मॉडलों का प्रशिक्षण उत्तल अनुकूलन समस्या को उसके प्रारंभिक या दोहरे फॉर्मूलेशन के माध्यम से हल करने से मेल खाता है। क्वांटम यांत्रिकी की संभाव्य प्रकृति के कारण, प्रशिक्षण एल्गोरिदम सांख्यिकीय अनिश्चितता से प्रभावित होते हैं, जिसका उनकी जटिलता पर बड़ा प्रभाव पड़ता है। हम दिखाते हैं कि दोहरी समस्या को $O(M^{4.67}/varepsilon^2)$ क्वांटम सर्किट मूल्यांकन में हल किया जा सकता है, जहां $M$ डेटा सेट के आकार को दर्शाता है और $varepsilon$ आदर्श की तुलना में समाधान सटीकता को दर्शाता है सटीक अपेक्षा मूल्यों का परिणाम है, जो केवल सिद्धांत में ही प्राप्य है। हम एक अनुभवजन्य रूप से प्रेरित धारणा के तहत साबित करते हैं कि कर्नेलाइज्ड प्रारंभिक समस्या को वैकल्पिक रूप से $O(min { M^2/varepsilon^6, , 1/varepsilon^{10 } })$ मूल्यांकन में एक ज्ञात शास्त्रीय के सामान्यीकरण को नियोजित करके हल किया जा सकता है। एल्गोरिथ्म को पेगासोस कहा जाता है। अनुभवजन्य परिणाम इन विश्लेषणात्मक जटिलताओं को अनिवार्य रूप से सख्त दर्शाते हैं। इसके अलावा, हम क्वांटम सपोर्ट वेक्टर मशीनों के लिए एक परिवर्तनीय सन्निकटन की जांच करते हैं और दिखाते हैं कि उनका अनुमानी प्रशिक्षण हमारे प्रयोगों में काफी बेहतर स्केलिंग प्राप्त करता है।

क्वांटम समर्थन वेक्टर मशीनें वर्गीकरण समस्याओं के लिए निकट भविष्य में क्वांटम लाभ प्रदर्शित करने के लिए उम्मीदवार हैं। विचार यह है कि एक (उम्मीद है कि उपयोगी) कर्नेल फ़ंक्शन एक कुशल क्वांटम सर्किट द्वारा दिया जाता है जिसका मूल्यांकन करना शास्त्रीय रूप से कठिन है। क्वांटम यांत्रिकी की संभाव्य प्रकृति के कारण ऐसे कर्नेल कार्य सांख्यिकीय अनिश्चितता से प्रभावित होते हैं। इस कार्य में, हम कठोरता से विश्लेषण करते हैं कि यह अनिश्चितता (जिसे शॉट शोर भी कहा जाता है) वर्गीकरण समस्या को हल करने के लिए समग्र कम्प्यूटेशनल जटिलता को कैसे प्रभावित करती है।

► BibTeX डेटा

► संदर्भ

[1] जे. बियामोंटे, पी. विटटेक, एन. पैनकोटी, पी. रेबेंट्रोस्ट, एन. विबे, और एस. लॉयड। क्वांटम मशीन लर्निंग। नेचर, 549(7671):195–202, 2017. डीओआई: 10.1038/नेचर23474।
https: / / doi.org/ 10.1038 / nature23474

[2] वी. हवेलिक, एडी कॉर्कोल्स, के. टेम्मे, एडब्ल्यू हैरो, ए. कंडाला, जेएम चाउ, और जेएम गैम्बेटा। क्वांटम-एन्हांस्ड फीचर स्पेस के साथ पर्यवेक्षित शिक्षण। नेचर, 567(7747):209–212, 2019। डीओआई: 10.1038/​एस41586-019-0980-2।
https:/​/​doi.org/​10.1038/​s41586-019-0980-2

[3] ए. अब्बास, डी. सटर, सी. ज़ौफ़ल, ए. लुच्ची, ए. फिगल्ली, और एस. वोर्नर। क्वांटम तंत्रिका नेटवर्क की शक्ति. नेचर कम्प्यूटेशनल साइंस, 1(जून), 2020। डीओआई: 10.1038/​एस43588-021-00084-1।
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] वाई. लियू, एस. अरुणाचलम, और के. टेम्मे। पर्यवेक्षित मशीन लर्निंग में एक कठोर और मजबूत क्वांटम स्पीड-अप। प्रकृति भौतिकी, 2021। डीओआई: 10.1038/​एस41567-021-01287-जेड।
https: / / doi.org/ 10.1038 / s41567-021-01287-z

[5] एस आरोनसन। बढ़िया प्रिंट पढ़ें. प्रकृति भौतिकी, 11(4):291-293, 2015। डीओआई: 10.1038/एनफिस3272।
https: / / doi.org/ 10.1038 / nphys3272

[6] ई. तांग. सिफ़ारिश प्रणालियों के लिए एक क्वांटम-प्रेरित शास्त्रीय एल्गोरिदम। कंप्यूटिंग के सिद्धांत पर 51वीं वार्षिक एसीएम सिगैक्ट संगोष्ठी की कार्यवाही में, एसटीओसी 2019, पृष्ठ 217-228, न्यूयॉर्क, एनवाई, यूएसए, 2019। एसोसिएशन फॉर कंप्यूटिंग मशीनरी। डीओआई: 10.1145/​3313276.3316310।
https: / / doi.org/ 10.1145 / १.१३,९४,२०८

[7] एन.-एच. चिया, ए. गिलियेन, टी. ली, एच.-एच. लिन, ई. टैंग, और सी. वांग। क्वांटम मशीन लर्निंग को डिक्वांटाइज करने के लिए सैंपलिंग-आधारित सबलाइनियर लो-रैंक मैट्रिक्स अंकगणितीय ढांचा, पृष्ठ 387-400। एसोसिएशन फॉर कंप्यूटिंग मशीनरी, न्यूयॉर्क, एनवाई, यूएसए, 2020। ऑनलाइन उपलब्ध: https://​/doi.org/​10.1145/​3357713.3384314।
https: / / doi.org/ 10.1145 / १.१३,९४,२०८

[8] टी. ली, एस. चक्रवर्ती, और एक्स. वू। रैखिक और कर्नेल-आधारित क्लासिफायर के प्रशिक्षण के लिए सबलाइनियर क्वांटम एल्गोरिदम। मशीन लर्निंग पर अंतर्राष्ट्रीय सम्मेलन में, पृष्ठ 3815-3824। पीएमएलआर, 2019।

[9] एस. थानासिल्प, एस. वांग, एम. सेरेज़ो, और जेड होम्स। क्वांटम कर्नेल विधियों में घातीय एकाग्रता और अप्रशिक्षितता, 2022। DOI: 10.48550/ARXIV.2208.11060।
https://​doi.org/​10.48550/​ARXIV.2208.11060

[10] एस शैलेव-श्वार्ट्ज और एन स्रेब्रो। एसवीएम अनुकूलन: प्रशिक्षण सेट आकार पर विपरीत निर्भरता। मशीन लर्निंग पर 25वें अंतर्राष्ट्रीय सम्मेलन की कार्यवाही, पृष्ठ 928-935, 2008।

[11] ए. थॉमसन. क्वांटम न्यूरल नेटवर्क और क्वांटम सपोर्ट वेक्टर मशीनों की तुलना करना। मास्टर थीसिस, ईटीएच ज्यूरिख, 2021-09-06। डीओआई: 20.500.11850/527559।

[12] बीई बोसेर, आईएम गयोन, और वीएन वाप्निक। इष्टतम मार्जिन क्लासिफायर के लिए एक प्रशिक्षण एल्गोरिदम। कम्प्यूटेशनल लर्निंग थ्योरी पर पांचवीं वार्षिक कार्यशाला की कार्यवाही में, COLT '92, पृष्ठ 144-152, न्यूयॉर्क, एनवाई, यूएसए, 1992। एसोसिएशन फॉर कंप्यूटिंग मशीनरी। डीओआई: 10.1145/​130385.130401।
https: / / doi.org/ 10.1145 / १.१३,९४,२०८

[13] सी. कोर्टेस और वी. वाप्निक। समर्थन-वेक्टर नेटवर्क। मशीन लर्निंग में, पृष्ठ 273-297, 1995।

[14] वीएन वाप्निक। सांख्यिकीय सिद्धांत सीखने की प्रकृति। स्प्रिंगर साइंस+बिजनेस मीडिया, एलएलसी, 2000।

[15] एफ. पेड्रेगोसा एट अल. स्किकिट-लर्न: पायथन में मशीन लर्निंग। जर्नल ऑफ़ मशीन लर्निंग रिसर्च, 12(85):2825–2830, 2011। ऑनलाइन उपलब्ध: http:/​/jmlr.org/​papers/​v12/​pedregosa11a.html।
http:/​/jmlr.org/​papers/​v12/​pedregosa11a.html

[16] एस. बॉयड और एल. वैंडेनबर्गे। उत्तल अनुकूलन. कैम्ब्रिज यूनिवर्सिटी प्रेस, 2004।

[17] एस. शैलेव-श्वार्ट्ज, वाई. सिंगर, एन. स्रेब्रो, और ए. कॉटर। पेगासोस: एसवीएम के लिए प्रारंभिक अनुमानित उप-ग्रेडिएंट सॉल्वर। गणितीय प्रोग्रामिंग, 127(1):3-30, 2011। डीओआई: 10.1007/एस10107-010-0420-4।
https:/​/​doi.org/​10.1007/​s10107-010-0420-4

[18] एमडीएस अनीस एट अल. किस्किट: क्वांटम कंप्यूटिंग के लिए एक ओपन-सोर्स फ्रेमवर्क, 2021। डीओआई: 10.5281/ज़ेनोडो.2573505।
https: / / doi.org/ 10.5281 / zenodo.2573505

[19] पी. रेबेंट्रोस्ट, एम. मोहसेनी, और एस. लॉयड। बड़े डेटा वर्गीकरण के लिए क्वांटम सपोर्ट वेक्टर मशीन। भौतिक समीक्षा पत्र, 113(3):1-5, 2014। डीओआई: 10.1103/फिजरेवलेट.113.130503।
https: / / doi.org/ 10.1103 / PhysRevLett.113.130503

[20] जे. कुबलर, एस. बुखोल्ज़, और बी. स्कोल्कोफ़। क्वांटम कर्नेल का आगमनात्मक पूर्वाग्रह। एम. रैंज़ाटो, ए. बेगेलज़िमर, वाई. डौफिन, पी. लियांग, और जेडब्ल्यू वॉन, संपादकों में, एडवांसेस इन न्यूरल इंफॉर्मेशन प्रोसेसिंग सिस्टम्स, खंड 34, पृष्ठ 12661-12673। कुरेन एसोसिएट्स, इंक., 2021। ऑनलाइन उपलब्ध: https://​/proceedings.neurips.cc/​paper_files/​paper/​2021/​file/​69adc1e107f7f7d035d7baf04342e1ca-Paper.pdf।
https:/​/​proceedings.neurips.cc/​paper_files/​paper/​2021/​file/​69adc1e107f7f7d035d7baf04342e1ca-Paper.pdf

[21] वी. हेयरॉड, जेड. ली, जेड. डेनिस, ए. ले बोइटे, और सी. सियुटी। शोर मचाने वाली क्वांटम कर्नेल मशीनें। भौतिक. रेव. ए, 106:052421, 2022. डीओआई: 10.1103/फिजरेवए.106.052421।
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

[22] सीजेसी बर्गेस और सीजेसी बर्गेस। पैटर्न पहचान के लिए सपोर्ट वेक्टर मशीनों पर एक ट्यूटोरियल। डेटा माइनिंग और नॉलेज डिस्कवरी, 2:121-167, 1998। ऑनलाइन उपलब्ध: https://​/www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -पैटर्न-पहचान के लिए मशीनें/​।
https:/​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector-machines-for-pattern-recognition/​

[23] एम. सेरेज़ो, ए. सोने, टी. वोल्कॉफ़, एल. सिन्सियो, और पी.जे. कोल्स। उथले पैरामीट्रिज्ड क्वांटम सर्किट में लागत फ़ंक्शन निर्भर बंजर पठार। नेचर कम्युनिकेशंस, 12(1):1791, 2021। डीओआई: 10.1038/एस41467-021-21728-डब्ल्यू।
https: / / doi.org/ 10.1038 / s41467-021-21728-w

[24] बेलिस, वासिलिस, गोंजालेज-कैस्टिलो, सैमुअल, रीसेल, क्रिस्टीना, वैलेकोर्सा, सोफिया, कोम्बारो, एलियास एफ., डिस्सर्टोरी, गुंथर, और रेइटर, फ्लोरेंटिन। क्वांटम क्लासिफायर के साथ हिग्स विश्लेषण। ईपीजे वेब कॉन्फ्रेंस, 251:03070, 2021। डीओआई: 10.1051/​ईपीजेकॉन्फ़/​202125103070।
https://​doi.org/​10.1051/​epjconf/​202125103070

[25] एम. सेरेज़ो, ए. एरास्मिथ, आर. बब्बुश, एससी बेंजामिन, एस. एंडो, के. फ़ूजी, जेआर मैक्लेन, के. मितराई, एक्स. युआन, एल. सिन्सियो, और पीजे कोल्स। वैरिएशनल क्वांटम एल्गोरिदम। प्रकृति समीक्षा भौतिकी, 3(9):625–644, 2021। डीओआई: 10.1038/एस42254-021-00348-9।
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[26] आर. मैकगिबॉर्न एट अल. क्वाडप्रोग: द्विघात प्रोग्रामिंग सॉल्वर (पायथन)। https://​/github.com/​quadprog/​quadprog, 2022।
https://​github.com/​quadprog/quadprog

[27] वाई नेस्टरोव। उत्तल अनुकूलन पर परिचयात्मक व्याख्यान: एक बुनियादी पाठ्यक्रम। अनुप्रयुक्त अनुकूलन. स्प्रिंगर, 2004. डीओआई: 10.1007/978-1-4419-8853-9।
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] जे. स्पैल. कुशल अनुकूलन के लिए एक साथ गड़बड़ी विधि का अवलोकन। जॉन हॉपकिंस एपीएल टेक्निकल डाइजेस्ट, 19(4), पृष्ठ 482-492, 1998।

[29] जी. जेंटिनेटा, ए. थॉमसन, डी. सटर, और एस. वोर्नर। पांडुलिपि के लिए कोड "क्वांटम समर्थन वेक्टर मशीनों की जटिलता"। 2022. डीओआई: https://​/doi.org/​10.5281/​zenodo.6303725।
https: / / doi.org/ 10.5281 / zenodo.6303725

[30] टी. हब्रेग्त्सेन, डी. वियरिच्स, ई. गिल-फस्टर, पी.-जेएचएस डर्क्स, पी.के. फेहरमन, और जे.जे. मेयर। निकटवर्ती क्वांटम कंप्यूटरों पर क्वांटम एम्बेडिंग कर्नेल का प्रशिक्षण। भौतिक. रेव. ए, 106:042431, 2022. डीओआई: 10.1103/फिजरेवए.106.042431।
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

[31] आर लताला। यादृच्छिक मैट्रिक्स के मानदंडों के कुछ अनुमान। अमेरिकी गणितीय सोसायटी की कार्यवाही, 133(5):1273-1282, 2005। डीओआई: 10.1090/एस0002-9939-04-07800-1।
https:/​/​doi.org/​10.1090/​s0002-9939-04-07800-1

[32] आर वर्शिनिन। यादृच्छिक मैट्रिक्स के गैर-स्पर्शोन्मुख विश्लेषण का परिचय। संपीड़ित सेंसिंग: सिद्धांत और अनुप्रयोग, पृष्ठ 210-268, 2009। डीओआई: 10.1017/​सीबीओ9780511794308.006।
https: / / doi.org/ 10.1017 / CBO9780511794308.006

[33] टी. हॉफमैन, बी. स्कोलकोफ, और ए जे स्मोला। मशीन लर्निंग में कर्नेल विधियाँ। सांख्यिकी के इतिहास, 36(3):1171-1220, 2008। डीओआई: 10.1214/​009053607000000677।
https: / / doi.org/ 10.1214 / १.१३,९४,२०८

[34] जेडब्ल्यू डेनियल. निश्चित द्विघात कार्यक्रमों के समाधान की स्थिरता. गणितीय प्रोग्रामिंग, 5(1):41-53, 1973. डीओआई: 10.1007/बीएफ01580110।
https: / / doi.org/ 10.1007 / BF01580110

द्वारा उद्धृत

[1] अलेक्जेंडर एम. डाल्ज़ेल, सैम मैकआर्डल, मारियो बर्टा, प्रेज़ेमीस्लाव बिएनियास, ची-फैंग चेन, एंड्रस गिलियेन, कॉनर टी. हैन, माइकल जे. कास्टोरियानो, एमिल टी. खाबीबोलाइन, अलेक्जेंडर कुबिका, ग्रांट साल्टन, सैमसन वांग, और फर्नांडो जीएसएल ब्रैंडाओ, "क्वांटम एल्गोरिदम: अनुप्रयोगों और अंत-से-अंत जटिलताओं का एक सर्वेक्षण", arXiv: 2310.03011, (2023).

[2] मारिया शुल्ड और नाथन किलोरन, "क्या क्वांटम एडवांटेज क्वांटम मशीन लर्निंग के लिए सही लक्ष्य है?", पीआरएक्स क्वांटम 3 3, 030101 (2022).

[3] मोहम्मद हसन हसनशाही, मार्सिन जस्त्रज़ेब्स्की, सारा मलिक, और ओफ़र लाहव, "आकाशगंगा वर्गीकरण के लिए एक क्वांटम-उन्नत समर्थन वेक्टर मशीन", आरएएस तकनीक और उपकरण 2 1, 752 (2023).

[4] कुआन-चेंग चेन, ज़ियाओटियन जू, हेनरी मखानोव, हुई-ह्सुआन चुंग, और चेन-यू लियू, "जीपीयू त्वरण के साथ बड़े पैमाने पर तारकीय वर्गीकरण के लिए क्वांटम-उन्नत समर्थन वेक्टर मशीन", arXiv: 2311.12328, (2023).

[5] सुपानुत थानासिलप, सैमसन वांग, एम. सेरेज़ो, और ज़ो होम्स, "क्वांटम कर्नेल विधियों में घातीय एकाग्रता और अप्रशिक्षितता", arXiv: 2208.11060, (2022).

[6] कौहेई नाकाजी, हिरोयुकी तेजुका, और नाओकी यामामोटो, "तंत्रिका स्पर्शरेखा कर्नेल शासन में क्वांटम-शास्त्रीय हाइब्रिड तंत्रिका नेटवर्क", क्वांटम विज्ञान और प्रौद्योगिकी 9 1, 015022 (2024).

[7] यस्विथा गुज्जू, अत्सुशी मात्सुओ, और रूडी रेमंड, "नियर-टर्म क्वांटम डिवाइसेस पर क्वांटम मशीन लर्निंग: वास्तविक दुनिया के अनुप्रयोगों के लिए पर्यवेक्षित और अनपर्यवेक्षित तकनीकों की वर्तमान स्थिति", arXiv: 2307.00908, (2023).

[8] राउल हीज़, थोर गेरलाच, साशा मुके, सबाइन मुलर, मैथियास जैकब्स, और निको पियाटकोव्स्की, "शेपली वैल्यूज़ के साथ क्वांटम सर्किट की व्याख्या: समझाने योग्य क्वांटम मशीन लर्निंग की ओर", arXiv: 2301.09138, (2023).

[9] जूलियन गैकोन, जेन्स नाइस, रिकार्डो रॉसी, स्टीफ़न वोर्नर, और ग्यूसेप कार्लियो, "क्वांटम जियोमेट्रिक टेंसर के बिना वैरिएशनल क्वांटम टाइम इवोल्यूशन", arXiv: 2303.12839, (2023).

[10] जियान जेंटिनेटा, डेविड सटर, क्रिस्टा ज़ौफ़ल, ब्राइस फुलर, और स्टीफन वोर्नर, "स्टोकेस्टिक ग्रेडिएंट डिसेंट के साथ क्वांटम कर्नेल संरेखण", arXiv: 2304.09899, (2023).

[11] फिलिपा डकेट, गेब्रियल फैसिनी, मार्सिन जस्त्रज़ेब्स्की, सारा मलिक, सेबेस्टियन रेट्टी, और टिम स्कैनलॉन, "क्वांटम-एन्हांस्ड सपोर्ट वेक्टर मशीन के साथ चार्ज किए गए कण ट्रैक सेगमेंट का पुनर्निर्माण", arXiv: 2212.07279, (2022).

[12] ट्रैविस एल. शोल्टेन, डेरिक पेरी, जोसेफ वाशिंगटन, जेनिफर आर. ग्लिक, और थॉमस वार्ड, "सर्किट निष्पादन रनटाइम के लिए एक मॉडल और व्यावहारिक डेटा सेट आकार में क्वांटम कर्नेल के लिए इसके निहितार्थ", arXiv: 2307.04980, (2023).

[13] सामंथा वी. बैरोन, डेनियल जे. एगर, एलिजा पेलोफ्स्के, एंड्रियास बार्टस्ची, स्टीफ़न ईडेनबेंज़, मैथिस लेहमकुहलर, और स्टीफ़न वोर्नर, "शोर नमूनों से गणना की गई शोर-मुक्त अपेक्षा मूल्यों के लिए सिद्ध सीमाएँ", arXiv: 2312.00733, (2023).

[14] एम. एमरे साहिन, बेंजामिन सीबी सिमंस, पुष्पक पति, फैयाज मिन्हास, डेक्लान मिलर, मारिया गब्रानी, ​​जान लुकास रॉबर्टस और स्टेफानो मेन्सा, "क्वांटम कर्नेल संरेखण के लिए कुशल पैरामीटर अनुकूलन: परिवर्तनीय प्रशिक्षण में एक उप-नमूना दृष्टिकोण" , arXiv: 2401.02879, (2024).

उपरोक्त उद्धरण से हैं SAO / NASA ADS (अंतिम अद्यतन सफलतापूर्वक 2024-01-12 02:12:22)। सूची अधूरी हो सकती है क्योंकि सभी प्रकाशक उपयुक्त और पूर्ण उद्धरण डेटा प्रदान नहीं करते हैं।

On Crossref की उद्धृत सेवा द्वारा कार्यों का हवाला देते हुए कोई डेटा नहीं मिला (अंतिम प्रयास 2024-01-12 02:12:21)।

समय टिकट:

से अधिक क्वांटम जर्नल