1Kvantinformatsiooni ja aine instituut, California Tehnoloogiainstituut, Pasadena, CA 91125, USA
2Arvutiteadus, Tuftsi ülikool, Medford, MA 02155, USA
Kas see artikkel on huvitav või soovite arutada? Scite või jätke SciRate'i kommentaar.
Abstraktne
Püsiv on nii keerukuse teooria kui ka kombinatoorika jaoks keskse tähtsusega. Kvantarvutuses ilmneb püsiv lineaarsete optiliste arvutuste väljundamplituudide väljenduses, näiteks Boson Sampling mudelis. Seda seost ära kasutades anname kvantidest inspireeritud tõendid paljude olemasolevate ja uute tähelepanuväärsete püsivate identiteetide kohta. Kõige olulisem on see, et anname kvantidest inspireeritud tõestuse MacMahoni põhiteoreemi kohta ja tõestused selle teoreemi uute üldistuste kohta. Selle teoreemi varasemates tõestustes kasutati täiesti erinevaid ideid. Lisaks nende puhtalt kombinatoorsetele rakendustele näitavad meie tulemused lineaarsete optiliste kvantarvutuste täpse ja ligikaudse proovivõtmise klassikalist kõvadust kassi sisendolekutega.
Esiletõstetud pilt: kvant-inspireeritud tõestused viivad uute keerukuse tulemusteni kassi olekute sisendiga kvantarvutuste kohta (abstraktne kujutis on loodud DALL.E abil).
Populaarne kokkuvõte
Kasutades lineaarsete optiliste kvantahelate püsivate ja amplituudide vahelisi seoseid, näitame, et kvant-inspireeritud tehnikad pakuvad kiireid tõendeid paljudele olulistele teoreemidele püsiva kohta, nagu MacMahoni meistri teoreem.
Meie kvantidest inspireeritud tõendid annavad kvantteadlasele uue ülevaate kombinatoorsetest teoreemidest ja avastavad uusi tulemusi kvantkeerukuse vallas.
► BibTeX-i andmed
► Viited
[1] H. Minc, “Permanents”, kd. 6. Cambridge University Press, 1984.
https:///doi.org/10.1017/CBO9781107340688
[2] JK Percus, “Kombinatoorsed meetodid”, kd. 4. Springer Science & Business Media, 2012.
https://doi.org/10.1007/978-1-4612-6404-0
[3] LG Valiant, "Püsiarvu arvutamise keerukus", Teoreetiline arvutiteadus, 8, 189–201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
[4] ER Caianiello, Kvantvälja teooriast – I: Dysoni võrrandi eksplitsiitne lahendus elektrodünaamikas ilma Feynmani graafikute kasutamiseta, Il Nuovo Cimento (1943-1954) 10, 1634-1652 (1953).
https:///doi.org/10.1007/BF02781659
[5] S. Scheel, "Püsid lineaarsetes optilistes võrkudes", quant-ph/0406127.
arXiv:quant-ph/0406127
[6] S. Aaronson ja A. Arkhipov, "Lineaaroptika arvutuslik keerukus", Theory of Computing 9, 143 (2013), arXiv:1011.3245.
https:///doi.org/10.1145/1993636.1993682
arXiv:arXiv:1011.3245
[7] S. Aaronson, "Lineaar-optiline tõestus, et püsiv on # P-kõva", 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 ja TC Ralph, „Mida võib kvantoptika öelda arvutusliku keerukuse teooria kohta?”, Physical Review letters 114, 060501 (2015).
https:///doi.org/10.1103/PhysRevLett.114.060501
[9] D. Grier ja L. Schaeffer, "Uued kõvaduse tulemused lineaarset optikat kasutades", arXiv:1610.04670.
arXiv:arXiv:1610.04670
[10] PP Rohde, DW Berry, KR Motes ja JP Dowling, "Kvantoptika argument mitmemõõtmeliste integraalide klassi $#$P kõvaduse kohta", arXiv:1607.04960.
arXiv:arXiv:1607.04960
[11] L. Chakhmakhchyan, NJ Cerf ja R. Garcia-Patron, "Kvant-inspireeritud algoritm positiivsete poolmääratletud maatriksite püsivuse hindamiseks", Physical Review A 96, 022329 (2017).
https:///doi.org/10.1103/PhysRevA.96.022329
[12] A. Meiburg, "Positiivsete poolmääratletud püsiainete ja kvantseisundi tomograafia ebaproksimaalsus", arXiv:2111.03142.
arXiv:arXiv:2111.03142
[13] PA MacMahon, “Combinatory Analysis, Volumes I and II”, vol. 137. American Mathematical Soc., 2001.
[14] I. Good, "Mõnede 'binoomsete" identiteetide tõendid MacMahoni "Master Theorem'i" abil, Cambridge Philosophical Society Mathematical Proceedings, vol. 58, lk 161–162, Cambridge University Press. 1962. aasta.
https:///doi.org/10.1017/S030500410003632X
[15] L. Carlitz, „MacMahoni põhiteoreemi rakendus”, SIAM Journal on Applied Mathematics 26, 431–436 (1974).
https:///doi.org/10.1137/0126040
[16] L. Carlitz, "Mõned MacMahoni põhiteoreemiga seotud laiendused ja konvolutsioonivalemid", SIAM Journal on Mathematical Analysis 8, 320–336 (1977).
https:///doi.org/10.1137/0508023
[17] HJ Ryser, "Kombinatoriaalne matemaatika", kd. 14. American Mathematical Soc., 1963.
[18] K. Balasubramanian, Maatriksite kombinatoorika ja diagonaalid. Doktoritöö, India Statistikainstituut-Kolkata, 1980.
[19] ET Bax, Lõpliku erinevuse algoritmid loendusülesannete jaoks. Doktoritöö, California Tehnoloogiainstituut, 1998.
[20] DG Glynn, “Ruudmaatriksi püsiv”, 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 ja JP Dowling, „Tõendid oletuse kohta, et üldistatud kassiseisundite proovide võtmine lineaarse optikaga on raske”, Physical Review A 91, 012342 (2015).
https:///doi.org/10.1103/PhysRevA.91.012342
[22] C. Weedbrook, S. Pirandola, R. García-Patron, NJ Cerf, TC Ralph, JH Shapiro ja S. Lloyd, „Gaussi kvantteave“, Reviews of Modern Physics 84, 621 (2012).
https:///doi.org/10.1103/RevModPhys.84.621
[23] A. Leverrier, „$SU(p, q)$ koherentsed olekud ja Gaussi de Finetti teoreem”, Journal of Mathematical Physics 59, 042202 (2018).
https:///doi.org/10.1063/1.5007334
[24] T. Jiang ja Y. Ma, “Juhuslike ortogonaalmaatriksite ja sõltumatute normaalide vahelised kaugused”, arXiv:1704.05205.
arXiv:arXiv:1704.05205
[25] AC Dixon, "Koefitsientide kuubikute summa teatud laienduses binoomteoreemi järgi", Messenger of Mathematics 20, 79–80 (1891).
[26] I. Good, "MacMahoni "Master Theoreemi" lühike tõestus, Cambridge Philosophical Society Mathematical Proceedings, vol. 58, lk 160–160, Cambridge University Press. 1962. aasta.
https:///doi.org/10.1017/S0305004100036318
[27] S. Garoufalidis, TT Lê ja 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 ja I. Pak, “MacMahoni meistri teoreemi mittekommutatiivsed laiendused”, Advances in Mathematics 216, 29–61 (2007).
https:///doi.org/10.1016/j.aim.2007.05.020
[29] MP Tuite, "Mõned MacMahoni meistri teoreemi üldistused", Journal of Combinatorial Theory, seeria A 120, 92–101 (2013).
https:///doi.org/10.1016/j.jcta.2012.07.007
[30] V. V. Kotšarovsky, V. V. Kotšarovsky ja SV Tarasov, "Hafni meisterteoreem", Lineaaralgebra ja selle rakendused 144–161 (2022).
https:///doi.org/10.1016/j.laa.2022.06.021
[31] WY Chen, H. Galbraith ja J. Louck, "Angular momentum theory, umbral calculus and kombinatorics", Computers & Mathematics with Applications 41, 1199–1214 (2001).
https://doi.org/10.1016/S0898-1221(01)00091-8
[32] BM Terhal ja DP DiVincenzo, "Mitteinterakteeruvate fermionide kvantahelate klassikaline simulatsioon", Physical Review A 65, 032325 (2002).
https:///doi.org/10.1103/PhysRevA.65.032325
[33] V. Shchesnovich, "Osalise eristamatuse teooria mitmefotoni katsete jaoks mitmepordiga seadmetes", Physical Review A 91, 013844 (2015).
https:///doi.org/10.1103/PhysRevA.91.013844
[34] D. Spivak, MY Niu, BC Sanders ja H. de Guise, „Fermionide ja bosonite üldine interferents”, Physical Review Research 4, 023013 (2022).
https:///doi.org/10.1103/PhysRevResearch.4.023013
[35] E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin ja 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 ja 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 ja B. Coecke, "Quantum Linear Optics via String Diagrams", arXiv:2204.12985.
arXiv:arXiv:2204.12985
[38] B. Peropadre, GG Guerreschi, J. Huh ja A. Aspuru-Guzik, „Ettepanek mikrolainebosoniproovide võtmiseks”, Physical review letters 117, 140505 (2016).
https:///doi.org/10.1103/PhysRevLett.117.140505
[39] S. Girvin, "Schrödingeri kassi seisundid qed-i ringrajal", arXiv:1710.03179.
arXiv:arXiv:1710.03179
[40] X. Gu, AF Kockum, A. Miranowicz, Y.-x. Liu ja F. Nori, "Microwave photoonics with superconducting quantum circuits", Physics Reports 718, 1–102 (2017).
https:///doi.org/10.1016/j.physrep.2017.10.002
[41] J. Huh, "Kiire kvantalgoritm püsimaatriksi arvutamiseks", arXiv:2205.01328.
arXiv:arXiv:2205.01328
[42] S. Aaronson ja T. Hance, "Gurvitsi lähenemisalgoritmi üldistamine ja derandomiseerimine püsivaks", Quantum Info. Arvuta. 14, 541–559 (2014).
https:///doi.org/10.26421/QIC14.7-8-1
[43] S. Chin ja J. Huh, „Generalized concurrence in boson sampling”, Scientific reports 8, 1–9 (2018).
https://doi.org/10.1038/s41598-018-24302-5
[44] M.-H. Yung, X. Gao ja J. Huh, „Universaalne seos lineaarse optika bosonite proovivõtul ja selle arvutuslikud tagajärjed”, National science review 6, 719–729 (2019).
https:///doi.org/10.1093/nsr/nwz048
[45] VS Shchesnovich, "Eristamatute bosonite kvantinterferentsitest diskreetide võtmise klassikalisest keerukusest", International Journal of Quantum Information 18, 2050044 (2020).
https:///doi.org/10.1142/S0219749920500446
[46] DM Jackson, "Teatud järjestuste loendusprobleemide ühendamine", Journal of Combinatorial Theory, seeria A 22, 92–96 (1977).
https://doi.org/10.1016/0097-3165(77)90066-8
[47] FR Cardoso, DZ Rossatto, GP Fernandes, G. Higgins ja CJ Villas-Boas, „Kaherežiimi pigistatud olekute superpositsioon kvantteabe töötlemiseks ja kvantsensinguks”, 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 ja TC Ralph, "Bosoni proovide võtmine Gaussi olekust", Physical Review letters 113, 100502 (2014).
https:///doi.org/10.1103/PhysRevLett.113.100502
[49] JP Olson, KP Seshadreesan, KR Motes, PP Rohde ja JP Dowling: "Suvalise footoniga lisatud või footoniga lahutatud pigistatud olekute proovide võtmine on samas keerukusklassis kui bosoni proovide võtmine", 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 ja I. Jex, "Gaussi bosoni proovide võtmine", Physical review letters 119, 170501 (2017).
https:///doi.org/10.1103/PhysRevLett.119.170501
[51] A. Lund, S. Rahimi-Keshari ja T. Ralph, "Täpne bosoniproovide võtmine Gaussi pidevmuutuja mõõtmistega", Physical Review A 96, 022301 (2017).
https:///doi.org/10.1103/PhysRevA.96.022301
[52] L. Chakhmakhchyan ja NJ Cerf, "Bosoni proovide võtmine Gaussi mõõtmistega", 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 ja G. Ferrini, "Pideva muutuja proovivõtt footoniga lisatud või footoniga lahutatud pigistatud olekutest", Physical Review A 96, 062307 ( 2017).
https:///doi.org/10.1103/PhysRevA.96.062307
[54] N. Quesada, JM Arrazola ja N. Killoran, „Gaussi bosoni proovide võtmine lävidetektorite abil”, 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 jt, “Quantum computational eelis via high -dimensiooniline Gaussi bosoni proovide võtmine,” Science advances 8, 7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894
Viidatud
See raamat on avaldatud Quantum all Creative Commons Attribution 4.0 International (CC BY 4.0) litsents. Autoriõigus jääb algsetele autoriõiguste valdajatele, näiteks autoritele või nende institutsioonidele.
