1Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, États-Unis
2Informatique, Tufts University, Medford, MA 02155, États-Unis
Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.
Abstract
Le permanent est essentiel à la fois à la théorie de la complexité et à la combinatoire. En informatique quantique, le permanent apparaît dans l'expression des amplitudes de sortie des calculs optiques linéaires, comme dans le modèle Boson Sampling. Profitant de cette connexion, nous donnons des preuves d'inspiration quantique de nombreuses identités permanentes remarquables existantes ainsi que de nouvelles. Plus particulièrement, nous donnons une preuve d'inspiration quantique du théorème maître de MacMahon ainsi que des preuves pour de nouvelles généralisations de ce théorème. Les preuves précédentes de ce théorème utilisaient des idées complètement différentes. Au-delà de leurs applications purement combinatoires, nos résultats démontrent la dureté classique de l'échantillonnage exact et approximatif des calculs quantiques optiques linéaires avec des états de chat en entrée.
Image en vedette : des preuves inspirées par le quantique conduisent à de nouveaux résultats de complexité sur les calculs quantiques avec une entrée d'états de chat (représentation abstraite générée à l'aide de DALL.E).
Résumé populaire
En exploitant les relations entre le permanent et les amplitudes des circuits quantiques optiques linéaires, nous montrons que les techniques d'inspiration quantique fournissent des preuves rapides de nombreux théorèmes importants sur le permanent, tels que le théorème principal de MacMahon.
Nos preuves d'inspiration quantique offrent de nouvelles perspectives aux scientifiques quantiques sur les théorèmes combinatoires et dévoilent de nouveaux résultats dans la complexité quantique.
► Données BibTeX
► Références
H. Minc, « Permanents », vol. 6. Cambridge University Press, 1984.
https: / / doi.org/ 10.1017 / CBO9781107340688
JK Percus, « Méthodes combinatoires », vol. 4. Springer Science & Business Media, 2012.
https://doi.org/10.1007/978-1-4612-6404-0
LG Valiant, « La complexité du calcul du permanent », Theoretical computer science 8, 189–201 (1979).
https://doi.org/10.1016/0304-3975(79)90044-6
ER Caianiello, «Sur la théorie quantique des champs - I: solution explicite de l'équation de Dyson en électrodynamique sans utilisation de graphes de Feynman», Il Nuovo Cimento (1943-1954) 10, 1634–1652 (1953).
https: / / doi.org/ 10.1007 / BF02781659
S. Scheel, « Permanents dans les réseaux optiques linéaires », quant-ph/0406127.
arXiv: quant-ph / 0406127
S. Aaronson et A. Arkhipov, « La complexité computationnelle de l'optique linéaire », Theory of Computing 9, 143 (2013), arXiv : 1011.3245.
https: / / doi.org/ 10.1145 / 1993636.1993682
arXiv: arXiv: 1011.3245
S. Aaronson, "Une preuve optique linéaire que le permanent est # P-hard", Actes de la Royal Society A: Mathematical, Physical and Engineering Sciences 467, 3393–3405 (2011).
https: / / doi.org/ 10.1098 / rspa.2011.0232
S. Rahimi-Keshari, AP Lund et TC Ralph, "Que peut dire l'optique quantique sur la théorie de la complexité computationnelle ?", Lettres d'examen physique 114, 060501 (2015).
https: / / doi.org/ 10.1103 / PhysRevLett.114.060501
D. Grier et L. Schaeffer, "Nouveaux résultats de dureté pour le permanent utilisant l'optique linéaire", arXiv: 1610.04670.
arXiv: arXiv: 1610.04670
PP Rohde, DW Berry, KR Motes et JP Dowling, "Un argument d'optique quantique pour la dureté $#$P d'une classe d'intégrales multidimensionnelles", arXiv: 1607.04960.
arXiv: arXiv: 1607.04960
L. Chakhmakhchyan, NJ Cerf et R. Garcia-Patron, "Algorithme d'inspiration quantique pour estimer le permanent des matrices semi-définies positives", Physical Review A 96, 022329 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022329
A. Meiburg, "Inapproximabilité des permanents semi-définis positifs et de la tomographie d'état quantique", arXiv: 2111.03142.
arXiv: arXiv: 2111.03142
PA MacMahon, « Analyse combinatoire, volumes I et II », vol. 137. Société mathématique américaine, 2001.
I. Good, « Preuves de certaines identités « binomiales » au moyen du « théorème principal » de MacMahon », dans Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, p. 161-162, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S030500410003632X
L. Carlitz, «Une application du théorème principal de MacMahon», SIAM Journal on Applied Mathematics 26, 431–436 (1974).
https: / / doi.org/ 10.1137 / 0126040
L. Carlitz, "Certaines expansions et formules de convolution liées au théorème principal de MacMahon", SIAM Journal on Mathematical Analysis 8, 320–336 (1977).
https: / / doi.org/ 10.1137 / 0508023
HJ Ryser, « Mathématiques combinatoires », vol. 14. Société mathématique américaine, 1963.
K. Balasubramanian, Combinatoire et diagonales des matrices. Thèse de doctorat, Indian Statistical Institute-Kolkata, 1980.
ET Bax, Algorithmes aux différences finies pour les problèmes de comptage. Thèse de doctorat, California Institute of Technology, 1998.
DG Glynn, "Le permanent d'une matrice carrée", European Journal of Combinatorics 31, 1887–1891 (2010).
https: / / doi.org/ 10.1016 / j.ejc.2010.01.010
PP Rohde, KR Motes, PA Knott, J. Fitzsimons, WJ Munro et JP Dowling, "Preuve de la conjecture selon laquelle l'échantillonnage d'états de chat généralisés avec une optique linéaire est difficile", Physical Review A 91, 012342 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.012342
C. Weedbrook, S. Pirandola, R. García-Patrón, NJ Cerf, TC Ralph, JH Shapiro et S. Lloyd, « Informations quantiques gaussiennes », Reviews of Modern Physics 84, 621 (2012).
https: / / doi.org/ 10.1103 / RevModPhys.84.621
A. Leverrier, « États cohérents $SU(p, q)$ et théorème gaussien de Finetti », Journal of Mathematical Physics 59, 042202 (2018).
https: / / doi.org/ 10.1063 / 1.5007334
T. Jiang et Y. Ma, « Distances entre les matrices orthogonales aléatoires et les normales indépendantes », arXiv : 1704.05205.
arXiv: arXiv: 1704.05205
AC Dixon, «Sur la somme des cubes des coefficients dans une certaine expansion par le théorème binomial», Messager des mathématiques 20, 79-80 (1891).
I. Good, « Une courte preuve du « théorème principal » de MacMahon », dans Mathematical Proceedings of the Cambridge Philosophical Society, vol. 58, p. 160-160, Cambridge University Press. 1962.
https: / / doi.org/ 10.1017 / S0305004100036318
S. Garoufalidis, TT Lê et D. Zeilberger, « Le théorème maître quantique de MacMahon », Actes de l'Académie nationale des sciences 103, 13928–13931 (2006).
https: / / doi.org/ 10.1073 / pnas.0606003103
M. Konvalinka et I. Pak, "Extensions non commutatives du théorème principal de MacMahon", Advances in Mathematics 216, 29–61 (2007).
https:///doi.org/10.1016/j.aim.2007.05.020
MP Tuite, « Quelques généralisations du théorème principal de MacMahon », Journal of Combinatorial Theory, série A 120, 92–101 (2013).
https: / / doi.org/ 10.1016 / j.jcta.2012.07.007
VV Kocharovsky, VV Kocharovsky et SV Tarasov, «Le théorème maître hafnien», Algèbre linéaire et ses applications 144–161 (2022).
https: / / doi.org/ 10.1016 / j.laa.2022.06.021
WY Chen, H. Galbraith et J. Louck, «Théorie du moment angulaire, calcul ombral et combinatoire», Computers & Mathematics with Applications 41, 1199–1214 (2001).
https://doi.org/10.1016/S0898-1221(01)00091-8
BM Terhal et DP DiVincenzo, « Simulation classique de circuits quantiques à fermions sans interaction », Physical Review A 65, 032325 (2002).
https: / / doi.org/ 10.1103 / PhysRevA.65.032325
V. Shchesnovich, «Théorie de l'indiscernabilité partielle pour les expériences multiphotons dans les dispositifs multiports», Physical Review A 91, 013844 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.013844
D. Spivak, MY Niu, BC Sanders et H. de Guise, «Interférence généralisée des fermions et des bosons», Physical Review Research 4, 023013 (2022).
https: / / doi.org/ 10.1103 / PhysRevResearch.4.023013
E.-J. Kuo, Y. Xu, D. Hangleiter, A. Grankin et M. Hafezi, "Boson Sampling for Generalized Bosons," arXiv:2204.08389.
https: / / doi.org/ 10.1103 / PhysRevResearch.4.043096
arXiv: arXiv: 2204.08389
A. Clément, N. Heurtel, S. Mansfield, S. Perdrix et B. Valiron, « LO$_text{v}$-Calculus : un langage graphique pour les circuits quantiques optiques linéaires », arXiv : 2204.11787.
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2022.35
arXiv: arXiv: 2204.11787
G. De Felice et B. Coecke, « Optique linéaire quantique via des diagrammes de chaînes », arXiv : 2204.12985.
arXiv: arXiv: 2204.12985
B. Peropadre, GG Guerreschi, J. Huh et A. Aspuru-Guzik, « Proposition d'échantillonnage de bosons micro-ondes », Lettres d'examen physique 117, 140505 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.140505
S. Girvin, "États de chat de Schrödinger dans le circuit qed", arXiv: 1710.03179.
arXiv: arXiv: 1710.03179
X. Gu, AF Kockum, A. Miranowicz, Y.-x. Liu et F. Nori, « Photonique micro-ondes avec circuits quantiques supraconducteurs », Physics Reports 718, 1–102 (2017).
https: / / doi.org/ 10.1016 / j.physrep.2017.10.002
J. Huh, « Un algorithme quantique rapide pour le calcul permanent de la matrice », arXiv : 2205.01328.
arXiv: arXiv: 2205.01328
S. Aaronson et T. Hance, "Généralisation et dérandomisation de l'algorithme d'approximation de Gurvits pour le permanent", Quantum Info. Calcul. 14, 541-559 (2014).
https: / / doi.org/ 10.26421 / QIC14.7-8-1
S. Chin et J. Huh, « Accord généralisé dans l'échantillonnage des bosons », Rapports scientifiques 8, 1–9 (2018).
https://doi.org/10.1038/s41598-018-24302-5
M.-H. Yung, X. Gao et J. Huh, «Liaison universelle sur l'échantillonnage des bosons en optique linéaire et ses implications informatiques», Revue scientifique nationale 6, 719–729 (2019).
https:///doi.org/10.1093/nsr/nwz048
VS Shchesnovich, «Sur la complexité classique de l'échantillonnage à partir de l'interférence quantique de bosons indiscernables», International Journal of Quantum Information 18, 2050044 (2020).
https: / / doi.org/ 10.1142 / S0219749920500446
DM Jackson, «L'unification de certains problèmes d'énumération pour les séquences», Journal of Combinatorial Theory, série A 22, 92–96 (1977).
https://doi.org/10.1016/0097-3165(77)90066-8
FR Cardoso, DZ Rossatto, GP Fernandes, G. Higgins et CJ Villas-Boas, «Superposition d'états comprimés à deux modes pour le traitement de l'information quantique et la détection quantique», Physical Review A 103, 062405 (2021).
https: / / doi.org/ 10.1103 / PhysRevA.103.062405
AP Lund, A. Laing, S. Rahimi-Keshari, T. Rudolph, JL O'Brien et TC Ralph, « Boson sampling from a Gaussian state », Physical Review Letters 113, 100502 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.100502
JP Olson, KP Seshadreesan, KR Motes, PP Rohde et JP Dowling, "L'échantillonnage d'états comprimés arbitraires de photons ajoutés ou soustraits de photons est dans la même classe de complexité que l'échantillonnage de bosons", Physical Review A 91, 022317 (2015).
https: / / doi.org/ 10.1103 / PhysRevA.91.022317
CS Hamilton, R. Kruse, L. Sansoni, S. Barkhofen, C. Silberhorn et I. Jex, « Echantillonnage de boson gaussien », Lettres d'examen physique 119, 170501 (2017).
https: / / doi.org/ 10.1103 / PhysRevLett.119.170501
A. Lund, S. Rahimi-Keshari et T. Ralph, « Échantillonnage exact de bosons à l'aide de mesures gaussiennes à variable continue », Physical Review A 96, 022301 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.022301
L. Chakhmakhchyan et NJ Cerf, « Échantillonnage de bosons avec des mesures gaussiennes », Physical Review A 96, 032326 (2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.032326
U. Chabaud, T. Douce, D. Markham, P. van Loock, E. Kashefi et G. Ferrini, "Échantillonnage à variation continue à partir d'états comprimés à photon ajouté ou soustrait à photon", Physical Review A 96, 062307 ( 2017).
https: / / doi.org/ 10.1103 / PhysRevA.96.062307
N. Quesada, JM Arrazola et N. Killoran, « Échantillonnage de boson gaussien à l'aide de détecteurs de seuil », Physical Review A 98, 062322 (2018).
https: / / doi.org/ 10.1103 / PhysRevA.98.062322
A. Deshpande, A. Mehta, T. Vincent, N. Quesada, M. Hinsche, M. Ioannou, L. Madsen, J. Lavoie, H. Qi, J. Eisert, et al. Échantillonnage de boson gaussien tridimensionnel », Science advances 8, 7894 (2022).
https:///doi.org/10.1126/sciadv.abi7894
Cité par
Cet article est publié dans Quantum sous le Creative Commons Attribution 4.0 International (CC BY 4.0) Licence. Le droit d'auteur reste la propriété des détenteurs d'origine tels que les auteurs ou leurs institutions.
