Yukawa Instituut voor Theoretische Fysica, Kyoto University, Kitashirakawa Oiwakecho, Sakyoku, Kyoto 606-8502, Japan
Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.
Abstract
Topologische data-analyse (TDA) is een opkomend gebied van data-analyse. De kritieke stap van TDA is het berekenen van de persistente Betti-nummers. Bestaande klassieke algoritmen voor TDA zijn beperkt als we willen leren van hoog-dimensionale topologische kenmerken omdat het aantal hoog-dimensionale simplices exponentieel groeit in de omvang van de data. In de context van kwantumberekening is eerder aangetoond dat er een efficiënt kwantumalgoritme bestaat voor het schatten van de Betti-getallen, zelfs in hoge dimensies. De Betti-getallen zijn echter minder algemeen dan de persistente Betti-getallen, en er zijn geen kwantumalgoritmen die de persistente Betti-getallen van willekeurige dimensies kunnen schatten.
Dit artikel toont het eerste kwantumalgoritme dat de ($genormaliseerde$) persistente Betti-getallen van willekeurige dimensies kan schatten. Ons algoritme is efficiënt voor simpliciale complexen zoals het Vietoris-Rips-complex en demonstreert exponentiële versnelling ten opzichte van de bekende klassieke algoritmen.
► BibTeX-gegevens
► Referenties
[1] Mehmet E Aktas, Esra Akbas en Ahmed El Fatmaoui. Persistentiehomologie van netwerken: methoden en toepassingen. Toegepaste netwerkwetenschap, 4 (1): 1–28, 2019. 10.1007/s41109-019-0179-3.
https://doi.org/10.1007/s41109-019-0179-3
[2] Jonathan Ariel Barmak en Elias Gabriel Minian. Sterke homotopietypes, zenuwen en instortingen. Discrete en computationele geometrie, 47 (2): 301–328, 2012. 10.1007/s00454-011-9357-5.
https://doi.org/10.1007/s00454-011-9357-5
[3] Andreas Bärtschi en Stephan Eidenbenz. Deterministische voorbereiding van dicke-toestanden. In International Symposium on Fundamentals of Computation Theory, pagina's 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 en Alain Tapp. Kwantumamplitude versterking en schatting. Hedendaagse wiskunde, 305: 53–74, 2002. 10.1090 / conm / 305/05215.
https: / / doi.org/ 10.1090 / conm / 305 / 05215
[5] Peter Bubenik et al. Statistische topologische gegevensanalyse met behulp van persistentielandschappen. J Mach. Leren. Res., 16 (1): 77–102, 2015. 10.5555/2789272.2789275.
https: / / doi.org/ 10.5555 / 2789272.2789275
[6] Frédéric Chazal en Bertrand Michel. Een inleiding tot topologische data-analyse: fundamentele en praktische aspecten voor datawetenschappers. Grenzen in kunstmatige intelligentie, 4, 2021. 10.3389/frai.2021.667963.
https:///doi.org/10.3389/frai.2021.667963
[7] Ho Yee Cheung, Tsz Chiu Kwok en Lap Chi Lau. Snelle matrixrangalgoritmen en toepassingen. Publicatieblad van de ACM (JACM), 60 (5): 1–25, 2013. 10.1145/2528404.
https: / / doi.org/ 10.1145 / 2528404
[8] David Cohen-Steiner, Herbert Edelsbrunner en John Harer. Stabiliteit van persistentiediagrammen. Discrete & computationele geometrie, 37 (1): 103–120, 2007. 10.1007/s00454-006-1276-5.
https://doi.org/10.1007/s00454-006-1276-5
[9] Alex Cole en Gary Shiu. Topologische data-analyse voor het stringlandschap. 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 en David Petrie Moulton. Een nieuw quantum ripple-carry additiecircuit. 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 en Yousef Saad. Efficiënte schatting van eigenwaardetellingen in een interval. Numerieke lineaire algebra met toepassingen, 23 (4): 674–692, 2016. 10.1002/nla.2048.
https:///doi.org/10.1002/nla.2048
[12] Robert H Dicke. Samenhang in spontane stralingsprocessen. Fysieke beoordeling, 93 (1): 99, 1954. 10.1103/PhysRev.93.99.
https: / / doi.org/ 10.1103 / PhysRev.93.99
[13] Herbert Edelsbrunner en John Harer. Computationele topologie: een introductie. 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 en Afra Zomorodian. Topologische persistentie en vereenvoudiging. In Proceedings 41e jaarlijkse symposium over de grondslagen van de informatica, pagina's 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. Aanhoudende homologie - een onderzoek. Hedendaagse wiskunde, 453: 257–282, 2008. 10.1090/conm/453/08802.
https: / / doi.org/ 10.1090 / conm / 453 / 08802
[16] Joël Friedman. Betti-getallen berekenen via combinatorische laplacians. Algorithmica, 21 (4): 331-346, 1998. 10.1007/PL00009218.
https: / / doi.org/ 10.1007 / PL00009218
[17] Robert Grist. Barcodes: de persistente topologie van data. Bulletin van de 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
[18] András Gilyén, Yuan Su, Guang Hao Low en Nathan Wiebe. Quantum singuliere waardetransformatie en verder: exponentiële verbeteringen voor kwantummatrixberekeningen. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pagina's 193–204, 2019. 10.1145/3313276.3316366.
https: / / doi.org/ 10.1145 / 3313276.3316366
[19] Sam Gunn en Niels Kornerup. Herziening van een kwantumalgoritme voor betti-getallen. arXiv voordruk 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 en Seth Lloyd. Kwantumalgoritme voor lineaire stelsels van vergelijkingen. Fysieke beoordelingsbrieven, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
[21] Ryu Hayakawa. Kwantumalgoritme voor persistente betti-getallen en topologische data-analyse. arXiv voordruk 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 en Suguru Tamaki. Fijnmazige kwantumsuprematie op basis van orthogonale vectoren, 3-som en alle paren kortste paden. arXiv voordruk 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 en Xiao-Feng Wang. Ontledingen van n-qubit toffoli-poorten met lineaire circuitcomplexiteit. International Journal of Theoretical Physics, 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 en Jian-Wei Pan. Demonstratie van topologische data-analyse op een kwantumprocessor. Optica, 5 (2): 193–198, 2018. 10.1364/OPTICA.5.000193.
https: / / doi.org/ 10.1364 / OPTICA.5.000193
[25] Lek-Heng Lim. Hodge laplacians op grafieken. SIAM Review, 62 (3): 685–715, 2020. 10.1137/18M1223101.
https: / / doi.org/ 10.1137 / 18M1223101
[26] Lin Lin, Yousef Saad en Chao Yang. Benadering van spectrale dichtheden van grote matrices. SIAM recensie, 58 (1): 34–65, 2016. 10.1137/130934283.
https: / / doi.org/ 10.1137 / 130934283
[27] Seth Lloyd, Silvano Garnerone en Paolo Zanardi. Kwantumalgoritmen voor topologische en geometrische analyse van gegevens. Natuurcommunicatie, 7 (1): 1–7, 2016. 10.1038/ncomms10138.
https: / / doi.org/ 10.1038 / ncomms10138
[28] John M Martyn, Zane M Rossi, Andrew K Tan en Isaac L Chuang. Grote unificatie van kwantumalgoritmen. PRX Quantum, 2 (4): 040203, 2021. 10.1103/PRXQuantum.2.040203.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
[29] RHAJ Meijer. Clustering met behulp van kwantumpersistente homologie. Masterscriptie, 2019.
[30] Facundo Mémoli, Zhengchao Wan en Yusu Wang. Aanhoudende laplacians: eigenschappen, algoritmen en implicaties. SIAM Journal on Mathematics of Data Science, 4 (2): 858–884, 2022. 10.1137/21M1435471.
https: / / doi.org/ 10.1137 / 21M1435471
[31] Niels Neumann en Sterre den Breeijen. Beperkingen van clustering met behulp van kwantumpersistente homologie. arXiv voordruk 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 en Heather A Harrington. Een stappenplan voor de berekening van persistente homologie. 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 en Mathijs Wintraecken. De topologie van het kosmische web in termen van aanhoudende betti-getallen. 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 en Kelin Xia. Persistent-homology-based machine learning: een enquête en een vergelijkende studie. Beoordeling kunstmatige intelligentie, pagina's 1-45, 2022. 10.1007/s10462-022-10146-z.
https: / / doi.org/ 10.1007 / s10462-022-10146-z
[35] Patrick Raall. Snellere coherente kwantumalgoritmen voor fase-, energie- en amplitudeschatting. 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 en Mohammed Tahir. Bewijs van bijectie voor combinatorisch getallenstelsel. arXiv voordruk 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 en Anna Wienhard. Het vinden van zelfgelijkend gedrag in de kwantumdynamica van veel lichamen via aanhoudende homologie. 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 en Lior Horesh. Kwantumtopologische gegevensanalyse met lineaire diepte en exponentiële versnelling. arXiv voordruk 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 en Guo-Wei Wei. Aanhoudende spectrale grafiek. Internationaal tijdschrift voor numerieke methoden in biomedische technologie, 36 (9): e3376, 2020. 10.1002/cnm.3376.
https:///doi.org/10.1002/cnm.3376
[40] Larry Wasserman. Topologische gegevensanalyse. Jaaroverzicht van statistieken en de toepassing ervan, 5: 501–532, 2018. 10.1146/annurev-statistics-031017-100045.
https:///doi.org/10.1146/annurev-statistics-031017-100045
[41] Kelin Xia en Guo-Wei Wei. Aanhoudende homologieanalyse van eiwitstructuur, flexibiliteit en vouwing. Internationaal tijdschrift voor numerieke methoden in biomedische technologie, 30 (8): 814–844, 2014. 10.1002/cnm.2655.
https:///doi.org/10.1002/cnm.2655
[42] Afra Zomorodian en Gunnar Carlsson. Persistente homologie berekenen. Discrete en computationele meetkunde, 33 (2): 249–274, 2005. 10.1007/s00454-004-1146-y.
https: / / doi.org/ 10.1007 / s00454-004-1146-y
Geciteerd door
[1] Alexander Schmidhuber en Seth Lloyd, "Complexiteitstheoretische beperkingen op kwantumalgoritmen voor topologische gegevensanalyse", arXiv: 2209.14286.
[2] Bernardo Ameneyro, Vasileios Maroulas en 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 en Ryan Babbush, "Kwantumvoordeel in topologische gegevensanalyse kwantificeren", arXiv: 2209.13581.
[4] Iordanis Kerenidis en Anupam Prakash, “Kwantummachine learning met subruimtetoestanden”, arXiv: 2202.00054.
[5] Bernardo Ameneyro, George Siopsis en Vasileios Maroulas, "Quantum Persistent Homology for Time Series", arXiv: 2211.04465.
[6] Simon Apers, Sayantan Sen en Dániel Szabó, "Een (eenvoudig) klassiek algoritme voor het schatten van Betti-getallen", arXiv: 2211.09618.
[7] Sam McArdle, András Gilyén en Mario Berta, "Een gestroomlijnd kwantumalgoritme voor topologische gegevensanalyse met exponentieel minder qubits", arXiv: 2209.12887.
[8] Andrew Vlasic en Anh Pham, "Inzicht in het in kaart brengen van gecodeerde gegevens door middel van een implementatie van kwantumtopologische analyse", arXiv: 2209.10596.
Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2022-12-07 16:42:14). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.
Kon niet ophalen Door Crossref geciteerde gegevens tijdens laatste poging 2022-12-07 16:42:12: kon niet geciteerde gegevens voor 10.22331 / q-2022-12-07-873 niet ophalen van Crossref. Dit is normaal als de DOI recent is geregistreerd.
Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.
