बुनियादी क्वांटम सबरूटीन्स: एकाधिक चिह्नित तत्वों और योग संख्याओं को ढूंढना

बुनियादी क्वांटम सबरूटीन्स: एकाधिक चिह्नित तत्वों और योग संख्याओं को ढूंढना

बुनियादी क्वांटम सबरूटीन्स: कई चिह्नित तत्वों को ढूंढना और संख्याओं का योग करना, प्लेटोब्लॉकचेन डेटा इंटेलिजेंस। लंबवत खोज. ऐ.

जोरन वैन अपेलडॉर्न1, सैंडर ग्रिब्लिंग2, तथा हेरोल्ड नीउबोएर3

1IViR और QuSoft, एम्स्टर्डम विश्वविद्यालय, नीदरलैंड
2अर्थमिति और संचालन अनुसंधान विभाग, टिलबर्ग विश्वविद्यालय, टिलबर्ग, नीदरलैंड
3कॉर्टेवेग-डी व्रीस इंस्टीट्यूट फॉर मैथमेटिक्स एंड क्यूसॉफ्ट, एम्स्टर्डम विश्वविद्यालय, नीदरलैंड और कंप्यूटर विज्ञान संकाय, रूहर विश्वविद्यालय बोचुम, जर्मनी और गणितीय विज्ञान विभाग, कोपेनहेगन विश्वविद्यालय, डेनमार्क

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

सार

हम दिखाते हैं कि क्वांटम प्रश्नों की इष्टतम संख्या $O(sqrt{N k})$ का उपयोग करके आकार $N$ की सूची में सभी $k$ चिह्नित तत्वों को कैसे ढूंढें और सेटिंग में गेट जटिलता में केवल एक पॉलीलॉगरिदमिक ओवरहेड किसी के पास छोटी क्वांटम मेमोरी होती है। पिछले एल्गोरिदम में या तो गेट जटिलता में एक कारक $k$ ओवरहेड खर्च हुआ था, या क्वेरी जटिलता में एक अतिरिक्त कारक $log(k)$ था।
फिर हम $s = sum_{i=1}^N v_i$ का गुणक $delta$-अनुमान खोजने की समस्या पर विचार करते हैं, जहां $v=(v_i) [0,1]^N$ में, क्वांटम क्वेरी एक्सेस दी गई है $v$ का एक द्विआधारी विवरण। हम एक एल्गोरिथ्म देते हैं जो $O(sqrt{N log(1/rho) / delta})$ क्वांटम प्रश्नों ($rho$ पर हल्की धारणाओं के तहत) का उपयोग करके, कम से कम $1-rho$ की संभावना के साथ ऐसा करता है। यह आयाम अनुमान के सीधे अनुप्रयोग की तुलना में $1/डेल्टा$ और $log(1/rho)$ पर निर्भरता में चतुष्कोणीय सुधार करता है। बेहतर $log(1/rho)$ निर्भरता प्राप्त करने के लिए हम पहले परिणाम का उपयोग करते हैं।

► BibTeX डेटा

► संदर्भ

[1] श्रीनिवासन अरुणाचलम और रोनाल्ड डी वुल्फ। क्वांटम खोज में द्वारों की संख्या का अनुकूलन। क्वांटम जानकारी. कंप्यूट., 17(3-4):251-261, 2017. doi:10.26421/​qic17.3-4.
https: / / doi.org/ १०.२६,४२१ / qic10.26421-17.3

[2] जोस ए. एडेल और पी. जोड्रा। सटीक कोलमोगोरोव और कुछ परिचित असतत वितरणों के बीच कुल भिन्नता दूरी। असमानताओं और अनुप्रयोगों का जर्नल, 2006(1):1-8, 2006। doi:10.1155/​JIA/​2006/​64307।
https://​doi.org/​10.1155/​JIA/​2006/​64307

