Kvante-inspirerede permanente identiteter

Genudgivet af Platon

Abonnenter: 0

Ulysse Chabaud¹, Abhinav Deshpande¹og Saeed Mehraban²

¹Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, USA
²Computer Science, Tufts University, Medford, MA 02155, USA

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Den permanente er central for både kompleksitetsteori og kombinatorik. I kvanteberegning optræder det permanente i udtrykket af outputamplituder af lineære optiske beregninger, såsom i Boson Sampling-modellen. Ved at udnytte denne forbindelse giver vi kvanteinspirerede beviser på mange eksisterende såvel som nye bemærkelsesværdige permanente identiteter. Mest bemærkelsesværdigt giver vi et kvante-inspireret bevis på MacMahon-mestersætningen samt beviser for nye generaliseringer af denne sætning. Tidligere beviser for denne teorem brugte helt andre ideer. Ud over deres rent kombinatoriske applikationer demonstrerer vores resultater den klassiske hårdhed af nøjagtig og omtrentlig prøveudtagning af lineære optiske kvanteberegninger med input cat-tilstande.

Udvalgt billede: Kvante-inspirerede beviser fører til nye kompleksitetsresultater om kvanteberegninger med input til kattetilstande (abstrakt afbildning genereret ved hjælp af DALL.E).

Populært resumé

Nogle matematiske størrelser er allestedsnærværende i matematik, fysik og datalogi. Dette er tilfældet med et kombinatorisk objekt ved navn permanenten.

Ved at udnytte forholdet mellem de permanente og amplituder af lineære optiske kvantekredsløb viser vi, at kvanteinspirerede teknikker giver hurtige beviser for mange vigtige teoremer om det permanente, såsom MacMahon Master Theorem.

Vores kvante-inspirerede beviser giver ny indsigt for kvanteforskeren om kombinatoriske sætninger og afslører nye resultater i kvantekompleksitet.

► BibTeX-data

@article{Chabaud2022quantuminspired, doi = {10.22331/q-2022-12-19-877}, url = {https://doi.org/10.22331/q-2022-12-19-877}, title = {Quantum-inspired permanent identities}, author = {Chabaud, Ulysse and Deshpande, Abhinav and Mehraban, Saeed}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {6}, pages = {877}, month = dec, year = {2022} }

► Referencer

[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: eksplicit løsning af Dysons ligning i elektrodynamik uden brug af 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 netværk," 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-hårdt," 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, "Hvad kan kvanteoptik sige om beregningsmæssig kompleksitetsteori?" Physical review letters 114, 060501 (2015).
https:///doi.org/10.1103/PhysRevLett.114.060501

[9] D. Grier og L. Schaeffer, "Nye hårdhedsresultater for permanent ved brug af lineær optik," 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, "Kvante-inspireret algoritme til at estimere permanenten af positive semidefinite matricer," 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, "Beviser for nogle 'binomiale' identiteter ved hjælp af 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 MacMahon's master theorem," SIAM Journal on Applied Mathematics 26, 431-436 (1974).
https:///doi.org/10.1137/0126040

[16] L. Carlitz, "Nogle udvidelser og foldningsformler relateret til MacMahons mastersætning," SIAM Journal on Mathematical Analysis 8, 320-336 (1977).
https:///doi.org/10.1137/0508023

[17] HJ Ryser, "Kombinatorisk matematik", vol. 14. American Mathematical Soc., 1963.

[18] K. Balasubramanian, kombinatorik og diagonaler af matricer. Ph.d.-afhandling, Indian Statistical Institute-Kolkata, 1980.

[19] ET Bax, Finite-difference algoritmer til tælleproblemer. Ph.d.-afhandling, 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 formodningen om, at prøvetagning af generaliserede kattetilstande med lineær optik er svært," 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," Reviews of Modern Physics 84, 621 (2012).
https:///doi.org/10.1103/RevModPhys.84.621

[23] A. Leverrier, "$SU(p, q)$ kohærente tilstande og en Gaussian de Finetti-sætning," Journal of Mathematical Physics 59, 042202 (2018).
https:///doi.org/10.1063/1.5007334

[24] T. Jiang og Y. Ma, "Afstande mellem tilfældige ortogonale matricer og uafhængige normaler," arXiv:1704.05205.
arXiv:arXiv:1704.05205

[25] AC Dixon, "Om summen af kuberne af koefficienterne i en vis ekspansion ved binomialsætningen," Messenger of Mathematics 20, 79-80 (1891).

[26] I. Godt, "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, "Some generalizations of the 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 af ikke-interagerende fermion kvantekredsløb," Physical Review A 65, 032325 (2002).
https:///doi.org/10.1103/PhysRevA.65.032325

[33] V. Shchesnovich, "Delvis udskillelighedsteori for multifotoneksperimenter i multiportenheder," 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, "Generaliseret interferens af 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ølgefotonik med superledende kvantekredsløb," Physics Reports 718, 1-102 (2017).
https:///doi.org/10.1016/j.physrep.2017.10.002

[41] J. Huh, "En hurtig kvantealgoritme til at beregne permanent matrix," arXiv:2205.01328.
arXiv:arXiv:2205.01328

[42] S. Aaronson og T. Hance, "Generalisering og derandomisering af Gurvits' tilnærmelsesalgoritme 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, "Generaliseret overenskomst i bosonprøvetagning," 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 bundet til sampling af bosoner i lineær optik og dens beregningsmæssige implikationer," National science review 6, 719-729 (2019).
https://doi.org/10.1093/nsr/nwz048

[45] VS Shchesnovich, "Om den klassiske kompleksitet af prøveudtagning fra kvanteinterferens af ikke-adskillelige bosoner," International Journal of Quantum Information 18, 2050044 (2020).
https:///doi.org/10.1142/S0219749920500446

[46] DM Jackson, "Foreningen af visse opregningsproblemer 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, "Superposition af to-mode pressede tilstande til kvanteinformationsbehandling og kvantesansning," 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-prøvetagning fra en Gaussisk tilstand," 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 af arbitrære foton-adderede eller foton-subtraherede pressede tilstande 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, "Nøjagtig bosonprøvetagning ved hjælp af Gaussiske kontinuerlige variable målinger," 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, "Kontinuerlig-variabel prøvetagning fra foton-adderede eller foton-subtraherede sammenpressede tilstande," Physical Review A 96, 062307 ( 2017).
https:///doi.org/10.1103/PhysRevA.96.062307

[54] N. Quesada, JM Arrazola og N. Killoran, "Gaussisk bosonprøvetagning ved hjælp af tærskeldetektorer," 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 -dimensionel Gaussisk bosonsampling,” Science advances 8, 7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894

Citeret af

Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.