1موسسه اطلاعات و ماده کوانتومی، موسسه فناوری کالیفرنیا، پاسادنا، CA 91125، ایالات متحده آمریکا
2علوم کامپیوتر، دانشگاه تافتس، مدفورد، MA 02155، ایالات متحده آمریکا
این مقاله را جالب می دانید یا می خواهید بحث کنید؟ SciRate را ذکر کنید یا در SciRate نظر بدهید.
چکیده
دایمی هم برای تئوری پیچیدگی و هم برای ترکیبیات بسیار مهم است. در محاسبات کوانتومی، دائمی در بیان دامنه‌های خروجی محاسبات نوری خطی، مانند مدل نمونه‌برداری بوزون، ظاهر می‌شود. با بهره گیری از این ارتباط، ما شواهد الهام گرفته از کوانتومی بسیاری از هویت های دائمی قابل توجه موجود و همچنین جدید ارائه می دهیم. مهم‌تر از همه، ما یک اثبات الهام‌گرفته از کوانتومی قضیه اصلی مک ماهون و همچنین اثبات‌هایی برای تعمیم‌های جدید این قضیه ارائه می‌دهیم. اثبات های قبلی این قضیه از ایده های کاملا متفاوتی استفاده می کردند. فراتر از کاربردهای کاملاً ترکیبی آنها، نتایج ما سختی کلاسیک نمونه برداری دقیق و تقریبی از محاسبات کوانتومی نوری خطی با حالت های ورودی گربه را نشان می دهد.
تصویر ویژه: اثبات‌های الهام‌گرفته از کوانتومی منجر به نتایج پیچیدگی جدیدی در مورد محاسبات کوانتومی با ورودی حالت‌های گربه می‌شوند (تصویر انتزاعی ایجاد شده با استفاده از DALL.E).
خلاصه محبوب
با بهره‌برداری از روابط بین دایمی و دامنه‌های مدارهای کوانتومی نوری خطی، نشان می‌دهیم که تکنیک‌های الهام‌گرفته از کوانتوم اثبات‌های سریع بسیاری از قضایای مهم در مورد دائمی، مانند قضیه استاد مک ماهون را ارائه می‌دهند.
اثبات‌های الهام‌گرفته از کوانتومی ما بینش جدیدی در مورد قضایای ترکیبی برای دانشمند کوانتومی فراهم می‌کند و نتایج جدیدی را در پیچیدگی کوانتومی کشف می‌کند.
► داده های BibTeX
◄ مراجع
[1] H. Minc، “Permanents”، ج. 6. انتشارات دانشگاه کمبریج، 1984.
https://doi.org/10.1017/CBO9781107340688
[2] JK Percus، "روشهای ترکیبی"، جلد. 4. Springer Science & Business Media، 2012.
https://doi.org/10.1007/978-1-4612-6404-0
[3] LG Valiant، "پیچیدگی محاسبات دائمی"، علوم کامپیوتر نظری 8، 189-201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
[4] ER Caianiello، "درباره نظریه میدان کوانتومی - I: حل صریح معادله دایسون در الکترودینامیک بدون استفاده از نمودارهای فاینمن"، Il Nuovo Cimento (1943-1954) 10، 1634-1652 (1953).
https://doi.org/10.1007/BF02781659
[5] S. Scheel، "دائمی در شبکه های نوری خطی"، quant-ph/0406127.
arXiv:quant-ph/0406127
[6] S. Aaronson و A. Arkhipov، "پیچیدگی محاسباتی اپتیک خطی"، نظریه محاسبات 9، 143 (2013)، arXiv:1011.3245.
https://doi.org/10.1145/1993636.1993682
arXiv:arXiv:1011.3245
[7] S. Aaronson، "یک اثبات خطی-اپتیکی که دائمی #P-hard است"، مجموعه مقالات انجمن سلطنتی A: علوم ریاضی، فیزیک و مهندسی 467، 3393-3405 (2011).
https://doi.org/10.1098/rspa.2011.0232
[8] S. Rahimi-Keshari، AP Lund و TC Ralph، "چه چیزی می تواند اپتیک کوانتومی در مورد نظریه پیچیدگی محاسباتی بگوید؟"، نامه های بررسی فیزیکی 114، 060501 (2015).
https://doi.org/10.1103/PhysRevLett.114.060501
[9] D. Grier و L. Schaeffer، "نتایج سختی جدید برای دائمی با استفاده از اپتیک خطی"، arXiv:1610.04670.
arXiv:arXiv:1610.04670
[10] PP Rohde، DW Berry، KR Motes، و JP Dowling، "یک استدلال اپتیک کوانتومی برای $#$P-سختی یک کلاس از انتگرال های چند بعدی،" arXiv:1607.04960.
arXiv:arXiv:1607.04960
[11] L. Chakhmakhchyan، NJ Cerf، و R. Garcia-Patron، "الگوریتم الهام گرفته از کوانتوم برای تخمین دائمی ماتریس های نیمه معین مثبت،" Physical Review A 96, 022329 (2017).
https://doi.org/10.1103/PhysRevA.96.022329
[12] A. Meiburg، "عدم تقریب دائمی های نیمه معین مثبت و توموگرافی حالت کوانتومی"، arXiv:2111.03142.
arXiv:arXiv:2111.03142
[13] PA MacMahon، "تحلیل ترکیبی، جلد اول و دوم،"، جلد. 137. انجمن ریاضی آمریکا، 2001.
[14] I. گود، «اثبات برخی از هویت‌های «دوجمله‌ای» با استفاده از «قضیه اصلی» مک ماهون، در مجموعه مقالات ریاضی انجمن فلسفی کمبریج، جلد. 58، صفحات 161-162، انتشارات دانشگاه کمبریج. 1962.
https://doi.org/10.1017/S030500410003632X
[15] ال. کارلیتز، "کاربردی از قضیه اصلی مک ماهون"، مجله SIAM در ریاضیات کاربردی 26، 431-436 (1974).
https://doi.org/10.1137/0126040
[16] ال. کارلیتز، "برخی فرمول‌های بسط و پیچش مربوط به قضیه اصلی مک ماهون،" SIAM Journal on Mathematical Analysis 8، 320-336 (1977).
https://doi.org/10.1137/0508023
[17] HJ Ryser، "ریاضیات ترکیبی"، جلد. 14. American Mathematical Soc., 1963.
[18] K. Balasubramanian، ترکیبات و قطرهای ماتریس. پایان نامه دکتری، موسسه آمار هند-کلکته، 1980.
[19] ET Bax، الگوریتم‌های تفاضل محدود برای شمارش مسائل. پایان نامه دکتری، موسسه فناوری کالیفرنیا، 1998.
[20] DG Glynn، "دائمی ماتریس مربع"، مجله اروپایی ترکیبیات 31، 1887-1891 (2010).
https://doi.org/10.1016/j.ejc.2010.01.010
[21] PP Rohde، KR Motes، PA Knott، J. Fitzsimons، WJ Munro، و JP Dowling، "شواهدی برای این حدس که نمونه برداری از حالت های عمومی گربه با اپتیک خطی سخت است"، Physical Review A 91, 012342 (2015).
https://doi.org/10.1103/PhysRevA.91.012342
[22] C. Weedbrook، S. Pirandola، R. García-Patrón، NJ Cerf، TC Ralph، JH Shapiro، و S. Lloyd، "اطلاعات کوانتومی گاوسی"، بررسی‌های فیزیک مدرن 84، 621 (2012).
https://doi.org/10.1103/RevModPhys.84.621
[23] A. Leverrier، "$SU(p, q)$ حالات منسجم و یک قضیه گاوسی د فینتی، مجله فیزیک ریاضی 59، 042202 (2018).
https://doi.org/10.1063/1.5007334
[24] T. Jiang و Y. Ma، "فاصله‌های بین ماتریس‌های متعامد تصادفی و نرمال‌های مستقل،" arXiv:1704.05205.
arXiv:arXiv:1704.05205
[25] ای سی دیکسون، "درباره مجموع مکعب های ضرایب در یک بسط معین توسط قضیه دو جمله ای"، رسول ریاضیات 20، 79-80 (1891).
[26] I. گود، "اثباتی کوتاه از "قضیه اصلی" مک ماهون، در مجموعه مقالات ریاضی انجمن فلسفی کمبریج، جلد. 58، صص 160-160، انتشارات دانشگاه کمبریج. 1962.
https://doi.org/10.1017/S0305004100036318
[27] S. Garoufalidis، TT Lê، و D. Zeilberger، "قضیه استاد کوانتومی مک ماهون"، مجموعه مقالات آکادمی ملی علوم 103، 13928-13931 (2006).
https://doi.org/10.1073/pnas.0606003103
[28] M. Konvalinka و I. Pak، "بسط های غیر جابجایی قضیه استاد مک ماهون"، Advances in Mathematics 216، 29-61 (2007).
https://doi.org/10.1016/j.aim.2007.05.020
[29] MP Tuite، "برخی از تعمیم های قضیه استاد مک ماهون"، مجله نظریه ترکیبی، سری A 120، 92-101 (2013).
https://doi.org/10.1016/j.jcta.2012.07.007
[30] VV Kocharovsky، VV Kocharovsky، و SV Tarasov، "The Hafnian Master Theorem"، جبر خطی و کاربردهای آن 144-161 (2022).
https://doi.org/10.1016/j.laa.2022.06.021
[31] WY Chen، H. Galbraith و J. Louck، "نظریه تکانه زاویه ای، حساب محاسباتی، و ترکیبیات"، کامپیوترها و ریاضیات با برنامه های کاربردی 41، 1199-1214 (2001).
https://doi.org/10.1016/S0898-1221(01)00091-8
[32] BM Terhal و DP DiVincenzo، «شبیه‌سازی کلاسیک مدارهای کوانتومی فرمیون غیر متقابل»، Physical Review A 65, 032325 (2002).
https://doi.org/10.1103/PhysRevA.65.032325
[33] V. Shchesnovich، "نظریه غیرقابل تشخیص جزئی برای آزمایش های چند فوتونی در دستگاه های چند پورت"، بررسی فیزیکی A 91، 013844 (2015).
https://doi.org/10.1103/PhysRevA.91.013844
[34] D. Spivak، MY Niu، BC Sanders، و H. de Guise، "تداخل عمومی فرمیون ها و بوزون ها"، تحقیقات بررسی فیزیکی 4، 023013 (2022).
https://doi.org/10.1103/PhysRevResearch.4.023013
[35] E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin, and M. Hafezi, "Sampling Boson for Generalized Bosons," arXiv:2204.08389.
https://doi.org/10.1103/PhysRevResearch.4.043096
arXiv:arXiv:2204.08389
[36] A. Clément, N. Heurtel, S. Mansfield, S. Perdrix, and B. Valiron, "LO$_text{v}$-Calculus: A Graphical Language for Linear Optical Quantum Circuits," arXiv:2204.11787.
https://doi.org/10.4230/LIPIcs.MFCS.2022.35
arXiv:arXiv:2204.11787
[37] G. De Felice و B. Coecke، "اپتیک خطی کوانتومی از طریق نمودارهای رشته ای"، arXiv:2204.12985.
arXiv:arXiv:2204.12985
[38] B. Peropadre، GG Guerreschi، J. Huh، و A. Aspuru-Guzik، "پیشنهاد برای نمونه برداری بوزون مایکروویو"، نامه های بررسی فیزیکی 117، 140505 (2016).
https://doi.org/10.1103/PhysRevLett.117.140505
[39] اس. گیروین، "حالات گربه شرودینگر در مدار qed،" arXiv:1710.03179.
arXiv:arXiv:1710.03179
[40] X. Gu، AF Kockum، A. Miranowicz، Y.-x. لیو و اف. نوری، "فتونیک مایکروویو با مدارهای کوانتومی ابررسانا"، Physics Reports 718، 1-102 (2017).
https://doi.org/10.1016/j.physrep.2017.10.002
[41] J. Huh، "یک الگوریتم کوانتومی سریع برای محاسبه دائمی ماتریس،" arXiv:2205.01328.
arXiv:arXiv:2205.01328
[42] S. Aaronson و T. Hance، "تعمیم و غیر تصادفی سازی الگوریتم تقریب گورویتز برای دائمی"، اطلاعات کوانتومی. محاسبه کنید. 14، 541-559 (2014).
https://doi.org/10.26421/QIC14.7-8-1
[43] S. Chin و J. Huh، "تطابق عمومی در نمونه گیری بوزون"، گزارش های علمی 8، 1-9 (2018).
https://doi.org/10.1038/s41598-018-24302-5
[44] M.-H. یونگ، ایکس. گائو و جی. هو، «محدوده جهانی در نمونه‌برداری از بوزون‌ها در اپتیک خطی و پیامدهای محاسباتی آن»، بررسی علمی ملی 6، 719-729 (2019).
https://doi.org/10.1093/nsr/nwz048
[45] VS Shchesnovich، "در مورد پیچیدگی کلاسیک نمونه برداری از تداخل کوانتومی بوزون های غیر قابل تشخیص"، مجله بین المللی اطلاعات کوانتومی 18، 2050044 (2020).
https://doi.org/10.1142/S0219749920500446
[46] DM Jackson، "یکسان سازی مسائل شمارش معین برای دنباله ها"، مجله نظریه ترکیبی، سری A 22، 92-96 (1977).
https://doi.org/10.1016/0097-3165(77)90066-8
[47] FR Cardoso، DZ Rossatto، GP Fernandes، G. Higgins و CJ Villas-Boas، "Superposition of two-mode comprested states for quantum data processing and quantum sensing," Physical Review A 103, 062405 (2021).
https://doi.org/10.1103/PhysRevA.103.062405
[48] AP Lund، A. Laing، S. Rahimi-Keshari، T. Rudolph، JL O'Brien، و TC Ralph، "نمونه برداری بوزون از حالت گاوسی"، نامه های بررسی فیزیکی 113، 100502 (2014).
https://doi.org/10.1103/PhysRevLett.113.100502
[49] JP Olson، KP Seshadreesan، KR Motes، PP Rohde، و JP Dowling، «نمونه‌برداری از حالت‌های فشرده شده با فوتون اضافه شده یا فوتون تفریق شده در همان کلاس پیچیدگی نمونه‌برداری بوزونی است،» Physical Review A 91, 022317 (2015).
https://doi.org/10.1103/PhysRevA.91.022317
[50] CS Hamilton، R. Kruse، L. Sansoni، S. Barkhofen، C. Silberhorn، و I. Jex، "نمونه برداری بوزون گاوسی"، نامه های بررسی فیزیکی 119، 170501 (2017).
https://doi.org/10.1103/PhysRevLett.119.170501
[51] A. Lund، S. Rahimi-Keshari و T. Ralph، "نمونه برداری دقیق بوزون با استفاده از اندازه گیری های متغیر پیوسته گاوسی"، بررسی فیزیکی A 96، 022301 (2017).
https://doi.org/10.1103/PhysRevA.96.022301
[52] L. Chakhmakhchyan و NJ Cerf، "نمونه برداری بوزون با اندازه گیری های گاوسی"، بررسی فیزیکی A 96، 032326 (2017).
https://doi.org/10.1103/PhysRevA.96.032326
[53] U. Chabaud، T. Douce، D. Markham، P. van Loock، E. Kashefi، و G. Ferrini، "نمونه گیری متغیر پیوسته از حالت های فشرده شده با فوتون اضافه شده یا فوتون تفریق شده،" Physical Review A 96, 062307 ( 2017).
https://doi.org/10.1103/PhysRevA.96.062307
[54] N. Quesada، JM Arrazola، و N. Killoran، "نمونه برداری بوزون گاوسی با استفاده از آشکارسازهای آستانه"، بررسی فیزیکی A 98، 062322 (2018).
https://doi.org/10.1103/PhysRevA.98.062322
[55] A. Deshpande, A. Mehta, T. Vincent, N. Quesada, M. Hinsche, M. Ioannou, L. Madsen, J. Lavoie, H. Qi, J. Eisert, et al., "مزیت محاسباتی کوانتومی از طریق بالا نمونه‌برداری بوزون گاوسی بعدی، پیشرفت علم 8، 7894 (2022).
https://doi.org/10.1126/sciadv.abi7894
ذکر شده توسط
این مقاله در Quantum تحت عنوان منتشر شده است Creative Commons Attribution 4.0 International (CC BY 4.0) مجوز. حق چاپ نزد دارندگان حق چاپ اصلی مانند نویسندگان یا مؤسسات آنها باقی می ماند.
