1INRIA – Equipe-projet Sierra, Paris, France
2Département d'informatique, University College London, Londres, Royaume-Uni
3Rahko Ltd., Londres, Royaume-Uni
4Département d'informatique, Université du Texas à Austin, Austin, États-Unis
5Département d'informatique, Université d'Oxford, Oxford, Royaume-Uni
6Statistiques computationnelles et apprentissage automatique, IIT, Gênes, Italie
Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.
Abstract
La simulation de l'évolution temporelle des systèmes de mécanique quantique est difficile pour le BQP et devrait être l'une des principales applications des ordinateurs quantiques. Nous considérons des algorithmes classiques pour l'approximation de la dynamique hamiltonienne en utilisant des méthodes de sous-échantillonnage de l'algèbre linéaire numérique randomisée. Nous dérivons une technique de simulation dont le temps d'exécution évolue de manière polynomiale dans le nombre de qubits et la norme de Frobenius de l'hamiltonien. Comme application immédiate, nous montrons que la simulation quantique basée sur un échantillon, un type d'évolution où l'hamiltonien est une matrice de densité, peut être efficacement simulée de manière classique dans des conditions structurelles spécifiques. Notre principale contribution technique est un algorithme randomisé pour approximer les exponentielles de la matrice hermitienne. La preuve s'appuie sur une approximation symétrique de rang inférieur via la méthode de Nyström. Nos résultats suggèrent que sous de fortes hypothèses d'échantillonnage, il existe des simulations temporelles poly-logarithmiques classiques de calculs quantiques.
► Données BibTeX
► Références
Aharonov et Ta-Shma "Génération d'états quantiques adiabatiques et connaissance statistique zéro" Actes du trente-cinquième symposium annuel de l'ACM sur la théorie de l'informatique 20-29 (2003).
https: / / doi.org/ 10.1145 / 780542.780546
Aleksandrov et Peller "Fonctions de l'opérateur Lipschitz" Russian Mathematical Surveys 71, 605 (2016).
https:///doi.org/10.1070/RM9729
Belabbas et Wolfe "Approximation rapide de rang inférieur pour les matrices de covariance" 2e atelier international IEEE sur les avancées informatiques dans le traitement adaptatif multi-capteurs, 2007. 293-296 (2007).
https:///doi.org/10.1109/CAMSAP.2007.4498023
Belabbas et Wolfe "Sur les représentations parcimonieuses des opérateurs linéaires et l'approximation des produits matriciels" 42e Conférence annuelle sur les sciences et les systèmes de l'information 258-263 (2008).
https: / / doi.org/ 10.1109 / CISS.2008.4558532
Berry, Childs et Kothari, "Simulation hamiltonienne avec une dépendance presque optimale sur tous les paramètres" IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) 792-809 (2015).
https: / / doi.org/ 10.1109 / FOCS.2015.54
Biamonte, Wittek, Pancotti, Rebentrost, Wiebe et Lloyd, "Apprentissage automatique quantique" Nature 549, 195 (2017).
https: / / doi.org/ 10.1038 / nature23474
Bravyi, Browne, Calpin, Campbell, Gosset et Howard, "Simulation de circuits quantiques par décompositions de stabilisateurs de rang inférieur" arXiv preprint arXiv:1808.00128 (2018).
https://doi.org/10.22331/q-2019-09-02-181
Chia, Gilyén, Li, Lin, Tang et Wang, "Cadre arithmétique matriciel sous-linéaire de bas rang basé sur l'échantillonnage pour déquantifier l'apprentissage automatique quantique" arXiv preprint arXiv:1910.06151 (2019).
Childs et Kothari "Simulating Sparse Hamiltonians with Star Decompositions" Actes de la 5e conférence sur la théorie du calcul quantique, de la communication et de la cryptographie 94-103 (2011).
https://doi.org/10.1007/978-3-642-18073-6_8
Childs et Wiebe "Simulation hamiltonienne utilisant des combinaisons linéaires d'opérations unitaires" Quantum Info. Calcul. 12, 901-924 (2012).
https: / / doi.org/ 10.5555 / 2481569.2481570
Childs, Cleve, Deotto, Farhi, Gutmann et Spielman, "Exponential Algorithmic Speedup by a Quantum Walk" Actes du trente-cinquième symposium annuel ACM sur la théorie de l'informatique 59-68 (2003).
https: / / doi.org/ 10.1145 / 780542.780552
Ciliberto, Herbster, Ialongo, Pontil, Rocchetto, Severini et Wossnig, "Apprentissage automatique quantique : une perspective classique" Proc. R. Soc. A 474, 20170551 (2018).
https: / / doi.org/ 10.1098 / rspa.2017.0551
Drineas, Kannan et Mahoney, "Algorithmes rapides de Monte Carlo pour les matrices I : multiplication matricielle approximative" SIAM Journal on Computing 36, 132-157 (2006).
https: / / doi.org/ 10.1137 / S0097539704442684
Drineas, Kannan et Mahoney, "Algorithmes Fast Monte Carlo pour les matrices II : Calcul d'une approximation de rang inférieur à une matrice" SIAM Journal on computing 36, 158-183 (2006).
https: / / doi.org/ 10.1137 / S0097539704442696
Drineas et Mahoney "Sur la méthode Nyström pour l'approximation d'une matrice Gram pour un apprentissage basé sur le noyau amélioré" J. Mach. Apprendre. Rés. 6, 2153-2175 (2005).
https: / / doi.org/ 10.5555 / 1046920.1194916
Drineas et Mahoney "Conférences sur l'algèbre linéaire numérique randomisée" The Mathematics of Data 25, 1 (2018).
Drineas, Mahoney, Muthukrishnan et Sarlós, « Approximation plus rapide des moindres carrés » Numer. Math. 117, 219-249 (2011).
https://doi.org/10.1007/s00211-010-0331-6
Fowlkes, Belongie, Chung et Malik, "Groupement spectral utilisant la méthode Nyström" IEEE Trans. Modèle Anal. Mach. Renseignement. 26, 214-225 (2004).
https: / / doi.org/ 10.1109 / TPAMI.2004.1262185
Frieze, Kannan et Vempala, "Algorithmes rapides de Monte-Carlo pour la recherche d'approximations de rang inférieur" J. ACM 51, 1025-1041 (2004).
https: / / doi.org/ 10.1145 / 1039488.1039494
Haegeman, Cirac, Osborne, Pižorn, Verschelde et Verstraete, "Principe variationnel dépendant du temps pour les réseaux quantiques" Lettres de revue physique 107, 070601 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.107.070601
Higham "La méthode de mise à l'échelle et de quadrature pour la matrice exponentielle revisitée" SIAM J. Matrix Anal. Appl. 26, 1179-1193 (2005).
https: / / doi.org/ 10.1137 / 04061101X
Higham "La méthode de mise à l'échelle et de quadrature pour la matrice exponentielle revisitée" SIAM Rev. 51, 747-764 (2009).
https: / / doi.org/ 10.1137 / 090768539
Hsu « Échantillonnage pondéré des produits extérieurs » arXiv preprint arXiv : 1410.4429 (2014).
Huang, Newman et Szegedy, "Limites inférieures explicites sur la simulation quantique forte" arXiv preprint arXiv:1804.10368 (2018).
Jónsson, Bauer et Carleo, "États de réseau de neurones pour la simulation classique de l'informatique quantique" arXiv preprint arXiv:1808.05232 (2018).
Kerenidis et Prakash "Systèmes de recommandation quantique" arXiv preprint arXiv:1603.08675 (2016).
Kimmel, Lin, Low, Ozols et Yoder, "Simulation hamiltonienne avec une complexité d'échantillon optimale" npj Quantum Information 3, 13 (2017).
https://doi.org/10.1038/s41534-017-0013-7
Kumar, Mohri et Talwalkar, "On Sampling-Based Approximate Spectral Decomposition" Actes de la
26e Conférence internationale annuelle sur l'apprentissage automatique 553-560 (2009).
https: / / doi.org/ 10.1145 / 1553374.1553446
Kumar, Mohri et Talwalkar, "Méthodes d'échantillonnage pour la méthode Nyström" Journal of Machine Learning Research 13, 981-1006 (2012).
https: / / doi.org/ 10.5555 / 2188385.2343678
Li, Kwok et Lu, "Rendre l'approximation de Nyström à grande échelle possible" Actes de la 27e Conférence internationale sur l'apprentissage automatique 631-638 (2010).
https: / / doi.org/ 10.5555 / 3104322.3104403
Lloyd "Universal Quantum Simulators" Science 273, 1073-1078 (1996).
https: / / doi.org/ 10.1126 / science.273.5278.1073
Lloyd, Mohseni et Rebentrost, "Analyse en composantes principales quantiques" Nature Physics 10, 631 (2014).
https: / / doi.org/ 10.1038 / nphys3029
Lowand Chuang « Hamiltonian Simulation by Uniform Spectral Amplification » arXiv preprint arXiv:1707.05391 (2017).
Mackey, Talwalkar et Jordan, "Divide-and-Conquer Matrix Factorization" Actes de la 24e Conférence internationale sur les systèmes de traitement de l'information neuronale 1134-1142 (2011).
https: / / doi.org/ 10.5555 / 2986459.2986586
Mahoney "Algorithmes aléatoires pour matrices et données" Foundations and Trends® 3, 123-224 (2011).
https: / / doi.org/ 10.1561 / 2200000035
Mathias "Approximation of matrix-valued functions" Revue SIAM sur l'analyse matricielle et ses applications 14, 1061-1063 (1993).
https: / / doi.org/ 10.1137 / 0614070
Al-Mohyand Higham "Un nouvel algorithme de mise à l'échelle et de mise au carré pour la matrice exponentielle" SIAM Journal on Matrix Analysis and Applications 31, 970-989 (2009).
https: / / doi.org/ 10.1137 / 09074721X
Al-Mohyand Higham "Calcul de l'action de la matrice exponentielle, avec une application aux intégrateurs exponentiels" Journal SIAM sur le calcul scientifique 33, 488-511 (2011).
https: / / doi.org/ 10.1137 / 100788860
Nakamoto « Une inégalité de norme pour les opérateurs hermitiens » Le mensuel mathématique américain 110, 238 (2003).
https: / / doi.org/ 10.1080 / 00029890.2003.11919961
Nyström "Über die praktische Auflösung von Integralgleichungen mit Anwendungen auf Randwertaufgaben" Acta Mathematica 54, 185-204 (1930).
https: / / doi.org/ 10.1007 / BF02547521
Orecchia, Sachdeva et Vishnoi, « Approximating the Exponential, the Lanczos Method and an Õ(m)-Time Spectral Algorithm for Balanced Separator », actes du quarante-quatrième symposium annuel ACM sur la théorie de l'informatique 1141-1160 (2012).
https: / / doi.org/ 10.1145 / 2213977.2214080
Orús "Une introduction pratique aux réseaux de tenseurs : États de produits matriciels et états de paires intriqués projetés" Annals of Physics 349, 117-158 (2014).
https: / / doi.org/ 10.1016 / j.aop.2014.06.013
Rebentrost, Mohseni et Lloyd, "Machine à vecteurs de support quantique pour la classification des mégadonnées" Lettres d'examen physique 113, 130503 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.130503
Rebentrost, Schuld, Wossnig, Petruccione et Lloyd, « Descente de gradient quantique et méthode de Newton pour l'optimisation polynomiale contrainte » New Journal of Physics 21, 073023 (2019).
https://doi.org/10.1088/1367-2630/ab2a9e
Rudi, Camoriano et Rosasco, "Less is More: Nyström Computational Regularization" Actes de la 28e Conférence internationale sur les systèmes de traitement de l'information neuronale - Volume 1 1657-1665 (2015).
https: / / doi.org/ 10.5555 / 2969239.2969424
Rudi, Camoriano et Rosasco, "Less is More: Nyström Computational Regularization" arXiv preprint arXiv:1507.04717 (2015).
Schuld, Sinayskiy et Petruccione, "Prédiction par régression linéaire sur un ordinateur quantique" Physical Review A 94, 022342 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.94.022342
Schwarz et Nest "Simulation de circuits quantiques avec des distributions de sortie clairsemées" arXiv preprint arXiv:1310.6749 (2013).
Spielman et Teng "Algorithmes de temps quasi-linéaires pour le partitionnement de graphes, la sparsification de graphes et la résolution de systèmes linéaires" Actes du trente-sixième symposium annuel ACM sur la théorie de l'informatique 81-90 (2004).
https: / / doi.org/ 10.1145 / 1007352.1007372
Spielman et Teng "Spectral sparsification of graphs" SIAM Journal on Computing 40, 981-1025 (2011).
https: / / doi.org/ 10.1137 / 08074489X
Suzuki "La formule de Trotter généralisée et les approximants systématiques des opérateurs exponentiels et des dérivations internes avec des applications aux problèmes à plusieurs corps" Communications in Mathematical Physics 51, 183-190 (1976).
https: / / doi.org/ 10.1007 / BF01609348
Talwalkar, Kumar et Rowley, « Apprentissage multiple à grande échelle » Conférence IEEE sur la vision par ordinateur et la reconnaissance de formes 1-8 (2008).
https: / / doi.org/ 10.1109 / CVPR.2008.4587670
Tang « Un algorithme classique d'inspiration quantique pour les systèmes de recommandation » Actes du 51e Symposium annuel ACM SIGACT sur la théorie de l'informatique 217-228 (2019).
https: / / doi.org/ 10.1145 / 3313276.3316310
Tropp "Limites de queue conviviales pour les sommes de matrices aléatoires" trouvées. Calcul. Math. 12, 389-434 (2012).
https: / / doi.org/ 10.1007 / s10208-011-9099-z
Trotter "Sur le produit de semi-groupes d'opérateurs" Actes de l'American Mathematical Society 10, 545-551 (1959).
https://doi.org/10.1090/S0002-9939-1959-0108732-6
Van Den Nest "Simulation classique du calcul quantique, le Gottesman" Quantum Information & Computation 10, 258-271 (2010).
https: / / doi.org/ 10.5555 / 2011350.2011356
Verstraete, Garcia-Ripoll et Cirac, "Opérateurs de densité de produits matriciels : simulation de systèmes à température finie et dissipatifs" Lettres de revue physique 93, 207204 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.93.207204
Verstraete, Murg et Cirac, "États de produits matriciels, états de paires intriqués projetés et méthodes de groupe de renormalisation variationnelle pour les systèmes de spin quantiques" Advances in Physics 57, 143-224 (2008).
https: / / doi.org/ 10.1063 / 1.5026985
Vidal "Simulation efficace des systèmes à plusieurs corps quantiques unidimensionnels" Phys. Rév. Lett. 93, 040502 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.93.040502
Williams et Seeger "Utilisation de la méthode Nyström pour accélérer les machines à noyau" Advances in Neural Information Processing Systems 13 682-688 (2001).
https: / / doi.org/ 10.5555 / 3008751.3008847
Williams, Rasmussen, Schwaighofer et Tresp, rapport "Observations on the Nyström Method for Gaussian Process Prediction" (2002).
Woodruff "Sketching as a tool for digital linear algebra" Foundations and Trends® 10, 1-157 (2014).
https: / / doi.org/ 10.1561 / 0400000060
Zhang et Kwok "Méthode Nyström en cluster pour l'apprentissage multiple à grande échelle et la réduction de dimension" IEEE Transactions on Neural Networks 21, 1576-1587 (2010).
https:///doi.org/10.1109/TNN.2010.2064786
Zhang, Tsang et Kwok, "Amélioration de l'approximation de bas rang de Nyström et de l'analyse des erreurs" Actes de la 25e Conférence internationale sur l'apprentissage automatique 1232-1239 (2008).
https: / / doi.org/ 10.1145 / 1390156.1390311
Cité par
[1] Ewin Tang, "Algorithmes classiques d'inspiration quantique pour l'analyse en composantes principales et le clustering supervisé", arXiv: 1811.00414.
[2] Juan A. Acebron, "Une méthode de Monte Carlo pour calculer l'action d'une exponentielle matricielle sur un vecteur", arXiv: 1904.12759.
[3] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang et Chunhao Wang, «Cadre arithmétique matriciel de bas rang sublinéaire basé sur l'échantillonnage pour déquantifier l'apprentissage machine quantique», arXiv: 1910.06151.
Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2020-02-20 15:40:36). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.
Impossible de récupérer Données de référence croisée lors de la dernière tentative 2020-02-20 15:40:34: Impossible de récupérer les données citées par 10.22331 / q-2020-02-20-234 de Crossref. C'est normal si le DOI a été enregistré récemment.
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.
Source : https://quantum-journal.org/papers/q-2020-02-20-234/
