Station Q, Microsoft Research, Santa Barbara, CA 93106-6105, États-Unis
Microsoft Quantum et Microsoft Research, Redmond, WA 98052, États-Unis
Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.
Abstract
Nous présentons des algorithmes classiques et quantiques basés sur des méthodes spectrales pour un problème d'analyse en composantes principales tensorielles. L'algorithme quantique réalise une accélération $ quartic $ tout en utilisant un espace exponentiellement plus petit que l'algorithme spectral classique le plus rapide, et une accélération super-polynomiale par rapport aux algorithmes classiques qui n'utilisent que l'espace polynomial. Les algorithmes classiques que nous présentons sont liés, mais légèrement différents de ceux présentés récemment dans la Réf. [1]. En particulier, nous avons un seuil amélioré de récupération et les algorithmes que nous présentons fonctionnent à la fois pour les tenseurs d'ordre pair et impair. Ces résultats suggèrent que les problèmes d'inférence à grande échelle sont une application future prometteuse pour les ordinateurs quantiques.
► Données BibTeX
► Références
Alexander S Wein, Ahmed El Alaoui et Cristopher Moore. La hiérarchie kikuchi et le tenseur pca. 2019. arXiv: 1904.03858.
arXiv: 1904.03858
Andrea Montanari et Emile Richard. Un modèle statistique pour le tenseur pca. In Advances in Neural Information Processing Systems, pages 2897-2905, 2014.
Thibault Lesieur, Leo Miolane, Marc Lelarge, Florent Krzakala et Lenka Zdeborova. Transitions de phase statistiques et de calcul dans l'estimation de tenseur dopé. En 2017, IEEE International Symposium on Information Theory (ISIT). IEEE, juin 2017. doi: 10.1109 / isit.2017.8006580.
https: / / doi.org/ 10.1109 / isit.2017.8006580
Samuel B Hopkins, Jonathan Shi et David Steurer. Analyse des composants principaux Tensor via des preuves de somme de carrés. Dans Conference on Learning Theory, pages 956–1006, 2015.
Samuel B. Hopkins, Tselil Schramm, Jonathan Shi et David Steurer. Algorithmes spectraux rapides à partir de preuves de somme de carrés: décomposition tenseur et vecteurs clairsemés plantés. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016. ACM Press, 2016. doi: 10.1145 / 2897518.2897529.
https: / / doi.org/ 10.1145 / 2897518.2897529
Vijay VSP Bhattiprolu, Mrinalkanti Ghosh, Euiwoong Lee, Venkatesan Guruswami et Madhur Tulsiani. Approximations multiplicatives pour l'optimisation polynomiale sur la sphère unitaire. CoRR, abs / 1611.05998, 2016. URL: http: / / arxiv.org/ abs / 1611.05998, arXiv: 1611.05998.
arXiv: 1611.05998
Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee et Madhur Tulsiani. Découplage faible, plis polynomiaux et optimisation approximative sur la sphère. En 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, octobre 2017. doi: 10.1109 / focs.2017.97.
https: / / doi.org/ 10.1109 / focs.2017.97
RF Werner. Grands écarts et systèmes quantiques à champ moyen. Dans Quantum Probability and Related Topics, pages 349–381. WORLD SCIENTIFIC, juillet 1992. doi: 10.1142 / 9789814354783_0024.
https: / / doi.org/ 10.1142 / 9789814354783_0024
Christina V. Kraus, Maciej Lewenstein et J. Ignacio Cirac. États fondamentaux des hamiltoniens du réseau fermionique avec symétrie de permutation. Physical Review A, 88 (2), août 2013. doi: 10.1103 / physreva.88.022335.
https: / / doi.org/ 10.1103 / physreva.88.022335
Fernando GSL Brandão et Aram W. Harrow. Approximations d'état de produit aux états quantiques. Communications in Mathematical Physics, 342 (1): 47–80, janvier 2016. doi: 10.1007 / s00220-016-2575-1.
https://doi.org/10.1007/s00220-016-2575-1
Scott Aaronson et Lijie Chen. Fondements théoriques de la complexité des expériences de suprématie quantique. Lors de la 32e conférence sur la complexité computationnelle (CCC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. arXiv: 1612.05903.
arXiv: 1612.05903
Madan Lal Mehta. Matrices aléatoires, volume 142. Elsevier, 2004.
James Demmel, Ioana Dumitriu et Olga Holtz. L'algèbre linéaire rapide est stable. Numerische Mathematik, 108 (1): 59–91, octobre 2007. doi: 10.1007 / s00211-007-0114-x.
https: / / doi.org/ 10.1007 / s00211-007-0114-x
Guang Hao Low et Isaac L. Chuang. Simulation hamiltonienne optimale par traitement du signal quantique. Phys. Rev. Lett., 118: 010501, 2017. arXiv: 1606.02685v2, doi: 10.1103 / PhysRevLett.118.010501.
https: / / doi.org/ 10.1103 / PhysRevLett.118.010501
arXiv: 1606.02685v2
Guang Hao Low et Isaac L. Chuang. Simulation hamiltonienne par qubitisation. 2016. arXiv: 1610.06546 https: / / doi.org/ 10.22331 / q-2019-07-12-163.
https://doi.org/10.22331/q-2019-07-12-163
arXiv: 1610.06546
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari et Rolando D. Somma. Amélioration exponentielle de la précision pour la simulation des hamiltoniens clairsemés. pages 283 à 292, 2014. arXiv: 1312.1414, doi: 10.1145 / 2591796.2591854.
https: / / doi.org/ 10.1145 / 2591796.2591854
arXiv: 1312.1414
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari et Rolando D. Somma. Simulation de la dynamique hamiltonienne avec une série de Taylor tronquée. Phys. Rev. Lett., 114: 090502, 2015. arXiv: 1412.4687, doi: 10.1103 / PhysRevLett.114.090502.
https: / / doi.org/ 10.1103 / PhysRevLett.114.090502
arXiv: 1412.4687
DW Berry, AM Childs et R. Kothari. Simulation hamiltonienne avec dépendance presque optimale de tous les paramètres. En 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 792–809, octobre 2015. arXiv: 1501.01715, doi: 10.1109 / FOCS.2015.54.
https: / / doi.org/ 10.1109 / FOCS.2015.54
arXiv: 1501.01715
Alexei Yu Kitaev, Alexander Shen et Mikhail N Vyalyi. Calcul classique et quantique, volume 47. American Mathematical Society Providence, 2002. doi: 10.1090 / gsm / 047.
https: / / doi.org/ 10.1090 / gsm / 047
Gilles Brassard, Peter Hoyer, Michele Mosca et Alain Tapp. Amplification et estimation d'amplitude quantique. Mathématiques contemporaines, 305: 53–74, 2002. doi: 10.1090 / conm / 305.
https: / / doi.org/ 10.1090 / conm / 305
Anthony Carbery et James Wright. Inégalités de distribution et de norme $ {L ^ q} $ pour les polynômes sur corps convexes dans $ {R ^ n} $. Mathematical Research Letters, 8 (3): 233–248, 2001. doi: 10.4310 / mrl.2001.v8.n3.a1.
https://doi.org/10.4310/mrl.2001.v8.n3.a1
Dave Wecker, Matthew B. Hastings, Nathan Wiebe, Bryan K. Clark, Chetan Nayak et Matthias Troyer. Résolution de modèles d'électrons fortement corrélés sur un ordinateur quantique. Physical Review A, 92 (6), décembre 2015. doi: 10.1103 / physreva.92.062318.
https: / / doi.org/ 10.1103 / physreva.92.062318
< p class="break"> Matthew B. Hastings. L'asymptotique de la coupure minimale quantique à débit maximal. Communications in Mathematical Physics, 351 (1): 387–418, novembre 2016. doi: 10.1007 / s00220-016-2791-8.
https://doi.org/10.1007/s00220-016-2791-8
Cité par
[1] Alexander S. Wein, Ahmed El Alaoui et Cristopher Moore, «The Kikuchi Hierarchy and Tensor PCA», arXiv: 1904.03858.
Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2020-02-28 01:28:52). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.
On Le service cité par Crossref aucune donnée sur la citation des œuvres n'a été trouvée (dernière tentative 2020-02-28 01:28:50).
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-27-237/
