Kwantum-geïnspireerde permanente identiteiten

Heruitgegeven door Plato

volgers: 0

Ulysse Chabaud¹, Abhinav Deshpande¹ en Saeed Mehraban²

¹Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, VS.
²Computerwetenschappen, Tufts University, Medford, MA 02155, VS

Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.

Abstract

De permanent is cruciaal voor zowel de complexiteitstheorie als de combinatoriek. Bij kwantumcomputing verschijnt het permanente in de uitdrukking van outputamplitudes van lineaire optische berekeningen, zoals in het Boson Sampling-model. Door gebruik te maken van deze verbinding, geven we op kwantum geïnspireerde bewijzen van vele bestaande en nieuwe opmerkelijke permanente identiteiten. Met name geven we een kwantum-geïnspireerd bewijs van de hoofdstelling van MacMahon, evenals bewijzen voor nieuwe generalisaties van deze stelling. Eerdere bewijzen van deze stelling gebruikten totaal andere ideeën. Naast hun puur combinatorische toepassingen, demonstreren onze resultaten de klassieke hardheid van exacte en geschatte bemonstering van lineaire optische kwantumberekeningen met invoerkattoestanden.

Uitgelichte afbeelding: op kwantum geïnspireerde bewijzen leiden tot nieuwe complexiteitsresultaten over kwantumberekeningen met invoer van kattoestanden (abstracte weergave gegenereerd met DALL.E).

Populaire samenvatting

Sommige wiskundige grootheden zijn alomtegenwoordig in wiskunde, natuurkunde en informatica. Dit is het geval bij een combinatorisch object met de naam permanent.

Door gebruik te maken van relaties tussen het permanente en de amplitude van lineaire optische kwantumcircuits, laten we zien dat op kwantum geïnspireerde technieken snelle bewijzen leveren van veel belangrijke stellingen over het permanente, zoals de MacMahon Master Theorem.

Onze op kwantum geïnspireerde bewijzen bieden de kwantumwetenschapper nieuw inzicht in combinatorische stellingen en onthullen nieuwe resultaten in kwantumcomplexiteit.

► BibTeX-gegevens

