Yukawa Institute for Theoretical Physics, Kyoto University, Kitashirakawa Oiwakecho, Sakyoku, Kyoto 606-8502, Japon
Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.
Abstract
L'analyse de données topologiques (ADT) est un domaine émergent de l'analyse de données. L'étape critique de TDA consiste à calculer les nombres persistants de Betti. Les algorithmes classiques existants pour TDA sont limités si nous voulons apprendre des caractéristiques topologiques de grande dimension car le nombre de simplexes de grande dimension croît de manière exponentielle dans la taille des données. Dans le cadre du calcul quantique, il a été précédemment montré qu'il existe un algorithme quantique efficace pour estimer les nombres de Betti même en grande dimension. Cependant, les nombres de Betti sont moins généraux que les nombres de Betti persistants, et il n'y a pas eu d'algorithmes quantiques capables d'estimer les nombres de Betti persistants de dimensions arbitraires.
Cet article montre le premier algorithme quantique qui peut estimer les nombres de Betti persistants ($normalisés$) de dimensions arbitraires. Notre algorithme est efficace pour les complexes simpliciaux tels que le complexe de Vietoris-Rips et démontre une accélération exponentielle par rapport aux algorithmes classiques connus.
► Données BibTeX
► Références
Mehmet E Aktas, Esra Akbas et Ahmed El Fatmaoui. Homologie de persistance des réseaux : méthodes et applications. Applied Network Science, 4 (1): 1–28, 2019. 10.1007/s41109-019-0179-3.
https://doi.org/10.1007/s41109-019-0179-3
Jonathan Ariel Barmak et Elias Gabriel Minian. Types d'homotopie forte, nerfs et effondrements. Géométrie discrète et computationnelle, 47 (2): 301–328, 2012. 10.1007/s00454-011-9357-5.
https://doi.org/10.1007/s00454-011-9357-5
Andreas Bärtschi et Stephan Eidenbenz. Préparation déterministe des états de Dicke. Dans Symposium international sur les principes fondamentaux de la théorie du calcul, pages 126–139. Springer, 2019. 10.1007/978-3-030-25027-0_9.
https://doi.org/10.1007/978-3-030-25027-0_9
Gilles Brassard, Peter Hoyer, Michele Mosca et Alain Tapp. Amplification et estimation d'amplitude quantique. Mathématiques contemporaines, 305: 53–74, 2002. 10.1090 / conm / 305/05215.
https: / / doi.org/ 10.1090 / conm / 305/05215
Peter Bubenik et al. Analyse statistique des données topologiques à l'aide de paysages de persistance. J.Mach. Apprendre. Rés., 16 (1): 77–102, 2015. 10.5555/2789272.2789275.
https: / / doi.org/ 10.5555 / 2789272.2789275
Frédéric Chazal et Bertrand Michel. Une introduction à l'analyse topologique des données : aspects fondamentaux et pratiques pour les data scientists. Aux frontières de l'intelligence artificielle, 4, 2021. 10.3389/frai.2021.667963.
https:///doi.org/10.3389/frai.2021.667963
Ho Yee Cheung, Tsz Chiu Kwok et Lap Chi Lau. Algorithmes et applications de rang matriciel rapide. Journal de l'ACM (JACM), 60 (5): 1–25, 2013. 10.1145/2528404.
https: / / doi.org/ 10.1145 / 2528404
David Cohen-Steiner, Herbert Edelsbrunner et John Harer. Stabilité des diagrammes de persistance. Géométrie discrète et computationnelle, 37 (1): 103–120, 2007. 10.1007/s00454-006-1276-5.
https://doi.org/10.1007/s00454-006-1276-5
Alex Cole et Gary Shiu. Analyse des données topologiques pour le paysage des cordes. Journal of High Energy Physics, 2019 (3): 1–31, 2019. 10.1007/JHEP03(2019)054.
https: / / doi.org/ 10.1007 / JHEP03 (2019) 054
Steven A Cuccaro, Thomas G Draper, Samuel A Kutin et David Petrie Moulton. Un nouveau circuit d'addition de transport d'ondulation quantique. arXiv preprint quant-ph/0410184, 2004. 10.48550/arXiv.quant-ph/0410184.
https:///doi.org/10.48550/arXiv.quant-ph/0410184
arXiv: quant-ph / 0410184
Edoardo Di Napoli, Eric Polizzi et Yousef Saad. Estimation efficace du nombre de valeurs propres dans un intervalle. Algèbre linéaire numérique avec applications, 23 (4): 674–692, 2016. 10.1002/nla.2048.
https:///doi.org/10.1002/nla.2048
Robert H Dicke. Cohérence dans les processus de rayonnement spontanés. Revue physique, 93 (1): 99, 1954. 10.1103/PhysRev.93.99.
https: / / doi.org/ 10.1103 / PhysRev.93.99
Herbert Edelsbrunner et John Harer. Topologie informatique: une introduction. American Mathematical Soc., 2010. 10.1007/978-3-540-33259-6_7.
https://doi.org/10.1007/978-3-540-33259-6_7
Herbert Edelsbrunner, David Letscher et Afra Zomorodian. Persistance topologique et simplification. Dans Actes du 41e symposium annuel sur les fondements de l'informatique, pages 454–463. IEEE, 2000. 10.1007/s00454-002-2885-2.
https://doi.org/10.1007/s00454-002-2885-2
Herbert Edelsbrunner, John Harer, et al. Homologie persistante - une enquête. Mathématiques contemporaines, 453 : 257–282, 2008. 10.1090/conm/453/08802.
https: / / doi.org/ 10.1090 / conm / 453/08802
Joël Friedman. Calcul des nombres de betti via des laplaciens combinatoires. Algorithmica, 21 (4) : 331–346, 1998. 10.1007/PL00009218.
https: / / doi.org/ 10.1007 / PL00009218
Robert Ghrist. Codes à barres : la topologie persistante des données. Bulletin de l'American Mathematical Society, 45 (1) : 61–75, 2008. 10.1090/S0273-0979-07-01191-3.
https://doi.org/10.1090/S0273-0979-07-01191-3
András Gilyén, Yuan Su, Guang Hao Low et Nathan Wiebe. Transformation de valeur singulière quantique et au-delà : améliorations exponentielles pour l'arithmétique matricielle quantique. Dans Actes du 51e symposium annuel ACM SIGACT sur la théorie de l'informatique, pages 193-204, 2019. 10.1145/3313276.3316366.
https: / / doi.org/ 10.1145 / 3313276.3316366
Sam Gunn et Niels Kornerup. Examen d'un algorithme quantique pour les nombres de betti. arXiv preprint arXiv:1906.07673, 2019. 10.48550/arXiv.1906.07673.
https:///doi.org/10.48550/arXiv.1906.07673
arXiv: 1906.07673
Aram W Harrow, Avinatan Hassidim et Seth Lloyd. Algorithme quantique pour les systèmes linéaires d'équations. Lettres d'examen physique, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
Ryû Hayakawa. Algorithme quantique pour les nombres de betti persistants et l'analyse des données topologiques. arXiv preprint arXiv:2111.00433v1, 2021. 10.48550/arXiv.2111.00433.
https:///doi.org/10.48550/arXiv.2111.00433
arXiv: 2111.00433v1
Ryu Hayakawa, Tomoyuki Morimae et Suguru Tamaki. Suprématie quantique à grain fin basée sur des vecteurs orthogonaux, des chemins les plus courts à 3 sommes et à toutes les paires. arXiv preprint arXiv:1902.08382, 2019. 10.48550/arXiv.1902.08382.
https:///doi.org/10.48550/arXiv.1902.08382
arXiv: 1902.08382
Yong He, Ming-Xing Luo, E Zhang, Hong-Ke Wang et Xiao-Feng Wang. Décompositions de portes Toffoli à n-qubits avec une complexité de circuit linéaire. Journal international de physique théorique, 56 (7): 2350–2361, 2017. 10.1007/s10773-017-3389-4.
https://doi.org/10.1007/s10773-017-3389-4
He-Liang Huang, Xi-Lin Wang, Peter P Rohde, Yi-Han Luo, You-Wei Zhao, Chang Liu, Li Li, Nai-Le Liu, Chao-Yang Lu et Jian-Wei Pan. Démonstration d'analyse de données topologiques sur un processeur quantique. Optica, 5 (2): 193–198, 2018. 10.1364/OPTICA.5.000193.
https: / / doi.org/ 10.1364 / OPTICA.5.000193
Lek-Heng Lim. Laplaciens de Hodge sur les graphiques. Revue SIAM, 62 (3) : 685–715, 2020. 10.1137/18M1223101.
https: / / doi.org/ 10.1137 / 18M1223101
Lin Lin, Yousef Saad et Chao Yang. Approximation des densités spectrales de grandes matrices. Revue SIAM, 58 (1) : 34–65, 2016. 10.1137/130934283.
https: / / doi.org/ 10.1137 / 130934283
Seth Lloyd, Silvano Garnerone et Paolo Zanardi. Algorithmes quantiques pour l'analyse topologique et géométrique des données. Nature communications, 7 (1) : 1–7, 2016. 10.1038/ncomms10138.
https: / / doi.org/ 10.1038 / ncomms10138
John M Martyn, Zane M Rossi, Andrew K Tan et Isaac L Chuang. Grande unification des algorithmes quantiques. PRX Quantum, 2 (4) : 040203, 2021. 10.1103/PRXQuantum.2.040203.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
RHAJ Meijer. Regroupement utilisant l'homologie persistante quantique. Mémoire de maîtrise, 2019.
Facundo Mémoli, Zhengchao Wan et Yusu Wang. Laplaciens persistants : Propriétés, algorithmes et implications. SIAM Journal on Mathematics of Data Science, 4 (2): 858–884, 2022. 10.1137/21M1435471.
https: / / doi.org/ 10.1137 / 21M1435471
Niels Neumann et Sterre den Breeijen. Limitations du clustering utilisant l'homologie persistante quantique. arXiv preprint arXiv:1911.10781, 2019. 10.48550/arXiv.1911.10781.
https:///doi.org/10.48550/arXiv.1911.10781
arXiv: 1911.10781
Nina Otter, Mason A Porter, Ulrike Tillmann, Peter Grindrod et Heather A Harrington. Une feuille de route pour le calcul de l'homologie persistante. EPJ Data Science, 6 : 1–38, 2017. 10.1140/epjds/s13688-017-0109-5.
https://doi.org/10.1140/epjds/s13688-017-0109-5
Pratyush Pranav, Herbert Edelsbrunner, Rien Van de Weygaert, Gert Vegter, Michael Kerber, Bernard JT Jones et Mathijs Wintraecken. La topologie de la toile cosmique en termes de nombres de betti persistants. Avis mensuels de la Royal Astronomical Society, 465 (4) : 4281–4310, 2017. 10.1093/mnras/stw2862.
https:///doi.org/10.1093/mnras/stw2862
Chi Seng Pun, Si Xian Lee et Kelin Xia. Apprentissage automatique basé sur l'homologie persistante : une enquête et une étude comparative. Revue de l'intelligence artificielle, pages 1 à 45, 2022. 10.1007/s10462-022-10146-z.
https: / / doi.org/ 10.1007 / s10462-022-10146-z
Patrick Rally. Algorithmes quantiques cohérents plus rapides pour l'estimation de la phase, de l'énergie et de l'amplitude. Quantique, 5 : 566, 2021. 10.22331/q-2021-10-19-566.
https://doi.org/10.22331/q-2021-10-19-566
Abu Bakar Siddique, Saadia Farid et Muhammad Tahir. Preuve de bijection pour le système de nombres combinatoires. arXiv preprint arXiv:1601.05794, 2016. 10.48550/arXiv.1601.05794.
https:///doi.org/10.48550/arXiv.1601.05794
arXiv: 1601.05794
Daniel Spitz, Jürgen Berges, Markus Oberthaler et Anna Wienhard. Trouver un comportement auto-similaire dans la dynamique quantique à plusieurs corps via une homologie persistante. SciPost Phys., 11 : 060, 2021. 10.21468/SciPostPhys.11.3.060. URL https://scipost.org/10.21468/SciPostPhys.11.3.060.
https: / / doi.org/ 10.21468 / SciPostPhys.11.3.060
Shashanka Ubaru, Ismail Yunus Akhalwaya, Mark S Squillante, Kenneth L Clarkson et Lior Horesh. Analyse de données topologiques quantiques avec profondeur linéaire et accélération exponentielle. arXiv preprint arXiv:2108.02811, 2021. 10.48550/arXiv.2108.02811.
https:///doi.org/10.48550/arXiv.2108.02811
arXiv: 2108.02811
Rui Wang, Duc Duy Nguyen et Guo-Wei Wei. Graphique spectral persistant. Revue internationale des méthodes numériques en génie biomédical, 36 (9) : e3376, 2020. 10.1002/cnm.3376.
https:///doi.org/10.1002/cnm.3376
Larry Wasserman. Analyse des données topologiques. Revue annuelle des statistiques et de leur application, 5 : 501–532, 2018. 10.1146/annurev-statistics-031017-100045.
https:///doi.org/10.1146/annurev-statistics-031017-100045
Kelin Xia et Guo-Wei Wei. Analyse d'homologie persistante de la structure, de la flexibilité et du repliement des protéines. Journal international des méthodes numériques en génie biomédical, 30 (8): 814–844, 2014. 10.1002/cnm.2655.
https:///doi.org/10.1002/cnm.2655
Afra Zomorodian et Gunnar Carlsson. Calcul de l'homologie persistante. Géométrie discrète et computationnelle, 33 (2): 249–274, 2005. 10.1007/s00454-004-1146-y.
https: / / doi.org/ 10.1007 / s00454-004-1146-y
Cité par
[1] Alexander Schmidhuber et Seth Lloyd, "Limitations de la théorie de la complexité sur les algorithmes quantiques pour l'analyse des données topologiques", arXiv: 2209.14286.
[2] Bernardo Ameneyro, Vasileios Maroulas et George Siopsis, "Quantum Persistent Homology", arXiv: 2202.12965.
[3] Dominic W. Berry, Yuan Su, Casper Gyurik, Robbie King, Joao Basso, Alexander Del Toro Barba, Abhishek Rajput, Nathan Wiebe, Vedran Dunjko et Ryan Babbush, "Quantifying Quantum Advantage in Topological Data Analysis", arXiv: 2209.13581.
[4] Iordanis Kerenidis et Anupam Prakash, "Apprentissage automatique quantique avec états subspatiaux", arXiv: 2202.00054.
[5] Bernardo Ameneyro, George Siopsis et Vasileios Maroulas, "Quantum Persistent Homology for Time Series", arXiv: 2211.04465.
[6] Simon Apers, Sayantan Sen et Dániel Szabó, "Un (simple) algorithme classique pour estimer les nombres de Betti", arXiv: 2211.09618.
[7] Sam McArdle, András Gilyén et Mario Berta, "Un algorithme quantique rationalisé pour l'analyse de données topologiques avec un nombre exponentiel de qubits", arXiv: 2209.12887.
[8] Andrew Vlasic et Anh Pham, "Comprendre le mappage des données d'encodage grâce à une mise en œuvre de l'analyse topologique quantique", arXiv: 2209.10596.
Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2022-12-07 16:42:14). 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 2022-12-07 16:42:12: Impossible de récupérer les données citées par 10.22331 / q-2022-12-07-873 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.
