Yukawa Institut for Teoretisk Fysik, Kyoto Universitet, Kitashirakawa Oiwakecho, Sakyoku, Kyoto 606-8502, Japan
Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.
Abstrakt
Topologisk dataanalyse (TDA) er et fremvoksende felt inden for dataanalyse. Det kritiske trin i TDA er at beregne de vedvarende Betti-tal. Eksisterende klassiske algoritmer for TDA er begrænsede, hvis vi ønsker at lære af højdimensionelle topologiske træk, fordi antallet af højdimensionelle simplicer vokser eksponentielt i størrelsen af dataene. I forbindelse med kvanteberegning er det tidligere blevet vist, at der eksisterer en effektiv kvantealgoritme til at estimere Betti-tallene selv i høje dimensioner. Imidlertid er Betti-tallene mindre generelle end de vedvarende Betti-tal, og der har ikke været nogen kvantealgoritmer, der kan estimere de vedvarende Betti-tal af vilkårlige dimensioner.
Dette papir viser den første kvantealgoritme, der kan estimere de ($normaliserede$) vedvarende Betti-tal af vilkårlige dimensioner. Vores algoritme er effektiv til simple komplekser såsom Vietoris-Rips-komplekset og demonstrerer eksponentiel speedup i forhold til de kendte klassiske algoritmer.
► BibTeX-data
► Referencer
[1] Mehmet E Aktas, Esra Akbas og Ahmed El Fatmaoui. Persistenshomologi af netværk: metoder og applikationer. 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 og Elias Gabriel Minian. Stærke homotopityper, nerver og kollaps. 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 og Stephan Eidenbenz. Deterministisk forberedelse af dicke-tilstande. I International Symposium on Fundamentals of Computation Theory, side 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 og Alain Tapp. Kvanteamplitudeforstærkning og estimering. Contemporary Mathematics, 305: 53–74, 2002. 10.1090/conm/305/05215.
https:///doi.org/10.1090/conm/305/05215
[5] Peter Bubenik et al. Statistisk topologisk dataanalyse ved brug af persistenslandskaber. J. Mach. Lære. Res., 16 (1): 77-102, 2015. 10.5555/2789272.2789275.
https:///doi.org/10.5555/2789272.2789275
[6] Frédéric Chazal og Bertrand Michel. En introduktion til topologisk dataanalyse: grundlæggende og praktiske aspekter for dataforskere. 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 og Lap Chi Lau. Hurtig matrix rang algoritmer og 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 og John Harer. Stabilitet af persistensdiagrammer. Diskret og beregningsgeometri, 37 (1): 103-120, 2007. 10.1007/s00454-006-1276-5.
https://doi.org/10.1007/s00454-006-1276-5
[9] Alex Cole og Gary Shiu. Topologisk dataanalyse for strenglandskabet. 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 og David Petrie Moulton. Et nyt quantum ripple-carry additionskredsløb. 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 og Yousef Saad. Effektiv estimering af egenværditællinger i et interval. Numerisk lineær algebra med applikationer, 23 (4): 674–692, 2016. 10.1002/nla.2048.
https:///doi.org/10.1002/nla.2048
[12] Robert H Dicke. Sammenhæng i spontane strålingsprocesser. Physical review, 93 (1): 99, 1954. 10.1103/PhysRev.93.99.
https:///doi.org/10.1103/PhysRev.93.99
[13] Herbert Edelsbrunner og John Harer. Beregningstopologi: 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 og Afra Zomorodian. Topologisk persistens og forenkling. I Proceedings 41. årlige symposium om grundlaget for datalogi, side 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. Vedvarende homologi - en undersøgelse. Moderne matematik, 453: 257–282, 2008. 10.1090/conm/453/08802.
https:///doi.org/10.1090/conm/453/08802
[16] Joel Friedman. Beregning af betti-tal via kombinatoriske laplacians. Algorithmica, 21 (4): 331-346, 1998. 10.1007/PL00009218.
https://doi.org/10.1007/PL00009218
[17] Robert Ghrist. Stregkoder: den vedvarende topologi af data. 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 og Nathan Wiebe. Kvantesingular værditransformation og videre: eksponentielle forbedringer for kvantematrix-aritmetik. I Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, side 193-204, 2019. 10.1145/3313276.3316366.
https:///doi.org/10.1145/3313276.3316366
[19] Sam Gunn og Niels Kornerup. Gennemgang af en kvantealgoritme for betti-tal. 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 og Seth Lloyd. Kvantealgoritme til lineære ligningssystemer. Physical review letters, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https:///doi.org/10.1103/PhysRevLett.103.150502
[21] Ryu Hayakawa. Kvantealgoritme til vedvarende betti-tal og topologisk dataanalyse. 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 og Suguru Tamaki. Finkornet kvanteoverherredømme baseret på ortogonale vektorer, 3-sum og alle-par korteste veje. 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 og Xiao-Feng Wang. Nedbrydninger af n-qubit toffoli-porte med lineær kredsløbskompleksitet. 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 og Jian-Wei Pan. Demonstration af topologisk dataanalyse på en kvanteprocessor. 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 og Chao Yang. Tilnærmelse af spektraltætheder af store matricer. SIAM review, 58 (1): 34–65, 2016. 10.1137/130934283.
https:///doi.org/10.1137/130934283
[27] Seth Lloyd, Silvano Garnerone og Paolo Zanardi. Kvantealgoritmer til topologisk og geometrisk analyse af 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 og Isaac L Chuang. Stor forening af kvantealgoritmer. PRX Quantum, 2 (4): 040203, 2021. 10.1103/PRXQuantum.2.040203.
https:///doi.org/10.1103/PRXQuantum.2.040203
[29] RHAJ Meijer. Klyngning ved brug af kvantepersistent homologi. Kandidatafhandling, 2019.
[30] Facundo Mémoli, Zhengchao Wan og Yusu Wang. Vedvarende laplacians: egenskaber, algoritmer og 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 og Sterre den Breeijen. Begrænsninger af klyngedannelse ved brug af kvantepersistent 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 og Heather A Harrington. En køreplan for beregning af vedvarende 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 og Mathijs Wintraecken. Topologien af det kosmiske web i form af vedvarende 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 og Kelin Xia. Vedvarende homologi-baseret maskinlæring: en undersøgelse og en sammenlignende undersøgelse. Artificial Intelligence Review, side 1-45, 2022. 10.1007/s10462-022-10146-z.
https:///doi.org/10.1007/s10462-022-10146-z
[35] Patrick Rall. Hurtigere sammenhængende kvantealgoritmer til fase-, energi- og amplitudeestimering. 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 og Muhammad Tahir. Bevis for bijektion for kombinatorisk 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 og Anna Wienhard. Finde selv-lignende adfærd i kvante mange-krops dynamik via vedvarende 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 og Lior Horesh. Kvantetopologisk dataanalyse med lineær dybde og eksponentiel fremskyndelse. 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 og Guo-Wei Wei. Vedvarende 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 dataanalyse. 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 og Guo-Wei Wei. Vedvarende homologianalyse af proteinstruktur, fleksibilitet og foldning. 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 og Gunnar Carlsson. Beregning af vedvarende homologi. Discrete & Computational Geometry, 33 (2): 249–274, 2005. 10.1007/s00454-004-1146-y.
https:///doi.org/10.1007/s00454-004-1146-y
Citeret af
[1] Alexander Schmidhuber og Seth Lloyd, "Kompleksitetsteoretiske begrænsninger på kvantealgoritmer til topologisk dataanalyse", arXiv: 2209.14286.
[2] Bernardo Ameneyro, Vasileios Maroulas og 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 og Ryan Babbush, "Quantifying Quantum Advantage in Topological Data Analysis", arXiv: 2209.13581.
[4] Iordanis Kerenidis og Anupam Prakash, "Quantum machine learning with subspace states", arXiv: 2202.00054.
[5] Bernardo Ameneyro, George Siopsis og Vasileios Maroulas, "Quantum Persistent Homology for Time Series", arXiv: 2211.04465.
[6] Simon Apers, Sayantan Sen og Dániel Szabó, "En (simpel) klassisk algoritme til at estimere Betti-tal", arXiv: 2211.09618.
[7] Sam McArdle, András Gilyén og Mario Berta, "En strømlinet kvantealgoritme til topologisk dataanalyse med eksponentielt færre qubits", arXiv: 2209.12887.
[8] Andrew Vlasic og Anh Pham, "Forståelse af kortlægningen af kodedata gennem en implementering af kvantetopologisk analyse", arXiv: 2209.10596.
Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2022-12-07 16:42:14). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.
Kunne ikke hente Crossref citeret af data under sidste forsøg 2022-12-07 16:42:12: Kunne ikke hente citerede data for 10.22331/q-2022-12-07-873 fra Crossref. Dette er normalt, hvis DOI blev registreret for nylig.
Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.
