بهبود پیچیدگی پرس و جو کوانتومی در ورودی‌های آسان‌تر

بهبود پیچیدگی پرس و جو کوانتومی در ورودی‌های آسان‌تر

تمبر زمان: 8 آوریل 2024 ساعت 11:29 صبح

نوئل تی اندرسون1، جی یو چونگ1, شلبی کیمل1دایئون کوه2، و Xiaohan Ye1,3

1کالج میدلبری، میدلبری، وی تی، ایالات متحده آمریکا
2کالج ویلیامز، ویلیامزتاون، MA، ایالات متحده آمریکا
3دانشگاه براون، پراویدنس، RI، ایالات متحده آمریکا

این مقاله را جالب می دانید یا می خواهید بحث کنید؟ SciRate را ذکر کنید یا در SciRate نظر بدهید.

چکیده

الگوریتم های برنامه دامنه کوانتومی برای ارزیابی توابع گاهی اوقات پیچیدگی پرس و جو را کاهش می دهند که وعده داده می شود ورودی ساختار خاصی دارد. ما یک الگوریتم برنامه span اصلاح‌شده طراحی می‌کنیم تا نشان دهیم که این پیشرفت‌ها حتی بدون وعده قبلی باقی می‌مانند، و این رویکرد را به مشکل کلی‌تر تبدیل حالت تعمیم می‌دهیم. به عنوان یک برنامه کاربردی، ما مزایای کوانتومی نمایی و ابرچند جمله ای را در پیچیدگی پرس و جوی متوسط ​​برای چندین مشکل جستجو ثابت می کنیم و جستجوی مونتانارو با مشاوره را تعمیم می دهیم [مونتانارو، TQC 2010].

Improved Quantum Query Complexity on Easier Inputs PlatoBlockchain Data Intelligence. Vertical Search. Ai.

تصویر ویژه: درخت تصمیم برای ایجاد یکی از الگوریتم‌های ما استفاده می‌شود.

خلاصه محبوب

ما انتظار داریم که الگوریتم‌های کوانتومی، مانند الگوریتم‌های کلاسیک، در ورودی‌های آسان‌تر سریع‌تر اجرا شوند. به عنوان مثال، اگر شما در حال جستجوی یک آیتم در یک لیست نامرتب هستید، و کپی های زیادی از آن آیتم وجود دارد، انتظار داریم الگوریتم کوانتومی در این شرایط در مقایسه با زمانی که فقط یک مورد علامت گذاری شده وجود دارد، حتی بدون اطلاع، سریعتر اجرا شود. تعداد آیتم های هدف از قبل در واقع، برای مشکل جستجو، مشخص است که چگونه می توان چنین مزیتی را در ورودی های آسان تر به دست آورد. با این حال، تعمیم این ایده به مشکلات فراتر از جستجو زمانی چالش برانگیز است که زمانی که محاسبات به اندازه کافی اجرا شده باشد، راه مشخصی برای پرچم گذاری وجود نداشته باشد. ما چندین چارچوب الگوریتمی محبوب را در مدل پرس‌وجو اصلاح می‌کنیم تا پرچم‌هایی ایجاد کنیم که به ما هشدار می‌دهند که آیا محاسبات به اندازه کافی اجرا شده است یا خیر، به ما این امکان را می‌دهد که الگوریتم را با ورودی‌های آسان‌تر پایان دهیم، بدون اینکه از قبل بدانیم آیا نمونه آسان است یا سخت. به عنوان یک برنامه کاربردی، با توجه به توزیع ورودی های آسان و سخت برای یک مسئله، می توانیم میانگین پیچیدگی پرس و جو را تجزیه و تحلیل کنیم. ما نشان می‌دهیم که توزیع‌های معینی از ورودی‌ها برای مشکلات جستجو، مزایای متوسط ​​پرس و جو کوانتومی نسبت به الگوریتم‌های کلاسیک را به همراه دارد.

► داده های BibTeX

◄ مراجع

[1] آندریس آمباینیس و رونالد دو ولف. پیچیدگی پرس و جو کوانتومی متوسط. مجله فیزیک الف: ریاضی و عمومی، 34(35):6741، 2001. doi:10.1088/​0305-4470/​34/​​35/​302.
https:/​/​doi.org/​10.1088/​0305-4470/​34/​35/​302

[2] دوریت آهارونوف. محاسبات کوانتومی بررسی سالانه فیزیک محاسباتی VI، صفحات 259-346، 1999. doi:10.1142/​9789812815569_0007.
https://doi.org/​10.1142/​9789812815569_0007

