1Kuantum Bilgi ve Madde Enstitüsü, California Teknoloji Enstitüsü, Pasadena, CA 91125, ABD
2Bilgisayar Bilimi, Tufts Üniversitesi, Medford, MA 02155, ABD
Bu makaleyi ilginç mi buldunuz yoksa tartışmak mı istiyorsunuz? SciRate'e çığlık at veya yorum bırak.
Özet
Kalıcı, hem karmaşıklık teorisi hem de kombinatorik için çok önemlidir. Kuantum hesaplamada kalıcı olan, Boson Örnekleme modelinde olduğu gibi doğrusal optik hesaplamaların çıktı genliklerinin ifadesinde görünür. Bu bağlantıdan yararlanarak, birçok mevcut ve yeni dikkate değer kalıcı kimliğin kuantumdan ilham alan kanıtlarını veriyoruz. En önemlisi, MacMahon ana teoreminin kuantumdan ilham alan bir kanıtını ve bu teoremin yeni genellemelerinin kanıtlarını veriyoruz. Bu teoremin önceki ispatlarında tamamen farklı fikirler kullanılmıştı. Tamamen kombinatoryal uygulamalarının ötesinde, sonuçlarımız, giriş kat durumları ile doğrusal optik kuantum hesaplamalarının tam ve yaklaşık örneklemesinin klasik zorluğunu göstermektedir.
Öne çıkan görsel: Kuantumdan ilham alan ispatlar, kat durumları girişiyle (DALL.E kullanılarak oluşturulan soyut tasvir) kuantum hesaplamaları hakkında yeni karmaşıklık sonuçlarına yol açar.
Popüler özet
Doğrusal optik kuantum devrelerinin kalıcı ve genlikleri arasındaki ilişkileri kullanarak, kuantumdan ilham alan tekniklerin, MacMahon Ana Teoremi gibi kalıcı olanla ilgili birçok önemli teoremin hızlı kanıtlarını sağladığını gösteriyoruz.
Kuantumdan ilham alan kanıtlarımız, kuantum bilim insanına kombinatoryal teoremler hakkında yeni bilgiler sağlar ve kuantum karmaşıklığında yeni sonuçlar ortaya çıkarır.
► BibTeX verileri
► Referanslar
[1] H. Minc, "Kalıcılar", cilt. 6. Cambridge University Press, 1984.
https: / / doi.org/ 10.1017 / CBO9781107340688
[2] JK Percus, "Kombinatoryal yöntemler", cilt. 4. Springer Science & Business Media, 2012.
https://doi.org/10.1007/978-1-4612-6404-0
[3] LG Valiant, “Kalıcıyı hesaplamanın karmaşıklığı,” Teorik bilgisayar bilimi 8, 189–201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
[4] ER Caianiello, "Kuantum alan teorisi üzerine—I: Feynman grafikleri kullanılmadan elektrodinamikte Dyson denkleminin açık çözümü", Il Nuovo Cimento (1943-1954) 10, 1634–1652 (1953).
https: / / doi.org/ 10.1007 / BF02781659
[5] S. Scheel, "Lineer optik ağlarda kalıcılar", quant-ph/0406127.
arXiv: kuant-ph / 0406127
[6] S. Aaronson ve A. Arkhipov, "Doğrusal Optiklerin Hesaplamalı Karmaşıklığı", Theory of Computing 9, 143 (2013), arXiv:1011.3245.
https: / / doi.org/ 10.1145 / 1993636.1993682
arXiv: arXiv: 1011.3245
[7] S. Aaronson, "Kalıcı olanın # P-zor olduğuna dair lineer optik bir kanıt", 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 ve TC Ralph, "Kuantum optiği, hesaplama karmaşıklığı teorisi hakkında ne söyleyebilir?", Physical derleme mektupları 114, 060501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.060501
[9] D. Grier ve L. Schaeffer, "Doğrusal optik kullanan kalıcılar için yeni sertlik sonuçları", arXiv:1610.04670.
arXiv: arXiv: 1610.04670
[10] PP Rohde, DW Berry, KR Motes ve JP Dowling, "Bir Çok Boyutlu İntegral Sınıfının $#$P-sertliği için Kuantum Optik Argümanı", arXiv:1607.04960.
arXiv: arXiv: 1607.04960
[11] L. Chakhmakhchyan, NJ Cerf ve R. Garcia-Patron, "Pozitif yarı kesin matrislerin kalıcılığını tahmin etmek için kuantumdan ilham alan algoritma," Physical Review A 96, 022329 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022329
[12] A. Meiburg, "Pozitif Yarı Kesin Kalıcıların Yaklaşılamazlığı ve Kuantum Durum Tomografisi", arXiv:2111.03142.
arXiv: arXiv: 2111.03142
[13] PA MacMahon, "Birleştirici Analiz, Cilt I ve II", cilt. 137. American Mathematical Soc., 2001.
[14] I. İyi, "MacMahon'un 'Ana Teoremi' aracılığıyla bazı 'iki terimli' özdeşliklerin kanıtları", Mathematical Proceedings of the Cambridge Philosophical Society, cilt. 58, s. 161–162, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S030500410003632X
[15] L. Carlitz, "MacMahon'un ana teoreminin bir uygulaması", SIAM Journal on Applied Mathematics 26, 431–436 (1974).
https: / / doi.org/ 10.1137 / 0126040
[16] L. Carlitz, “MacMahon'un ana teoremi ile ilgili bazı açılımlar ve evrişim formülleri,” SIAM Journal on Mathematical Analysis 8, 320–336 (1977).
https: / / doi.org/ 10.1137 / 0508023
[17] HJ Ryser, "Kombinatoryal matematik", cilt. 14. American Mathematical Soc., 1963.
[18] K. Balasubramanian, Kombinatorik ve matrislerin köşegenleri. Doktora tezi, Indian Statistical Institute-Kolkata, 1980.
[19] ET Bax, Sayım problemleri için sonlu fark algoritmaları. Doktora tezi, California Institute of Technology, 1998.
[20] DG Glynn, "Kare matrisin kalıcılığı", 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 ve JP Dowling, "Doğrusal optikle genelleştirilmiş kedi durumlarını örneklemenin zor olduğu varsayımı için kanıt", 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 ve S. Lloyd, “Gauss kuantum bilgisi”, Reviews of Modern Physics 84, 621 (2012).
https: / / doi.org/ 10.1103 / RevModPhys.84.621
[23] A. Leverrier, "$SU(p, q)$ tutarlı durumlar ve bir Gaussian de Finetti teoremi," Journal of Mathematical Physics 59, 042202 (2018).
https: / / doi.org/ 10.1063 / 1.5007334
[24] T. Jiang ve Y. Ma, "Rastgele ortogonal matrisler ve bağımsız normaller arasındaki mesafeler", arXiv:1704.05205.
arXiv: arXiv: 1704.05205
[25] AC Dixon, "Binom teoremiyle belirli bir açılımda katsayıların küplerinin toplamı üzerine", Messenger of Mathematics 20, 79–80 (1891).
[26] I. Good, "A short proof of MacMahon's 'Master Theorem'", Mathematical Proceedings of the Cambridge Philosophical Society, cilt. 58, s. 160–160, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S0305004100036318
[27] S. Garoufalidis, TT Lê ve D. Zeilberger, "Kuantum MacMahon ana teoremi", Proceedings of the National Academy of Sciences 103, 13928–13931 (2006).
https: / / doi.org/ 10.1073 / pnas.0606003103
[28] M. Konvalinka ve 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, “MacMahon Master Theorem'in bazı genellemeleri,” Kombinasyon Teorisi Dergisi, Seri A 120, 92–101 (2013).
https: / / doi.org/ 10.1016 / j.jcta.2012.07.007
[30] VV Kocharovsky, VV Kocharovsky ve SV Tarasov, "The Hafnian Master Theorem", Linear Cebir ve Uygulamaları 144–161 (2022).
https: / / doi.org/ 10.1016 / j.laa.2022.06.021
[31] WY Chen, H. Galbraith ve J. Louck, "Açısal momentum teorisi, umbral hesap ve kombinatorik", Computers & Mathematics with Applications 41, 1199–1214 (2001).
https://doi.org/10.1016/S0898-1221(01)00091-8
[32] BM Terhal ve DP DiVincenzo, “Etkileşimsiz fermiyon kuantum devrelerinin klasik simülasyonu,” Physical Review A 65, 032325 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.65.032325
[33] V. Shchesnovich, "Çok portlu cihazlarda çoklu foton deneyleri için kısmi ayırt edilemezlik teorisi", Physical Review A 91, 013844 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.013844
[34] D. Spivak, MY Niu, BC Sanders ve H. de Guise, "Genelleştirilmiş interferans of fermiyonlar ve bozonlar", Physical Review Research 4, 023013 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.023013
[35] E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin ve 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 ve 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 ve B. Coecke, "Dize Diyagramları Üzerinden Kuantum Doğrusal Optik", arXiv:2204.12985.
arXiv: arXiv: 2204.12985
[38] B. Peropadre, GG Guerreschi, J. Huh ve A. Aspuru-Guzik, "Proposal for mikrodalga bozon örneklemesi", Physical derleme mektupları 117, 140505 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.140505
[39] S. Girvin, "Schrödinger kedisi devre qed'de belirtiyor" arXiv:1710.03179.
arXiv: arXiv: 1710.03179
[40] X. Gu, AF Koçum, A. Miranowicz, Y.-x. Liu ve F. Nori, "Süper iletken kuantum devreleriyle mikrodalga fotonik", Physics Reports 718, 1–102 (2017).
https: / / doi.org/ 10.1016 / j.physrep.2017.10.002
[41] J. Huh, "Kalıcı matris hesaplamak için hızlı bir kuantum algoritması" arXiv:2205.01328.
arXiv: arXiv: 2205.01328
[42] S. Aaronson ve T. Hance, “Gurvits'in Kalıcı Olmak İçin Yaklaşım Algoritmasını Genelleştirme ve Derandomize Etme,” Quantum Info. bilgisayar. 14, 541–559 (2014).
https: / / doi.org/ 10.26421 / QIC14.7-8-1
[43] S. Chin ve J. Huh, "Boson örneklemesinde genelleştirilmiş uyum", Scientific Reports 8, 1–9 (2018).
https://doi.org/10.1038/s41598-018-24302-5
[44] M.-H. Yung, X. Gao ve J. Huh, "Doğrusal optikte bozonları örneklemeye evrensel bağlı ve bunun hesaplamalı sonuçları," National science review 6, 719–729 (2019).
https:///doi.org/10.1093/nsr/nwz048
[45] VS Shchesnovich, "Ayırt edilemez bozonların kuantum girişiminden örneklemenin klasik karmaşıklığı üzerine" International Journal of Quantum Information 18, 2050044 (2020).
https: / / doi.org/ 10.1142 / S0219749920500446
[46] DM Jackson, "Diziler için belirli numaralandırma problemlerinin birleştirilmesi" Kombinasyon Teorisi Dergisi, 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 ve CJ Villas-Boas, "Superposition of two-mode sıkıştırılmış durumlar için kuantum bilgi işleme ve kuantum algılama," 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 ve TC Ralph, “Boson örnekleme from a Gaussian state,” Physical derleme mektupları 113, 100502 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.100502
[49] JP Olson, KP Seshadreesan, KR Motes, PP Rohde ve JP Dowling, "Sampling keyfi foton eklenmiş veya foton çıkarılmış sıkılmış durumlar, bozon örneklemesi ile aynı karmaşıklık sınıfındadır," 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 ve I. Jex, “Gauss bozonu örneklemesi,” Fiziksel inceleme mektupları 119, 170501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.170501
[51] A. Lund, S. Rahimi-Keshari ve T. Ralph, "Gauss sürekli değişken ölçümlerini kullanarak kesin bozon örneklemesi", Physical Review A 96, 022301 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022301
[52] L. Chakhmakhchyan ve NJ Cerf, “Gauss ölçümleriyle Bozon örneklemesi”, Physical Review A 96, 032326 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.032326
[53] U. Chabaud, T. Douce, D. Markham, P. van Loock, E. Kashefi ve G. Ferrini, "Foton eklenmiş veya foton çıkarılmış sıkılmış durumlardan sürekli değişken örnekleme," Physical Review A 96, 062307 ( 2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062307
[54] N. Quesada, JM Arrazola ve N. Killoran, "Eşik dedektörleri kullanılarak Gauss bozonu örneklemesi", Physical Review 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, vd., “Yüksek yoluyla kuantum hesaplama avantajı -boyutlu Gauss bozonu örneklemesi,” Science advances 8, 7894 (2022).
https://doi.org/10.1126/sciadv.abi7894
Alıntılama
Bu Makale, Quantum'da Creative Commons Atıf 4.0 Uluslararası (CC BY 4.0) lisans. Telif hakkı, yazarlar veya kurumları gibi orijinal telif hakkı sahiplerine aittir.
