زیربرنامه های پایه کوانتومی: یافتن چندین عنصر مشخص شده و جمع اعداد

زیربرنامه های پایه کوانتومی: یافتن چندین عنصر مشخص شده و جمع اعداد

تمبر زمان: 14 مارس 2024، 9:40 صبح
Basic quantum subroutines: finding multiple marked elements and summing numbers PlatoBlockchain Data Intelligence. Vertical Search. Ai.

جوران ون آپلدورن1, ساندر گریبلینگ2و هارولد نیوبور3

1IViR و QuSoft، دانشگاه آمستردام، هلند
2گروه اقتصاد سنجی و تحقیقات عملیاتی، دانشگاه تیلبورگ، تیلبورگ، هلند
3موسسه ریاضیات Korteweg-de Vries و QuSoft، دانشگاه آمستردام، هلند و دانشکده علوم کامپیوتر، دانشگاه روهر بوخوم، آلمان و گروه علوم ریاضی، دانشگاه کپنهاگ، دانمارک

این مقاله را جالب می دانید یا می خواهید بحث کنید؟ SciRate را ذکر کنید یا در 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

◄ مراجع

[1] سرینیواسان آروناچالم و رونالد دو ولف. بهینه سازی تعداد گیت ها در جستجوی کوانتومی اطلاعات کوانتومی Comput., 17(3-4):251-261, 2017. doi:10.26421/​qic17.3-4.
https://doi.org/​10.26421/​qic17.3-4

[2] خوزه آدل و پی جودرا. کلموگروف دقیق و فاصله تغییرات کل بین برخی از توزیع های گسسته آشنا. مجله نابرابری ها و کاربردها، 2006 (1): 1-8، 2006. doi:10.1155/​JIA/​2006/​64307.
https://doi.org/​10.1155/​JIA/​2006/​64307

