1Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, USA
2Datavitenskap, Tufts University, Medford, MA 02155, USA
Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.
Abstrakt
Den permanente er sentral for både kompleksitetsteori og kombinatorikk. I kvanteberegning vises det permanente i uttrykket av utgangsamplituder til lineære optiske beregninger, slik som i Boson Sampling-modellen. Ved å dra nytte av denne forbindelsen gir vi kvanteinspirerte bevis på mange eksisterende så vel som nye bemerkelsesverdige permanente identiteter. Mest bemerkelsesverdig gir vi et kvanteinspirert bevis på MacMahon-mesterteoremet, samt bevis for nye generaliseringer av denne teoremet. Tidligere bevis på denne teoremet brukte helt andre ideer. Utover deres rent kombinatoriske applikasjoner, viser resultatene våre den klassiske hardheten til eksakt og omtrentlig prøvetaking av lineære optiske kvanteberegninger med input cat-tilstander.
Utvalgt bilde: Kvanteinspirerte bevis fører til nye kompleksitetsresultater om kvanteberegninger med input for katttilstander (abstrakt avbildning generert ved hjelp av DALL.E).
Populært sammendrag
Ved å utnytte relasjonene mellom de permanente og amplitudene til lineære optiske kvantekretser, viser vi at kvanteinspirerte teknikker gir raske bevis på mange viktige teoremer om det permanente, for eksempel MacMahon Master Theorem.
Våre kvanteinspirerte bevis gir ny innsikt for kvanteforskeren om kombinatoriske teoremer og avdekker nye resultater i kvantekompleksitet.
► BibTeX-data
► Referanser
[1] H. Minc, "Permanenter", vol. 6. Cambridge University Press, 1984.
https: / / doi.org/ 10.1017 / CBO9781107340688
[2] JK Percus, "Kombinatoriske metoder", vol. 4. Springer Science & Business Media, 2012.
https://doi.org/10.1007/978-1-4612-6404-0
[3] LG Valiant, "The complexity of computing the permanent," Theoretical Computer science 8, 189–201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
[4] ER Caianiello, "Om kvantefeltteori - I: eksplisitt løsning av Dysons ligning i elektrodynamikk uten bruk av Feynman-grafer," Il Nuovo Cimento (1943-1954) 10, 1634–1652 (1953).
https: / / doi.org/ 10.1007 / BF02781659
[5] S. Scheel, "Permanenter i lineære optiske nettverk," quant-ph/0406127.
arxiv: Quant-ph / 0406127
[6] S. Aaronson og 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, "Et lineært-optisk bevis på at det permanente er # 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 og TC Ralph, "Hva kan kvanteoptikk si om beregningskompleksitetsteori?" Physical review letters 114, 060501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.060501
[9] D. Grier og L. Schaeffer, "Ny hardhet resultater for permanent bruk av lineær optikk," arXiv:1610.04670.
arxiv: arxiv: 1610.04670
[10] PP Rohde, DW Berry, KR Motes og 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 og R. Garcia-Patron, "Kvanteinspirert algoritme for å estimere permanenten av positive semidefinite matriser," Physical Review A 96, 022329 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022329
[12] A. Meiburg, "Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography," arXiv:2111.03142.
arxiv: arxiv: 2111.03142
[13] PA MacMahon, "Kombinatorisk analyse, bind I og II", vol. 137. American Mathematical Soc., 2001.
[14] I. Good, "Bevis for noen 'binomiale' identiteter ved hjelp av MacMahons 'Master Theorem'," i Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, s. 161–162, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S030500410003632X
[15] L. Carlitz, "An application of MacMahons master theorem," SIAM Journal on Applied Mathematics 26, 431–436 (1974).
https: / / doi.org/ 10.1137 / 0126040
[16] L. Carlitz, "Noen utvidelser og konvolusjonsformler relatert til MacMahons masterteorem," SIAM Journal on Mathematical Analysis 8, 320–336 (1977).
https: / / doi.org/ 10.1137 / 0508023
[17] HJ Ryser, "Kombinatorisk matematikk", vol. 14. American Mathematical Soc., 1963.
[18] K. Balasubramanian, Combinatorics and diagonals of matrices. PhD-avhandling, Indian Statistical Institute-Kolkata, 1980.
[19] ET Bax, endelige forskjellsalgoritmer for telleproblemer. PhD-avhandling, 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 og JP Dowling, "Bevis for antagelsen om at prøvetaking av generaliserte kattetilstander med lineær optikk er vanskelig," 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 og S. Lloyd, “Gaussian quantum information,” Anmeldelser av moderne fysikk 84, 621 (2012).
https: / / doi.org/ 10.1103 / RevModPhys.84.621
[23] A. Leverrier, "$SU(p, q)$ koherente tilstander og et Gaussian de Finetti-teorem," Journal of Mathematical Physics 59, 042202 (2018).
https: / / doi.org/ 10.1063 / 1.5007334
[24] T. Jiang og Y. Ma, "Avstander mellom tilfeldige ortogonale matriser og uavhengige normaler," arXiv:1704.05205.
arxiv: arxiv: 1704.05205
[25] AC Dixon, "På summen av kubene til koeffisientene i en viss utvidelse av binomiale teoremet," Messenger of Mathematics 20, 79–80 (1891).
[26] I. Good, "Et kort bevis på MacMahons 'Master Theorem'," i Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, s. 160–160, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S0305004100036318
[27] S. Garoufalidis, TT Lê og 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 og 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, "Noen generaliseringer av 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 og 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 og J. Louck, "Angular momentum theory, umbral calculus, and combinatorics," Computers & Mathematics with Applications 41, 1199–1214 (2001).
https://doi.org/10.1016/S0898-1221(01)00091-8
[32] BM Terhal og DP DiVincenzo, “Klassisk simulering av ikke-interagerende-fermion kvantekretser,” Physical Review A 65, 032325 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.65.032325
[33] V. Shchesnovich, "Delvis utskillelighetsteori for multifotoneksperimenter i multiportenheter," Physical Review A 91, 013844 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.013844
[34] D. Spivak, MY Niu, BC Sanders og H. de Guise, "Generalisert interferens av fermioner og bosoner," Physical Review Research 4, 023013 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.023013
[35] E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin og 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 og 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 og B. Coecke, "Quantum Linear Optics via String Diagrams," arXiv:2204.12985.
arxiv: arxiv: 2204.12985
[38] B. Peropadre, GG Guerreschi, J. Huh og 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, "Schrödinger cat states in circuit qed," arXiv:1710.03179.
arxiv: arxiv: 1710.03179
[40] X. Gu, AF Kockum, A. Miranowicz, Y.-x. Liu og F. Nori, "Mikrobølgefotonikk med superledende kvantekretser," Physics Reports 718, 1–102 (2017).
https: / / doi.org/ 10.1016 / j.physrep.2017.10.002
[41] J. Huh, "En rask kvantealgoritme for permanent databehandling av matrise," arXiv:2205.01328.
arxiv: arxiv: 2205.01328
[42] S. Aaronson og T. Hance, "Generalisere og avrandomisere Gurvits tilnærmingsalgoritme for det permanente," Quantum Info. Comput. 14, 541–559 (2014).
https: / / doi.org/ 10.26421 / QIC14.7-8-1
[43] S. Chin og J. Huh, "Generalisert samtidighet i bosonprøvetaking," Scientific-rapporter 8, 1–9 (2018).
https://doi.org/10.1038/s41598-018-24302-5
[44] M.-H. Yung, X. Gao og J. Huh, "Universal bound on sampling bosons in linear optics and its computational implikations," National science review 6, 719–729 (2019).
https:///doi.org/10.1093/nsr/nwz048
[45] VS Shchesnovich, "Om den klassiske kompleksiteten til prøvetaking fra kvanteinterferens av utskillelige bosoner," International Journal of Quantum Information 18, 2050044 (2020).
https: / / doi.org/ 10.1142 / S0219749920500446
[46] DM Jackson, "Foreningen av visse oppregningsproblemer for sekvenser," 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 og CJ Villas-Boas, "Superposisjon av to-modus pressede tilstander for kvanteinformasjonsbehandling og kvantesensing," 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 og 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 og JP Dowling, "Sampling av vilkårlige foton-adderte eller foton-subtraherte pressede tilstander er i samme kompleksitetsklasse som boson-sampling," 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 og I. Jex, “Gaussian boson sampling,” Physical review letters 119, 170501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.170501
[51] A. Lund, S. Rahimi-Keshari og T. Ralph, "Exact boson sampling using Gaussian continuous-variable measurements," Physical Review A 96, 022301 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022301
[52] L. Chakhmakhchyan og NJ Cerf, "Bosonsampling with Gaussian measurements," 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 og G. Ferrini, "Continuous-variable sampling from photon-added or photon-subtracted squeezed states," Physical Review A 96, 062307 ( 2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062307
[54] N. Quesada, JM Arrazola og N. Killoran, "Gaussisk bosonprøvetaking ved bruk av terskeldetektorer," 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 advantage via high -dimensjonal Gaussian boson sampling,” Science advances 8, 7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894
Sitert av
Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.