[3] میشل بویر، ژیل براسارد، پیتر هویر و آلن تپ. محدودیت های محدود در جستجوی کوانتومی Fortschritte der Physik, 46(4-5):493-505, 1998. doi:10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2 -پ.
<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

[4] الکساندر بلووس. برنامه های span برای توابع با گواهینامه های 1 با اندازه ثابت: چکیده توسعه یافته. در مجموعه مقالات چهل و چهارمین سمپوزیوم سالانه ACM در نظریه محاسبات، STOC '12، صفحات 77-84، 2012. doi:10.1145/​2213977.2213985.
https://doi.org/​10.1145/​2213977.2213985

[5] ژیل براسارد، پیتر هویر، میشل موسکا و آلن تپ. تقویت و تخمین دامنه کوانتومی در محاسبات و اطلاعات کوانتومی جلد 305 Contemp. ریاضی، صفحات 53-74. عامر ریاضی. Soc., Providence, RI, 2002. doi:10.1090/​conm/​305/​05215.
https://doi.org/​10.1090/​conm/​305/​05215

[6] ژیل براسارد، پیتر هویر و آلن تپ. شمارش کوانتومی در Automata، Languages ​​and Programming، صفحات 820–831، 1998. doi:10.1007/​BFb0055105.
https://doi.org/​10.1007/​BFb0055105

[7] الکساندر بلوز و بن دبلیو رایشارت. برنامه های span و الگوریتم های کوانتومی برای اتصال st و تشخیص پنجه. یادداشت های سخنرانی در علوم کامپیوتر، 7501 LNCS:193–204، 2012. doi:10.1007/​978-3-642-33090-2_18.
https:/​/​doi.org/​10.1007/​978-3-642-33090-2_18

[8] الکساندر بلووس و انسیس روزمانیس. کران پایین کوانتومی محکم برای شمارش تقریبی با حالات کوانتومی. 2020. arXiv:2002.06879.
arXiv: 2002.06879

[9] سلمان بیگی و لیلا تقوی. افزایش سرعت کوانتومی بر اساس درختان تصمیم گیری کلاسیک. Quantum، 4:241، 2020. doi:10.22331/​q-2020-03-02-241.
https:/​/​doi.org/​10.22331/​q-2020-03-02-241

[10] الکساندر بلووس و دویال یولکو. بلیط یک طرفه به لاس وگاس و دشمن کوانتومی. 2023. arXiv:2301.02003.
arXiv: 2301.02003

[11] ریچارد. کلیو، آرتور. اکرت، کیارا ماکیاولو و میکله موسکا. الگوریتم‌های کوانتومی مورد بازبینی قرار گرفتند. مجموعه مقالات انجمن سلطنتی لندن. سری A: علوم ریاضی، فیزیک و مهندسی، 454 (1969): 339–354، 1998. doi:10.1098/​rspa.1998.0164.
https://doi.org/​10.1098/​rspa.1998.0164

[12] آریان کورنلیسن، استیسی جفری، ماریس اوزولز و آلوارو پیدرافیتا. بازه برنامه ها و پیچیدگی زمانی کوانتومی در چهل و پنجمین سمپوزیوم بین المللی مبانی ریاضی علوم کامپیوتر (MFCS 45). Schloss Dagstuhl-Leibniz-Zentrum für Informatik، 2020. doi:2020/​LIPIcs.MFCS.10.4230.
https://doi.org/​10.4230/​LIPIcs.MFCS.2020.26

[13] کریس کید، اشلی مونتانارو و الکساندر بلووس. الگوریتم‌های کوانتومی کارآمد زمان و مکان برای تشخیص چرخه‌ها و آزمایش دو بخشی اطلاعات و محاسبات کوانتومی، 18 (1-2): 18-50، 2018.

[14] کای دلورنزو، شلبی کیمل و آر. تیل ویتر. کاربردهای الگوریتم کوانتومی برای st-Connectivity. در چهاردهمین کنفرانس تئوری محاسبات کوانتومی، ارتباطات و رمزنگاری (TQC 14)، صفحات 2019:6–1:6، 14. doi:2019/​LIPIcs.TQC.10.4230.
https://doi.org/​10.4230/​LIPIcs.TQC.2019.6

[15] دیمیتری گرینکو، جولین گاکن، کریستا زوفال و استفان وورنر. تخمین دامنه کوانتومی تکراری اطلاعات کوانتومی npj، 7(1):52، مارس 2021. doi:10.1038/​s41534-021-00379-1.
https:/​/​doi.org/​10.1038/​s41534-021-00379-1

