जेफिरनेट लोगो

टेन्सर प्रिंसिपल कम्पोनेंट एनालिसिस के लिए क्लासिकल और क्वांटम एल्गोरिदम

दिनांक:

मैथ्यू बी हेस्टिंग्स

स्टेशन क्यू, माइक्रोसॉफ्ट रिसर्च, सांता बारबरा, सीए 93106-6105, यूएसए
Microsoft क्वांटम और माइक्रोसॉफ्ट रिसर्च, रेडमंड, WA 98052, यूएसए

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

सार

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

► BibTeX डेटा

► संदर्भ

[1] अलेक्जेंडर एस वेन, अहमद अल अलाउई, और क्रिस्टोफर मूर। किकुची पदानुक्रम और टेंसर पीसीए। 2019. arXiv:1904.03858।
arXiv: 1904.03858

[2] एंड्रिया मोंटानारी और एमिल रिचर्ड। टेंसर पीसीए के लिए एक सांख्यिकीय मॉडल। तंत्रिका सूचना प्रसंस्करण प्रणालियों में प्रगति में, पृष्ठ 2897-2905, 2014।

[3] थिबॉल्ट लेसीउर, लियो मियोलेन, मार्क लेलार्ज, फ्लोरेंट क्रज़ाकाला, और लेंका ज़ेडेबोरोवा। स्पाइक्ड टेंसर अनुमान में सांख्यिकीय और कम्प्यूटेशनल चरण संक्रमण। 2017 में सूचना सिद्धांत (आईएसआईटी) पर आईईईई अंतर्राष्ट्रीय संगोष्ठी। आईईईई, जून 2017. doi:10.1109/​isit.2017.8006580।
https: / / doi.org/ 10.1109 / isit.2017.8006580

[4] सैमुअल बी हॉपकिंस, जोनाथन शी, और डेविड स्टीयरर। वर्ग प्रमाणों के योग के माध्यम से टेंसर प्रमुख घटक विश्लेषण। लर्निंग थ्योरी पर सम्मेलन में, पृष्ठ 956-1006, 2015।

[5] सैमुअल बी. हॉपकिंस, त्सेलिल श्राम, जोनाथन शी, और डेविड स्टीयरर। वर्ग प्रमाणों के योग से तेज़ वर्णक्रमीय एल्गोरिदम: टेंसर अपघटन और लगाए गए विरल वैक्टर। कंप्यूटिंग के सिद्धांत पर 48वें वार्षिक एसीएम सिगैक्ट संगोष्ठी की कार्यवाही में - एसटीओसी 2016। एसीएम प्रेस, 2016। doi:10.1145/​2897518.2897529।
https: / / doi.org/ 10.1145 / १.१३,९४,२०८

[6] विजय वीएसपी भट्टिप्रोलू, मृणालकांति घोष, इउइवोंग ली, वेंकटेशन गुरुस्वामी और मधुर तुलसियानी। इकाई क्षेत्र पर बहुपद अनुकूलन के लिए गुणक सन्निकटन। सीओआरआर, एबीएस/1611.05998, 2016। यूआरएल: http://​//arxiv.org/​abs/1611.05998, arXiv:1611.05998।
arXiv: 1611.05998

[7] विजय भट्टिप्रोलू, मृणालकांति घोष, वेंकटेशन गुरुस्वामी, यूइवूंग ली और मधुर तुलसियानी। कमज़ोर डिकॉउलिंग, बहुपद वलन और गोले पर अनुमानित अनुकूलन। 2017 में कंप्यूटर विज्ञान की नींव (एफओसीएस) पर आईईईई 58वीं वार्षिक संगोष्ठी। आईईईई, अक्टूबर 2017। doi:10.1109/focs.2017.97।
https: / / doi.org/ 10.1109 / focs.2017.97

[8] आरएफ वर्नर. बड़े विचलन और माध्य-क्षेत्र क्वांटम सिस्टम। क्वांटम संभाव्यता और संबंधित विषयों में, पृष्ठ 349-381। विश्व वैज्ञानिक, जुलाई 1992. doi:10.1142/​9789814354783_0024।
https: / / doi.org/ 10.1142 / 9789814354783_0024

[9] क्रिस्टीना वी. क्रॉस, मैसीज लेवेनस्टीन, और जे. इग्नासियो सिराक। क्रमपरिवर्तन समरूपता के साथ फर्मिओनिक जाली हैमिल्टनियन की जमीनी अवस्थाएँ। फिजिकल रिव्यू ए, 88(2), अगस्त 2013। doi:10.1103/फिजरेवा.88.022335।
https: / / doi.org/ 10.1103 / physreva.88.022335

[10] फर्नांडो जीएसएल ब्रैंडाओ और अराम डब्ल्यू. हैरो। क्वांटम अवस्थाओं के लिए उत्पाद-स्थिति सन्निकटन। गणितीय भौतिकी में संचार, 342(1):47-80, जनवरी 2016। doi:10.1007/​s00220-016-2575-1।
https:/​/​doi.org/​10.1007/​s00220-016-2575-1

[11] स्कॉट आरोनसन और लिजी चेन। क्वांटम वर्चस्व प्रयोगों की जटिलता-सैद्धांतिक नींव। 32वें कम्प्यूटेशनल जटिलता सम्मेलन (सीसीसी 2017) में। श्लॉस डैगस्टुहल-लीबनिज़-ज़ेंट्रम फ्यूअर इंफॉर्मेटिक, 2017. arXiv:1612.05903।
arXiv: 1612.05903

