Inštitut za teoretično fiziko Yukawa, Univerza v Kjotu, Kitashirakawa Oiwakecho, Sakyoku, Kjoto 606-8502, Japonska
Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.
Minimalizem
Topološka analiza podatkov (TDA) je novo področje analize podatkov. Ključni korak TDA je izračun vztrajnih Bettijevih števil. Obstoječi klasični algoritmi za TDA so omejeni, če se želimo učiti iz visokodimenzionalnih topoloških značilnosti, ker število visokodimenzionalnih poenostavljenih eksponentno raste glede na velikost podatkov. V kontekstu kvantnega računanja je bilo predhodno dokazano, da obstaja učinkovit kvantni algoritem za ocenjevanje Bettijevih števil tudi v visokih dimenzijah. Vendar so Bettijeva števila manj splošna kot obstojna Bettijeva števila in ni bilo kvantnih algoritmov, ki bi lahko ocenili obstojna Bettijeva števila poljubnih dimenzij.
Ta članek prikazuje prvi kvantni algoritem, ki lahko oceni ($normalizirana$) obstojna Bettijeva števila poljubnih dimenzij. Naš algoritem je učinkovit za simplicialne komplekse, kot je kompleks Vietoris-Rips, in dokazuje eksponentno pospešitev v primerjavi z znanimi klasičnimi algoritmi.
► BibTeX podatki
► Reference
[1] Mehmet E Aktas, Esra Akbas in Ahmed El Fatmaoui. Obstojna homologija omrežij: metode in aplikacije. 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 in Elias Gabriel Minian. Močni homotopični tipi, živci in kolapsi. Diskretna in računalniška geometrija, 47 (2): 301–328, 2012. 10.1007/s00454-011-9357-5.
https://doi.org/10.1007/s00454-011-9357-5
[3] Andreas Bärtschi in Stephan Eidenbenz. Deterministična priprava dickejevih stanj. V mednarodnem simpoziju o osnovah teorije računanja, strani 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 in Alain Tapp. Kvantna amplitudna ojačitev in ocena. Sodobna matematika, 305: 53–74, 2002. 10.1090 / conm / 305/05215.
https: / / doi.org/ 10.1090 / conm / 305/05215
[5] Peter Bubenik idr. Statistična topološka analiza podatkov z uporabo obstojnih pokrajin. J. Mach. Naučite se. Res., 16 (1): 77–102, 2015. 10.5555/2789272.2789275.
https: / / doi.org/ 10.5555 / 2789272.2789275
[6] Frédéric Chazal in Bertrand Michel. Uvod v topološko analizo podatkov: temeljni in praktični vidiki za podatkovne znanstvenike. Meje umetne inteligence, 4, 2021. 10.3389/frai.2021.667963.
https:///doi.org/10.3389/frai.2021.667963
[7] Ho Yee Cheung, Tsz Chiu Kwok in Lap Chi Lau. Hitri algoritmi in aplikacije za rangiranje matrik. Revija ACM (JACM), 60 (5): 1–25, 2013. 10.1145/2528404.
https: / / doi.org/ 10.1145 / 2528404
[8] David Cohen-Steiner, Herbert Edelsbrunner in John Harer. Stabilnost diagramov obstojnosti. Diskretna in računalniška geometrija, 37 (1): 103–120, 2007. 10.1007/s00454-006-1276-5.
https://doi.org/10.1007/s00454-006-1276-5
[9] Alex Cole in Gary Shiu. Topološka analiza podatkov za pokrajino nizov. 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 in David Petrie Moulton. Novo kvantno vezje za dodajanje prenosa valovanja. arXiv prednatis 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 in Yousef Saad. Učinkovita ocena števila lastnih vrednosti v intervalu. Numerična linearna algebra z aplikacijami, 23 (4): 674–692, 2016. 10.1002/nla.2048.
https:///doi.org/10.1002/nla.2048
[12] Robert H Dicke. Koherenca v procesih spontanega sevanja. Fizični pregled, 93 (1): 99, 1954. 10.1103/PhysRev.93.99.
https: / / doi.org/ 10.1103 / PhysRev.93.99
[13] Herbert Edelsbrunner in John Harer. Računalniška topologija: uvod. 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 in Afra Zomorodian. Topološka obstojnost in poenostavitev. V zborniku 41. letnega simpozija o temeljih računalništva, strani 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. Trajna homologija - raziskava. Contemporary mathematics, 453: 257–282, 2008. 10.1090/conm/453/08802.
https: / / doi.org/ 10.1090 / conm / 453/08802
[16] Joel Friedman. Računanje bettijevih števil prek kombinatoričnih laplacianov. Algorithmica, 21 (4): 331–346, 1998. 10.1007/PL00009218.
https:///doi.org/10.1007/PL00009218
[17] Robert Ghrist. Črtne kode: obstojna topologija podatkov. Bilten Ameriškega matematičnega društva, 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 in Nathan Wiebe. Kvantna transformacija singularne vrednosti in več: eksponentne izboljšave za kvantno matrično aritmetiko. V zborniku 51. letnega simpozija ACM SIGACT o teoriji računalništva, strani 193–204, 2019. 10.1145/3313276.3316366.
https: / / doi.org/ 10.1145 / 3313276.3316366
[19] Sam Gunn in Niels Kornerup. Pregled kvantnega algoritma za bettijeva števila. arXiv prednatis 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 in Seth Lloyd. Kvantni algoritem za linearne sisteme enačb. Physical review letters, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
[21] Ryu Hayakawa. Kvantni algoritem za obstojna Bettijeva števila in topološko analizo podatkov. arXiv prednatis 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 in Suguru Tamaki. Drobnozrnata kvantna premoč, ki temelji na ortogonalnih vektorjih, najkrajših poteh treh vsot in vseh parov. arXiv prednatis 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 in Xiao-Feng Wang. Razgradnje n-kubitnih toffoli vrat s kompleksnostjo linearnega vezja. 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 in Jian-Wei Pan. Demonstracija topološke analize podatkov na kvantnem procesorju. Optika, 5 (2): 193–198, 2018. 10.1364/OPTICA.5.000193.
https: / / doi.org/ 10.1364 / OPTICA.5.000193
[25] Lek-Heng Lim. Hodgejevi laplaciani na grafih. SIAM Review, 62 (3): 685–715, 2020. 10.1137/18M1223101.
https: / / doi.org/ 10.1137 / 18M1223101
[26] Lin Lin, Yousef Saad in Chao Yang. Približevanje spektralnih gostot velikih matrik. Pregled SIAM, 58 (1): 34–65, 2016. 10.1137/130934283.
https: / / doi.org/ 10.1137 / 130934283
[27] Seth Lloyd, Silvano Garnerone in Paolo Zanardi. Kvantni algoritmi za topološko in geometrijsko analizo podatkov. 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 in Isaac L Chuang. Velika združitev kvantnih algoritmov. PRX Quantum, 2 (4): 040203, 2021. 10.1103/PRXQuantum.2.040203.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
[29] RHAJ Meijer. Grozdenje z uporabo kvantne obstojne homologije. Magistrsko delo, 2019.
[30] Facundo Mémoli, Zhengchao Wan in Yusu Wang. Vztrajni laplaci: Lastnosti, algoritmi in posledice. SIAM Journal on Mathematics of Data Science, 4 (2): 858–884, 2022. 10.1137/21M1435471.
https: / / doi.org/ 10.1137 / 21M1435471
[31] Niels Neumann in Sterre den Breeijen. Omejitve združevanja v gruče z uporabo kvantne obstojne homologije. arXiv prednatis 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 in Heather A Harrington. Načrt za izračun obstojne homologije. 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 in Mathijs Wintraecken. Topologija kozmičnega spleta v smislu obstojnih bettijevih števil. 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 in Kelin Xia. Strojno učenje na podlagi obstojne homologije: raziskava in primerjalna študija. Artificial Intelligence Review, strani 1–45, 2022. 10.1007/s10462-022-10146-z.
https: / / doi.org/ 10.1007 / s10462-022-10146-z
[35] Patrick Rall. Hitrejši koherentni kvantni algoritmi za oceno faze, energije in amplitude. 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 in Muhammad Tahir. Dokaz bijekcije za kombinatorni številski sistem. arXiv prednatis 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 in Anna Wienhard. Iskanje samopodobnega vedenja v kvantni dinamiki več teles prek obstojne homologije. 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 in Lior Horesh. Kvantna topološka analiza podatkov z linearno globino in eksponentno pospešitvijo. arXiv prednatis 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 in Guo-Wei Wei. Trajni spektralni graf. Mednarodni časopis za numerične metode v biomedicinskem inženirstvu, 36 (9): e3376, 2020. 10.1002/cnm.3376.
https:///doi.org/10.1002/cnm.3376
[40] Larry Wasserman. Topološka analiza podatkov. Letni pregled statistike in njene uporabe, 5: 501–532, 2018. 10.1146/annurev-statistics-031017-100045.
https:///doi.org/10.1146/annurev-statistics-031017-100045
[41] Kelin Xia in Guo-Wei Wei. Analiza obstojne homologije proteinske strukture, prožnosti in zvijanja. Mednarodna revija za numerične metode v biomedicinskem inženirstvu, 30 (8): 814–844, 2014. 10.1002/cnm.2655.
https:///doi.org/10.1002/cnm.2655
[42] Afra Zomorodian in Gunnar Carlsson. Računanje obstojne homologije. Discrete & Computational Geometry, 33 (2): 249–274, 2005. 10.1007/s00454-004-1146-y.
https: / / doi.org/ 10.1007 / s00454-004-1146-y
Navedel
[1] Alexander Schmidhuber in Seth Lloyd, "Teoretične omejitve kompleksnosti kvantnih algoritmov za analizo topoloških podatkov", arXiv: 2209.14286.
[2] Bernardo Ameneyro, Vasileios Maroulas in George Siopsis, "Kvantna vztrajna homologija", 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 in Ryan Babbush, »Kvantificiranje kvantne prednosti pri analizi topoloških podatkov«, arXiv: 2209.13581.
[4] Iordanis Kerenidis in Anupam Prakash, "Kvantno strojno učenje s podprostorskimi stanji", arXiv: 2202.00054.
[5] Bernardo Ameneyro, George Siopsis in Vasileios Maroulas, "Kvantna obstojna homologija za časovne vrste", arXiv: 2211.04465.
[6] Simon Apers, Sayantan Sen in Dániel Szabó, "(preprost) klasični algoritem za ocenjevanje Bettijevih števil", arXiv: 2211.09618.
[7] Sam McArdle, András Gilyén in Mario Berta, "Poenostavljen kvantni algoritem za topološko analizo podatkov z eksponentno manj kubiti", arXiv: 2209.12887.
[8] Andrew Vlasic in Anh Pham, "Understanding the Mapping of Encode Data Through An Implementation of Quantum Topological Analysis", arXiv: 2209.10596.
Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2022-12-07 16:42:14). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.
Pridobitve ni bilo mogoče Crossref citirani podatki med zadnjim poskusom 2022-12-07 16:42:12: Citiranih podatkov za 10.22331 / q-2022-12-07-873 od Crossrefa ni bilo mogoče pridobiti. To je normalno, če je bil DOI registriran pred kratkim.
Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.
