1Kvanttitieto- ja aineinstituutti, Kalifornian teknillinen instituutti, Pasadena, CA 91125, USA
2Tietojenkäsittelytiede, Tufts University, Medford, MA 02155, USA
Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.
Abstrakti
Pysyvä on avainasemassa sekä kompleksiteoriassa että kombinatoriikassa. Kvanttilaskennassa pysyvä esiintyy lineaaristen optisten laskelmien lähtöamplitudien ilmaisussa, kuten Boson Sampling -mallissa. Tätä yhteyttä hyödyntäen annamme kvanttivaikutteisia todisteita monista olemassa olevista ja uusista merkittävistä pysyvistä identiteeteistä. Merkittävintä on, että annamme kvanttivaikutteisen todisteen MacMahonin päälauseesta sekä todisteita tämän lauseen uusille yleistyksille. Tämän lauseen aikaisemmat todistukset käyttivät täysin erilaisia ideoita. Niiden puhtaasti kombinatoristen sovellusten lisäksi tuloksemme osoittavat lineaaristen optisten kvanttilaskenttien tarkan ja likimääräisen näytteenoton klassisen kovuuden syötettävillä kissatiloilla.
Suositeltu kuva: Kvanttivaikutteiset todisteet johtavat uusiin monimutkaisiin tuloksiin kvanttilaskentasta kissan tilojen syötteellä (abstrakti kuvaus luotu DALL.E:llä).
Suosittu yhteenveto
Hyödyntämällä lineaaristen optisten kvanttipiirien pysyvien ja amplitudien välisiä suhteita osoitamme, että kvanttivaikutteiset tekniikat tarjoavat nopeita todisteita monille tärkeille pysyvää koskeville teoreemoille, kuten MacMahonin päälauseelle.
Kvanttivaikutteiset todistuksemme tarjoavat kvanttitutkijalle uutta näkemystä kombinatorisista teoreemoista ja paljastavat uusia tuloksia kvanttimonimutkaisuudesta.
► BibTeX-tiedot
► Viitteet
[1] H. Minc, "Permanents", voi. 6. Cambridge University Press, 1984.
https: / / doi.org/ 10.1017 / CBO9781107340688
[2] JK Percus, "Kombinatoriset menetelmät", voi. 4. Springer Science & Business Media, 2012.
https://doi.org/10.1007/978-1-4612-6404-0
[3] LG Valiant, "Pysyvän laskennan monimutkaisuus", Theoretical Computer Science 8, 189–201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
[4] ER Caianiello, "Kvanttikenttäteoriasta – I: Dysonin yhtälön eksplisiittinen ratkaisu sähködynamiikassa ilman Feynman-graafien käyttöä", Il Nuovo Cimento (1943-1954) 10, 1634-1652 (1953).
https: / / doi.org/ 10.1007 / BF02781659
[5] S. Scheel, "Permanents in linear optical networks", quant-ph/0406127.
arXiv: kvant-ph / 0406127
[6] S. Aaronson ja 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, "Lineaari-optinen todiste siitä, että pysyvä on # P-kova", 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, "Mitä kvanttioptiikka voi sanoa laskennallisen monimutkaisuuden teoriasta?", Physical review letters 114, 060501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.060501
[9] D. Grier ja L. Schaeffer, "Uusia kovuustuloksia lineaarioptiikkaa käyttäville pysyvälle", arXiv:1610.04670.
arXiv: arXiv: +1610.04670
[10] PP Rohde, DW Berry, KR Motes ja JP Dowling, "Kvanttioptiikan argumentti moniulotteisten integraalien luokan $#$P-kovuuden puolesta", arXiv:1607.04960.
arXiv: arXiv: +1607.04960
[11] L. Chakhmakhchyan, NJ Cerf ja R. Garcia-Patron, "Kvantti-inspiroitu algoritmi positiivisten puolimääräisten matriisien pysyvän arvioimiseksi", Physical Review A 96, 022329 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022329
[12] A. Meiburg, "Positiivisten puolimääräisten pysyvien aineiden ja kvanttitilatomografian epäsuoraisuus", arXiv:2111.03142.
arXiv: arXiv: +2111.03142
[13] PA MacMahon, "Combinatory Analysis, Volumes I and II", voi. 137. American Mathematical Soc., 2001.
[14] I. Good, "Todisteita joistakin 'binomiaalisista' identiteeteistä MacMahonin 'päälauseen' avulla", julkaisussa Mathematical Proceedings of the Cambridge Philosophical Society, voi. 58, s. 161–162, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S030500410003632X
[15] L. Carlitz, "MacMahonin päälauseen soveltaminen", SIAM Journal on Applied Mathematics 26, 431-436 (1974).
https: / / doi.org/ 10.1137 / +0126040
[16] L. Carlitz, "Joitakin laajennuksia ja konvoluutiokaavoja, jotka liittyvät MacMahonin päälauseeseen", SIAM Journal on Mathematical Analysis 8, 320-336 (1977).
https: / / doi.org/ 10.1137 / +0508023
[17] HJ Ryser, "Kombinatorinen matematiikka", voi. 14. American Mathematical Soc., 1963.
[18] K. Balasubramanian, Matriisien kombinatoriikka ja diagonaalit. Väitöskirja, Indian Statistical Institute-Kolkata, 1980.
[19] ET Bax, Äärellisen eron algoritmit laskentatehtäviin. PhD-väitöskirja, California Institute of Technology, 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 ja JP Dowling, "Todiste olettamukselle, että yleistettyjen kissan tilojen näytteenotto lineaarisen optiikan avulla on vaikeaa", 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 ja S. Lloyd, "Gaussin kvanttitiedot", Review of Modern Physics 84, 621 (2012).
https: / / doi.org/ 10.1103 / RevModPhys.84.621
[23] A. Leverrier, "$SU(p, q)$ koherentit tilat ja Gaussin de Finetti-lause", Journal of Mathematical Physics 59, 042202 (2018).
https: / / doi.org/ 10.1063 / +1.5007334
[24] T. Jiang ja Y. Ma, "Satunnaisten ortogonaalisten matriisien ja riippumattomien normaalien väliset etäisyydet", arXiv:1704.05205.
arXiv: arXiv: +1704.05205
[25] AC Dixon, "Kertimien kuutioiden summasta tietyssä laajennuksessa binomilauseen mukaan", Messenger of Mathematics 20, 79–80 (1891).
[26] I. Good, "Lyhyt todiste MacMahonin 'Master Theorem'sta" julkaisussa Mathematical Proceedings of the Cambridge Philosophical Society, voi. 58, s. 160–160, Cambridge University Press. 1962.
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, "MacMahon Master Theorem -lauseen ei-kommutatiiviset laajennukset", Advances in Mathematics 216, 29–61 (2007).
https: / / doi.org/ 10.1016 / j.aim.2007.05.020
[29] MP Tuite, "Joitakin MacMahon Master Theorem -lauseen yleistyksiä", 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 ja SV Tarasov, "Hafnian Master Theorem", Lineaarinen algebra ja sen sovellukset 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 kombinatoriics", Computers & Mathematics with Applications 41, 1199–1214 (2001).
https://doi.org/10.1016/S0898-1221(01)00091-8
[32] BM Terhal ja DP DiVincenzo, "Klassinen simulaatio ei-vuorovaikutteisilla fermionikvanttipiireillä", Physical Review A 65, 032325 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.65.032325
[33] V. Shchesnovich, "Osittainen erottamattomuuden teoria monifotonikokeille moniporttilaitteissa", 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, "Fermionien ja bosonien yleinen häiriö", 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: 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, "Ehdotus mikroaaltobosoninäytteiden ottamiseen", Physical review letters 117, 140505 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.140505
[39] S. Girvin, "Schrödingerin kissan tilat qed-piirissä", arXiv:1710.03179.
arXiv: arXiv: +1710.03179
[40] X. Gu, AF Kockum, A. Miranowicz, Y.-x. Liu ja F. Nori, "Microwave photonics with supraconducting quantum circuits", Physics Reports 718, 1–102 (2017).
https: / / doi.org/ 10.1016 / j.physrep.2017.10.002
[41] J. Huh, "Nopea kvanttialgoritmi pysyvän matriisin laskemiseen", arXiv:2205.01328.
arXiv: arXiv: +2205.01328
[42] S. Aaronson ja T. Hance, "Gurvitsin approximaatioalgoritmin yleistäminen ja derandomisointi pysyvälle", Quantum Info. Comput. 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, "Universal bound on näytteenottobosonit lineaarisessa optiikassa ja sen laskennalliset vaikutukset", National science review 6, 719–729 (2019).
https:///doi.org/10.1093/nsr/nwz048
[45] VS Shchesnovich, "Kvanttihäiriöstä erottamattomien bosonien näytteenoton klassisesta monimutkaisuudesta", International Journal of Quantum Information 18, 2050044 (2020).
https: / / doi.org/ 10.1142 / S0219749920500446
[46] DM Jackson, "Tiettyjen sekvenssien luettelointiongelmien yhdistäminen", Journal of Combinatorial Theory, Series 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, "Kaksimoodien puristettujen tilojen superpositio kvanttiinformaation käsittelyyn ja kvanttitunnistukseen", 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, "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 ja JP Dowling, "Mitunnaisvaltaisten fotonien lisättyjen tai fotoneilla vähennettyjen puristettujen tilojen näytteenotto on samassa monimutkaisuusluokassa kuin bosoninäytteenotto", 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, ”Gaussian boson sampling”, Physical review kirjeet 119, 170501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.170501
[51] A. Lund, S. Rahimi-Keshari ja T. Ralph, "Tarkka bosonin näytteenotto Gaussin jatkuvan muuttujan mittauksilla", Physical Review A 96, 022301 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022301
[52] L. Chakhmakhchyan ja NJ Cerf, "Bosonin näytteenotto Gaussin mittauksilla", 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, "Continuous-variable sampling from fotonien lisätty tai fotonilla vähennetty squeezed states", Physical Review A 96, 062307 ( 2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062307
[54] N. Quesada, JM Arrazola ja N. Killoran, "Gaussin bosonin näytteenotto kynnysilmaisimien avulla", 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, et al., “Quantum computational etu via high -ulotteinen Gaussin bosonin näytteenotto”, Science advances 8, 7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894
Viitattu
Tämä kirja on julkaistu Quantum - lehdessä Creative Commons Nimeäminen 4.0 Kansainvälinen (CC BY 4.0) lisenssin. Tekijänoikeudet säilyvät alkuperäisillä tekijänoikeuksien haltijoilla, kuten tekijöillä tai heidän instituutioillaan.
