الإجراءات الفرعية الكمومية الأساسية: العثور على عناصر محددة متعددة وجمع الأرقام

الإجراءات الفرعية الكمومية الأساسية: العثور على عناصر محددة متعددة وجمع الأرقام

الطابع الزمني: 14 مارس 2024 9:40 صباحًا
الإجراءات الفرعية الكمومية الأساسية: العثور على عناصر محددة متعددة وجمع الأرقام وذكاء بيانات PlatoBlockchain. البحث العمودي. منظمة العفو الدولية.

جوران فان أبلدورن1, ساندر جريبلينج2و هارولد نيوبور3

1IViR وQuSoft، جامعة أمستردام، هولندا
2قسم الاقتصاد القياسي وبحوث العمليات، جامعة تيلبورج، تيلبورج، هولندا
3معهد كورتيفيغ دي فريس للرياضيات وQuSoft، جامعة أمستردام، هولندا وكلية علوم الكمبيوتر، جامعة الرور بوخوم، ألمانيا وقسم العلوم الرياضية، جامعة كوبنهاغن، الدنمارك

تجد هذه الورقة مثيرة للاهتمام أو ترغب في مناقشة؟ Scite أو ترك تعليق على SciRate.

ملخص

نعرض كيفية العثور على جميع العناصر المميزة بـ $k$ في قائمة بالحجم $N$ باستخدام العدد الأمثل $O(sqrt{N k})$ من الاستعلامات الكمومية والحمل متعدد اللوغاريتمي فقط في تعقيد البوابة، في الإعداد حيث واحد لديه ذاكرة كمومية صغيرة. تحملت الخوارزميات السابقة عاملًا إضافيًا $k$ في تعقيد البوابة، أو كان لها عامل إضافي $log(k)$ في تعقيد الاستعلام.
نحن بعد ذلك نفكر في مشكلة العثور على $delta$-تقريبي مضاعف لـ $s = sum_{i=1}^N v_i$ حيث $v=(v_i) في [0,1]^N$، مع توفر وصول الاستعلام الكمي إلى وصف ثنائي لـ $v$. نقدم خوارزمية تقوم بذلك، مع احتمال لا يقل عن $1-rho$، باستخدام $O(sqrt{N log(1/rho) / delta})$ استعلامات كمومية (في ظل افتراضات معتدلة على $rho$). يؤدي هذا إلى تحسين الاعتماد على $1/delta$ و$log(1/rho)$ بشكل تربيعي مقارنة بالتطبيق المباشر لتقدير السعة. للحصول على الاعتماد المحسن $log(1/rho)$ نستخدم النتيجة الأولى.

► بيانات BibTeX

ferences المراجع

[1] سرينيفاسان أروناتشالام ورونالد دي وولف. تحسين عدد البوابات في البحث الكمي. معلومات الكم. حساب.، 17(3-4):251-261، 2017. دوى:10.26421/qic17.3-4.
https: / / doi.org/ 10.26421 / qic17.3-4

[2] خوسيه أ. أديل وب. جودرا. Kolmogorov الدقيق ومسافات التباين الإجمالية بين بعض التوزيعات المنفصلة المألوفة. مجلة عدم المساواة والتطبيقات، 2006 (1): 1-8، 2006. دوى:10.1155/JIA/2006/64307.
https://​/doi.org/10.1155/JIA/2006/64307