[3] जोरान वैन एपेलडॉर्न, सैंडर ग्रिबलिंग, यिनान ली, हेरोल्ड निउबोएर, माइकल वाल्टर और रोनाल्ड डी वुल्फ। मैट्रिक्स स्केलिंग और मैट्रिक्स संतुलन के लिए क्वांटम एल्गोरिदम। ऑटोमेटा, भाषाएं और प्रोग्रामिंग पर 48वीं अंतर्राष्ट्रीय संगोष्ठी की कार्यवाही में (ICALP'21), खंड 198, पृष्ठ 110:1-110:17, 2021। arXiv:2011.12823, doi:10.4230/LIPIcs.ICALP.2021.110।
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.110
arXiv: 2011.12823

[4] स्कॉट आरोनसन और पैट्रिक रॉल। क्वांटम अनुमानित गणना, सरलीकृत। एल्गोरिदम में सरलता पर संगोष्ठी में, पृष्ठ 24-32, 2020। doi:10.1137/​1.9781611976014.5।
https: / / doi.org/ 10.1137 / १.१३,९४,२०८

[5] मिशेल बोयर, गाइल्स ब्रासार्ड, पीटर होयर, और एलेन टैप। क्वांटम खोज पर कड़ी सीमाएं। फ़ोर्ट्सक्रिट डेर फिजिक, 46(4-5):493-505, 1998। फिजकॉम्प'96 में पूर्व संस्करण। arXiv:क्वांट-पीएच/9605034।
arXiv: बल्ली से ढकेलना-पीएच / 9605034

[6] हैरी बुहरमैन, रिचर्ड क्लेव, रोनाल्ड डी वुल्फ, और क्रिस्टोफ़ ज़ाल्का। लघु-त्रुटि और शून्य-त्रुटि क्वांटम एल्गोरिदम के लिए सीमाएं। कंप्यूटर विज्ञान की नींव पर 40वीं वार्षिक संगोष्ठी (एफओसीएस'99) में, पृष्ठ 358-368। आईईईई कंप्यूटर सोसायटी, 1999।

[7] गाइल्स ब्रासार्ड, पीटर होयर, मिशेल मोस्का, और एलेन टैप। क्वांटम आयाम प्रवर्धन और अनुमान। क्वांटम कम्प्यूटेशन और क्वांटम सूचना में: एक मिलेनियम वॉल्यूम, समकालीन गणित का खंड 305, पृष्ठ 53-74। अमेरिकन मैथमैटिकल सोसायटी, 2002. doi:10.1002/​(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P.
<a href="https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P”>https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P

[8] रिचर्ड ब्रेंट और पॉल ज़िम्मरमैन। आधुनिक कंप्यूटर अंकगणित, खंड 18। कैम्ब्रिज यूनिवर्सिटी प्रेस, 2010।

[9] रैन कैनेटी, गाइ इवन, और ओडेड गोल्डरिच। औसत का अनुमान लगाने के लिए नमूनाकरण एल्गोरिदम की निचली सीमाएं। सूचना प्रसंस्करण पत्र, 53(1):17-25, जनवरी 1995। doi:10.1016/​0020-0190(94)00171-टी।
https:/​/​doi.org/​10.1016/​0020-0190(94)00171-T

[10] कार्लो सिलिबर्टो, मार्क हर्बस्टर, एलेसेंड्रो डेविड इलोंगो, मासिमिलियानो पोंटिल, एंड्रिया रोचेटो, सिमोन सेवेरिनी और लियोनार्ड वोसनिग। क्वांटम मशीन लर्निंग: एक शास्त्रीय परिप्रेक्ष्य। रॉयल सोसाइटी ए की कार्यवाही: गणितीय, भौतिक और इंजीनियरिंग विज्ञान, 474(2209):20170551, जनवरी 2018। doi:10.1098/rspa.2017.0551।
https: / / doi.org/ 10.1098 / rspa.2017.0551

[11] थॉमस एच. कॉर्मेन, चार्ल्स ई. लीसर्सन, रोनाल्ड एल. रिवेस्ट, और क्लिफोर्ड स्टीन। एल्गोरिदम का परिचय. एमआईटी प्रेस, चौथा संस्करण, 4।

[12] पी. डायकोनिस और डी. फ्रीडमैन। परिमित विनिमेय अनुक्रम. द एनल्स ऑफ प्रॉबेबिलिटी, 8(4):745-764, 1980। यूआरएल: https:/​/​www.jstor.org/​stable/​2242823।
https: / / www.jstor.org/ स्थिर / 2242823

[13] क्रिस्टोफ़ ड्यूर और पीटर होयर। न्यूनतम ज्ञात करने के लिए एक क्वांटम एल्गोरिदम, 1996। doi:10.48550/​arXiv.quant-ph/​9607014।
https://​doi.org/​10.48550/​arXiv.quant-ph/​9607014
arXiv: बल्ली से ढकेलना-पीएच / 9607014

[14] क्रिस्टोफ़ ड्यूर, मार्क हेइलिगमैन, पीटर होयर, और मेहदी म्हल्ला। कुछ ग्राफ़ समस्याओं की क्वांटम क्वेरी जटिलता। कंप्यूटिंग पर सियाम जर्नल, 35(6):1310-1328, जनवरी 2006। doi:10.1137/​050644719।
https: / / doi.org/ 10.1137 / १.१३,९४,२०८

[15] पॉल डैगम, रिचर्ड कार्प, माइकल लुबी और शेल्डन रॉस। मोंटे कार्लो अनुमान के लिए एक इष्टतम एल्गोरिदम। कंप्यूटिंग पर सियाम जर्नल, 29(5):1484-1496, जनवरी 2000। doi:10.1137/​S0097539797315306।
https: / / doi.org/ 10.1137 / S0097539797315306

[16] विटोरियो जियोवनेटी, सेठ लॉयड, और लोरेंजो मैककोन। क्वांटम रैंडम एक्सेस मेमोरी। भौतिक समीक्षा पत्र, 100(16), अप्रैल 2008। doi:10.1103/physrevlett.100.160501।
https: / / doi.org/ 10.1103 / physrevlett.100.160501

[17] सैंडर ग्रिबलिंग और हेरोल्ड नीउबोएर। मैट्रिक्स स्केलिंग के लिए बेहतर क्वांटम निचली और ऊपरी सीमाएं। कंप्यूटर विज्ञान के सैद्धांतिक पहलुओं पर 39वें अंतर्राष्ट्रीय संगोष्ठी की कार्यवाही में (एसटीएसीएस'22), खंड 219, पृष्ठ 35:1-35:23, 2022। arXiv:2109.15282, doi:10.4230/LIPIcs.STACS.2022.35।
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2022.35
arXiv: 2109.15282

[18] मार्ट डी ग्राफ़ और रोनाल्ड डी वुल्फ। याओ सिद्धांत के क्वांटम संस्करणों पर। कंप्यूटर विज्ञान के सैद्धांतिक पहलुओं पर 19वीं संगोष्ठी (एसटीएसीएस'02) में, कंप्यूटर विज्ञान में व्याख्यान नोट्स का खंड 2285, पृष्ठ 347-358, बर्लिन, हीडलबर्ग, 2002। स्प्रिंगर। doi:10.1007/​3-540-45841-7_28.
https:/​/​doi.org/​10.1007/​3-540-45841-7_28

[19] लव के. ग्रोवर. डेटाबेस खोज के लिए एक तेज़ क्वांटम मैकेनिकल एल्गोरिदम। कंप्यूटिंग के सिद्धांत (STOC'38) पर 96वें वार्षिक ACM संगोष्ठी की कार्यवाही में, पृष्ठ 212–219, 1996. arXiv:quant-ph/​9605043, doi:10.1145/​237814.237866।
https: / / doi.org/ 10.1145 / १.१३,९४,२०८
arXiv: बल्ली से ढकेलना-पीएच / 9605043

[20] लव के. ग्रोवर. क्वांटम दूरसंचार, 1997। बेल लैब्स तकनीकी ज्ञापन ITD97-31630F। doi:10.48550/​arXiv.quant-ph/​9704012.
https://​doi.org/​10.48550/​arXiv.quant-ph/​9704012
arXiv: बल्ली से ढकेलना-पीएच / 9704012

[21] लव के. ग्रोवर. तेज़ क्वांटम मैकेनिकल एल्गोरिदम के लिए एक रूपरेखा। कंप्यूटिंग के सिद्धांत पर तीसवीं वार्षिक एसीएम संगोष्ठी की कार्यवाही में (एसटीओसी'98), पृष्ठ 53-62, 1998। arXiv:quant-ph/​9711043, doi:10.1145/​276698.276712।
https: / / doi.org/ 10.1145 / १.१३,९४,२०८
arXiv: बल्ली से ढकेलना-पीएच / 9711043

[22] यासीन हमौदी. क्वांटम उप-गॉसियन माध्य अनुमानक। एल्गोरिदम पर 29वें वार्षिक यूरोपीय संगोष्ठी (ईएसए 2021) में, लाइबनिज इंटरनेशनल प्रोसीडिंग्स इन इंफॉर्मेटिक्स (एलआईपीआईसी) का खंड 204, पृष्ठ 50:1-50:17, 2021। doi:10.4230/LIPIcs.ESA.2021.50।
https://​doi.org/​10.4230/​LIPIcs.ESA.2021.50

[23] स्वंते जानसन. ज्यामितीय और घातांकीय चरों के योग के लिए टेल सीमाएँ। सांख्यिकी और संभाव्यता पत्र, 135:1-6, 2018। doi:10.1016/​j.spl.2017.11.017।
https://​/doi.org/​10.1016/​j.spl.2017.11.017

[24] डोनाल्ड एर्विन नुथ। कंप्यूटर प्रोग्रामिंग की कला, खंड III। एडिसन-वेस्ले, दूसरा संस्करण, 2. यूआरएल: https:/​/​www.worldcat.org/​oclc/​1998।
https://​/​www.worldcat.org/​oclc/​312994415

[25] रॉबिन कोठारी और रयान ओ'डोनेल। जब आपके पास स्रोत कोड हो तो माध्य अनुमान लगाएं; या, क्वांटम मोंटे कार्लो विधियाँ। असतत एल्गोरिदम (SODA'2023) पर 23 वार्षिक ACM-SIAM संगोष्ठी की कार्यवाही में, पृष्ठ 1186–1215, 2023। doi:10.1137/​1.9781611977554.ch44।
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

[26] माइकल ए। नीलसन और इसहाक एल। चुआंग। क्वांटम गणना और क्वांटम जानकारी। कैम्ब्रिज यूनिवर्सिटी प्रेस, 2002।

[27] अश्विन नायक और फेलिक्स वू। माध्यिका और संबंधित आँकड़ों का अनुमान लगाने की क्वांटम क्वेरी जटिलता। कंप्यूटिंग के सिद्धांत (STOC'31) पर 99वें वार्षिक ACM SIGACT संगोष्ठी की कार्यवाही में, पृष्ठ 384-393, 1999। arXiv:quant-ph/​9804066, doi:10.1145/​301250.301349।
https: / / doi.org/ 10.1145 / १.१३,९४,२०८
arXiv: बल्ली से ढकेलना-पीएच / 9804066

[28] बी रूस. पॉइसन द्विपद वितरण का द्विपद सन्निकटन: क्रौटचौक विस्तार। संभाव्यता का सिद्धांत और उसके अनुप्रयोग, 45(2):258-272, 2001। doi:10.1137/​S0040585X9797821X।
https:///doi.org/10.1137/S0040585X9797821X

[29] रॉबर्ट एम. यंग. 75.9 यूलर स्थिरांक. गणितीय राजपत्र, 75(472):187-190, 1991. doi:10.2307/​3620251।
https: / / doi.org/ 10.2307 / १.१३,९४,२०८

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

समय टिकट:

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