Yukawa Institute for Theoretical Physics, Kyoto University, Kitashirakawa Oiwakecho, Sakyoku, Kyoto 606-8502, Japan
Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.
Abstrakt
Topologisk dataanalys (TDA) är ett framväxande område för dataanalys. Det kritiska steget i TDA är att beräkna de bestående Betti-talen. Befintliga klassiska algoritmer för TDA är begränsade om vi vill lära av högdimensionella topologiska egenskaper eftersom antalet högdimensionella förenklingar växer exponentiellt i storleken på datan. I samband med kvantberäkning har det tidigare visats att det finns en effektiv kvantalgoritm för att uppskatta Betti-talen även i höga dimensioner. Betti-talen är dock mindre generella än de beständiga Betti-talen, och det har inte funnits några kvantalgoritmer som kan uppskatta de beständiga Betti-talen av godtyckliga dimensioner.
Detta dokument visar den första kvantalgoritmen som kan uppskatta de ($normaliserade$) bestående Betti-talen av godtyckliga dimensioner. Vår algoritm är effektiv för enkla komplex som Vietoris-Rips-komplexet och visar exponentiell snabbhet jämfört med de kända klassiska algoritmerna.
► BibTeX-data
► Referenser
[1] Mehmet E Aktas, Esra Akbas och Ahmed El Fatmaoui. Persistenshomologi av nätverk: metoder och tillämpningar. 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 och Elias Gabriel Minian. Starka homotopityper, nerver och kollapser. 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 och Stephan Eidenbenz. Deterministisk beredning av dicke-tillstånd. I International Symposium on Fundamentals of Computation Theory, sidorna 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 och Alain Tapp. Kvant amplitudförstärkning och uppskattning. Modern matematik, 305: 53–74, 2002. 10.1090 / conm / 305/05215.
https: / / doi.org/ 10.1090 / conm / 305 / 05215
[5] Peter Bubenik et al. Statistisk topologisk dataanalys med beständighetslandskap. J. Mach. Lära sig. Res., 16 (1): 77–102, 2015. 10.5555/2789272.2789275.
https: / / doi.org/ 10.5555 / 2789272.2789275
[6] Frédéric Chazal och Bertrand Michel. En introduktion till topologisk dataanalys: grundläggande och praktiska aspekter för datavetare. Frontiers in artificiell intelligens, 4, 2021. 10.3389/frai.2021.667963.
https:///doi.org/10.3389/frai.2021.667963
[7] Ho Yee Cheung, Tsz Chiu Kwok och Lap Chi Lau. Snabbmatrisrankningsalgoritmer och applikationer. 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 och John Harer. Stabilitet av persistensdiagram. Diskret & beräkningsgeometri, 37 (1): 103–120, 2007. 10.1007/s00454-006-1276-5.
https://doi.org/10.1007/s00454-006-1276-5
[9] Alex Cole och Gary Shiu. Topologisk dataanalys för stränglandskapet. 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 och David Petrie Moulton. En ny quantum ripple-carry additionskrets. arXiv preprint quant-ph/0410184, 2004. 10.48550/arXiv.quant-ph/0410184.
https:///doi.org/10.48550/arXiv.quant-ph/0410184
arXiv: kvant-ph / 0410184
[11] Edoardo Di Napoli, Eric Polizzi och Yousef Saad. Effektiv uppskattning av egenvärdesräkningar i ett intervall. Numerisk linjär algebra med tillämpningar, 23 (4): 674–692, 2016. 10.1002/nla.2048.
https:///doi.org/10.1002/nla.2048
[12] Robert H Dicke. Koherens i spontana strålningsprocesser. Physical review, 93 (1): 99, 1954. 10.1103/PhysRev.93.99.
https: / / doi.org/ 10.1103 / PhysRev.93.99
[13] Herbert Edelsbrunner och John Harer. Beräkningstopologi: en introduktion. 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 och Afra Zomorodian. Topologisk persistens och förenkling. I Proceedings 41:a årliga symposiet om grunderna för datavetenskap, sidorna 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. Ihållande homologi - en undersökning. Samtida matematik, 453: 257–282, 2008. 10.1090/conm/453/08802.
https: / / doi.org/ 10.1090 / conm / 453 / 08802
[16] Joel Friedman. Beräknar betti-tal via kombinatoriska laplacians. Algorithmica, 21 (4): 331–346, 1998. 10.1007/PL00009218.
https: / / doi.org/ 10.1007 / PL00009218
[17] Robert Ghrist. Streckkoder: datas ihållande topologi. 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 och Nathan Wiebe. Kvantsingular värdetransformation och bortom: exponentiella förbättringar för kvantmatrisaritmetik. I Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, sidorna 193–204, 2019. 10.1145/3313276.3316366.
https: / / doi.org/ 10.1145 / 3313276.3316366
[19] Sam Gunn och Niels Kornerup. Granskning av en kvantalgoritm för bettital. 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 och Seth Lloyd. Kvantalgoritm för linjära ekvationssystem. Physical review letters, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
[21] Ryu Hayakawa. Kvantalgoritm för ihållande betti-tal och topologisk dataanalys. 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 och Suguru Tamaki. Finkornig kvantöverlägsenhet baserat på ortogonala vektorer, 3-summor och alla pars kortaste vägar. 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 och Xiao-Feng Wang. Nedbrytningar av n-qubit toffoli-grindar med linjär kretskomplexitet. 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 och Jian-Wei Pan. Demonstration av topologisk dataanalys på en kvantprocessor. 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 på grafer. SIAM Review, 62 (3): 685–715, 2020. 10.1137/18M1223101.
https: / / doi.org/ 10.1137 / 18M1223101
[26] Lin Lin, Yousef Saad och Chao Yang. Ungefärlig spektraldensitet för stora matriser. SIAM recension, 58 (1): 34–65, 2016. 10.1137/130934283.
https: / / doi.org/ 10.1137 / 130934283
[27] Seth Lloyd, Silvano Garnerone och Paolo Zanardi. Kvantalgoritmer för topologisk och geometrisk analys av data. Naturkommunikation, 7 (1): 1–7, 2016. 10.1038/ncomms10138.
https: / / doi.org/ 10.1038 / ncomms10138
[28] John M Martyn, Zane M Rossi, Andrew K Tan och Isaac L Chuang. Stor förening av kvantalgoritmer. PRX Quantum, 2 (4): 040203, 2021. 10.1103/PRXQuantum.2.040203.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
[29] RHAJ Meijer. Klustring med hjälp av kvantbeständig homologi. Magisteruppsats, 2019.
[30] Facundo Mémoli, Zhengchao Wan och Yusu Wang. Ihållande laplacians: egenskaper, algoritmer och implikationer. SIAM Journal on Mathematics of Data Science, 4 (2): 858–884, 2022. 10.1137/21M1435471.
https: / / doi.org/ 10.1137 / 21M1435471
[31] Niels Neumann och Sterre den Breeijen. Begränsningar av klustring med användning av kvantbeständig homologi. 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 och Heather A Harrington. En färdplan för beräkning av ihållande homologi. 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 och Mathijs Wintraecken. Topologin av den kosmiska webben i termer av ihållande betti-tal. 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 och Kelin Xia. Persistent-homologi-baserad maskininlärning: en undersökning och en jämförande studie. Artificial Intelligence Review, sidorna 1–45, 2022. 10.1007/s10462-022-10146-z.
https: / / doi.org/ 10.1007 / s10462-022-10146-z
[35] Patrick Rall. Snabbare koherenta kvantalgoritmer för fas-, energi- och amplituduppskattning. 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 och Muhammad Tahir. Bevis på bijektion för kombinatoriskt talsystem. 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 och Anna Wienhard. Att hitta självliknande beteende i kvantmångakroppsdynamik via ihållande homologi. 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 och Lior Horesh. Kvanttopologisk dataanalys med linjärt djup och exponentiell hastighet. 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 och Guo-Wei Wei. Ihållande spektralgraf. International journal for numerical methods in biomedical engineering, 36 (9): e3376, 2020. 10.1002/cnm.3376.
https:///doi.org/10.1002/cnm.3376
[40] Larry Wasserman. Topologisk dataanalys. Annual 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 och Guo-Wei Wei. Ihållande homologianalys av proteinstruktur, flexibilitet och veckning. International journal for numerical methods in biomedical engineering, 30 (8): 814–844, 2014. 10.1002/cnm.2655.
https:///doi.org/10.1002/cnm.2655
[42] Afra Zomorodian och Gunnar Carlsson. Beräkning av ihållande homologi. Discrete & Computational Geometry, 33 (2): 249–274, 2005. 10.1007/s00454-004-1146-y.
https: / / doi.org/ 10.1007 / s00454-004-1146-y
Citerad av
[1] Alexander Schmidhuber och Seth Lloyd, "Komplexitetsteoretiska begränsningar på kvantalgoritmer för topologisk dataanalys", arXiv: 2209.14286.
[2] Bernardo Ameneyro, Vasileios Maroulas och 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 och Ryan Babbush, "Quantifying Quantum Advantage in Topological Data Analysis", arXiv: 2209.13581.
[4] Iordanis Kerenidis och Anupam Prakash, "Quantum machine learning with subspace states", arXiv: 2202.00054.
[5] Bernardo Ameneyro, George Siopsis och Vasileios Maroulas, "Quantum Persistent Homology for Time Series", arXiv: 2211.04465.
[6] Simon Apers, Sayantan Sen och Dániel Szabó, "En (enkel) klassisk algoritm för att uppskatta Betti-tal", arXiv: 2211.09618.
[7] Sam McArdle, András Gilyén och Mario Berta, "En strömlinjeformad kvantalgoritm för topologisk dataanalys med exponentiellt färre kvantbitar", arXiv: 2209.12887.
[8] Andrew Vlasic och Anh Pham, "Förstå kartläggningen av kodningsdata genom en implementering av kvanttopologisk analys", arXiv: 2209.10596.
Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2022-12-07 16:42:14). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.
Det gick inte att hämta Crossref citerade data under senaste försöket 2022-12-07 16:42:12: Det gick inte att hämta citerade data för 10.22331 / q-2022-12-07-873 från Crossref. Detta är normalt om DOI registrerades nyligen.
Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.
