Instituto Yukawa de Física Teórica, Universidad de Kyoto, Kitashirakawa Oiwakecho, Sakyoku, Kyoto 606-8502, Japón
¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.
Resumen
El análisis de datos topológicos (TDA) es un campo emergente del análisis de datos. El paso crítico de TDA es calcular los números persistentes de Betti. Los algoritmos clásicos existentes para TDA están limitados si queremos aprender de características topológicas de alta dimensión porque el número de simples de alta dimensión crece exponencialmente en el tamaño de los datos. En el contexto de la computación cuántica, se ha demostrado previamente que existe un algoritmo cuántico eficiente para estimar los números de Betti incluso en grandes dimensiones. Sin embargo, los números de Betti son menos generales que los números de Betti persistentes, y no ha habido algoritmos cuánticos que puedan estimar los números de Betti persistentes de dimensiones arbitrarias.
Este artículo muestra el primer algoritmo cuántico que puede estimar los números de Betti persistentes ($normalizados$) de dimensiones arbitrarias. Nuestro algoritmo es eficiente para complejos simpliciales como el complejo Vietoris-Rips y demuestra una aceleración exponencial sobre los algoritmos clásicos conocidos.
► datos BibTeX
► referencias
[ 1 ] Mehmet E Aktas, Esra Akbas y Ahmed El Fatmaoui. Persistencia de homología de redes: métodos y aplicaciones. Ciencia de red aplicada, 4 (1): 1–28, 2019. 10.1007/s41109-019-0179-3.
https://doi.org/10.1007/s41109-019-0179-3
[ 2 ] Jonathan Ariel Barmak y Elias Gabriel Minian. Fuertes tipos de homotopía, nervios y colapsos. Geometría discreta y computacional, 47 (2): 301–328, 2012. 10.1007/s00454-011-9357-5.
https://doi.org/10.1007/s00454-011-9357-5
[ 3 ] Andreas Bärtschi y Stephan Eidenbenz. Preparación determinista de los estados de Dicke. En Simposio internacional sobre los fundamentos de la teoría de la computación, páginas 126–139. Springer, 2019. 10.1007/978-3-030-25027-0_9.
https://doi.org/10.1007/978-3-030-25027-0_9
[ 4 ] Gilles Brassard, Peter Hoyer, Michele Mosca y Alain Tapp. Amplificación y estimación de amplitud cuántica. Contemporary Mathematics, 305: 53–74, 2002. 10.1090 / conm / 305/05215.
https: / / doi.org/ 10.1090 / conm / 305/05215
[ 5 ] Peter Bubenik et al. Análisis estadístico de datos topológicos utilizando paisajes de persistencia. J. Mach. Aprender. Res., 16 (1): 77–102, 2015. 10.5555/2789272.2789275.
https: / / doi.org/ 10.5555 / 2789272.2789275
[ 6 ] Frederic Chazal y Bertrand Michel. Una introducción al análisis de datos topológicos: aspectos fundamentales y prácticos para los científicos de datos. Fronteras en inteligencia artificial, 4, 2021. 10.3389/frai.2021.667963.
https://doi.org/10.3389/frai.2021.667963
[ 7 ] Ho Yee Cheung, Tsz Chiu Kwok y Lap Chi Lau. Algoritmos y aplicaciones de rango de matriz rápida. Diario de la ACM (JACM), 60 (5): 1–25, 2013. 10.1145/2528404.
https: / / doi.org/ 10.1145 / 2528404
[ 8 ] David Cohen-Steiner, Herbert Edelsbrunner y John Harer. Estabilidad de los diagramas de persistencia. Geometría discreta y computacional, 37 (1): 103–120, 2007. 10.1007/s00454-006-1276-5.
https://doi.org/10.1007/s00454-006-1276-5
[ 9 ] Alex Cole y Gary Shiu. Análisis de datos topológicos para el paisaje de cuerdas. Journal of High Energy Physics, 2019 (3): 1–31, 2019. 10.1007/JHEP03(2019)054.
https: / / doi.org/ 10.1007 / JHEP03 (2019) 054
[ 10 ] Steven A Cuccaro, Thomas G Draper, Samuel A Kutin y David Petrie Moulton. Un nuevo circuito cuántico de adición de acarreo de ondas. 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
[ 11 ] Edoardo Di Napoli, Eric Polizzi y Yousef Saad. Estimación eficiente de recuentos de valores propios en un intervalo. Álgebra lineal numérica con aplicaciones, 23 (4): 674–692, 2016. 10.1002/nla.2048.
https:///doi.org/10.1002/nla.2048
[ 12 ] Robert H. Dicke. Coherencia en los procesos de radiación espontánea. Revisión física, 93 (1): 99, 1954. 10.1103/PhysRev.93.99.
https: / / doi.org/ 10.1103 / PhysRev.93.99
[ 13 ] Herbert Edelsbrunner y John Harer. Topología computacional: una introducción. Sociedad Matemática Estadounidense, 2010. 10.1007/978-3-540-33259-6_7.
https://doi.org/10.1007/978-3-540-33259-6_7
[ 14 ] Herbert Edelsbrunner, David Letscher y Afra Zomorodian. Persistencia topológica y simplificación. En Actas del 41.er simposio anual sobre fundamentos de la informática, páginas 454–463. IEEE, 2000. 10.1007/s00454-002-2885-2.
https://doi.org/10.1007/s00454-002-2885-2
[ 15 ] Herbert Edelsbrunner, John Harer, et al. Homología persistente: una encuesta. Matemáticas contemporáneas, 453: 257–282, 2008. 10.1090/conm/453/08802.
https: / / doi.org/ 10.1090 / conm / 453/08802
[ 16 ] Joel Friedman. Cálculo de números betti a través de laplacianos combinatorios. Algorithmica, 21 (4): 331–346, 1998. 10.1007/PL00009218.
https: / / doi.org/ 10.1007 / PL00009218
[ 17 ] Roberto Grist. Códigos de barras: la topología persistente de los datos. Boletín de la Sociedad Matemática Estadounidense, 45 (1): 61–75, 2008. 10.1090/S0273-0979-07-01191-3.
https://doi.org/10.1090/S0273-0979-07-01191-3
[ 18 ] András Gilyén, Yuan Su, Guang Hao Low y Nathan Wiebe. Transformación cuántica de valores singulares y más allá: mejoras exponenciales para la aritmética de matrices cuánticas. En Actas del 51° Simposio Anual ACM SIGACT sobre Teoría de la Computación, páginas 193–204, 2019. 10.1145/3313276.3316366.
https: / / doi.org/ 10.1145 / 3313276.3316366
[ 19 ] Sam Gunn y Niels Kornerup. Revisión de un algoritmo cuántico para números betti. preimpresión de arXiv arXiv:1906.07673, 2019. 10.48550/arXiv.1906.07673.
https:///doi.org/10.48550/arXiv.1906.07673
arXiv: 1906.07673
[ 20 ] Aram W Harrow, Avinatan Hassidim y Seth Lloyd. Algoritmo cuántico para sistemas lineales de ecuaciones. Cartas de revisión física, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
[ 21 ] Ryu Hayakawa. Algoritmo cuántico para números betti persistentes y análisis de datos topológicos. preimpresión de arXiv arXiv:2111.00433v1, 2021. 10.48550/arXiv.2111.00433.
https:///doi.org/10.48550/arXiv.2111.00433
arXiv: 2111.00433v1
[ 22 ] Ryu Hayakawa, Tomoyuki Morimae y Suguru Tamaki. Supremacía cuántica de grano fino basada en vectores ortogonales, rutas más cortas de 3 sumas y de todos los pares. Preimpresión de arXiv arXiv:1902.08382, 2019. 10.48550/arXiv.1902.08382.
https:///doi.org/10.48550/arXiv.1902.08382
arXiv: 1902.08382
[ 23 ] Yong He, Ming-Xing Luo, E Zhang, Hong-Ke Wang y Xiao-Feng Wang. Descomposiciones de puertas Toffoli de n-qubit con complejidad de circuito lineal. Revista internacional de física teórica, 56 (7): 2350–2361, 2017. 10.1007/s10773-017-3389-4.
https://doi.org/10.1007/s10773-017-3389-4
[ 24 ] 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 y Jian-Wei Pan. Demostración de análisis de datos topológicos en un procesador cuántico. Óptica, 5 (2): 193–198, 2018. 10.1364/OPTICA.5.000193.
https: / / doi.org/ 10.1364 / OPTICA.5.000193
[ 25 ] Lek-Heng Lim. Laplacianos de Hodge en grafos. Revista SIAM, 62 (3): 685–715, 2020. 10.1137/18M1223101.
https: / / doi.org/ 10.1137 / 18M1223101
[ 26 ] Lin Lin, Yousef Saad y Chao Yang. Aproximación de densidades espectrales de matrices grandes. Revisión SIAM, 58 (1): 34–65, 2016. 10.1137/130934283.
https: / / doi.org/ 10.1137 / 130934283
[ 27 ] Seth Lloyd, Silvano Garnerone y Paolo Zanardi. Algoritmos cuánticos para análisis topológico y geométrico de datos. Comunicaciones de la naturaleza, 7 (1): 1–7, 2016. 10.1038/ncomms10138.
https: / / doi.org/ 10.1038 / ncomms10138
[ 28 ] John M Martyn, Zane M Rossi, Andrew K Tan e Isaac L Chuang. Gran unificación de algoritmos cuánticos. PRX Quantum, 2 (4): 040203, 2021. 10.1103/PRXQuantum.2.040203.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
[ 29 ] RHAJ Meijer. Agrupación mediante homología persistente cuántica. Trabajo de fin de máster, 2019.
[ 30 ] Facundo Mémoli, Zhengchao Wan y Yusu Wang. Laplacianos persistentes: propiedades, algoritmos e implicaciones. SIAM Journal on Mathematics of Data Science, 4 (2): 858–884, 2022. 10.1137/21M1435471.
https: / / doi.org/ 10.1137 / 21M1435471
[ 31 ] Niels Neumann y Sterre den Breeijen. Limitaciones de la agrupación mediante homología cuántica persistente. Preimpresión de arXiv arXiv:1911.10781, 2019. 10.48550/arXiv.1911.10781.
https:///doi.org/10.48550/arXiv.1911.10781
arXiv: 1911.10781
[ 32 ] Nina Otter, Mason A Porter, Ulrike Tillmann, Peter Grindrod y Heather A Harrington. Una hoja de ruta para el cálculo de la homología persistente. EPJ Data Science, 6: 1–38, 2017. 10.1140/epjds/s13688-017-0109-5.
https://doi.org/10.1140/epjds/s13688-017-0109-5
[ 33 ] Pratyush Pranav, Herbert Edelsbrunner, Rien Van de Weygaert, Gert Vegter, Michael Kerber, Bernard JT Jones y Mathijs Wintraecken. La topología de la red cósmica en términos de números betti persistentes. Avisos mensuales de la Royal Astronomical Society, 465 (4): 4281–4310, 2017. 10.1093/mnras/stw2862.
https://doi.org/10.1093/mnras/stw2862
[ 34 ] Chi Seng Pun, Si Xian Lee y Kelin Xia. Aprendizaje automático basado en homología persistente: una encuesta y un estudio comparativo. Revisión de inteligencia artificial, páginas 1–45, 2022. 10.1007/s10462-022-10146-z.
https: / / doi.org/ 10.1007 / s10462-022-10146-z
[ 35 ] Patricio Rall. Algoritmos cuánticos coherentes más rápidos para la estimación de fase, energía y amplitud. Cuántica, 5: 566, 2021. 10.22331/q-2021-10-19-566.
https://doi.org/10.22331/q-2021-10-19-566
[ 36 ] Abu Bakar Siddique, Saadia Farid y Muhammad Tahir. Prueba de biyección para el sistema numérico combinatorio. Preimpresión de arXiv arXiv:1601.05794, 2016. 10.48550/arXiv.1601.05794.
https:///doi.org/10.48550/arXiv.1601.05794
arXiv: 1601.05794
[ 37 ] Daniel Spitz, Jürgen Berges, Markus Oberthaler y Anna Wienhard. Encontrar un comportamiento autosimilar en la dinámica cuántica de muchos cuerpos a través de la homología persistente. 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
[ 38 ] Shashanka Ubaru, Ismail Yunus Akhalwaya, Mark S Squillante, Kenneth L Clarkson y Lior Horesh. Análisis de datos topológicos cuánticos con profundidad lineal y aceleración exponencial. preimpresión de arXiv arXiv:2108.02811, 2021. 10.48550/arXiv.2108.02811.
https:///doi.org/10.48550/arXiv.2108.02811
arXiv: 2108.02811
[ 39 ] Rui Wang, Duc Duy Nguyen y Guo-Wei Wei. Gráfico espectral persistente. Revista internacional de métodos numéricos en ingeniería biomédica, 36 (9): e3376, 2020. 10.1002/cnm.3376.
https:///doi.org/10.1002/cnm.3376
[ 40 ] Larry Wasserman. Análisis de datos topológicos. Revisión anual de estadísticas y su aplicación, 5: 501–532, 2018. 10.1146/annurev-statistics-031017-100045.
https://doi.org/10.1146/annurev-statistics-031017-100045
[ 41 ] Kelin Xia y Guo-Wei Wei. Análisis de homología persistente de estructura, flexibilidad y plegamiento de proteínas. Revista internacional de métodos numéricos en ingeniería biomédica, 30 (8): 814–844, 2014. 10.1002/cnm.2655.
https:///doi.org/10.1002/cnm.2655
[ 42 ] Afra Zomorodian y Gunnar Carlsson. Cálculo de la homología persistente. Geometría discreta y computacional, 33 (2): 249–274, 2005. 10.1007/s00454-004-1146-y.
https: / / doi.org/ 10.1007 / s00454-004-1146-y
Citado por
[1] Alexander Schmidhuber y Seth Lloyd, "Limitaciones teóricas de la complejidad de los algoritmos cuánticos para el análisis de datos topológicos", arXiv: 2209.14286.
[2] Bernardo Ameneyro, Vasileios Maroulas y 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 y Ryan Babbush, “Cuantificación de la ventaja cuántica en el análisis de datos topológicos”, arXiv: 2209.13581.
[4] Iordanis Kerenidis y Anupam Prakash, “Aprendizaje de máquinas cuánticas con estados subespaciales”, arXiv: 2202.00054.
[5] Bernardo Ameneyro, George Siopsis y Vasileios Maroulas, “Quantum Persistent Homology for Time Series”, arXiv: 2211.04465.
[6] Simon Apers, Sayantan Sen y Dániel Szabó, “Un algoritmo clásico (simple) para estimar los números de Betti”, arXiv: 2211.09618.
[7] Sam McArdle, András Gilyén y Mario Berta, “Un algoritmo cuántico simplificado para el análisis de datos topológicos con una cantidad exponencialmente menor de qubits”, arXiv: 2209.12887.
[8] Andrew Vlasic y Anh Pham, "Comprender el mapeo de datos de codificación a través de una implementación del análisis topológico cuántico", arXiv: 2209.10596.
Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2022-12-07 16:42:14). La lista puede estar incompleta ya que no todos los editores proporcionan datos de citas adecuados y completos.
No se pudo recuperar Crossref citado por datos durante el último intento 2022-12-07 16:42:12: No se pudieron obtener los datos citados por 10.22331 / q-2022-12-07-873 de Crossref. Esto es normal si el DOI se registró recientemente.
Este documento se publica en Quantum bajo el Creative Commons Reconocimiento 4.0 Internacional (CC BY 4.0) licencia. Los derechos de autor permanecen con los titulares de derechos de autor originales, como los autores o sus instituciones.
