Yukawa Institute for Theoretical Physics, Kyoto University, Kitashirakawa Oiwakecho, Sakyoku, Kyoto 606-8502, Japonia
Czy ten artykuł jest interesujący czy chcesz dyskutować? Napisz lub zostaw komentarz do SciRate.
Abstrakcyjny
Topologiczna analiza danych (TDA) to nowa dziedzina analizy danych. Krytycznym krokiem TDA jest obliczenie trwałych liczb Bettiego. Istniejące klasyczne algorytmy TDA są ograniczone, jeśli chcemy uczyć się na podstawie wielowymiarowych cech topologicznych, ponieważ liczba wielowymiarowych uproszczeń rośnie wykładniczo wraz z rozmiarem danych. W kontekście obliczeń kwantowych wykazano wcześniej, że istnieje wydajny algorytm kwantowy do szacowania liczb Bettiego nawet w dużych wymiarach. Jednak liczby Bettiego są mniej ogólne niż trwałe liczby Bettiego i nie było algorytmów kwantowych, które mogłyby oszacować trwałe liczby Bettiego o dowolnych wymiarach.
W tym artykule przedstawiono pierwszy algorytm kwantowy, który może oszacować ($znormalizowane$) trwałe liczby Bettiego o dowolnych wymiarach. Nasz algorytm jest wydajny dla uproszczonych kompleksów, takich jak kompleks Vietorisa-Ripsa, i wykazuje wykładnicze przyspieszenie w stosunku do znanych algorytmów klasycznych.
► Dane BibTeX
► Referencje
[1] Mehmet E Aktas, Esra Akbas i Ahmed El Fatmaoui. Homologia trwałości sieci: metody i zastosowania. 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 i Elias Gabriel Minian. Silne typy homotopii, nerwy i załamania. Dyskretna i obliczeniowa geometria, 47 (2): 301–328, 2012. 10.1007/s00454-011-9357-5.
https://doi.org/10.1007/s00454-011-9357-5
[3] Andreas Bärtschi i Stephan Eidenbenz. Deterministyczne przygotowanie stanów Dicke'a. W Międzynarodowym Sympozjum na temat podstaw teorii obliczeń, strony 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 i Alain Tapp. Amplifikacja i estymacja amplitudy kwantowej. Współczesna matematyka, 305: 53–74, 2002. 10.1090 / conm / 305/05215.
https: / / doi.org/ 10.1090 / conm / 305/05215
[5] Piotr Bubenik i in. Statystyczna analiza danych topologicznych z wykorzystaniem krajobrazów trwałości. J. Mach. Uczyć się. Rez., 16 (1): 77–102, 2015. 10.5555/2789272.2789275.
https: / / doi.org/ 10.5555 / 2789272.2789275
[6] Frédéric Chazal i Bertrand Michel. Wprowadzenie do topologicznej analizy danych: podstawowe i praktyczne aspekty dla naukowców zajmujących się danymi. Granice w sztucznej inteligencji, 4, 2021. 10.3389/frai.2021.667963.
https:///doi.org/10.3389/frai.2021.667963
[7] Ho Yee Cheung, Tsz Chiu Kwok i Lap Chi Lau. Szybkie algorytmy i aplikacje rankingów macierzy. Dziennik ACM (JACM), 60 (5): 1–25, 2013. 10.1145/2528404.
https: / / doi.org/ 10.1145 / 2528404
[8] Davida Cohena-Steinera, Herberta Edelsbrunnera i Johna Harera. Stabilność diagramów trwałości. Dyskretna i obliczeniowa geometria, 37 (1): 103–120, 2007. 10.1007/s00454-006-1276-5.
https://doi.org/10.1007/s00454-006-1276-5
[9] Alexa Cole'a i Gary'ego Shiu. Analiza danych topologicznych dla krajobrazu strunowego. 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 i David Petrie Moulton. Nowy kwantowy obwód dodawania tętnień przenoszenia. 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 i Yousef Saad. Efektywne oszacowanie zliczeń wartości własnych w przedziale. Numeryczna algebra liniowa z aplikacjami, 23 (4): 674–692, 2016. 10.1002/nla.2048.
https:///doi.org/10.1002/nla.2048
[12] Robert H Dicke. Spójność w spontanicznych procesach radiacyjnych. Przegląd fizyczny, 93 (1): 99, 1954. 10.1103/PhysRev.93.99.
https: / / doi.org/ 10.1103 / PhysRev.93.99
[13] Herberta Edelsbrunnera i Johna Harera. Topologia obliczeniowa: wprowadzenie. 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 i Afra Zomorodian. Trwałość topologiczna i uproszczenie. W Proceedings 41. doroczne sympozjum na temat podstaw informatyki, strony 454–463. IEEE, 2000. 10.1007/s00454-002-2885-2.
https://doi.org/10.1007/s00454-002-2885-2
[15] Herbert Edelsbrunner, John Harer i in. Trwała homologia - ankieta. Współczesna matematyka, 453: 257–282, 2008. 10.1090/conm/453/08802.
https: / / doi.org/ 10.1090 / conm / 453/08802
[16] Joela Friedmana. Obliczanie liczb Bettiego za pomocą kombinatorycznych laplacianów. Algorithmica, 21 (4): 331–346, 1998. 10.1007/PL00009218.
https: // doi.org/ 10.1007 / PL00009218
[17] Roberta Grysta. Kody kreskowe: trwała topologia danych. Biuletyn Amerykańskiego Towarzystwa Matematycznego, 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 i Nathan Wiebe. Kwantowa transformacja wartości osobliwej i nie tylko: wykładnicze ulepszenia arytmetyki macierzy kwantowej. W Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, strony 193-204, 2019. 10.1145/3313276.3316366.
https: / / doi.org/ 10.1145 / 3313276.3316366
[19] Sama Gunna i Nielsa Kornerupa. Przegląd algorytmu kwantowego dla liczb Bettiego. 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 i Seth Lloyd. Algorytm kwantowy dla liniowych układów równań. Listy dotyczące przeglądu fizycznego, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
[21] Ryu Hayakawa. Algorytm kwantowy dla trwałych liczb Bettiego i analizy danych topologicznych. 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 i Suguru Tamaki. Drobnoziarnista supremacja kwantowa oparta na wektorach ortogonalnych, najkrótszych ścieżkach o sumie 3 i wszystkich parach. 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 i Xiao-Feng Wang. Dekompozycje n-kubitowych bramek Toffoliego o liniowej złożoności obwodu. 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 i Jian-Wei Pan. Demonstracja topologicznej analizy danych na procesorze kwantowym. 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 na wykresach. Przegląd SIAM, 62 (3): 685–715, 2020. 10.1137/18M1223101.
https: / / doi.org/ 10.1137 / 18M1223101
[26] Lin Lin, Yousef Saad i Chao Yang. Przybliżone gęstości widmowe dużych macierzy. Przegląd SIAM, 58 (1): 34–65, 2016. 10.1137/130934283.
https: / / doi.org/ 10.1137 / 130934283
[27] Seth Lloyd, Silvano Garnerone i Paolo Zanardi. Algorytmy kwantowe do topologicznej i geometrycznej analizy danych. Komunikaty przyrodnicze, 7 (1): 1–7, 2016. 10.1038/ncomms10138.
https: / / doi.org/ 10.1038 / ncomms10138
[28] John M Martyn, Zane M Rossi, Andrew K Tan i Isaac L Chuang. Wielka unifikacja algorytmów kwantowych. PRX Quantum, 2 (4): 040203, 2021. 10.1103/PRXQuantum.2.040203.
https: // doi.org/ 10.1103 / PRXQuantum.2.040203
[29] RHAJ Meijer. Klastrowanie przy użyciu trwałej homologii kwantowej. praca magisterska, 2019.
[30] Facundo Mémoli, Zhengchao Wan i Yusu Wang. Trwali laplacianie: właściwości, algorytmy i implikacje. SIAM Journal on Mathematics of Data Science, 4 (2): 858–884, 2022. 10.1137/21M1435471.
https: / / doi.org/ 10.1137 / 21M1435471
[31] Niels Neumann i Sterre den Breeijen. Ograniczenia grupowania przy użyciu trwałej homologii kwantowej. arXiv przedruk 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 i Heather A Harrington. Mapa drogowa do obliczania trwałej homologii. 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 i Mathijs Wintraecken. Topologia kosmicznej sieci pod względem trwałych liczb bettiego. Miesięczne ogłoszenia Królewskiego Towarzystwa Astronomicznego, 465 (4): 4281–4310, 2017. 10.1093/mnras/stw2862.
https:///doi.org/10.1093/mnras/stw2862
[34] Chi Seng Pun, Si Xian Lee i Kelin Xia. Uczenie maszynowe oparte na trwałej homologii: ankieta i badanie porównawcze. Przegląd sztucznej inteligencji, strony 1–45, 2022. 10.1007/s10462-022-10146-z.
https: / / doi.org/ 10.1007 / s10462-022-10146-z
[35] Patryk Rall. Szybsze spójne algorytmy kwantowe do szacowania fazy, energii i amplitudy. 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 i Muhammad Tahir. Dowód bijekcji dla kombinatorycznego systemu liczbowego. 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 i Anna Wienhard. Znalezienie samopodobnego zachowania w kwantowej dynamice wielu ciał poprzez trwałą 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 i Lior Horesh. Kwantowa topologiczna analiza danych z liniową głębią i wykładniczym przyspieszeniem. 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 i Guo-Wei Wei. Trwały wykres widmowy. Międzynarodowe czasopismo poświęcone metodom numerycznym w inżynierii biomedycznej, 36 (9): e3376, 2020. 10.1002/cnm.3376.
https:///doi.org/10.1002/cnm.3376
[40] Larry'ego Wassermana. Analiza danych topologicznych. Roczny przegląd statystyki i jej zastosowania, 5: 501–532, 2018. 10.1146/annurev-statistics-031017-100045.
https:///doi.org/10.1146/annurev-statistics-031017-100045
[41] Kelin Xia i Guo-Wei Wei. Trwała analiza homologii struktury, elastyczności i fałdowania białek. Międzynarodowe czasopismo dotyczące metod numerycznych w inżynierii biomedycznej, 30 (8): 814–844, 2014. 10.1002/cnm.2655.
https:///doi.org/10.1002/cnm.2655
[42] Afra Zomorodian i Gunnar Carlsson. Obliczanie trwałej homologii. Dyskretna i obliczeniowa geometria, 33 (2): 249–274, 2005. 10.1007/s00454-004-1146-y.
https: / / doi.org/ 10.1007 / s00454-004-1146-y
Cytowany przez
[1] Alexander Schmidhuber i Seth Lloyd, „Teoretyczne ograniczenia złożoności algorytmów kwantowych do analizy danych topologicznych”, arXiv: 2209.14286.
[2] Bernardo Amenyro, Vasileios Maroulas i 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 i Ryan Babbush, „Quantifying Quantum Advantage in Topological Data Analysis”, arXiv: 2209.13581.
[4] Iordanis Kerenidis i Anupam Prakash, „Uczenie maszynowe kwantowe ze stanami podprzestrzennymi”, arXiv: 2202.00054.
[5] Bernardo Amenyro, George Siopsis i Vasileios Maroulas, „Quantum Persistent Homology for Time Series”, arXiv: 2211.04465.
[6] Simon Apers, Sayantan Sen i Dániel Szabó, „(Prosty) klasyczny algorytm szacowania liczb Bettiego”, arXiv: 2211.09618.
[7] Sam McArdle, András Gilyén i Mario Berta, „Uproszczony algorytm kwantowy do analizy danych topologicznych z wykładniczo mniejszą liczbą kubitów”, arXiv: 2209.12887.
[8] Andrew Vlasic i Anh Pham, „Zrozumienie mapowania kodowanych danych poprzez implementację kwantowej analizy topologicznej”, arXiv: 2209.10596.
Powyższe cytaty pochodzą z Reklamy SAO / NASA (ostatnia aktualizacja pomyślnie 2022-12-07 16:42:14). Lista może być niekompletna, ponieważ nie wszyscy wydawcy podają odpowiednie i pełne dane cytowania.
Nie można pobrać Przywołane przez Crossref dane podczas ostatniej próby 2022-12-07 16:42:12: Nie można pobrać cytowanych danych dla 10.22331 / q-2022-12-07-873 z Crossref. Jest to normalne, jeśli DOI zostało niedawno zarejestrowane.
Niniejszy artykuł opublikowano w Quantum pod Creative Commons Uznanie autorstwa 4.0 Międzynarodowe (CC BY 4.0) licencja. Prawa autorskie należą do pierwotnych właścicieli praw autorskich, takich jak autorzy lub ich instytucje.
