1گروه فیزیک، ETH زوریخ، سوئیس
2موسسه مطالعات نظری، ETH زوریخ، سوئیس
این مقاله را جالب می دانید یا می خواهید بحث کنید؟ SciRate را ذکر کنید یا در SciRate نظر بدهید.
چکیده
اثبات کوانتومی نوعی پروتکل چالش-پاسخ است که در آن یک تأییدکننده کلاسیک می‌تواند به طور مؤثری $textit{مزیت کوانتومی}$ یک اثبات‌کننده نامعتبر را تأیید کند. به این معنا که یک اثبات‌کننده کوانتومی می‌تواند به درستی به چالش‌های تأییدکننده پاسخ دهد و پذیرفته شود، در حالی که هر اثبات‌کننده کلاسیک چند جمله‌ای بر اساس فرضیات محاسباتی قابل قبول، با احتمال زیاد رد می‌شود. برای پاسخ به چالش‌های تأییدکننده، اثبات‌های موجود کوانتومی معمولاً به اثبات‌کننده کوانتومی نیاز دارند که ترکیبی از مدارها و اندازه‌گیری‌های کوانتومی با اندازه چند جمله‌ای را انجام دهد.
در این مقاله، دو اثبات ساختار کوانتومی ارائه می‌کنیم که در آنها اثبات‌کننده فقط باید $textit{مدارهای کوانتومی با عمق ثابت}$ (و اندازه‌گیری‌ها) را همراه با محاسبات کلاسیک با عمق لگ انجام دهد. اولین ساخت ما یک کامپایلر عمومی است که به ما امکان می دهد تمام اثبات های موجود کوانتومی را به نسخه های عمق کوانتومی ثابت ترجمه کنیم. ساختار دوم ما بر اساس مشکل $textit{learning with rounding}$ است، و مدارهایی با عمق کمتر و نیاز به کیوبیت های کمتری نسبت به ساختار عمومی دارد. علاوه بر این، ساخت و ساز دوم نیز از استحکام خاصی در برابر نویز برخوردار است.
► داده های BibTeX
◄ مراجع
[1] اسکات آرونسون و الکس آرخیپوف پیچیدگی محاسباتی اپتیک خطی در مجموعه مقالات چهل و سومین سمپوزیوم سالانه ACM در نظریه محاسبات، صفحات 333-342، 2011.
https://doi.org/10.1145/1993636.1993682
[2] فرانک آروت، کونال آریا، رایان بابوش، دیو بیکن، جوزف سی باردین، رامی بارندز، روپاک بیسواس، سرجیو بویکسو، فرناندو جی‌اس‌ال براندائو، دیوید آ بوئل و دیگران. برتری کوانتومی با استفاده از یک پردازنده ابررسانا قابل برنامه ریزی. Nature، 574(7779):505–510، 2019.
https://doi.org/10.1038/s41586-019-1666-5
[3] MD SAJID ANIS، Abby-Mitchell، Héctor Abraham، AduOffei، و همکاران. Qiskit: یک چارچوب منبع باز برای محاسبات کوانتومی، 2021.
[4] Sanjeev Arora و Boaz Barak. پیچیدگی محاسباتی: یک رویکرد مدرن انتشارات دانشگاه کمبریج، 2009.
[5] اسکات آرونسون و لیجی چن. پیچیدگی-تئوری مبانی آزمایش های برتری کوانتومی. در مجموعه مقالات سی و دومین کنفرانس پیچیدگی محاسباتی، CCC '32، صفحات 17-1، Dagstuhl، DEU، 67. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https://doi.org/10.48550/arXiv.1612.05903
[6] اسکات آرونسون و سام گان در مورد سختی کلاسیک جعل محک خطی متقاطع آنتروپی. نظریه محاسبات، 16 (11): 1-8، 2020.
https://doi.org/10.4086/toc.2020.v016a011
[7] B. Applebaum، Y. Ishai و E. Kushilevitz. رمزنگاری در ${NC}^0$. در چهل و پنجمین سمپوزیوم سالانه IEEE در مبانی علوم کامپیوتر، صفحات 45-166، 175.
https://doi.org/10.1109/FOCS.2004.20
[8] جوئل آلون، استفان کرن، کریستوف پیترزاک و دانیل ویچس. یادگیری با Rounding، بازبینی شده است. In Advances in Cryptology – CRYPTO 2013, pages 57–74, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-40041-4_4
[9] دیوید بارینگتون. برنامه های انشعاب با اندازه چند جمله ای با پهنای محدود دقیقاً آن زبان ها را در ${NC}^1$ تشخیص می دهند. مجله علوم کامپیوتر و سیستم، 38 (1): 150-164، 1989.
https://doi.org/10.1016/0022-0000(89)90037-8
[10] زویکا براکرسکی، پل کریستیانو، اورمیلا مهادف، اومش وزیرانی و توماس ویدیک. تست رمزنگاری کوانتومی و تصادفی بودن قابل تایید از یک دستگاه کوانتومی منفرد. در سال 2018 IEEE پنجاه و نهمین سمپوزیوم سالانه مبانی علوم کامپیوتر (FOCS)، صفحات 59-320. IEEE، 331.
https://doi.org/10.1145/3441309
[11] کالین دی. بروزوویچ، جان چیاورینی، رابرت مک کانل، و جرمی ام. سیج. محاسبات کوانتومی یون به دام افتاده: پیشرفت و چالش ها بررسی های فیزیک کاربردی، 2019.
https://doi.org/10.1063/1.5088164
[12] آدام بولند، بیل ففرمن، چینمای نیرکه و اومش وزیرانی. در مورد پیچیدگی و تأیید نمونه‌برداری مدار تصادفی کوانتومی. فیزیک طبیعت، 15 (2): 159-163، فوریه 2019.
https://doi.org/10.1038/s41567-018-0318-2
[13] سرجیو بویکسو، سرگئی وی ایزاکوف، وادیم ان اسملیانسکی، رایان بابوش، نان دینگ، ژانگ جیانگ، مایکل جی برمنر، جان ام مارتینیس و هارتموت نون. مشخص کردن برتری کوانتومی در دستگاه های کوتاه مدت فیزیک طبیعت، 14 (6): 595-600، 2018.
https://doi.org/10.1038/s41567-018-0124-x
[14] زویکا براکرسکی، ونکاتا کوپولا، اومش وزیرانی و توماس ویدیک. اثبات ساده تر کوانتومی در پانزدهمین کنفرانس تئوری محاسبات کوانتومی، ارتباطات و رمزنگاری (TQC 15)، جلد 2020 مجموعه مقالات بین المللی لایبنیتس در انفورماتیک (LIPIcs)، صفحات 158:8-1:8، داگستول، آلمان، 14. SchlossLeniz-Dagstuhl– Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.TQC.2020.8
[15] آبیشک بانرجی، کریس پیکرت و آلون روزن. توابع و شبکه های شبه تصادفی In Advances in Cryptology – EUROCRYPT 2012، صفحات 719-737. اسپرینگر برلین هایدلبرگ، 2012.
https://doi.org/10.1007/978-3-642-29011-4_42
[16] جان اف کلوزر، مایکل اِهورن، آبنر شیمونی و ریچارد آ هولت. آزمایش پیشنهادی برای آزمایش نظریه‌های متغیر پنهان محلی Physical Review Letters، 23(15):880، 1969.
https://doi.org/10.1103/PhysRevLett.23.880
[17] متیو کودرون، ژالکس استارک و توماس ویدیک. محل معامله برای زمان: تصادفی بودن قابل تایید از مدارهای با عمق پایین. ارتباطات در فیزیک ریاضی، 382 (1): 49-86، 2021.
https://doi.org/10.1007/s00220-021-03963-w
[18] ریچارد کلیو و جان واتروس مدارهای موازی سریع برای تبدیل فوریه کوانتومی. در مجموعه مقالات چهل و یکمین سمپوزیوم سالانه مبانی علوم کامپیوتر، صفحات 41-526. IEEE، 536.
https://doi.org/10.1109/SFCS.2000.892140
[19] پیر دوزارت. Autour de la fonction qui compte le nombre de nombres premiers. پایان نامه دکتری، دانشگاه لیموژ، 1998.
https://www.unilim.fr/laco/theses/1998/T1998_01.pdf
[20] آستین جی فاولر، متئو ماریانتونی، جان ام مارتینیس و اندرو ان کلیلند. کدهای سطحی: به سوی محاسبات کوانتومی در مقیاس بزرگ. بررسی فیزیکی A، 86 (3): 032324، 2012.
https://doi.org/10.1103/PhysRevA.86.032324
[21] فرانسوا لو گال. مکاتبات خصوصی، 2022.
[22] کریگ گیدنی و مارتین اکراو. چگونه اعداد صحیح 2048 بیتی RSA را در 8 ساعت با استفاده از 20 میلیون کیوبیت پر سر و صدا فاکتور کنیم. کوانتوم، 5:433، 2021.
https://doi.org/10.22331/q-2021-04-15-433
[23] الکساندرو گئورگیو و متی جی هوبان. تخمین آنتروپی خروجی های مدار کم عمق دشوار است. پیش چاپ arXiv arXiv:2002.12814، 2020.
https://doi.org/10.48550/arXiv.2002.12814
arXiv: 2002.12814
[24] شویچی هیراهارا و فرانسوا لو گال. تست کوانتومی با مدارهای کوانتومی با عمق کوچک. در چهل و ششمین سمپوزیوم بین‌المللی مبانی ریاضی علوم کامپیوتر (MFCS 46)، جلد 2021 مجموعه مقالات بین‌المللی لایبنیتس در انفورماتیک (LIPIcs)، صفحات 202:59–1:59، داگستول، آلمان، 15. Schloss Dagstuhl – Leibniz-Leibniz .
https://doi.org/10.4230/LIPIcs.MFCS.2021.59
[25] آرام دبلیو هارو و اشلی مونتانارو. برتری محاسباتی کوانتومی Nature، 549(7671):203-209، 2017.
https://doi.org/10.1038/nature23458
[26] پیتر هویر و رابرت اسپالک. فن اوت کوانتومی قدرتمند است. نظریه محاسبات، 1 (5): 81-103، 2005.
https://doi.org/10.4086/toc.2005.v001a005
[27] Cupjin Huang، Fang Zhang، Michael Newman، Junjie Cai، Xun Gao، Zhengxiong Tian، Junyin Wu، Haihong Xu، Huanjun Yu، Bo Yuan، Mario Szegedy، Yaoyun Shi و Jianxin Chen. شبیه سازی کلاسیک مدارهای برتری کوانتومی. پیش چاپ arXiv arXiv:2005.06787، 2020.
https://doi.org/10.48550/arXiv.2005.06787
arXiv: 2005.06787
[28] گرگوری دی کاهاناموکو-مایر. جعل داده های کوانتومی: به طور کلاسیک شکست دادن آزمایش کوانتومی مبتنی بر IQP. پیش چاپ arXiv arXiv:1912.05547، 2019.
https://doi.org/10.48550/arXiv.1912.05547
arXiv: 1912.05547
[29] گرگوری دی. کاهاناموکو-مایر، سون وون چوی، اومش وی. وزیرانی، و نورمن ی. یائو. مزیت کوانتومی قابل تأیید کلاسیک از آزمون بل محاسباتی. فیزیک طبیعت، 18 (8): 918-924، 2022.
https://doi.org/10.1038/s41567-022-01643-7
[30] وادیم لیوباشفسکی، کریس پیکرت و اودد رگو. در شبکه های ایده آل و یادگیری با خطاهای روی حلقه ها. در کنفرانس بین المللی سالانه نظریه و کاربردهای تکنیک های رمزنگاری، صفحات 1-23. اسپرینگر، 2010.
https://doi.org/10.1145/2535925
[31] اورمیلا مهادف. تایید کلاسیک محاسبات کوانتومی در سال 2018 IEEE پنجاه و نهمین سمپوزیوم سالانه مبانی علوم کامپیوتر (FOCS)، صفحات 59-259. IEEE، 267.
https://doi.org/10.1109/FOCS.2018.00033
[32] مایکل آ نیلسن و آیزاک چوانگ. محاسبات کوانتومی و اطلاعات کوانتومی، 2002.
[33] AS Popova و AN Rubtsov. شکستن آستانه مزیت کوانتومی برای نمونه برداری از بوزون گاوسی. در کنفرانس و نمایشگاه کوانتوم 2.0، صفحه QW2A.15. گروه انتشارات اپتیکا، 2022.
https://doi.org/10.1364/QUANTUM.2022.QW2A.15
[34] جان پرسکیل. محاسبات کوانتومی در عصر NISQ و فراتر از آن. کوانتوم، 2:79، 2018.
https://doi.org/10.22331/q-2018-08-06-79
[35] مایکل او رابین الگوریتم احتمالی برای آزمایش اولیه بودن. مجله نظریه اعداد، 12 (1): 128-138، 1980.
https://doi.org/10.1016/0022-314X(80)90084-0
[36] اودد رگو. در شبکه‌ها، یادگیری با خطاها، کدهای خطی تصادفی و رمزنگاری. مجله ACM (JACM)، 56 (6): 1-40، 2009.
https://doi.org/10.1145/1568318.1568324
[37] دن شپرد و مایکل جی برمنر. محاسبات کوانتومی بدون ساختار زمانی مجموعه مقالات انجمن سلطنتی الف: علوم ریاضی، فیزیک و مهندسی، 465 (2105): 1413-1439، 2009.
https://doi.org/10.1098/rspa.2008.0443
[38] پیتر دبلیو شور. الگوریتم‌های محاسبات کوانتومی: لگاریتم‌های گسسته و فاکتورسازی در مجموعه مقالات سی و پنجمین سمپوزیوم سالانه مبانی علوم کامپیوتر، صفحات 35-124. IEEE، 134.
https://doi.org/10.1109/SFCS.1994.365700
[39] یولین وو، وان سو بائو، سیروی کائو، فوشنگ چن، مینگ-چنگ چن، شیاوی چن، تونگ-هسون چونگ، هوی دنگ، یاجی دو، دائوجین فن، مینگ گونگ، چنگ گو، چو گو، شائوجون گو، لیانچن هان لینین هونگ، ه-لیانگ هوانگ، یونگ-هنگ هو، لیپینگ لی، نا لی، شائووی لی، یوان لی، فوتین لیانگ، چون لین، جین لین، هائوران کیان، دان کیائو، هائو رونگ، هونگ سو، لیهوا سان، لیانگیوان وانگ، شییو وانگ، داچائو وو، یو خو، کای یان، ویفنگ یانگ، یانگ یانگ، یانگسن یه، جیانگهان یین، چونگ یینگ، جیاله یو، چن ژا، چا ژانگ، هایبین ژانگ، کایلی ژانگ، ییمینگ ژانگ، هان ژائو ، یووی ژائو، لیانگ ژو، چینگلینگ ژو، چائو یانگ لو، چنگ-ژی پنگ، شیائوبو ژو و جیان وی پان. مزیت محاسباتی کوانتومی قوی با استفاده از یک پردازنده کوانتومی ابررسانا. فیزیک Rev. Lett., 127:180501, 2021.
https://doi.org/10.1103/PhysRevLett.127.180501
[40] K Wright، KM Beck، Sea Debnath، JM Amini، Y Nam، N Grzesiak، JS Chen، NC Pisenti، M Chmielewski، C Collins، و همکاران. ارزیابی یک کامپیوتر کوانتومی 11 کیوبیتی ارتباطات طبیعت، 10 (1): 1-6، 2019.
https://doi.org/10.1038/s41467-019-13534-2
[41] جی وندین. پردازش اطلاعات کوانتومی با مدارهای ابررسانا: بررسی گزارش‌های پیشرفت در فیزیک، 80(10):106001، 2017.
https://doi.org/10.1088/1361-6633/aa7e1a
[42] آدام بن واتس، رابین کوتاری، لوک شفر و آویشای تال. جدایی نمایی بین مدارهای کوانتومی کم عمق و مدارهای کلاسیک کم عمق فن نامحدود. در مجموعه مقالات پنجاه و یکمین سمپوزیوم سالانه ACM SIGACT در نظریه محاسبات، صفحات 51-515، 526.
https://doi.org/10.1145/3313276.3316404
[43] اندرو چی چیه یائو نحوه تولید و تبادل اسرار در بیست و هفتمین سمپوزیوم سالانه مبانی علوم کامپیوتر (sfcs 27)، صفحات 1986-162. IEEE، 167.
https://doi.org/10.1109/SFCS.1986.25
[44] چینگلینگ ژو، سیروی کائو، فوشنگ چن، مینگ-چنگ چن، ژیاوی چن، تونگ-هسون چونگ، هوی دنگ، یاجی دو، دائوجین فن، مینگ گونگ، چنگ گو، چو گو، شائوجون گو، لیانچن هان، لینین هونگ، او -لیانگ هوانگ، یونگ-هنگ هو، لیپینگ لی، نا لی، شائووی لی، یوان لی، فوتین لیانگ، چون لین، جین لین، هائوران کیان، دان کیائو، هائو رونگ، هونگ سو، لیهوا سان، لیانگیوان وانگ، شییو وانگ داچائو وو، یولین وو، یو خو، کای یان، ویفنگ یانگ، یانگ یانگ، یانگسن یه، جیانگهان یین، چونگ یینگ، جیاله یو، چن ژا، چا ژانگ، هایبین ژانگ، کیلی ژانگ، ییمین ژانگ، هان ژائو، یووی ژائو، لیانگ ژو، چائو یانگ لو، چنگ ژی پنگ، شیائوبو ژو و جیان وی پان. مزیت محاسباتی کوانتومی از طریق نمونه برداری مدار تصادفی 60 سیکلی 24 کیوبیتی. بولتن علوم، 67 (3): 240-245، 2022.
https://doi.org/10.1016/j.scib.2021.10.017
[45] دایوی ژو، گرگوری دی. کاهاناموکو-مایر، لورا لوئیس، کریستال نوئل، اور کاتز، بها هراز، چینگ فنگ وانگ، اندرو رایزینگر، لی فنگ، دبوپریو بیسواس، لیرد ایگان، الکساندرو گئورگیو، یونسئونگ نام، توماس ویدیک، یائو، مارکو سیتینا و کریستوفر مونرو. پروتکل های تعاملی برای مزیت کوانتومی قابل تأیید کلاسیک. پیش چاپ arXiv arXiv:2112.05156، 2021.
https://doi.org/10.48550/arXiv.2112.05156
arXiv: 2112.05156
[46] هان سن ژونگ، هوی وانگ، یو هائو دنگ، مینگ چنگ چن، لی چائو پنگ، یی هان لو، جیان چین، دیان وو، زینگ دینگ، یی هو، پنگ هو، شیائو-یان یانگ، وی- جون ژانگ، هائو لی، یوشوان لی، شیائو جیانگ، لین گان، گوانگ ون یانگ، لیکسینگ یو، ژن وانگ، لی لی، نای-له لیو، چائو یانگ لو و جیان وی پان. مزیت محاسباتی کوانتومی با استفاده از فوتون Science, 370(6523):1460-1463, 2020.
https://doi.org/10.1126/science.abe8770
ذکر شده توسط
[1] ناتانان تانتیواساداکارن، اشوین ویشوانات و روبن ورسن، "سلسله مراتبی از نظم توپولوژیکی از واحدهای عمق محدود، اندازه گیری و پیشخور" arXiv: 2209.06202.
[2] سرگئی براوی، آیزاک کیم، الکساندر کلیش، و رابرت کونیگ، "مدارهای عمق ثابت تطبیقی برای دستکاری افراد غیرآبلین"، arXiv: 2205.01933.
[3] دایوی ژو، گرگوری دی. کاهاناموکو-مایر، لورا لوئیس، کریستال نوئل، یا کاتز، بها هراز، چینگ فنگ وانگ، اندرو رایزینگر، لی فنگ، دبوپریو بیسواس، لیرد ایگان، الکساندرو گئورگیو، یونسئونگ نام، توماس ویدی وزیرانی، نورمن وای یائو، مارکو سیتینا و کریستوفر مونرو، «پروتکل‌های تعاملی برای مزیت کوانتومی قابل تأیید کلاسیک»، arXiv: 2112.05156.
[4] ویپین سینگ سهروات، فو یی یو، و دیمیتری واسیلیف، "PRF های کلیدی هممورفیک خاص ستاره از رگرسیون خطی و نظریه مجموعه های اکستریمال"، arXiv: 2205.00861.
[5] Gregory D. Kahanamoku-Meyer، Soonwon Choi، Umesh V. Vazirani و Norman Y. Yao، "مزیت کوانتومی قابل تایید کلاسیک از آزمون بل محاسباتی". Nature Physics 18 8, 918 (2022).
[6] روزبه باسیریان، آدام بولاند، بیل ففرمن، سام گان و آویشای تال، «درباره تصادفی بودن تایید شده از آزمایش‌های مزیت کوانتومی»، arXiv: 2111.14846.
[7] Nai-Hui Chia و Shih-Han Hung، "تأیید کلاسیک عمق کوانتومی"، arXiv: 2205.04656.
[8] آکیهیرو میزوتانی، یوکی تاکوچی، ریو هیروماسا، یوسوکه آیکاوا و سیچیرو تانی، "خودآزمایی محاسباتی برای حالات جادویی درهم تنیده"، بررسی فیزیکی A 106 1، L010601 (2022).
[9] Yihui Quek، Mark M. Wilde و Eneet Kaur، "تخمین ردیابی چند متغیره در عمق کوانتومی ثابت"، arXiv: 2206.15405.
نقل قول های بالا از SAO/NASA Ads (آخرین به روز رسانی با موفقیت 2022-09-21 12:16:02). فهرست ممکن است ناقص باشد زیرا همه ناشران داده های استنادی مناسب و کاملی را ارائه نمی دهند.
On سرویس استناد شده توسط Crossref هیچ داده ای در مورد استناد به آثار یافت نشد (آخرین تلاش 2022-09-21 12:16:00).
این مقاله در Quantum تحت عنوان منتشر شده است Creative Commons Attribution 4.0 International (CC BY 4.0) مجوز. حق چاپ نزد دارندگان حق چاپ اصلی مانند نویسندگان یا مؤسسات آنها باقی می ماند.