[3] جوران ون آپلدورن، ساندر گریبلینگ، یینان لی، هارولد نیوبور، مایکل والتر و رونالد دی ولف. الگوریتم‌های کوانتومی برای مقیاس‌بندی ماتریس و متعادل‌سازی ماتریس. در مجموعه مقالات چهل و هشتمین کنفرانس بین المللی خودکار، زبان ها و برنامه نویسی (ICALP'48)، جلد 21، صفحات 198:110–1:110، 17. arXiv:2021, doi:2011.12823/​LIPics.10.4230.
https://doi.org/​10.4230/​LIPIcs.ICALP.2021.110
arXiv: 2011.12823

[4] اسکات آرونسون و پاتریک رال. شمارش تقریبی کوانتومی، ساده شده. در Symposium on Simplicity in Algorithms، صفحات 24-32، 2020. doi:10.1137/​1.9781611976014.5.
https://doi.org/​10.1137/​1.9781611976014.5

[5] میشل بویر، ژیل براسارد، پیتر هویر و آلن تپ. محدودیت های محکم در جستجوی کوانتومی. Fortschritte der Physik, 46(4-5):493-505, 1998. نسخه قبلی در Physcomp'96. arXiv:quant-ph/9605034.
arXiv:quant-ph/9605034

[6] هری بورمن، ریچارد کلیو، رونالد دی ولف و کریستف زالکا. مرزهای الگوریتم های کوانتومی با خطای کوچک و صفر خطا. در چهلمین سمپوزیوم سالانه مبانی علوم کامپیوتر (FOCS'40)، صفحات 99-358. IEEE Computer Society، 368.

[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-T.
https:/​/​doi.org/​10.1016/​0020-0190(94)00171-T

[10] کارلو کیلیبرتو، مارک هربستر، الساندرو داویده ایالونگو، ماسیمیلیانو پونتیل، آندره آ روچتو، سیمونه سورینی و لئونارد ووسنیگ. یادگیری ماشین کوانتومی: دیدگاه کلاسیک Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, Jan 2018. doi:10.1098/​rspa.2017.0551.
https://doi.org/​10.1098/​rspa.2017.0551

[11] توماس اچ. کورمن، چارلز ای. لیزرسون، رونالد ال. ریوست، و کلیفورد استاین. مقدمه ای بر الگوریتم ها مطبوعات MIT، ویرایش چهارم، 4.

[12] P. Diaconis و D. Freedman. دنباله های قابل تعویض محدود The Annals of Probability, 8 (4): 745-764, 1980. URL: https://www.jstor.org/​stable/​2242823.
https://www.jstor.org/​stable/​2242823

[13] کریستف دور و پیتر هویر. یک الگوریتم کوانتومی برای یافتن حداقل، 1996. doi:10.48550/​arXiv.quant-ph/​9607014.
https://doi.org/​10.48550/​arXiv.quant-ph/​9607014
arXiv:quant-ph/9607014

[14] کریستوف دور، مارک هایلیگمن، پیتر هویر و مهدی محلا. پیچیدگی پرس و جوی کوانتومی برخی از مسائل گراف. SIAM Journal on Computing, 35(6):1310-1328, ژانویه 2006. doi:10.1137/​050644719.
https://doi.org/​10.1137/​050644719

[15] پل داگوم، ریچارد کارپ، مایکل لوبی و شلدون راس. الگوریتم بهینه برای تخمین مونت کارلو SIAM Journal on Computing, 29(5):1484–1496, ژانویه 2000. doi:10.1137/​S0097539797315306.
https://doi.org/​10.1137/​S0097539797315306

[16] ویتوریو جیووانتی، ست لوید و لورنزو مکونه. حافظه دسترسی تصادفی کوانتومی Physical Review Letters، 100(16)، آوریل 2008. doi:10.1103/​physrevlett.100.160501.
https://doi.org/​10.1103/​physrevlett.100.160501

[17] ساندر گریبلینگ و هارولد نیوبور. مرزهای پایین و بالایی کوانتومی برای مقیاس بندی ماتریس بهبود یافته است. در مجموعه مقالات سی و نهمین سمپوزیوم بین المللی جنبه های نظری علوم کامپیوتر (STACS'39)، جلد 22، صفحات 219:35–1:35، 23. arXiv:2022, doi:2109.15282/​LIPIcs.10.4230.STACS.2022.35.
https://doi.org/​10.4230/​LIPIcs.STACS.2022.35
arXiv: 2109.15282

[18] مارت دو گراف و رونالد دو ولف. در مورد نسخه های کوانتومی اصل یائو در نوزدهمین سمپوزیوم جنبه های نظری علوم کامپیوتر (STACS'19)، جلد 02 از یادداشت های سخنرانی در علوم کامپیوتر، صفحات 2285-347، برلین، هایدلبرگ، 358. Springer. doi: 2002/​10.1007-3-540-45841_7.
https:/​/​doi.org/​10.1007/​3-540-45841-7_28

[19] لاو کی گروور. یک الگوریتم مکانیکی کوانتومی سریع برای جستجو در پایگاه داده. در مجموعه مقالات سی و هشتمین سمپوزیوم سالانه ACM در تئوری محاسبات (STOC'38)، صفحات 96-212، 219. arXiv:quant-ph/​1996, doi:9605043/​10.1145.
https://doi.org/​10.1145/​237814.237866
arXiv:quant-ph/9605043

[20] لاو کی گروور. محاسبات کوانتومی، 1997. یادداشت فنی آزمایشگاه های بل ITD97-31630F. doi:10.48550/​arXiv.quant-ph/​9704012.
https://doi.org/​10.48550/​arXiv.quant-ph/​9704012
arXiv:quant-ph/9704012

[21] لاو کی گروور. چارچوبی برای الگوریتم های مکانیکی کوانتومی سریع در مجموعه مقالات سی امین سمپوزیوم سالانه ACM در نظریه محاسبات (STOC'98)، صفحات 53-62، 1998. arXiv:quant-ph/​9711043, doi:10.1145/​276698.276712.
https://doi.org/​10.1145/​276698.276712
arXiv:quant-ph/9711043

[22] یاسین حمودی. برآوردگر میانگین کوانتومی زیر گاوسی. در بیست و نهمین سمپوزیوم سالانه اروپایی در مورد الگوریتم ها (ESA 29)، جلد 2021 مجموعه مقالات بین المللی لایب نیتس در انفورماتیک (LIPIcs)، صفحات 204:50–1:50، 17. doi:2021/​LIPIcs.ESA.10.4230.
https://doi.org/​10.4230/​LIPIcs.ESA.2021.50

[23] سوانت جانسون. کران دم برای مجموع متغیرهای هندسی و نمایی. Statistics & Probability Letters، 135:1–6، 2018. doi:10.1016/​j.spl.2017.11.017.
https://doi.org/​10.1016/​j.spl.2017.11.017

[24] دونالد اروین کنوت. هنر برنامه نویسی کامپیوتر جلد سوم. ادیسون-وسلی، ویرایش دوم، 2. نشانی اینترنتی: https://www.worldcat.org/​oclc/​1998.
https://www.worldcat.org/​oclc/​312994415

[25] رابین کوتاری و رایان اودانل برآورد میانگین زمانی که کد منبع را دارید. یا روش های کوانتومی مونت کارلو. در مجموعه مقالات سمپوزیوم سالانه ACM-SIAM 2023 در مورد الگوریتم های گسسته (SODA'23)، صفحات 1186-1215، 2023. doi:10.1137/​1.9781611977554.ch44.
https://doi.org/​10.1137/​1.9781611977554.ch44

[26] مایکل ای. نیلسن و آیزاک ال. چوانگ. محاسبات کوانتومی و اطلاعات کوانتومی انتشارات دانشگاه کمبریج، 2002.

[27] اشوین نایاک و فلیکس وو. پیچیدگی پرس و جوی کوانتومی تقریب میانه و آمار مرتبط. در مجموعه مقالات سی و یکمین سمپوزیوم سالانه ACM SIGACT در نظریه محاسبات (STOC'31)، صفحات 99-384، 393. arXiv:quant-ph/​1999, doi:9804066/​10.1145.
https://doi.org/​10.1145/​301250.301349
arXiv:quant-ph/9804066

[28] B. Roos. تقریب دو جمله ای به توزیع دو جمله ای پواسون: بسط Krawtchouk. نظریه احتمال و کاربردهای آن، 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/​3620251

ذکر شده توسط

این مقاله در Quantum تحت عنوان منتشر شده است Creative Commons Attribution 4.0 International (CC BY 4.0) مجوز. حق چاپ نزد دارندگان حق چاپ اصلی مانند نویسندگان یا مؤسسات آنها باقی می ماند.

تمبر زمان:

بیشتر از مجله کوانتومی