Institutul Yukawa pentru Fizică Teoretică, Universitatea Kyoto, Kitashirakawa Oiwakecho, Sakyoku, Kyoto 606-8502, Japonia
Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.
Abstract
Analiza topologică a datelor (TDA) este un domeniu emergent al analizei datelor. Pasul critic al TDA este calcularea numerelor Betti persistente. Algoritmii clasici existenți pentru TDA sunt limitați dacă dorim să învățăm din caracteristicile topologice de înaltă dimensiune deoarece numărul de simplexuri de înaltă dimensiune crește exponențial în dimensiunea datelor. În contextul calculului cuantic, s-a arătat anterior că există un algoritm cuantic eficient pentru estimarea numerelor Betti chiar și în dimensiuni mari. Cu toate acestea, numerele Betti sunt mai puțin generale decât numerele Betti persistente și nu au existat algoritmi cuantici care să poată estima numerele Betti persistente de dimensiuni arbitrare.
Această lucrare prezintă primul algoritm cuantic care poate estima numerele Betti persistente ($normalizate$) de dimensiuni arbitrare. Algoritmul nostru este eficient pentru complexe simple, cum ar fi complexul Vietoris-Rips și demonstrează o accelerare exponențială față de algoritmii clasici cunoscuți.
► Date BibTeX
► Referințe
[1] Mehmet E Aktas, Esra Akbas și Ahmed El Fatmaoui. Omologia persistenței rețelelor: metode și aplicații. Applied Network Science, 4 (1): 1–28, 2019. 10.1007/s41109-019-0179-3.
https://doi.org/10.1007/s41109-019-0179-3
[2] Jonathan Ariel Barmak și Elias Gabriel Minian. Tipuri puternice de homotopie, nervi și colapsuri. Discrete & Computational Geometry, 47 (2): 301–328, 2012. 10.1007/s00454-011-9357-5.
https://doi.org/10.1007/s00454-011-9357-5
[3] Andreas Bärtschi și Stephan Eidenbenz. Pregătirea deterministă a stărilor Dicke. În Simpozionul Internațional privind Fundamentele Teoriei Calculului, paginile 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 și Alain Tapp. Amplificarea și estimarea amplitudinii cuantice. Contemporary Mathematics, 305: 53–74, 2002. 10.1090/conm/305/05215.
https: / / doi.org/ 10.1090 / conm / 305/05215
[5] Peter Bubenik și colab. Analiza statistică a datelor topologice folosind peisaje de persistență. J. Mach. Învăța. Res., 16 (1): 77–102, 2015. 10.5555/2789272.2789275.
https: / / doi.org/ 10.5555 / 2789272.2789275
[6] Frédéric Chazal și Bertrand Michel. O introducere în analiza topologică a datelor: aspecte fundamentale și practice pentru oamenii de știință ai datelor. Frontiers in artificial intelligence, 4, 2021. 10.3389/frai.2021.667963.
https:///doi.org/10.3389/frai.2021.667963
[7] Ho Yee Cheung, Tsz Chiu Kwok și Lap Chi Lau. Algoritmi și aplicații rapide de rang matrice. Journal of the ACM (JACM), 60 (5): 1–25, 2013. 10.1145/2528404.
https: / / doi.org/ 10.1145 / 2528404
[8] David Cohen-Steiner, Herbert Edelsbrunner și John Harer. Stabilitatea diagramelor de persistență. Geometrie discretă și computațională, 37 (1): 103–120, 2007. 10.1007/s00454-006-1276-5.
https://doi.org/10.1007/s00454-006-1276-5
[9] Alex Cole și Gary Shiu. Analiza topologică a datelor pentru peisajul șirurilor. 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 și David Petrie Moulton. Un nou circuit cuantic de adăugare a ondulației. 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 și Yousef Saad. Estimarea eficientă a numărului de valori proprii într-un interval. Numerical Linear Algebra with Applications, 23 (4): 674–692, 2016. 10.1002/nla.2048.
https:///doi.org/10.1002/nla.2048
[12] Robert H Dicke. Coerența în procesele de radiații spontane. Revizuire fizică, 93 (1): 99, 1954. 10.1103/PhysRev.93.99.
https: / / doi.org/ 10.1103 / PhysRev.93.99
[13] Herbert Edelsbrunner și John Harer. Topologie computațională: o introducere. American Mathematical Soc., 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 și Afra Zomorodian. Persistență și simplificare topologică. În Proceedings, cel de-al 41-lea simpozion anual despre fundamentele informaticii, paginile 454–463. IEEE, 2000. 10.1007/s00454-002-2885-2.
https://doi.org/10.1007/s00454-002-2885-2
[15] Herbert Edelsbrunner, John Harer și colab. Omologie persistentă-un sondaj. Matematică contemporană, 453: 257–282, 2008. 10.1090/conm/453/08802.
https: / / doi.org/ 10.1090 / conm / 453/08802
[16] Joel Friedman. Calcularea numerelor betti prin laplacieni combinatori. Algorithmica, 21 (4): 331–346, 1998. 10.1007/PL00009218.
https:///doi.org/10.1007/PL00009218
[17] Robert Ghrist. Codurile de bare: topologia persistentă a datelor. Buletinul Societății Americane de Matematică, 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 și Nathan Wiebe. Transformarea valorii singulare cuantice și nu numai: îmbunătățiri exponențiale pentru aritmetica matricei cuantice. În Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, paginile 193–204, 2019. 10.1145/3313276.3316366.
https: / / doi.org/ 10.1145 / 3313276.3316366
[19] Sam Gunn și Niels Kornerup. Revizuirea unui algoritm cuantic pentru numerele betti. arXiv preprint 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 și Seth Lloyd. Algoritm cuantic pentru sisteme liniare de ecuații. Scrisori de revizuire fizică, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
[21] Ryu Hayakawa. Algoritm cuantic pentru numere betti persistente și analiza datelor topologice. arXiv preprint 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 și Suguru Tamaki. Supremație cuantică fină bazată pe vectori ortogonali, cele mai scurte căi de 3 sume și toate perechile. arXiv preprint 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 și Xiao-Feng Wang. Descompuneri de porți toffoli de n-qubit cu complexitate de circuit liniar. Jurnalul Internațional de Fizică Teoretică, 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 și Jian-Wei Pan. Demonstrarea analizei datelor topologice pe un procesor cuantic. Optica, 5 (2): 193–198, 2018. 10.1364/OPTICA.5.000193.
https: / / doi.org/ 10.1364 / OPTICA.5.000193
[25] Lek-Heng Lim. Hodge laplaciani pe grafice. SIAM Review, 62 (3): 685–715, 2020. 10.1137/18M1223101.
https: / / doi.org/ 10.1137 / 18M1223101
[26] Lin Lin, Yousef Saad și Chao Yang. Aproximarea densităților spectrale ale matricilor mari. Revizuirea SIAM, 58 (1): 34–65, 2016. 10.1137/130934283.
https: / / doi.org/ 10.1137 / 130934283
[27] Seth Lloyd, Silvano Garnerone și Paolo Zanardi. Algoritmi cuantici pentru analiza topologică și geometrică a datelor. Nature communications, 7 (1): 1–7, 2016. 10.1038/ncomms10138.
https: / / doi.org/ 10.1038 / ncomms10138
[28] John M Martyn, Zane M Rossi, Andrew K Tan și Isaac L Chuang. Marea unificare a algoritmilor cuantici. PRX Quantum, 2 (4): 040203, 2021. 10.1103/PRXQuantum.2.040203.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
[29] RHAJ Meijer. Clustering folosind omologie persistentă cuantică. Teză de master, 2019.
[30] Facundo Mémoli, Zhengchao Wan și Yusu Wang. Laplacieni persistenti: proprietăți, algoritmi și implicații. SIAM Journal on Mathematics of Data Science, 4 (2): 858–884, 2022. 10.1137/21M1435471.
https: / / doi.org/ 10.1137 / 21M1435471
[31] Niels Neumann și Sterre den Breeijen. Limitările grupării utilizând omologie persistentă cuantică. arXiv preprint 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 și Heather A Harrington. O foaie de parcurs pentru calculul omologiei 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 și Mathijs Wintraecken. Topologia rețelei cosmice în termeni de numere betti persistente. Monthly Notices of the 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 și Kelin Xia. Învățare automată bazată pe omologie persistentă: un sondaj și un studiu comparativ. Artificial Intelligence Review, paginile 1–45, 2022. 10.1007/s10462-022-10146-z.
https: / / doi.org/ 10.1007 / s10462-022-10146-z
[35] Patrick Rall. Algoritmi cuantici coerenți mai rapidi pentru estimarea fazei, energiei și amplitudinii. Quantum, 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 și Muhammad Tahir. Dovada bijecției pentru sistemul de numere combinatoriu. arXiv preprint 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 și Anna Wienhard. Găsirea unui comportament auto-similar în dinamica cuantică a mai multor corpuri prin omologie persistentă. 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 și Lior Horesh. Analiza datelor topologice cuantice cu adâncime liniară și accelerare exponențială. arXiv preprint 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 și Guo-Wei Wei. Graficul spectral persistent. Jurnal internațional pentru metode numerice în inginerie biomedicală, 36 (9): e3376, 2020. 10.1002/cnm.3376.
https:///doi.org/10.1002/cnm.3376
[40] Larry Wasserman. Analiza datelor topologice. Anual Review of Statistics and Its Application, 5: 501–532, 2018. 10.1146/annurev-statistics-031017-100045.
https:///doi.org/10.1146/annurev-statistics-031017-100045
[41] Kelin Xia și Guo-Wei Wei. Analiza omologie persistentă a structurii proteinei, flexibilității și plierii. Jurnal internațional pentru metode numerice în inginerie biomedicală, 30 (8): 814–844, 2014. 10.1002/cnm.2655.
https:///doi.org/10.1002/cnm.2655
[42] Afra Zomorodian și Gunnar Carlsson. Calcularea omologiei persistente. Discrete & Computational Geometry, 33 (2): 249–274, 2005. 10.1007/s00454-004-1146-y.
https: / / doi.org/ 10.1007 / s00454-004-1146-y
Citat de
[1] Alexander Schmidhuber și Seth Lloyd, „Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis”, arXiv: 2209.14286.
[2] Bernardo Ameneyro, Vasileios Maroulas și 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 și Ryan Babbush, „Quantifying Quantum Advantage in Topological Data Analysis”, arXiv: 2209.13581.
[4] Iordanis Kerenidis și Anupam Prakash, „Învățare automată cuantică cu stări subspațiale”, arXiv: 2202.00054.
[5] Bernardo Ameneyro, George Siopsis și Vasileios Maroulas, „Quantum Persistent Homology for Time Series”, arXiv: 2211.04465.
[6] Simon Apers, Sayantan Sen și Dániel Szabó, „A (simple) classical algorithm for estimating Betti numbers”, arXiv: 2211.09618.
[7] Sam McArdle, András Gilyén și Mario Berta, „Un algoritm cuantic simplificat pentru analiza datelor topologice cu exponențial mai puțini qubiți”, arXiv: 2209.12887.
[8] Andrew Vlasic și Anh Pham, „Înțelegerea cartografierii datelor de codificare printr-o implementare a analizei topologice cuantice”, arXiv: 2209.10596.
Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2022-12-07 16:42:14). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.
Nu a putut să aducă Date citate încrucișate în ultima încercare 2022-12-07 16:42:12: Nu s-au putut prelua date citate pentru 10.22331 / q-2022-12-07-873 de la Crossref. Acest lucru este normal dacă DOI a fost înregistrat recent.
Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.
