Yukawan teoreettisen fysiikan instituutti, Kioton yliopisto, Kitashirakawa Oiwakecho, Sakyoku, Kioto 606-8502, Japani
Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.
Abstrakti
Topologinen data-analyysi (TDA) on nouseva data-analyysin ala. TDA:n kriittinen vaihe on pysyvien Betti-lukujen laskeminen. Olemassa olevat klassiset TDA-algoritmit ovat rajallisia, jos haluamme oppia korkeadimensionaalisista topologisista ominaisuuksista, koska suuriulotteisten yksinkertaisteiden määrä kasvaa eksponentiaalisesti datan koossa. Kvanttilaskennan yhteydessä on aiemmin osoitettu, että on olemassa tehokas kvanttialgoritmi Betti-lukujen estimoimiseksi jopa suurissa ulottuvuuksissa. Betti-luvut ovat kuitenkin vähemmän yleisiä kuin pysyvät Betti-luvut, eikä ole olemassa kvanttialgoritmeja, jotka pystyisivät arvioimaan mielivaltaisten ulottuvuuksien pysyviä Betti-lukuja.
Tässä artikkelissa esitetään ensimmäinen kvanttialgoritmi, joka voi estimoida mielivaltaisten ulottuvuuksien ($normalisoitu$) pysyvät Betti-luvut. Algoritmimme on tehokas yksinkertaisissa komplekseissa, kuten Vietoris-Rips -kompleksissa, ja se osoittaa eksponentiaalista nopeutta tunnettuihin klassisiin algoritmeihin verrattuna.
► BibTeX-tiedot
► Viitteet
[1] Mehmet E Aktas, Esra Akbas ja Ahmed El Fatmaoui. Verkkojen pysyvyyshomologia: menetelmät ja sovellukset. 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. Vahvat homotopiatyypit, hermot ja romahdukset. 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-tilojen deterministinen valmistelu. International Symposium on Fundamentals of Computation Theory, sivut 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. Kvanttien amplitudivahvistus ja estimointi. Contemporary Mathematics, 305: 53–74, 2002. 10.1090 / conm / 305/05215.
https: / / doi.org/ 10.1090 / conm / 305/05215
[5] Peter Bubenik et ai. Tilastollinen topologinen tiedon analysointi pysyvyysmaisemien avulla. J. Mach. Oppia. 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. Johdatus topologiseen data-analyysiin: perus- ja käytännön näkökohdat datatieteilijöille. Tekoälyn rajat, 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. Nopeat matriisisijoitusalgoritmit ja -sovellukset. 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. Pysyvyyskaavioiden vakaus. Diskreetti ja laskennallinen geometria, 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. Merkkijonomaiseman topologinen data-analyysi. 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. Uusi kvanttiripple-carry-lisäyspiiri. 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 ja Yousef Saad. Tehokas ominaisarvojen estimoiminen välissä. Numeerinen lineaarinen algebra sovelluksilla, 23 (4): 674–692, 2016. 10.1002/nla.2048.
https:///doi.org/10.1002/nla.2048
[12] Robert H Dicke. Koherenssi spontaaneissa säteilyprosesseissa. 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. Laskennallinen topologia: johdanto. 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. Topologinen pysyvyys ja yksinkertaistaminen. Teoksessa Proceedings 41st Annual Symposium on Foundations of Computer Science, sivut 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 ai. Pysyvä homologia - kysely. Contemporary Mathematics, 453: 257–282, 2008. 10.1090/conm/453/08802.
https: / / doi.org/ 10.1090 / conm / 453/08802
[16] Joel Friedman. Betti-lukujen laskeminen kombinatoristen laplacianien avulla. Algorithmica, 21 (4): 331-346, 1998. 10.1007/PL00009218.
https: / / doi.org/ 10.1007 / PL00009218
[17] Robert Ghrist. Viivakoodit: jatkuva tiedon topologia. 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. Kvanttiyksikköarvon muunnos ja sen jälkeen: eksponentiaalisia parannuksia kvanttimatriisiaritmetiikkaan. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, sivut 193–204, 2019. 10.1145/3313276.3316366.
https: / / doi.org/ 10.1145 / +3313276.3316366
[19] Sam Gunn ja Niels Kornerup. Katsaus betti-lukujen kvanttialgoritmiin. 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 ja Seth Lloyd. Kvanttialgoritmi lineaarisille yhtälöjärjestelmille. Physical Review letters, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
[21] Ryu Hayakawa. Kvanttialgoritmi pysyviin betti-lukuihin ja topologisen tiedon analysointiin. 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 ja Suguru Tamaki. Hienojakoinen kvanttiylivalta, joka perustuu ortogonaalisiin vektoreihin, kolmen summan ja kaikkien parien lyhimpiin polkuihin. arXiv preprint arXiv:3, 1902.08382. 2019/arXiv.10.48550.
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. Lineaarisen piirin monimutkaisuuden omaavien n-qubit-toffoliporttien hajotukset. 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. Topologisen datan analyysin esittely kvanttiprosessorilla. 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 kaavioissa. SIAM Review, 62 (3): 685–715, 2020. 10.1137/18M1223101.
https: / / doi.org/ 10.1137 / 18M1223101
[26] Lin Lin, Yousef Saad ja Chao Yang. Suurten matriisien spektritiheyksien likiarvo. SIAM-katsaus, 58 (1): 34–65, 2016. 10.1137/130934283.
https: / / doi.org/ 10.1137 / +130934283
[27] Seth Lloyd, Silvano Garnerone ja Paolo Zanardi. Kvanttialgoritmit datan topologiseen ja geometriseen analyysiin. 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 ja Isaac L Chuang. Kvanttialgoritmien suuri yhdistäminen. PRX Quantum, 2 (4): 040203, 2021. 10.1103/PRXQuantum.2.040203.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
[29] RHAJ Meijer. Klusterointi käyttämällä kvanttipysyvää homologiaa. Diplomityö, 2019.
[30] Facundo Mémoli, Zhengchao Wan ja Yusu Wang. Pysyvät laplacians: Ominaisuudet, algoritmit ja implikaatiot. 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. Klusterin rajoitukset käyttämällä kvanttipysyvää homologiaa. 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 ja Heather A Harrington. Etenemissuunnitelma pysyvän homologian laskemiseksi. 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. Kosmisen verkon topologia pysyvien betti-lukujen suhteen. 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 ja Kelin Xia. Pysyvä-homologiaan perustuva koneoppiminen: kysely ja vertaileva tutkimus. Artificial Intelligence Review, sivut 1–45, 2022. 10.1007/s10462-022-10146-z.
https: / / doi.org/ 10.1007 / s10462-022-10146-z
[35] Patrick Rall. Nopeammat koherentit kvanttialgoritmit vaihe-, energia- ja amplitudiarviointiin. 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. Todistus bijektiosta kombinatoriselle lukujärjestelmälle. 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 ja Anna Wienhard. Itsesamanlaisen käyttäytymisen löytäminen kvanttimonikehodynamiikassa jatkuvan homologian avulla. SciPost Phys., 11: 060, 2021. 10.21468/SciPostPhys.11.3.060. URL-osoite 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. Kvanttitopologinen dataanalyysi lineaarisella syvyydellä ja eksponentiaalisella nopeudella. 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 ja Guo-Wei Wei. Pysyvä spektrikaavio. Kansainvälinen biolääketieteen menetelmien numeeristen menetelmien lehti, 36 (9): e3376, 2020. 10.1002/cnm.3376.
https:///doi.org/10.1002/cnm.3376
[40] Larry Wasserman. Topologinen data-analyysi. Tilastojen ja sen soveltamisen vuosikatsaus, 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. Proteiinirakenteen, joustavuuden ja laskostumisen jatkuva homologia-analyysi. Kansainvälinen biolääketieteen menetelmiä käsittelevä lehti, 30 (8): 814–844, 2014. 10.1002/cnm.2655.
https:///doi.org/10.1002/cnm.2655
[42] Afra Zomorodian ja Gunnar Carlsson. Pysyvän homologian laskeminen. Discrete & Computational Geometry, 33 (2): 249–274, 2005. 10.1007/s00454-004-1146-y.
https: / / doi.org/ 10.1007 / s00454-004-1146-y
Viitattu
[1] Alexander Schmidhuber ja Seth Lloyd, "Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis", 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, "Kvanttikoneoppiminen aliavaruuden tiloilla", 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ó, "(Yksinkertainen) klassinen algoritmi Betti-lukujen arvioimiseen", arXiv: 2211.09618.
[7] Sam McArdle, András Gilyén ja Mario Berta, "Virtaviivainen kvanttialgoritmi topologisen datan analysointiin eksponentiaalisesti vähemmällä kubitilla". arXiv: 2209.12887.
[8] Andrew Vlasic ja Anh Pham, "Understanding the Mapping of Encode Data Through An Implementation of Quantum Topological Analysis", arXiv: 2209.10596.
Yllä olevat sitaatit ovat peräisin SAO: n ja NASA: n mainokset (viimeksi päivitetty onnistuneesti 2022-12-07 16:42:14). Lista voi olla puutteellinen, koska kaikki julkaisijat eivät tarjoa sopivia ja täydellisiä viittaustietoja.
Ei voitu noutaa Crossref siteeratut tiedot viimeisen yrityksen aikana 2022-12-07 16:42:12: Ei voitu noutaa viittauksia 10.22331 / q-2022-12-07-873 mainittuihin tietoihin Crossrefiltä. Tämä on normaalia, jos DOI rekisteröitiin äskettäin.
Tämä kirja on julkaistu Quantum - lehdessä Creative Commons Nimeäminen 4.0 Kansainvälinen (CC BY 4.0) lisenssin. Tekijänoikeudet säilyvät alkuperäisillä tekijänoikeuksien haltijoilla, kuten tekijöillä tai heidän instituutioillaan.