@article{Chabaud2022quantumgeïnspireerd, doi = {10.22331/q-2022-12-19-877}, url = {https://doi.org/10.22331/q-2022-12-19-877}, title = {Quantum-geïnspireerde permanente identiteiten}, auteur = {Chabaud, Ulysse en Deshpande, Abhinav en Mehraban, Saeed}, dagboek = {{Quantum}}, issn = {2521-327X}, uitgever = {{Verein zur F{“{o}}rderung des Open Access Publizierens in de Quantenwissenschaften}}, volume = {6}, pagina's = {877}, maand = december, jaar = {2022} }

► Referenties

[1] H. Minc, "Permanents", vol. 6. Cambridge Universitaire Pers, 1984.
https: / / doi.org/ 10.1017 / CBO9781107340688

[2] JK Percus, "Combinatorische methoden", vol. 4. Springer Wetenschap en zakelijke media, 2012.
https://doi.org/10.1007/978-1-4612-6404-0

[3] LG Valiant, "De complexiteit van het berekenen van het permanente", Theoretische informatica 8, 189-201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6

[4] ER Caianiello, "Over kwantumveldentheorie - I: expliciete oplossing van de vergelijking van Dyson in de elektrodynamica zonder gebruik te maken van Feynman-grafieken", Il Nuovo Cimento (1943-1954) 10, 1634-1652 (1953).
https: / / doi.org/ 10.1007 / BF02781659

[5] S. Scheel, "Permanents in lineaire optische netwerken", quant-ph/0406127.
arXiv: quant-ph / 0406127

[6] S. Aaronson en A. Arkhipov, "De computationele complexiteit van lineaire optica", Theory of Computing 9, 143 (2013), arXiv: 1011.3245.
https: / / doi.org/ 10.1145 / 1993636.1993682
arXiv: arXiv: 1011.3245

[7] S. Aaronson, "Een lineair-optisch bewijs dat het permanente # P-hard is", 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 en TC Ralph, "Wat kan kwantumoptica zeggen over computationele complexiteitstheorie?", Physical review letters 114, 060501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.060501

[9] D. Grier en L. Schaeffer, "Nieuwe hardheidsresultaten voor het permanente gebruik van lineaire optica", arXiv: 1610.04670.
arXiv: arXiv: 1610.04670

[10] PP Rohde, DW Berry, KR Motes en 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 en R. Garcia-Patron, "Quantum-geïnspireerd algoritme voor het schatten van de permanente van positieve semidefiniete matrices", Physical Review A 96, 022329 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022329

[12] A. Meiburg, "Onbenaderbaarheid van positieve semi-definitieve permanenten en kwantumtoestandstomografie", arXiv: 2111.03142.
arXiv: arXiv: 2111.03142

[13] PA MacMahon, "Combinatory Analysis, Volumes I en II", vol. 137. American Mathematical Soc., 2001.

[14] I. Good, "Bewijzen van enkele 'binominale' identiteiten door middel van MacMahons 'Master Theorem'," in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, blz. 161-162, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S030500410003632X

[15] L. Carlitz, "Een toepassing van de hoofdstelling van MacMahon", SIAM Journal on Applied Mathematics 26, 431–436 (1974).
https: / / doi.org/ 10.1137 / 0126040

[16] L. Carlitz, "Sommige uitbreidingen en convolutieformules met betrekking tot de hoofdstelling van MacMahon", SIAM Journal on Mathematical Analysis 8, 320-336 (1977).
https: / / doi.org/ 10.1137 / 0508023

[17] HJ Ryser, "Combinatorische wiskunde", vol. 14. American Mathematical Soc., 1963.

[18] K. Balasubramanian, Combinatoriek en diagonalen van matrices. Proefschrift, Indian Statistical Institute-Kolkata, 1980.

[19] ET Bax, Finite-difference-algoritmen voor telproblemen. Proefschrift, California Institute of Technology, 1998.

[20] DG Glynn, "De permanente van een vierkante 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 en JP Dowling, "Bewijs voor het vermoeden dat het moeilijk is om gegeneraliseerde kattoestanden met lineaire optica te bemonsteren", 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 en S. Lloyd, "Gaussiaanse kwantuminformatie", beoordelingen van Modern Physics 84, 621 (2012).
https: / / doi.org/ 10.1103 / RevModPhys.84.621

[23] A. Leverrier, "$SU(p, q)$ coherente toestanden en een stelling van Gauss de Finetti", Journal of Mathematical Physics 59, 042202 (2018).
https: / / doi.org/ 10.1063 / 1.5007334

[24] T. Jiang en Y. Ma, "Afstanden tussen willekeurige orthogonale matrices en onafhankelijke normalen", arXiv: 1704.05205.
arXiv: arXiv: 1704.05205

[25] AC Dixon, "Over de som van de kubussen van de coëfficiënten in een bepaalde uitbreiding door de binominale stelling", Messenger of Mathematics 20, 79-80 (1891).

[26] I. Goed, "Een kort bewijs van MacMahons 'Master Theorem'," in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, blz. 160-160, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S0305004100036318

[27] S. Garoufalidis, TT Lê en 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 en I. Pak, "Niet-commutatieve uitbreidingen van de MacMahon Master Theorem", Advances in Mathematics 216, 29-61 (2007).
https:///doi.org/10.1016/j.aim.2007.05.020

[29] MP Tuite, "Enkele generalisaties van de MacMahon Master Theorem," Journal of Combinatorische theorie, serie A 120, 92-101 (2013).
https: / / doi.org/ 10.1016 / j.jcta.2012.07.007

[30] VV Kocharovsky, VV Kocharovsky en 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 en 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 en DP DiVincenzo, "Klassieke simulatie van niet-interagerende fermion-quantumcircuits", Physical Review A 65, 032325 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.65.032325

[33] V. Shchesnovich, "Gedeeltelijke ononderscheidbaarheidstheorie voor multiphoton-experimenten in apparaten met meerdere poorten", Physical Review A 91, 013844 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.013844

[34] D. Spivak, MY Niu, BC Sanders en H. de Guise, "Gegeneraliseerde interferentie van fermionen en bosonen", Physical Review Research 4, 023013 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.023013

[35] E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin en M. Hafezi, "Boson-bemonstering voor gegeneraliseerde 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 en B. Valiron, “LO$_text{v}$-Calculus: een grafische taal voor lineaire optische kwantumcircuits,” arXiv:2204.11787.
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2022.35
arXiv: arXiv: 2204.11787

[37] G. De Felice en B. Coecke, "Quantum lineaire optica via snaardiagrammen", arXiv: 2204.12985.
arXiv: arXiv: 2204.12985

[38] B. Peropadre, GG Guerreschi, J. Huh en A. Aspuru-Guzik, "Voorstel voor microgolfbosonbemonstering", Physical review letters 117, 140505 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.140505

[39] S. Girvin, "Schrödinger-katstaten in circuit qed", arXiv: 1710.03179.
arXiv: arXiv: 1710.03179

[40] X. Gu, AF Kockum, A. Miranowicz, Y.-x. Liu en F. Nori, "Microgolffotonica met supergeleidende kwantumcircuits", Physics Reports 718, 1–102 (2017).
https: / / doi.org/ 10.1016 / j.physrep.2017.10.002

[41] J. Huh, "Een snel kwantumalgoritme voor het permanent berekenen van matrix", arXiv: 2205.01328.
arXiv: arXiv: 2205.01328

[42] S. Aaronson en T. Hance, "Gurvits' benaderingsalgoritme generaliseren en derandomiseren voor het permanente", Quantum Info. Bereken. 14, 541-559 (2014).
https: / / doi.org/ 10.26421 / QIC14.7-8-1

[43] S. Chin en J. Huh, "Gegeneraliseerde samenloop bij bosonbemonstering", wetenschappelijke rapporten 8, 1–9 (2018).
https://doi.org/10.1038/s41598-018-24302-5

[44] M.-H. Yung, X. Gao en J. Huh, "Universal bound on sampling bosonen in lineaire optica en de computationele implicaties ervan", National science review 6, 719-729 (2019).
https:///doi.org/10.1093/nsr/nwz048

[45] VS Shchesnovich, "Over de klassieke complexiteit van bemonstering door kwantuminterferentie van niet te onderscheiden bosonen", International Journal of Quantum Information 18, 2050044 (2020).
https: / / doi.org/ 10.1142 / S0219749920500446

[46] DM Jackson, "De unificatie van bepaalde opsommingsproblemen voor reeksen", 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 en CJ Villas-Boas, "Superposition of two-mode squeezed states for quantum information processing and quantum sensing", 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 en 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 en JP Dowling, "Sampling van willekeurige foton-toegevoegde of foton-afgetrokken geperste toestanden valt in dezelfde complexiteitsklasse als 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 en 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 en T. Ralph, "Exacte bosonbemonstering met behulp van Gaussiaanse continu-variabele metingen", Physical Review A 96, 022301 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022301

[52] L. Chakhmakhchyan en NJ Cerf, "Boson-bemonstering met Gauss-metingen", 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 en 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 en N. Killoran, "Gaussian boson sampling using threshold detectors", 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 computationeel voordeel via hoge -dimensionale Gaussiaanse boson-bemonstering,” Science Advances 8, 7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894

Geciteerd door

Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.