[12] मदन लाल मेहता. रैंडम मैट्रिसेस, वॉल्यूम 142. एल्सेवियर, 2004।

[13] जेम्स डेमेल, इओना डुमित्रीउ, और ओल्गा होल्ट्ज़। तेज़ रैखिक बीजगणित स्थिर है। संख्यात्मक गणित, 108(1):59-91, अक्टूबर 2007। doi:10.1007/​s00211-007-0114-x।
https: / / doi.org/ 10.1007 / s00211-007-0114-x

[14] गुआंग हाओ लो और इसहाक एल चुआंग। क्वांटम सिग्नल प्रोसेसिंग द्वारा इष्टतम हैमिल्टनियन सिमुलेशन। भौतिक. रेव. लेट., 118:010501, 2017. arXiv:1606.02685v2, doi:10.1103/फिज़रेवलेट.118.010501।
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501
arXiv: 1606.02685v2

[15] गुआंग हाओ लो और इसहाक एल चुआंग। क्विबिटाइज़ेशन द्वारा हैमिल्टनियन सिमुलेशन। 2016. arXiv:1610.06546 https://​/doi.org/​10.22331/​q-2019-07-12-163.
https:/​/​doi.org/​10.22331/​q-2019-07-12-163
arXiv: 1610.06546

[16] डोमिनिक डब्ल्यू. बेरी, एंड्रयू एम. चिल्ड्स, रिचर्ड क्लेव, रॉबिन कोठारी, और रोलैंडो डी. सोम्मा। विरल हैमिल्टनियनों के अनुकरण के लिए परिशुद्धता में तेजी से सुधार। पृष्ठ 283-292, 2014। arXiv:1312.1414, doi:10.1145/2591796.2591854।
https: / / doi.org/ 10.1145 / १.१३,९४,२०८
arXiv: 1312.1414

[17] डोमिनिक डब्ल्यू. बेरी, एंड्रयू एम. चिल्ड्स, रिचर्ड क्लेव, रॉबिन कोठारी, और रोलैंडो डी. सोम्मा। एक कटी हुई टेलर श्रृंखला के साथ हैमिल्टनियन गतिशीलता का अनुकरण। भौतिक. रेव. लेट., 114:090502, 2015। arXiv:1412.4687, doi:10.1103/फिज़रेवलेट.114.090502।
https: / / doi.org/ 10.1103 / PhysRevLett.114.090502
arXiv: 1412.4687

[18] डीडब्ल्यू बेरी, एएम चिल्ड्स, और आर. कोठारी। सभी मापदंडों पर लगभग इष्टतम निर्भरता के साथ हैमिल्टनियन सिमुलेशन। 2015 में कंप्यूटर विज्ञान की नींव पर आईईईई 56वीं वार्षिक संगोष्ठी, पृष्ठ 792-809, अक्टूबर 2015। arXiv:1501.01715, doi:10.1109/​FOCS.2015.54।
https: / / doi.org/ 10.1109 / FOCS.2015.54
arXiv: 1501.01715

[19] एलेक्सी यू किताएव, अलेक्जेंडर शेन, और मिखाइल एन व्यालि। शास्त्रीय और क्वांटम संगणना, खंड 47। अमेरिकन गणितीय सोसायटी प्रोविडेंस, 2002। doi:10.1090/जीएसएम/047।
https: / / doi.org/ 10.1090 / जीएसएम / 047

[20] गाइल्स ब्रासार्ड, पीटर होयर, मिशेल मोस्का, और एलेन टैप। क्वांटम आयाम प्रवर्धन और अनुमान। समसामयिक गणित, 305:53-74, 2002। doi:10.1090/​conm/​305।
https: / / doi.org/ 10.1090 / conm / 305

[21] एंथोनी कारबेरी और जेम्स राइट। ${R^n}$ में उत्तल पिंडों पर बहुपदों के लिए वितरणात्मक और ${L^q}$ मानक असमानताएँ। गणितीय अनुसंधान पत्र, 8(3):233-248, 2001। doi:10.4310/​mrl.2001.v8.n3.a1।
https:/​/​doi.org/​10.4310/​mrl.2001.v8.n3.a1

[22] डेव वेकर, मैथ्यू बी. हेस्टिंग्स, नाथन विबे, ब्रायन के. क्लार्क, चेतन नायक, और मैथियास ट्रॉयर। क्वांटम कंप्यूटर पर दृढ़ता से सहसंबद्ध इलेक्ट्रॉन मॉडल को हल करना। फिजिकल रिव्यू ए, 92(6), दिसंबर 2015। doi:10.1103/फिजरेवा.92.062318।
https: / / doi.org/ 10.1103 / physreva.92.062318

<पी क्लास='ब्रेक'>[23] मैथ्यू बी हेस्टिंग्स। क्वांटम अधिकतम-प्रवाह न्यूनतम-कट की स्पर्शोन्मुखता। गणितीय भौतिकी में संचार, 351(1):387–418, नवंबर 2016। doi:10.1007/​s00220-016-2791-8।
https:/​/​doi.org/​10.1007/​s00220-016-2791-8

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

[1] अलेक्जेंडर एस. वेन, अहमद एल अलाउई, और क्रिस्टोफर मूर, "द किकुची पदानुक्रम और टेन्सर पीसीए", arXiv: 1904.03858.

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

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

स्रोत: https://quantum-journal.org/papers/q-2020-02-27-237/

स्पॉट_आईएमजी

नवीनतम खुफिया

स्पॉट_आईएमजी

हमारे साथ चैट करें

नमस्ते! मैं आपकी कैसे मदद कर सकता हूँ?