[16] لاو کی گروور. مکانیک کوانتومی به جستجوی سوزن در انبار کاه کمک می کند. Physical Review Letters، 79(2):325–328، 1997. doi:10.1103/​PhysRevLett.79.325.
https://doi.org/​10.1103/​PhysRevLett.79.325

[17] واسیلی هوفدینگ نابرابری های احتمال برای مجموع متغیرهای تصادفی محدود. مجله انجمن آماری آمریکا، 58 (301): 13-30، 1963. doi:10.1080/​01621459.1963.10500830.
https://doi.org/​10.1080/​01621459.1963.10500830

[18] تسویوشی ایتو و استیسی جفری برنامه های تقریبی Span. الگوریتمیکا، 81 (6): 2158–2195، 2019. doi:10.1007/​s00453-018-0527-1.
https:/​/​doi.org/​10.1007/​s00453-018-0527-1

[19] مایکل جارت، استیسی جفری، شلبی کیمل و آلوارو پیدرافیتا. الگوریتم های کوانتومی برای اتصال و مسائل مرتبط در بیست و ششمین سمپوزیوم سالانه اروپایی در مورد الگوریتم ها (ESA 26)، صفحات 2018:49–1:49، 13. doi:2018/​LIPIcs.ESA.10.4230.
https://doi.org/​10.4230/​LIPIcs.ESA.2018.49

[20] الکسی یو کیتایف. اندازه گیری های کوانتومی و مسئله تثبیت کننده آبلی 1995. arXiv:quant-ph/​9511026.
arXiv:quant-ph/9511026

[21] تروی لی، راجات میتال، بن دبلیو ریچارد، رابرت اسپالک و ماریو سگدی. پیچیدگی پرس و جوی کوانتومی تبدیل حالت. در سال 2011 پنجاه و دومین سمپوزیوم سالانه IEEE در مبانی علوم کامپیوتر، صفحات 52-344، 353. doi:2011/​FOCS.10.1109.
https://doi.org/​10.1109/​FOCS.2011.75

[22] فردریک مگنیز، اشوین نایاک، ژرمی رولان و میکلوس سانتا. جستجو از طریق کوانتوم واک SIAM Journal on Computing, 40(1):142-164, 2011. doi:10.1137/​090745854.
https://doi.org/​10.1137/​090745854

[23] اشلی مونتانارو. جستجوی کوانتومی با مشاوره در کنفرانس محاسبات کوانتومی، ارتباطات و رمزنگاری، صفحات 77-93. Springer, 2010. doi:10.1007/​978-3-642-18073-6_7.
https:/​/​doi.org/​10.1007/​978-3-642-18073-6_7

[24] بن دبلیو رایشارت برنامه های span و پیچیدگی پرس و جو کوانتومی: کران دشمن عمومی برای هر تابع بولی تقریباً محدود است. پنجاهمین سمپوزیوم سالانه IEEE در مبانی علوم کامپیوتر، صفحات 50-544، 551. doi:2009/​FOCS.10.1109.
https://doi.org/​10.1109/​FOCS.2009.55

[25] بن دبلیو رایشارت بازتاب هایی برای الگوریتم های پرس و جو کوانتومی. در مجموعه مقالات سمپوزیوم سالانه ACM-SIAM 2011 در مورد الگوریتم های گسسته، مجموعه مقالات، صفحات 560-569. 2011. doi:10.1137/​1.9781611973082.44.
https://doi.org/​10.1137/​1.9781611973082.44

[26] لیلا تقوی. الگوریتم کوانتومی ساده شده برای مسئله شناسایی اوراکل. هوش ماشین کوانتومی، 4 (2): 19، 2022. doi:10.1007/​s42484-022-00080-2.
https:/​/​doi.org/​10.1007/​s42484-022-00080-2

ذکر شده توسط

[1] استیسی جفری، شلبی کیمل، و آلوارو پیدرافیتا، "الگوریتم کوانتومی برای نمونه برداری از لبه مسیر"، arXiv: 2303.03319, (2023).

[2] مایکل چکانسکی، شلبی کیمل و آر. تیل ویتر، «الگوریتم‌های کوانتومی دشمن دوگانه قوی و کارآمد»، arXiv: 2306.15040, (2023).

نقل قول های بالا از SAO/NASA Ads (آخرین به روز رسانی با موفقیت 2024-04-11 15:45:18). فهرست ممکن است ناقص باشد زیرا همه ناشران داده های استنادی مناسب و کاملی را ارائه نمی دهند.

On سرویس استناد شده توسط Crossref هیچ داده ای در مورد استناد به آثار یافت نشد (آخرین تلاش 2024-04-11 15:45:17).

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

تمبر زمان:

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