Yukawa Institute for Theoretical Physics, Πανεπιστήμιο Kyoto, Kitashirakawa Oiwakecho, Sakyoku, Kyoto 606-8502, Ιαπωνία
Βρείτε αυτό το άρθρο ενδιαφέρουσα ή θέλετε να συζητήσετε; Scite ή αφήστε ένα σχόλιο για το SciRate.
Περίληψη
Η τοπολογική ανάλυση δεδομένων (TDA) είναι ένα αναδυόμενο πεδίο ανάλυσης δεδομένων. Το κρίσιμο βήμα του TDA είναι ο υπολογισμός των επίμονων αριθμών Betti. Οι υπάρχοντες κλασικοί αλγόριθμοι για το TDA είναι περιορισμένοι, εάν θέλουμε να μάθουμε από τοπολογικά χαρακτηριστικά υψηλής διάστασης, επειδή ο αριθμός των απλών υψηλών διαστάσεων αυξάνεται εκθετικά στο μέγεθος των δεδομένων. Στο πλαίσιο του κβαντικού υπολογισμού, έχει αποδειχθεί προηγουμένως ότι υπάρχει ένας αποτελεσματικός κβαντικός αλγόριθμος για την εκτίμηση των αριθμών Betti ακόμη και σε υψηλές διαστάσεις. Ωστόσο, οι αριθμοί Betti είναι λιγότερο γενικοί από τους επίμονους αριθμούς Betti και δεν έχουν υπάρξει κβαντικοί αλγόριθμοι που να μπορούν να εκτιμήσουν τους επίμονους αριθμούς Betti αυθαίρετων διαστάσεων.
Αυτό το έγγραφο δείχνει τον πρώτο κβαντικό αλγόριθμο που μπορεί να εκτιμήσει τους ($normalized$) επίμονους αριθμούς Betti αυθαίρετων διαστάσεων. Ο αλγόριθμός μας είναι αποτελεσματικός για απλά συμπλέγματα όπως το σύμπλεγμα Vietoris-Rips και δείχνει εκθετική επιτάχυνση σε σχέση με τους γνωστούς κλασικούς αλγόριθμους.
► Δεδομένα BibTeX
► Αναφορές
[1] Ο Mehmet E Aktas, η Esra Akbas και ο Ahmed El Fatmaoui. Εμμονή ομολογία δικτύων: μέθοδοι και εφαρμογές. 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 και Elias Gabriel Minian. Ισχυροί τύποι ομοτοπίας, νεύρα και καταρρεύσεις. 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 και Stephan Eidenbenz. Ντετερμινιστική προετοιμασία καταστάσεων dicke. Στο International Symposium on Fundamentals of Computation Theory, σελίδες 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 και Alain Tapp. Ενίσχυση και εκτίμηση κβαντικού πλάτους. Σύγχρονα Μαθηματικά, 305: 53–74, 2002. 10.1090 / conm / 305/05215.
https: / / doi.org/ 10.1090 / conm / 305/05215
[5] Οι Peter Bubenik et al. Στατιστική τοπολογική ανάλυση δεδομένων με χρήση τοπίων εμμονής. J. Mach. Μαθαίνω. Res., 16 (1): 77–102, 2015. 10.5555/2789272.2789275.
https: / / doi.org/ 10.5555 / 2789272.2789275
[6] Frédéric Chazal και Bertrand Michel. Εισαγωγή στην τοπολογική ανάλυση δεδομένων: θεμελιώδεις και πρακτικές πτυχές για τους επιστήμονες δεδομένων. Σύνορα στην τεχνητή νοημοσύνη, 4, 2021. 10.3389/frai.2021.667963.
https://doi.org/10.3389/frai.2021.667963
[7] Ho Yee Cheung, Tsz Chiu Kwok και Lap Chi Lau. Γρήγοροι αλγόριθμοι και εφαρμογές κατάταξης μήτρας. 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 και John Harer. Διαγράμματα σταθερότητας ανθεκτικότητας. Discrete & computational geometry, 37 (1): 103–120, 2007. 10.1007/s00454-006-1276-5.
https://doi.org/10.1007/s00454-006-1276-5
[9] Alex Cole και Gary Shiu. Τοπολογική ανάλυση δεδομένων για το τοπίο των χορδών. 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 και David Petrie Moulton. Ένα νέο κύκλωμα προσθήκης κβαντικού κυματισμού. arXiv προεκτύπωση 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 και Yousef Saad. Αποτελεσματική εκτίμηση των μετρήσεων ιδιοτιμών σε ένα διάστημα. Numerical Linear Algebra with Applications, 23 (4): 674–692, 2016. 10.1002/nla.2048.
https://doi.org/10.1002/nla.2048
[12] Robert H Dicke. Συνοχή σε διαδικασίες αυθόρμητης ακτινοβολίας. Physical review, 93 (1): 99, 1954. 10.1103/PhysRev.93.99.
https: / / doi.org/ 10.1103 / PhysRev.93.99
[13] Herbert Edelsbrunner και John Harer. Υπολογιστική τοπολογία: μια εισαγωγή. 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 και Afra Zomorodian. Τοπολογική εμμονή και απλοποίηση. Στο Πρακτικά 41ο ετήσιο συμπόσιο για τα θεμέλια της επιστήμης των υπολογιστών, σελίδες 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. Επίμονη ομολογία-μια έρευνα. Σύγχρονα μαθηματικά, 453: 257–282, 2008. 10.1090/conm/453/08802.
https: / / doi.org/ 10.1090 / conm / 453/08802
[16] Τζόελ Φρίντμαν. Υπολογισμός αριθμών betti μέσω συνδυαστικών λαπλάσιων. Algorithmica, 21 (4): 331–346, 1998. 10.1007/PL00009218.
https://doi.org/ 10.1007/PL00009218
[17] Robert Ghrist. Barcodes: η επίμονη τοπολογία δεδομένων. 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 και Nathan Wiebe. Κβαντικός μετασχηματισμός μοναδικής τιμής και πέρα: εκθετικές βελτιώσεις για την αριθμητική κβαντικών πινάκων. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, σελίδες 193–204, 2019. 10.1145/3313276.3316366.
https: / / doi.org/ 10.1145 / 3313276.3316366
[19] Sam Gunn και Niels Kornerup. Ανασκόπηση ενός κβαντικού αλγορίθμου για αριθμούς betti. arXiv προεκτύπωση 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 και Seth Lloyd. Κβαντικός αλγόριθμος για γραμμικά συστήματα εξισώσεων. Επιστολές φυσικής αναθεώρησης, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
[21] Ryu Hayakawa. Κβαντικός αλγόριθμος για επίμονους αριθμούς betti και ανάλυση τοπολογικών δεδομένων. arXiv προεκτύπωση 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 και Suguru Tamaki. Λεπτόκοκκη κβαντική υπεροχή που βασίζεται σε ορθογώνια διανύσματα, 3-αθροίσματα και συντομότερα μονοπάτια όλων των ζευγών. arXiv προεκτύπωση 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 και Xiao-Feng Wang. Αποσυνθέσεις πυλών toffoli n-qubit με πολυπλοκότητα γραμμικού κυκλώματος. 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 και Jian-Wei Pan. Επίδειξη τοπολογικής ανάλυσης δεδομένων σε κβαντικό επεξεργαστή. Optica, 5 (2): 193–198, 2018. 10.1364/OPTICA.5.000193.
https: / / doi.org/ 10.1364 / OPTICA.5.000193
[25] Λεκ-Χενγκ Λιμ. Hodge Laplacians σε γραφήματα. SIAM Review, 62 (3): 685–715, 2020. 10.1137/18M1223101.
https: / / doi.org/ 10.1137 / 18M1223101
[26] Lin Lin, Yousef Saad και Chao Yang. Προσεγγίζοντας τις φασματικές πυκνότητες μεγάλων πινάκων. SIAM κριτική, 58 (1): 34–65, 2016. 10.1137/130934283.
https: / / doi.org/ 10.1137 / 130934283
[27] Σεθ Λόιντ, Σιλβάνο Γκαρνερόνε και Πάολο Ζανάρντι. Κβαντικοί αλγόριθμοι για τοπολογική και γεωμετρική ανάλυση δεδομένων. 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 και Isaac L Chuang. Μεγάλη ενοποίηση κβαντικών αλγορίθμων. PRX Quantum, 2 (4): 040203, 2021. 10.1103/PRXQuantum.2.040203.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
[29] RHAJ Meijer. Ομαδοποίηση με χρήση κβαντικής επίμονης ομολογίας. Μεταπτυχιακή εργασία, 2019.
[30] Facundo Mémoli, Zhengchao Wan και Yusu Wang. Επίμονοι Λαπλάσιοι: Ιδιότητες, αλγόριθμοι και επιπτώσεις. SIAM Journal on Mathematics of Data Science, 4 (2): 858–884, 2022. 10.1137/21M1435471.
https: / / doi.org/ 10.1137 / 21M1435471
[31] Niels Neumann και Sterre den Breeijen. Περιορισμοί της ομαδοποίησης με χρήση κβαντικής επίμονης ομολογίας. arXiv προεκτύπωση 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 και Heather A Harrington. Ένας οδικός χάρτης για τον υπολογισμό της επίμονης ομολογίας. 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 και Mathijs Wintraecken. Η τοπολογία του κοσμικού ιστού από την άποψη των επίμονων αριθμών betti. 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 και Kelin Xia. Μηχανική μάθηση με επίμονη ομολογία: μια έρευνα και μια συγκριτική μελέτη. Επιθεώρηση τεχνητής νοημοσύνης, σελίδες 1–45, 2022. 10.1007/s10462-022-10146-z.
https: / / doi.org/ 10.1007 / s10462-022-10146-z
[35] Πάτρικ Ραλ. Ταχύτεροι συνεκτικοί κβαντικοί αλγόριθμοι για εκτίμηση φάσης, ενέργειας και πλάτους. 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 και Muhammad Tahir. Απόδειξη διχοτόμησης για συνδυαστικό σύστημα αριθμών. arXiv προεκτύπωση 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 και Anna Wienhard. Εύρεση αυτο-όμοιας συμπεριφοράς στην κβαντική δυναμική πολλών σωμάτων μέσω επίμονης ομολογίας. 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 και Lior Horesh. Κβαντική τοπολογική ανάλυση δεδομένων με γραμμικό βάθος και εκθετική επιτάχυνση. arXiv προεκτύπωση 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 και Guo-Wei Wei. Επίμονο φασματικό γράφημα. Διεθνές περιοδικό για τις αριθμητικές μεθόδους στη βιοϊατρική μηχανική, 36 (9): e3376, 2020. 10.1002/cnm.3376.
https://doi.org/10.1002/cnm.3376
[40] Λάρι Βάσερμαν. Τοπολογική ανάλυση δεδομένων. 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 και Guo-Wei Wei. Επίμονη ανάλυση ομολογίας της πρωτεϊνικής δομής, ευελιξίας και αναδίπλωσης. Διεθνές περιοδικό για τις αριθμητικές μεθόδους στη βιοϊατρική μηχανική, 30 (8): 814–844, 2014. 10.1002/cnm.2655.
https://doi.org/10.1002/cnm.2655
[42] Afra Zomorodian και Gunnar Carlsson. Υπολογισμός επίμονης ομολογίας. Discrete & Computational Geometry, 33 (2): 249–274, 2005. 10.1007/s00454-004-1146-y.
https: / / doi.org/ 10.1007 / s00454-004-1146-y
Αναφέρεται από
[1] Alexander Schmidhuber και Seth Lloyd, «Περιορισμοί πολυπλοκότητας-θεωρητικούς σε κβαντικούς αλγόριθμους για τοπολογική ανάλυση δεδομένων», arXiv: 2209.14286.
[2] Bernardo Ameneyro, Βασίλειος Μαρούλας και Γιώργος Σιώψης, «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 και Ryan Babbush, «Quantifying Quantum Advantage in Topological Data Analysis». arXiv: 2209.13581.
[4] Ιορδάνης Κερενίδης και Anupam Prakash, «Κβαντική μηχανική μάθηση με υποδιαστημικές καταστάσεις», arXiv: 2202.00054.
[5] Bernardo Ameneyro, George Siopsis, and Vasileios Maroulas, “Quantum Persistent Homology for Time Series”, arXiv: 2211.04465.
[6] Simon Apers, Sayantan Sen και Dániel Szabó, «Ένας (απλός) κλασικός αλγόριθμος για την εκτίμηση των αριθμών Betti», arXiv: 2211.09618.
[7] Sam McArdle, András Gilyén και Mario Berta, «Ένας βελτιωμένος κβαντικός αλγόριθμος για ανάλυση τοπολογικών δεδομένων με εκθετικά λιγότερα qubits», arXiv: 2209.12887.
[8] Andrew Vlasic και Anh Pham, «Κατανόηση της χαρτογράφησης των κωδικοποιημένων δεδομένων μέσω της υλοποίησης της κβαντικής τοπολογικής ανάλυσης», arXiv: 2209.10596.
Οι παραπάνω αναφορές είναι από SAO / NASA ADS (τελευταία ενημέρωση επιτυχώς 2022-12-07 16:42:14). Η λίστα μπορεί να είναι ελλιπής, καθώς δεν παρέχουν όλοι οι εκδότες τα κατάλληλα και πλήρη στοιχεία αναφοράς.
Δεν ήταν δυνατή η λήψη Crossref αναφερόμενα δεδομένα κατά την τελευταία προσπάθεια 2022-12-07 16:42:12: Δεν ήταν δυνατή η λήψη των αναφερόμενων δεδομένων για το 10.22331 / q-2022-12-07-873 από την Crossref. Αυτό είναι φυσιολογικό αν το DOI καταχωρήθηκε πρόσφατα.
Αυτό το Βιβλίο δημοσιεύεται στο Quantum στο πλαίσιο του Creative Commons Attribution 4.0 Διεθνής (CC BY 4.0) άδεια. Τα πνευματικά δικαιώματα παραμένουν στους κατόχους των πρωτότυπων δικαιωμάτων πνευματικής ιδιοκτησίας όπως οι δημιουργοί ή τα ιδρύματά τους
