1สถาบันข้อมูลและสสารควอนตัม California Institute of Technology, Pasadena, CA 91125, USA
2วิทยาการคอมพิวเตอร์ Tufts University, Medford, MA 02155, USA
พบบทความนี้ที่น่าสนใจหรือต้องการหารือ? Scite หรือแสดงความคิดเห็นใน SciRate.
นามธรรม
ถาวรเป็นหัวใจสำคัญของทั้งทฤษฎีความซับซ้อนและ combinatorics ในการคำนวณควอนตัม ค่าถาวรจะปรากฏในนิพจน์ของเอาต์พุตแอมพลิจูดของการคำนวณด้วยแสงเชิงเส้น เช่น ในแบบจำลอง Boson Sampling ใช้ประโยชน์จากการเชื่อมต่อนี้ เราให้ข้อพิสูจน์ที่ได้รับแรงบันดาลใจจากควอนตัมของตัวตนที่มีอยู่มากมายตลอดจนตัวตนถาวรที่น่าทึ่งใหม่ ที่โดดเด่นที่สุดคือเราได้ให้ข้อพิสูจน์ที่ได้รับแรงบันดาลใจจากควอนตัมของทฤษฎีบทหลักของ MacMahon ตลอดจนข้อพิสูจน์สำหรับการสรุปภาพรวมใหม่ของทฤษฎีบทนี้ การพิสูจน์ทฤษฎีบทก่อนหน้านี้ใช้แนวคิดที่แตกต่างไปจากเดิมอย่างสิ้นเชิง ผลลัพธ์ของเราแสดงให้เห็นถึงความแข็งแบบคลาสสิกของการสุ่มตัวอย่างที่แม่นยำและใกล้เคียงของการคำนวณควอนตัมออปติกเชิงเส้นด้วยสถานะแมวอินพุต
สรุปยอดนิยม
ด้วยการใช้ประโยชน์จากความสัมพันธ์ระหว่างความถาวรและแอมพลิจูดของวงจรควอนตัมออปติกเชิงเส้น เราแสดงให้เห็นว่าเทคนิคที่ได้รับแรงบันดาลใจจากควอนตัมให้การพิสูจน์อย่างรวดเร็วของทฤษฎีบทสำคัญมากมายเกี่ยวกับถาวร เช่น ทฤษฎีบทหลักของ MacMahon
การพิสูจน์ที่ได้รับแรงบันดาลใจจากควอนตัมของเราให้ข้อมูลเชิงลึกใหม่สำหรับนักวิทยาศาสตร์ควอนตัมเกี่ยวกับทฤษฎีบทเชิงผสม และค้นพบผลลัพธ์ใหม่ในความซับซ้อนของควอนตัม
► ข้อมูล BibTeX
► ข้อมูลอ้างอิง
[1] H. Minc, “ผู้ถาวร”, vol. 6. สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ 1984
https://doi.org/10.1017/CBO9781107340688
[2] เจเค เพอร์คัส, “Combinatorial method,”, vol. 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:ปริมาณ-ph/0406127
[6] S. Aaronson และ A. Arkhipov, “The computational Complexity of Linear Optics,” Theory of Computing 9, 143 (2013), arXiv:1011.3245
https://doi.org/10.1145/1993636.1993682
arXiv:arXiv:1011.3245
[7] S. Aaronson, “ข้อพิสูจน์เชิงแสงเชิงเส้นว่าสิ่งถาวรคือ # P-hard” การดำเนินการของ Royal Society 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, “A Quantum Optics Argument for the $#$P-hardness of a Class of Multidimensional Integrals,” 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, “ความประมาณไม่ได้ของ Positive Semidefinite Permanents และ Quantum State Tomography,” arXiv:2111.03142
arXiv:arXiv:2111.03142
[13] พีเอ แมคมาฮอน “Combinatory Analysis, Volumes I and II,”, vol. 137. สมาคมคณิตศาสตร์อเมริกัน พ.ศ. 2001
[14] I. ดี “การพิสูจน์อัตลักษณ์ 'ทวินาม' บางอย่างโดยใช้ 'ทฤษฎีบทหลัก' ของแมคมาฮอน” ใน Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58 หน้า 161–162 สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ 1962.
https://doi.org/10.1017/S030500410003632X
[15] แอล. คาร์ลิทซ์, “การประยุกต์ทฤษฎีบทหลักของแมคมาฮอน,” วารสารสยามด้านคณิตศาสตร์ประยุกต์ 26, 431–436 (1974)
https://doi.org/10.1137/0126040
[16] แอล. คาร์ลิทซ์ “สูตรการขยายและการหมุนบางส่วนที่เกี่ยวข้องกับทฤษฎีบทหลักของแมคมาฮอน” วารสาร SIAM เรื่อง Mathematical Analysis 8, 320–336 (1977)
https://doi.org/10.1137/0508023
[17] HJ Ryser, “คณิตศาสตร์เชิงผสม,”, ฉบับที่ 14. สมาคมคณิตศาสตร์อเมริกัน พ.ศ. 1963
[18] K. Balasubramanian, Combinatorics และเส้นทแยงมุมของเมทริกซ์ วิทยานิพนธ์ปริญญาเอก, Indian Statistical Institute-Kolkata, 1980
[19] ET Bax อัลกอริธึมผลต่างจำกัดสำหรับปัญหาการนับ วิทยานิพนธ์ปริญญาเอก, California Institute of Technology, 1998.
[20] DG Glynn, “ความถาวรของเมทริกซ์สี่เหลี่ยม” European Journal of Combinatorics 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, “หลักฐานสำหรับการคาดคะเนว่าการสุ่มตัวอย่าง cat state ทั่วไปด้วยออปติกเชิงเส้นนั้นยาก” 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, and S. Lloyd, “Gaussian quantum information,” Reviews of Modern Physics 84, 621 (2012)
https://doi.org/10.1103/RevModPhys.84.621
[23] A. Leverrier, “$SU(p, q)$ coherent state and a Gaussian de Finetti theorem,” Journal of Mathematical Physics 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. ดี, “A short proof of 'Master Theorem' of MacMahon,” in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58 หน้า 160–160 สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ 1962.
https://doi.org/10.1017/S0305004100036318
[27] S. Garoufalidis, TT Lê และ D. Zeilberger, “The quantum MacMahon master theorem,” Proceedings of the National Academy of Sciences 103, 13928–13931 (2006)
https://doi.org/10.1073/pnas.0606003103
[28] M. Konvalinka และ I. Pak, “Non-commutative extensions of the MacMahon Master Theorem,” Advances in Mathematics 216, 29–61 (2007)
https://doi.org/10.1016/j.aim.2007.05.020
[29] MP Tuite, “Some generalizations of the MacMahon Master Theorem,” Journal of Combinatorial Theory, Series 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,” Linear Algebra and its Applications 144–161 (2022)
https://doi.org/10.1016/j.laa.2022.06.021
[31] WY Chen, H. Galbraith และ J. Louck, “ทฤษฎีโมเมนตัมเชิงมุม แคลคูลัสอัมบราล และคอมบิเนทอริกส์” Computers & Mathematics with Applications 41, 1199–1214 (2001)
https://doi.org/10.1016/S0898-1221(01)00091-8
[32] BM Terhal และ DP DiVincenzo "การจำลองแบบคลาสสิกของวงจรควอนตัมที่ไม่โต้ตอบ-fermion" การทบทวนทางกายภาพ 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] อี.-เจ. Kuo, Y. Xu, D. Hangleiter, A. Grankin และ M. Hafezi, “Boson Sampling 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 และ 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, “Quantum Linear Optics via String Diagrams,” 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] S. Girvin, “แมวชโรดิงเงอร์อยู่ในวงจร qed,” arXiv:1710.03179
arXiv:arXiv:1710.03179
[40] X. Gu, AF Kockum, A. Miranowicz, Y.-x. Liu และ F. Nori, “โฟโตนิกส์ไมโครเวฟกับวงจรควอนตัมตัวนำยิ่งยวด” รายงานฟิสิกส์ 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, “การสรุปและแยกอัลกอริทึมการประมาณค่าของ Gurvits สำหรับสิ่งถาวร” ข้อมูลควอนตัม คอมพิวเตอร์ 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] จ.-ส. Yung, X. Gao และ J. Huh, “ขอบเขตสากลในการสุ่มตัวอย่างโบซอนในออปติคเชิงเส้นและความหมายเชิงคำนวณของมัน” การทบทวนวิทยาศาสตร์แห่งชาติ 6, 719–729 (2019)
https://doi.org/10.1093/nsr/nwz048
[45] VS Shchesnovich, “ในความซับซ้อนแบบดั้งเดิมของการสุ่มตัวอย่างจากการรบกวนควอนตัมของโบซอนที่แยกไม่ออก” วารสารนานาชาติของข้อมูลควอนตัม 18, 2050044 (2020)
https://doi.org/10.1142/S0219749920500446
[46] ดี.เอ็ม. แจ็กสัน “การรวมปัญหาการแจงนับบางอย่างสำหรับลำดับ” วารสารทฤษฎีเชิงผสม ชุด 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, “การซ้อนทับของสถานะบีบสองโหมดสำหรับการประมวลผลข้อมูลควอนตัมและการตรวจจับควอนตัม” การทบทวนทางกายภาพ 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, “การสุ่มตัวอย่าง Boson จากรัฐ Gaussian,” จดหมายทบทวนทางกายภาพ 113, 100502 (2014)
https://doi.org/10.1103/PhysRevLett.113.100502
[49] JP Olson, KP Seshadreesan, KR Motes, PP Rohde และ JP Dowling, “การสุ่มตัวอย่างสถานะบีบโฟตอนที่เพิ่มหรือลบโฟตอนโดยพลการนั้นอยู่ในระดับความซับซ้อนเดียวกันกับการสุ่มตัวอย่างโบซอน” การทบทวนทางกายภาพ 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, “Gaussian boson sampling,” จดหมายทบทวนทางกายภาพ 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, “การสุ่มตัวอย่างแบบแปรผันต่อเนื่องจากสถานะบีบโฟตอนที่เพิ่มหรือลบโฟตอน” การทบทวนทางกายภาพ 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 ภายใต้ the ครีเอทีฟคอมมอนส์แบบแสดงที่มา 4.0 สากล (CC BY 4.0) ใบอนุญาต ลิขสิทธิ์ยังคงอยู่กับผู้ถือลิขสิทธิ์ดั้งเดิม เช่น ผู้เขียนหรือสถาบันของพวกเขา