Yukawa teoreetilise füüsika instituut, Kyoto ülikool, Kitashirakawa Oiwakecho, Sakyoku, Kyoto 606-8502, Jaapan
Kas see artikkel on huvitav või soovite arutada? Scite või jätke SciRate'i kommentaar.
Abstraktne
Topoloogiline andmete analüüs (TDA) on andmeanalüüsi esilekerkiv valdkond. TDA kriitiline samm on püsivate Betti numbrite arvutamine. Olemasolevad klassikalised TDA algoritmid on piiratud, kui tahame õppida kõrgmõõtmelistest topoloogilistest tunnustest, kuna suuremõõtmeliste lihtsuste arv kasvab andmete suuruses eksponentsiaalselt. Kvantarvutuse kontekstis on varem näidatud, et on olemas tõhus kvantalgoritm Betti arvude hindamiseks isegi suurtes mõõtmetes. Kuid Betti arvud on vähem üldised kui püsivad Betti numbrid ja pole olnud kvantalgoritme, mis suudaksid hinnata suvaliste mõõtmetega püsivaid Betti arve.
See artikkel näitab esimest kvantalgoritmi, mis suudab hinnata ($normaliseeritud $) suvaliste mõõtmetega püsivaid Betti arve. Meie algoritm on tõhus lihtsate komplekside jaoks, nagu Vietoris-Ripsi kompleks, ja näitab eksponentsiaalset kiirust võrreldes tuntud klassikaliste algoritmidega.
► BibTeX-i andmed
► Viited
[1] Mehmet E Aktas, Esra Akbas ja Ahmed El Fatmaoui. Võrkude püsivushomoloogia: meetodid ja rakendused. 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 ja Elias Gabriel Minian. Tugevad homotoopiatüübid, närvid ja kollapsid. 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 ja Stephan Eidenbenz. Dike olekute deterministlik ettevalmistamine. In International Symposium on Fundamentals of Computation Theory, lk 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 ja Alain Tapp. Kvantamplituudi võimendamine ja hindamine. Kaasaegne matemaatika, 305: 53–74, 2002. 10.1090/conm/305/05215.
https:///doi.org/10.1090/conm/305/05215
[5] Peter Bubenik jt. Statistiline topoloogiliste andmete analüüs, kasutades püsivusmaastikke. J. Mach. Õppige. Res., 16 (1): 77–102, 2015. 10.5555/2789272.2789275.
https:///doi.org/10.5555/2789272.2789275
[6] Frédéric Chazal ja Bertrand Michel. Sissejuhatus topoloogilise andmeanalüüsi: fundamentaalsed ja praktilised aspektid andmeteadlaste jaoks. Piirid tehisintellektis, 4, 2021. 10.3389/frai.2021.667963.
https:///doi.org/10.3389/frai.2021.667963
[7] Ho Yee Cheung, Tsz Chiu Kwok ja Lap Chi Lau. Kiired maatriksjärjestuse algoritmid ja rakendused. 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 ja John Harer. Püsivusdiagrammide stabiilsus. Diskreetne ja arvutuslik geomeetria, 37 (1): 103–120, 2007. 10.1007/s00454-006-1276-5.
https://doi.org/10.1007/s00454-006-1276-5
[9] Alex Cole ja Gary Shiu. Stringmaastiku topoloogiliste andmete analüüs. 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 ja David Petrie Moulton. Uus kvantpulsatsiooni kandmise liitmisahel. arXiv eeltrükk 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 ja Yousef Saad. Intervalli omaväärtuste loenduste tõhus hindamine. Numbriline lineaaralgebra rakendustega, 23 (4): 674–692, 2016. 10.1002/nla.2048.
https:///doi.org/10.1002/nla.2048
[12] Robert H Dicke. Sidusus spontaansetes kiirgusprotsessides. Physical Review, 93 (1): 99, 1954. 10.1103/PhysRev.93.99.
https:///doi.org/10.1103/PhysRev.93.99
[13] Herbert Edelsbrunner ja John Harer. Arvutuslik topoloogia: sissejuhatus. 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 ja Afra Zomorodian. Topoloogiline püsivus ja lihtsustamine. Väljaandes Proceedings 41st Year Symposium on Foundations of Computer Science, lk 454–463. IEEE, 2000. 10.1007/s00454-002-2885-2.
https://doi.org/10.1007/s00454-002-2885-2
[15] Herbert Edelsbrunner, John Harer jt. Püsiv homoloogia - uuring. Kaasaegne matemaatika, 453: 257–282, 2008. 10.1090/conm/453/08802.
https:///doi.org/10.1090/conm/453/08802
[16] Joel Friedman. Betti-arvude arvutamine kombinatoorsete laplaste abil. Algorithmica, 21 (4): 331–346, 1998. 10.1007/PL00009218.
https:///doi.org/10.1007/PL00009218
[17] Robert Ghrist. Vöötkoodid: andmete püsiv topoloogia. Bulletin of the 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 ja Nathan Wiebe. Kvant-ainsuse väärtuse teisendus ja kaugemalegi: kvantmaatriksi aritmeetika eksponentsiaalsed täiustused. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, lk 193–204, 2019. 10.1145/3313276.3316366.
https:///doi.org/10.1145/3313276.3316366
[19] Sam Gunn ja Niels Kornerup. Betti-arvude kvantalgoritmi ülevaade. arXiv eeltrükk 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 ja Seth Lloyd. Lineaarsete võrrandisüsteemide kvantalgoritm. Physical Review letters, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https:///doi.org/10.1103/PhysRevLett.103.150502
[21] Ryu Hayakawa. Kvantalgoritm püsivate betti-arvude ja topoloogiliste andmete analüüsi jaoks. arXiv eeltrükk 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 ja Suguru Tamaki. Peeneteraline kvantülemus, mis põhineb ortogonaalsetel vektoritel, 3-summalistel ja kõigi paaride lühimatel teedel. arXiv eeltrükk 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 ja Xiao-Feng Wang. Lineaarse ahela keerukusega n-qubit toffoli väravate lagunemised. 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 ja Jian-Wei Pan. Topoloogiliste andmete analüüsi demonstreerimine kvantprotsessoril. 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 graafikutel. SIAM Review, 62 (3): 685–715, 2020. 10.1137/18M1223101.
https:///doi.org/10.1137/18M1223101
[26] Lin Lin, Yousef Saad ja Chao Yang. Suurte maatriksite spektraaltiheduste lähendamine. SIAM ülevaade, 58 (1): 34–65, 2016. 10.1137/130934283.
https:///doi.org/10.1137/130934283
[27] Seth Lloyd, Silvano Garnerone ja Paolo Zanardi. Kvantalgoritmid andmete topoloogiliseks ja geomeetriliseks analüüsiks. Looduskommunikatsioonid, 7 (1): 1–7, 2016. 10.1038/ncomms10138.
https:///doi.org/10.1038/ncomms10138
[28] John M. Martyn, Zane M Rossi, Andrew K Tan ja Isaac L Chuang. Suur kvantalgoritmide ühendamine. PRX Quantum, 2 (4): 040203, 2021. 10.1103 / PRXQuantum.2.040203.
https:///doi.org/10.1103/PRXQuantum.2.040203
[29] RHAJ Meijer. Klasterdamine kvantpüsihomoloogia abil. Magistritöö, 2019. a.
[30] Facundo Mémoli, Zhengchao Wan ja Yusu Wang. Püsivad laplased: omadused, algoritmid ja tagajärjed. SIAM Journal on Mathematics of Data Science, 4 (2): 858–884, 2022. 10.1137/21M1435471.
https:///doi.org/10.1137/21M1435471
[31] Niels Neumann ja Sterre den Breeijen. Kvantpüsivat homoloogiat kasutava klastrite piirangud. arXiv eeltrükk 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 ja Heather A Harrington. Tegevuskava püsiva homoloogia arvutamiseks. 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 ja Mathijs Wintraecken. Kosmilise veebi topoloogia püsivate betti numbrite järgi. Kuningliku astronoomiaühingu igakuised teated, 465 (4): 4281–4310, 2017. 10.1093/mnras/stw2862.
https:///doi.org/10.1093/mnras/stw2862
[34] Chi Seng Pun, Si Xian Lee ja Kelin Xia. Püsihomoloogial põhinev masinõpe: küsitlus ja võrdlev uuring. Tehisintellekti ülevaade, lk 1–45, 2022. 10.1007/s10462-022-10146-z.
https:///doi.org/10.1007/s10462-022-10146-z
[35] Patrick Rall. Kiiremad koherentsed kvantalgoritmid faasi, energia ja amplituudi hindamiseks. 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 ja Muhammad Tahir. Bijektsiooni tõestus kombinatoorsele arvusüsteemile. arXiv eeltrükk 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 ja Anna Wienhard. Sarnase käitumise leidmine kvant-mitmekehade dünaamikas püsiva homoloogia kaudu. 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 ja Lior Horesh. Kvanttopoloogiliste andmete analüüs lineaarse sügavuse ja eksponentsiaalse kiirendusega. arXiv eeltrükk 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 ja Guo-Wei Wei. Püsiv spektraalgraafik. Rahvusvaheline biomeditsiinitehnika numbrimeetodite ajakiri, 36 (9): e3376, 2020. 10.1002/cnm.3376.
https:///doi.org/10.1002/cnm.3376
[40] Larry Wasserman. Topoloogiline andmete analüüs. Statistika ja selle rakendamise aastaülevaade, 5: 501–532, 2018. 10.1146/annurev-statistics-031017-100045.
https:///doi.org/10.1146/annurev-statistics-031017-100045
[41] Kelin Xia ja Guo-Wei Wei. Valgu struktuuri, painduvuse ja voltimise püsiv homoloogiaanalüüs. Rahvusvaheline biomeditsiinitehnika numbrimeetodite ajakiri, 30 (8): 814–844, 2014. 10.1002/cnm.2655.
https:///doi.org/10.1002/cnm.2655
[42] Afra Zomorodian ja Gunnar Carlsson. Püsihomoloogia arvutamine. Discrete & Computational Geometry, 33 (2): 249–274, 2005. 10.1007/s00454-004-1146-y.
https:///doi.org/10.1007/s00454-004-1146-y
Viidatud
[1] Alexander Schmidhuber ja Seth Lloyd, Topoloogiliste andmete analüüsi kvantalgoritmide keerukusteoreetilised piirangud, arXiv: 2209.14286.
[2] Bernardo Ameneyro, Vasileios Maroulas ja 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 ja Ryan Babbush, "Quantifying Quantum Advantage in Topological Data Analysis", arXiv: 2209.13581.
[4] Iordanis Kerenidis ja Anupam Prakash, "Kvantmasinaõpe alamruumi olekutega", arXiv: 2202.00054.
[5] Bernardo Ameneyro, George Siopsis ja Vasileios Maroulas, "Quantum Persistent Homology for Time Series", arXiv: 2211.04465.
[6] Simon Apers, Sayantan Sen ja Dániel Szabó, "(Lihtne) klassikaline algoritm Betti arvude hindamiseks", arXiv: 2211.09618.
[7] Sam McArdle, András Gilyén ja Mario Berta, „Sujuv kvantalgoritm topoloogiliste andmete analüüsiks eksponentsiaalselt vähemate kubitidega” arXiv: 2209.12887.
[8] Andrew Vlasic ja Anh Pham, "Andmete kodeerimise kaardistamise mõistmine kvanttopoloogilise analüüsi rakendamise kaudu". arXiv: 2209.10596.
Ülaltoodud tsitaadid on pärit SAO/NASA KUULUTUSED (viimati edukalt värskendatud 2022-12-07 16:42:14). Loend võib olla puudulik, kuna mitte kõik väljaandjad ei esita sobivaid ja täielikke viiteandmeid.
Ei saanud tuua Ristviide viidatud andmete alusel viimase katse ajal 2022-12-07 16:42:12: 10.22331/q-2022-12-07-873 viidatud andmeid ei saanud Crossrefist tuua. See on normaalne, kui DOI registreeriti hiljuti.
See raamat on avaldatud Quantum all Creative Commons Attribution 4.0 International (CC BY 4.0) litsents. Autoriõigus jääb algsetele autoriõiguste valdajatele, näiteks autoritele või nende institutsioonidele.
