1Institut Informasi dan Materi Kuantum, Institut Teknologi California, Pasadena, CA 91125, AS
2Ilmu Komputer, Universitas Tufts, Medford, MA 02155, AS
Apakah makalah ini menarik atau ingin dibahas? Scite atau tinggalkan komentar di SciRate.
Abstrak
Permanen sangat penting untuk teori kompleksitas dan kombinatorik. Dalam komputasi kuantum, yang permanen muncul dalam ekspresi amplitudo keluaran perhitungan optik linier, seperti dalam model Boson Sampling. Mengambil keuntungan dari koneksi ini, kami memberikan bukti yang diilhami oleh kuantum dari banyak identitas permanen baru yang luar biasa. Terutama, kami memberikan bukti yang diilhami oleh kuantum dari teorema master MacMahon serta bukti untuk generalisasi baru dari teorema ini. Bukti sebelumnya dari teorema ini menggunakan ide yang sama sekali berbeda. Di luar aplikasi kombinatorial murni mereka, hasil kami menunjukkan kekerasan klasik dari pengambilan sampel yang tepat dan perkiraan dari komputasi kuantum optik linier dengan status input cat.
Gambar unggulan: Bukti yang terinspirasi kuantum menghasilkan hasil kompleksitas baru tentang komputasi kuantum dengan input status kucing (penggambaran abstrak dihasilkan menggunakan DALL.E).
Ringkasan populer
Dengan mengeksploitasi hubungan antara permanen dan amplitudo sirkuit kuantum optik linier, kami menunjukkan bahwa teknik yang terinspirasi kuantum memberikan bukti cepat dari banyak teorema penting tentang permanen, seperti Teorema Master MacMahon.
Bukti terinspirasi kuantum kami memberikan wawasan baru bagi ilmuwan kuantum tentang teorema kombinatorial dan mengungkap hasil baru dalam kompleksitas kuantum.
► data BibTeX
► Referensi
[1] H. Minc, “Permanen,”, vol. 6. Cambridge University Press, 1984.
https: / / doi.org/ 10.1017 / CBO9781107340688
[2] JK Percus, “Metode kombinatorial,”, vol. 4. Media Sains & Bisnis Springer, 2012.
https://doi.org/10.1007/978-1-4612-6404-0
[3] LG Valiant, "Kompleksitas komputasi permanen," Ilmu komputer teoretis 8, 189-201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
[4] ER Caianiello, “Tentang teori medan kuantum—I: solusi eksplisit persamaan Dyson dalam elektrodinamika tanpa menggunakan grafik Feynman,” Il Nuovo Cimento (1943-1954) 10, 1634–1652 (1953).
https: / / doi.org/ 10.1007 / BF02781659
[5] S. Scheel, “Permanen dalam jaringan optik linier,” quant-ph/0406127.
arXiv: quant-ph / 0406127
[6] S. Aaronson dan A. Arkhipov, "Kompleksitas Komputasi Optik Linier," Teori Komputasi 9, 143 (2013), arXiv:1011.3245.
https: / / doi.org/ 10.1145 / 1993636.1993682
arXiv: arXiv: 1011.3245
[7] S. Aaronson, "A linear-optical proof that the permanent is# P-hard," Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467, 3393–3405 (2011).
https: / / doi.org/ 10.1098 / rspa.2011.0232
[8] S. Rahimi-Keshari, AP Lund, dan TC Ralph, "Apa yang bisa dikatakan optik kuantum tentang teori kompleksitas komputasi?", Surat ulasan fisik 114, 060501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.060501
[9] D. Grier dan L. Schaeffer, “Hasil kekerasan baru untuk permanen menggunakan optik linier,” arXiv:1610.04670.
arXiv: arXiv: 1610.04670
[10] PP Rohde, DW Berry, KR Motes, dan JP Dowling, “Argumen Optik Kuantum untuk kekerasan $#$P dari Kelas Integral Multidimensi,” arXiv:1607.04960.
arXiv: arXiv: 1607.04960
[11] L. Chakhmakhchyan, NJ Cerf, dan R. Garcia-Patron, “Algoritme yang terinspirasi kuantum untuk memperkirakan matriks semidefinisi positif permanen,” Tinjauan Fisik A 96, 022329 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022329
[12] A. Meiburg, “Ketidakpastian Permanen Semidefinite Positif dan Tomografi Keadaan Kuantum,” arXiv:2111.03142.
arXiv: arXiv: 2111.03142
[13] PA MacMahon, “Analisis Kombinasi, Volume I dan II,”, vol. 137. American Mathematical Soc., 2001.
[14] I. Baik, "Bukti dari beberapa identitas 'binomial' melalui 'Teorema Master' MacMahon," dalam Prosiding Matematika dari Cambridge Philosophical Society, vol. 58, hlm. 161–162, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S030500410003632X
[15] L. Carlitz, “Sebuah penerapan teorema master MacMahon,” Jurnal SIAM tentang Matematika Terapan 26, 431–436 (1974).
https: / / doi.org/ 10.1137 / 0126040
[16] L. Carlitz, “Beberapa rumus ekspansi dan konvolusi yang berkaitan dengan teorema master MacMahon,” SIAM Journal on Mathematical Analysis 8, 320–336 (1977).
https: / / doi.org/ 10.1137 / 0508023
[17] HJ Ryser, “Matematika Kombinatorial,”, vol. 14. American Mathematical Soc., 1963.
[18] K. Balasubramanian, Kombinatorik dan diagonal matriks. Tesis PhD, Institut Statistik India-Kolkata, 1980.
[19] ET Bax, algoritma Finite-difference untuk menghitung masalah. Tesis PhD, Institut Teknologi California, 1998.
[20] DG Glynn, “The permanent of a square matrix,” 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, dan JP Dowling, “Bukti dugaan bahwa pengambilan sampel keadaan kucing umum dengan optik linier itu sulit,” Tinjauan Fisik 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, dan S. Lloyd, "informasi kuantum Gaussian," Ulasan Fisika Modern 84, 621 (2012).
https: / / doi.org/ 10.1103 / RevModPhys.84.621
[23] A. Leverrier, “$SU(p, q)$ keadaan koheren dan teorema Gaussian de Finetti,” Journal of Mathematical Physics 59, 042202 (2018).
https: / / doi.org/ 10.1063 / 1.5007334
[24] T. Jiang dan Y. Ma, “Jarak antara matriks ortogonal acak dan normal independen,” arXiv:1704.05205.
arXiv: arXiv: 1704.05205
[25] AC Dixon, "Pada jumlah kubus dari koefisien dalam ekspansi tertentu dengan teorema binomial," Messenger matematika 20, 79-80 (1891).
[26] I. Bagus, "Bukti singkat dari 'Teorema Master' MacMahon," dalam Prosiding Matematika dari Cambridge Philosophical Society, vol. 58, hlm. 160–160, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S0305004100036318
[27] S. Garoufalidis, TT Lê, dan D. Zeilberger, “Teorema master kuantum MacMahon,” Prosiding National Academy of Sciences 103, 13928–13931 (2006).
https: / / doi.org/ 10.1073 / pnas.0606003103
[28] M. Konvalinka dan I. Pak, “Perpanjangan non-komutatif dari Teorema Master MacMahon,” Kemajuan dalam Matematika 216, 29–61 (2007).
https:///doi.org/10.1016/j.aim.2007.05.020
[29] MP Tuite, “Beberapa generalisasi Teorema Master MacMahon,” Jurnal Teori Kombinatorial, Seri A 120, 92–101 (2013).
https: / / doi.org/ 10.1016 / j.jcta.2012.07.007
[30] VV Kocharovsky, VV Kocharovsky, dan SV Tarasov, “The Hafnian Master Theorem,” Aljabar Linier dan Penerapannya 144–161 (2022).
https: / / doi.org/ 10.1016 / j.laa.2022.06.021
[31] WY Chen, H. Galbraith, dan J. Louck, "Teori momentum sudut, kalkulus umbral, dan kombinatorika," Komputer & Matematika dengan Aplikasi 41, 1199–1214 (2001).
https://doi.org/10.1016/S0898-1221(01)00091-8
[32] BM Terhal dan DP DiVincenzo, "Simulasi klasik sirkuit kuantum fermion noninteracting," Tinjauan Fisik A 65, 032325 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.65.032325
[33] V. Shchesnovich, "Teori ketidakterbedaan parsial untuk eksperimen multifoton dalam perangkat multiport," Tinjauan Fisik A 91, 013844 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.013844
[34] D. Spivak, MY Niu, BC Sanders, dan H. de Guise, “Gangguan umum fermion dan boson,” Penelitian Tinjauan Fisik 4, 023013 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.023013
[35] E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin, dan M. Hafezi, “Pengambilan Sampel Boson untuk Boson Umum,” 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, dan B. Valiron, “LO$_text{v}$-Calculus: Bahasa Grafis untuk Sirkuit Kuantum Optik Linier,” arXiv:2204.11787.
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2022.35
arXiv: arXiv: 2204.11787
[37] G. De Felice dan B. Coecke, “Optik Linear Kuantum melalui Diagram String,” arXiv:2204.12985.
arXiv: arXiv: 2204.12985
[38] B. Peropadre, GG Guerreschi, J. Huh, dan A. Aspuru-Guzik, “Proposal for microwave boson sampling,” Physical review letters 117, 140505 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.140505
[39] S. Girvin, “status kucing Schrödinger di sirkuit qed,” arXiv:1710.03179.
arXiv: arXiv: 1710.03179
[40] X.Gu, AF Kockum, A. Miranowicz, Y.-x. Liu, dan F. Nori, "Microwave photonics with superconducting quantum circuits," Physics Reports 718, 1–102 (2017).
https: / / doi.org/ 10.1016 / j.physrep.2017.10.002
[41] J.Huh, “Algoritme kuantum cepat untuk menghitung matriks permanen,” arXiv:2205.01328.
arXiv: arXiv: 2205.01328
[42] S. Aaronson dan T. Hance, “Generalisasi dan Derandomisasi Algoritma Pendekatan Gurvits untuk Permanen,” Quantum Info. Komputer. 14, 541–559 (2014).
https: / / doi.org/ 10.26421 / QIC14.7-8-1
[43] S. Chin dan J. Huh, “Persetujuan umum dalam pengambilan sampel boson,” Laporan ilmiah 8, 1–9 (2018).
https://doi.org/10.1038/s41598-018-24302-5
[44] M.-H. Yung, X. Gao, dan J. Huh, "Universal terikat pada pengambilan sampel boson dalam optik linier dan implikasi komputasinya," Ulasan sains nasional 6, 719–729 (2019).
https:///doi.org/10.1093/nsr/nwz048
[45] VS Shchesnovich, “Tentang kompleksitas klasik pengambilan sampel dari interferensi kuantum boson yang tidak dapat dibedakan,” Jurnal Internasional Informasi Kuantum 18, 2050044 (2020).
https: / / doi.org/ 10.1142 / S0219749920500446
[46] DM Jackson, “Penyatuan masalah pencacahan tertentu untuk urutan,” Jurnal Teori Kombinatorial, Seri A 22, 92–96 (1977).
https://doi.org/10.1016/0097-3165(77)90066-8
[47] FR Cardoso, DZ Rossatto, GP Fernandes, G. Higgins, dan CJ Villas-Boas, “Superposisi keadaan terjepit dua mode untuk pemrosesan informasi kuantum dan pengindraan kuantum,” Tinjauan Fisik 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, dan TC Ralph, “Boson sampling from a Gaussian state,” Physical review letters 113, 100502 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.100502
[49] JP Olson, KP Seshadreesan, KR Motes, PP Rohde, dan JP Dowling, “Pengambilan sampel keadaan terjepit yang ditambahkan foton atau dikurangi foton sewenang-wenang berada dalam kelas kompleksitas yang sama dengan pengambilan sampel boson,” Tinjauan Fisik A 91, 022317 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.022317
[50] CS Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn, dan I. Jex, "Sampel Gaussian boson," Surat tinjauan fisik 119, 170501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.170501
[51] A. Lund, S. Rahimi-Keshari, dan T. Ralph, “Pengambilan sampel boson yang tepat menggunakan pengukuran variabel kontinu Gaussian,” Tinjauan Fisik A 96, 022301 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022301
[52] L. Chakhmakhchyan dan NJ Cerf, “Sampel Boson dengan pengukuran Gaussian,” Tinjauan Fisik A 96, 032326 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.032326
[53] U. Chabaud, T. Douce, D. Markham, P. van Loock, E. Kashefi, dan G. Ferrini, “Continuous-variable sampling from photon-added atau photon-subtracted squeeze state,” Tinjauan Fisik A 96, 062307 ( 2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062307
[54] N. Quesada, JM Arrazola, dan N. Killoran, “Pengambilan sampel boson Gaussian menggunakan detektor ambang,” Tinjauan Fisik 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, dkk., “Keunggulan komputasi kuantum melalui -dimensional Gaussian boson sampling,” Science advances 8, 7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894
Dikutip oleh
Makalah ini diterbitkan dalam Quantum di bawah Creative Commons Attribution 4.0 Internasional (CC BY 4.0) lisensi. Hak cipta tetap berada pada pemegang hak cipta asli seperti penulis atau lembaganya.