[3] يوران فان أبلدورن، ساندر غريبلينج، ينان لي، هارولد نيوبور، مايكل والتر، ورونالد دي وولف. خوارزميات الكم لقياس المصفوفة وموازنة المصفوفة. في وقائع الندوة الدولية الثامنة والأربعين حول الأتمتة واللغات والبرمجة (ICALP'48)، المجلد 21، الصفحات 198:110–1:110، 17. أرخايف:2021، دوى:2011.12823/LIPIcs.ICALP.10.4230.
الشبكي: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.110
أرخايف: 2011.12823

[4] سكوت آرونسون وباتريك رال. العد التقريبي الكمي، مبسط. في ندوة حول البساطة في الخوارزميات، الصفحات 24-32، 2020. دوى:10.1137/1.9781611976014.5.
الشبكي: / / doi.org/ 10.1137 / 1.9781611976014.5

[5] ميشيل بوير، جيل براسارد، بيتر هوير، وآلان تاب. حدود ضيقة على البحث الكمي. Fortschritte der Physik, 46(4–5):493–505, 1998. نسخة سابقة في Physcomp'96. أرخايف:كمية فتاه/9605034.
أرخايف: ضليع في الرياضيات، وعل / 9605034

[6] هاري بورمان، وريتشارد كليف، ورونالد دي وولف، وكريستوف زالكا. حدود الخوارزميات الكمومية ذات الأخطاء الصغيرة والخطأ الصفري. في الندوة السنوية الأربعون حول أسس علوم الكمبيوتر (FOCS'40)، الصفحات 99-358. جمعية IEEE للكمبيوتر، 368.

[7] جيل براسارد، بيتر هوير، ميشيل موسكا، وآلان تاب. تضخيم السعة الكمومية وتقديرها. في الحساب الكمي والمعلومات الكمومية: مجلد الألفية، المجلد 305 من الرياضيات المعاصرة، الصفحات 53-74. الجمعية الرياضية الأمريكية، 2002. دوى: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. دوى:10.1016/0020-0190(94)00171-T.
https:/​/​doi.org/​10.1016/​0020-0190(94)00171-T

[10] كارلو سيليبرتو، ومارك هيربستر، وأليساندرو دافيد إيلونغو، وماسيميليانو بونتيل، وأندريا روكيتو، وسيمون سيفيريني، وليونارد ووسنيغ. التعلم الآلي الكمي: منظور كلاسيكي. وقائع الجمعية الملكية أ: العلوم الرياضية والفيزيائية والهندسية، 474 (2209): 20170551، يناير 2018. دوى:10.1098/RSPA.2017.0551.
الشبكي: / / doi.org/ 10.1098 / rspa.2017.0551

[11] توماس إتش. كورمين، وتشارلز إي. ليسرسون، ورونالد إل. ريفست، وكليفورد شتاين. مقدمة في الخوارزميات. مطبعة معهد ماساتشوستس للتكنولوجيا، الطبعة الرابعة، 4.

[12] P. دياكونيس ود. فريدمان. تسلسلات محدودة قابلة للتبديل. حوليات الاحتمالية، 8 (4): 745-764، 1980. URL: https://​/​www.jstor.org/​stable/​2242823.
https: / / www.jstor.org/able / 2242823

[13] كريستوف دور وبيتر هوير. خوارزمية كمومية لإيجاد الحد الأدنى، 1996. دوى:10.48550/arXiv.quant-ph/9607014.
https: / / doi.org/10.48550 / arXiv.quant-ph / 9607014
أرخايف: ضليع في الرياضيات، وعل / 9607014

[14] كريستوف دور، مارك هيليجمان، بيتر هوير، ومهدي محلا. تعقيد الاستعلام الكمي لبعض مشاكل الرسم البياني. مجلة SIAM حول الحوسبة، 35(6):1310–1328، يناير 2006. دوى:10.1137/050644719.
الشبكي: / / doi.org/ 10.1137 / 050644719

[15] بول داغوم، ريتشارد كارب، مايكل لوبي، وشيلدون روس. الخوارزمية المثالية لتقدير مونت كارلو. مجلة SIAM حول الحوسبة، 29(5):1484–1496، يناير 2000. دوى:10.1137/S0097539797315306.
الشبكي: / / doi.org/ 10.1137 / S0097539797315306

[16] فيتوريو جيوفانيتي وسيث لويد ولورنزو ماكون. ذاكرة الوصول العشوائي الكمومية. رسائل المراجعة البدنية، 100(16)، أبريل 2008. دوى:10.1103/​physrevlett.100.160501.
الشبكي: / / doi.org/ 10.1103 / physrevlett.100.160501

[17] ساندر جريبلينج وهارولد نيوبور. تحسين الحدود الكمومية الدنيا والعليا لتحجيم المصفوفة. في وقائع الندوة الدولية التاسعة والثلاثين حول الجوانب النظرية لعلوم الكمبيوتر (STACS'39)، المجلد 22، الصفحات 219:35–1:35، 23. أرخايف:2022، دوى:2109.15282/LIPIcs.STACS.10.4230.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2022.35
أرخايف: 2109.15282

[18] مارت دي جراف ورونالد دي وولف. على الإصدارات الكمومية لمبدأ ياو. في الندوة التاسعة عشرة حول الجوانب النظرية لعلوم الكمبيوتر (STACS'19)، المجلد 02 من ملاحظات المحاضرات في علوم الكمبيوتر، الصفحات 2285-347، برلين، هايدلبرغ، 358. سبرينغر. دوى:2002/10.1007-3-540-45841_7.
https:/​/​doi.org/​10.1007/​3-540-45841-7_28

[19] لوف ك. جروفر. خوارزمية ميكانيكية الكم سريعة للبحث عن قاعدة البيانات. في وقائع ندوة ACM السنوية الثامنة والثلاثين حول نظرية الحوسبة (STOC'38)، الصفحات 96-212، 219. أرخايف:quant-ph/1996، دوى:9605043/10.1145.
الشبكي: / / doi.org/ 10.1145 / 237814.237866
أرخايف: ضليع في الرياضيات، وعل / 9605043

[20] لوف ك. جروفر. الحوسبة الكمومية عن بعد، 1997. المذكرة الفنية لمختبرات بيل ITD97-31630F. دوى:10.48550/arXiv.quant-ph/9704012.
https: / / doi.org/10.48550 / arXiv.quant-ph / 9704012
أرخايف: ضليع في الرياضيات، وعل / 9704012

[21] لوف ك. جروفر. إطار عمل لخوارزميات ميكانيكا الكم السريعة. في وقائع ندوة ACM السنوية الثلاثين حول نظرية الحوسبة (STOC'98)، الصفحات 53-62، 1998. أرخايف:quant-ph/9711043، دوى:10.1145/276698.276712.
الشبكي: / / doi.org/ 10.1145 / 276698.276712
أرخايف: ضليع في الرياضيات، وعل / 9711043

[22] ياسين حمودي . مقدر المتوسط ​​الكمي الفرعي. في الندوة الأوروبية السنوية التاسعة والعشرون حول الخوارزميات (ESA 29)، المجلد 2021 من Leibniz International Proceedings in المعلوماتية (LIPIcs)، الصفحات 204:50–1:50، 17. doi:2021/LIPIcs.ESA.10.4230.
https: / / doi.org/ 10.4230 / LIPIcs.ESA.2021.50

[23] سفانتي يانسون. حدود الذيل لمجموع المتغيرات الهندسية والأسية. رسائل الإحصاء والاحتمالات، 135: 1-6، 2018. دوى:10.1016/j.spl.2017.11.017.
https://​/doi.org/10.1016/​j.spl.2017.11.017

[24] دونالد إرفين كنوث. فن برمجة الكمبيوتر، المجلد الثالث. أديسون ويسلي، الطبعة الثانية، 2. URL: https://​/​www.worldcat.org/​oclc/1998.
https://www.worldcat.org/oclc/312994415

[25] روبن كوثاري وريان أودونيل. يعني التقدير عندما يكون لديك شفرة المصدر؛ أو طرق مونت كارلو الكمومية. في وقائع ندوة ACM-SIAM السنوية لعام 2023 حول الخوارزميات المنفصلة (SODA'23)، الصفحات 1186-1215، 2023. دوى:10.1137/1.9781611977554.ch44.
https: / / doi.org/ 10.1137/1.9781611977554.ch44

[26] مايكل أ. نيلسن وإسحاق شوانغ. حساب الكم والمعلومات الكمية. مطبعة جامعة كامبريدج ، 2002.

[27] أشوين ناياك وفيليكس وو. تعقيد الاستعلام الكمي لتقريب الوسيط والإحصائيات ذات الصلة. في وقائع ندوة ACM SIGACT السنوية الحادية والثلاثين حول نظرية الحوسبة (STOC'31)، الصفحات 99-384، 393. أرخايف:quant-ph/1999، دوى:9804066/10.1145.
الشبكي: / / doi.org/ 10.1145 / 301250.301349
أرخايف: ضليع في الرياضيات، وعل / 9804066

[28] بي روس. التقريب ذو الحدين لتوزيع بواسون ذي الحدين: توسيع كروتشوك. نظرية الاحتمالية وتطبيقاتها، 45(2):258-272، 2001. دوى:10.1137/S0040585X9797821X.
https: / / doi.org/ 10.1137 / S0040585X9797821X

[29] روبرت م. يونغ. 75.9 ثابت أويلر. الجريدة الرياضية، 75 (472): 187-190، 1991. دوى:10.2307 / 3620251.
الشبكي: / / doi.org/ 10.2307 / 3620251

دليلنا يستخدم من قبل

نشرت هذه الورقة في الكم تحت نسبة المشاع الإبداعي 4.0 الدولية (CC BY 4.0) رخصة. يظل حقوق الطبع والنشر مع مالكي حقوق الطبع والنشر الأصليين مثل المؤلفين أو مؤسساتهم.

الطابع الزمني:

اكثر من مجلة الكم