מכון יוקאווה לפיזיקה תיאורטית, אוניברסיטת קיוטו, קיטאשיראקווה אויבקצ'ו, סאקיוקו, קיוטו 606-8502, יפן
מצא את העיתון הזה מעניין או רוצה לדון? סקייט או השאירו תגובה ב- SciRate.
תַקצִיר
ניתוח נתונים טופולוגי (TDA) הוא תחום מתפתח של ניתוח נתונים. השלב הקריטי של TDA הוא חישוב מספרי Betti המתמשכים. האלגוריתמים הקלאסיים הקיימים עבור TDA מוגבלים אם ברצוננו ללמוד מתכונות טופולוגיות בממדים גבוהים, מכיוון שמספר הפשטים הממדים הגבוהים גדל באופן אקספוננציאלי בגודל הנתונים. בהקשר של חישוב קוונטי, הוכח בעבר שקיים אלגוריתם קוונטי יעיל להערכת מספרי בטי גם בממדים גבוהים. עם זאת, מספרי Betti הם פחות כלליים ממספרי Betti המתמשכים, ולא היו אלגוריתמים קוונטיים שיכולים להעריך את מספרי Betti המתמשכים של ממדים שרירותיים.
מאמר זה מציג את האלגוריתם הקוונטי הראשון שיכול להעריך את מספרי Betti המתמשכים ($מנורמלים$) של ממדים שרירותיים. האלגוריתם שלנו יעיל עבור קומפלקסים פשוטים כמו קומפלקס Vietoris-Rips ומדגים מהירות מעריפית על פני האלגוריתמים הקלאסיים הידועים.
► נתוני BibTeX
► הפניות
[1] מהמט א אקטאס, אסרה אקבס ואחמד אל פאטמאוי. הומולוגיה של רשתות: שיטות ויישומים. Applied Network Science, 4 (1): 1–28, 2019. 10.1007/s41109-019-0179-3.
https://doi.org/10.1007/s41109-019-0179-3
[2] יונתן אריאל ברמק ואליאס גבריאל מיניאן. סוגי הומטופיה חזקים, עצבים וקריסות. Discrete & Computational Geometry, 47 (2): 301–328, 2012. 10.1007/s00454-011-9357-5.
https://doi.org/10.1007/s00454-011-9357-5
[3] אנדראס ברטשי וסטפן איידנבנץ. הכנה דטרמיניסטית של מצבי דיק. בסימפוזיון הבינלאומי על יסודות תורת החישובים, עמודים 126–139. שפרינגר, 2019. 10.1007/978-3-030-25027-0_9.
https://doi.org/10.1007/978-3-030-25027-0_9
[4] ז'יל בראסארד, פיטר הוייר, מישל מוסקה ואלן טאפ. הגברה ואומדן משרעת קוונטית. מתמטיקה עכשווית, 305: 53–74, 2002. 10.1090/conm/305/05215.
https: / / doi.org/ 10.1090 / conm / 305/05215
[5] פיטר Bubenik וחב'. ניתוח נתונים טופולוגי סטטיסטי באמצעות נופי התמדה. ג'יי מאך. לִלמוֹד. שו"ת, 16 (1): 77–102, 2015. 10.5555/2789272.2789275.
https: / / doi.org/ 10.5555 / 2789272.2789275
[6] פרדריק שאזל וברטרנד מישל. מבוא לניתוח נתונים טופולוגי: היבטים בסיסיים ומעשיים עבור מדעני נתונים. גבולות בבינה מלאכותית, 4, 2021. 10.3389/frai.2021.667963.
https://doi.org/10.3389/frai.2021.667963
[7] Ho Yee Cheung, Tsz Chiu Kwok ולפ צ'י לאו. אלגוריתמים ויישומים בדירוג מטריצה מהירים. Journal of the ACM (JACM), 60 (5): 1–25, 2013. 10.1145/2528404.
https: / / doi.org/ 10.1145 / 2528404
[8] דיוויד כהן-שטיינר, הרברט אדלסברונר וג'ון הרר. יציבות של דיאגרמות התמדה. גיאומטריה דיסקרטית וחישובית, 37 (1): 103–120, 2007. 10.1007/s00454-006-1276-5.
https://doi.org/10.1007/s00454-006-1276-5
[9] אלכס קול וגארי שיו. ניתוח נתונים טופולוגי עבור נוף המיתרים. Journal of High Energy Physics, 2019 (3): 1–31, 2019. 10.1007/JHEP03(2019)054.
https: / / doi.org/ 10.1007 / JHEP03 (2019) 054
[10] סטיבן א קוקארו, תומס ג'י דרייפר, סמואל קוטין ודיוויד פיטרי מולטון. מעגל תוספת אדוות קוונטי חדש. 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] אדוארדו די נאפולי, אריק פוליצי ויוסף סעד. הערכה יעילה של ספירות ערכים עצמיים במרווח. Numerical Linear Algebra with Applications, 23 (4): 674–692, 2016. 10.1002/nla.2048.
https://doi.org/10.1002/nla.2048
[12] רוברט ה דיק. קוהרנטיות בתהליכי קרינה ספונטניים. סקירה פיזית, 93 (1): 99, 1954. 10.1103/PhysRev.93.99.
https: / / doi.org/ 10.1103 / PhysRev.93.99
[13] הרברט אדלסברונר וג'ון הרר. טופולוגיה חישובית: מבוא. American Mathematical Soc., 2010. 10.1007/978-3-540-33259-6_7.
https://doi.org/10.1007/978-3-540-33259-6_7
[14] הרברט אדלסברונר, דיוויד לשר ואפרה זומורודיאן. התמדה טופולוגית ופישוט. בסימפוזיון השנתי ה-41 של הליכים על יסודות מדעי המחשב, עמודים 454–463. IEEE, 2000. 10.1007/s00454-002-2885-2.
https://doi.org/10.1007/s00454-002-2885-2
[15] הרברט אדלסברונר, ג'ון הרר ועוד. הומולוגיה מתמשכת - סקר. מתמטיקה עכשווית, 453: 257–282, 2008. 10.1090/conm/453/08802.
https: / / doi.org/ 10.1090 / conm / 453/08802
[16] יואל פרידמן. חישוב מספרי בטי באמצעות laplacians קומבינטוריים. אלגוריתמיקה, 21 (4): 331–346, 1998. 10.1007/PL00009218.
https: / / doi.org/ 10.1007 / PL00009218
[17] רוברט גריסט. ברקודים: הטופולוגיה המתמשכת של נתונים. עלון של האגודה האמריקאית למתמטיקה, 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, and Nathan Wiebe. טרנספורמציה של ערך יחיד קוונטי ומעבר לכך: שיפורים מעריכי עבור אריתמטיקה של מטריצה קוונטית. ב-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] סם גאן ונילס קורנרופ. סקירה של אלגוריתם קוונטי למספרי בטי. arXiv preprint arXiv:1906.07673, 2019. 10.48550/arXiv.1906.07673.
https:///doi.org/10.48550/arXiv.1906.07673
arXiv: 1906.07673
[20] ארם וו הארו, אבינתן חסידים וסת לויד. אלגוריתם קוונטי למערכות ליניאריות של משוואות. מכתבי סקירה פיזית, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
[21] ריו הייקאווה. אלגוריתם קוונטי למספרי בטי מתמשכים וניתוח נתונים טופולוגי. 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 ו- Suguru Tamaki. עליונות קוונטית דקיקה המבוססת על וקטורים אורתוגונליים, 3 סכום וכל זוגות הנתיבים הקצרים ביותר. arXiv preprint arXiv:1902.08382, 2019. 10.48550/arXiv.1902.08382.
https:///doi.org/10.48550/arXiv.1902.08382
arXiv: 1902.08382
[23] יונג הוא, מינג-שינג לואו, אי ג'אנג, הונג-קה וואנג ושיאו-פנג וואנג. פירוק שערי n-qubit toffoli עם מורכבות מעגל ליניארי. 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, and Jian-Wei Pan. הדגמה של ניתוח נתונים טופולוגי על מעבד קוונטי. Optica, 5 (2): 193–198, 2018. 10.1364/OPTICA.5.000193.
https: / / doi.org/ 10.1364 / OPTICA.5.000193
[25] לק-הנג לים. הודג' לאפלציאנים על גרפים. SIAM Review, 62 (3): 685–715, 2020. 10.1137/18M1223101.
https: / / doi.org/ 10.1137 / 18M1223101
[26] לין לין, יוסף סעד וצ'או יאנג. צפיפות ספקטרלית בקירוב של מטריצות גדולות. סקירת SIAM, 58 (1): 34–65, 2016. 10.1137/130934283.
https: / / doi.org/ 10.1137 / 130934283
[27] סת לויד, סילבנו גרנרון ופאולו זנרדי. אלגוריתמים קוונטיים לניתוח טופולוגי וגיאומטרי של נתונים. תקשורת טבע, 7 (1): 1–7, 2016. 10.1038/ncomms10138.
https: / / doi.org/ 10.1038 / ncomms10138
[28] ג'ון מ. מרטין, זאן מ. רוסי, אנדרו ק. טאן ואייזק ל' צ'ואנג. איחוד גדול של אלגוריתמים קוונטיים. 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] נילס נוימן וסטר דן ברייגן. מגבלות של אשכולות באמצעות הומולוגיה מתמשכת קוונטית. arXiv preprint arXiv:1911.10781, 2019. 10.48550/arXiv.1911.10781.
https:///doi.org/10.48550/arXiv.1911.10781
arXiv: 1911.10781
[32] נינה אוטר, מייסון א. פורטר, אולריקה טילמן, פיטר גרינדרו, והתר א הרינגטון. מפת דרכים לחישוב הומולוגיה מתמשכת. 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, and Mathijs Wintraecken. הטופולוגיה של הרשת הקוסמית במונחים של מספרי בטי מתמשכים. הודעות חודשיות של החברה המלכותית לאסטרונומית, 465 (4): 4281–4310, 2017. 10.1093/mnras/stw2862.
https://doi.org/10.1093/mnras/stw2862
[34] צ'י סנג פאן, סי שיאן לי וקלין שיה. למידת מכונה מבוססת-הומולוגיה מתמדת: סקר ומחקר השוואתי. סקירת בינה מלאכותית, עמודים 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] אבו בכר סידיק, סעדיה פריד ומוחמד טאהיר. הוכחת חילוף למערכת המספרים הקומבינטורית. arXiv preprint arXiv:1601.05794, 2016. 10.48550/arXiv.1601.05794.
https:///doi.org/10.48550/arXiv.1601.05794
arXiv: 1601.05794
[37] דניאל שפיץ, יורגן ברגס, מרקוס אוברטהלר ואנה ויינהרד. מציאת התנהגות דומה לעצמה בדינמיקה קוונטית של גופים רבים באמצעות הומולוגיה מתמשכת. SciPost Phys., 11: 060, 2021. 10.21468/SciPostPhys.11.3.060. כתובת אתר 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, וליאור חורש. ניתוח נתונים טופולוגי קוונטי עם עומק ליניארי והאצה אקספוננציאלית. 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 ו-Guo-Wei Wei. גרף ספקטרלי מתמשך. כתב עת בינלאומי לשיטות נומריות בהנדסה ביו-רפואית, 36 (9): e3376, 2020. 10.1002/cnm.3376.
https://doi.org/10.1002/cnm.3376
[40] לארי וסרמן. ניתוח נתונים טופולוגי. סקירה שנתית של סטטיסטיקה ויישומה, 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] אפרה זומורודיאן וגונאר קרלסון. הומולוגיה מתמשכת מחשובית. Discrete & Computational Geometry, 33 (2): 249–274, 2005. 10.1007/s00454-004-1146-y.
https: / doi.org/â € ‹10.1007 / s00454-004-1146-y
מצוטט על ידי
[1] אלכסנדר שמידהובר וסת לויד, "הגבלות תיאורטיות-מורכבות על אלגוריתמים קוונטיים לניתוח נתונים טופולוגי", arXiv: 2209.14286.
[2] ברנרדו אמניירו, וסיליוס מרולאס וג'ורג' סיאופסיס, "הומולוגיה מתמשכת קוונטית", 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, and Ryan Babbush, "Quantifying Quantum Advantage in Analysis Data Topological", arXiv: 2209.13581.
[4] Iordanis Kerenidis ואנופאם פראקש, "למידת מכונה קוונטית עם מצבי תת-מרחב", arXiv: 2202.00054.
[5] ברנרדו אמניירו, ג'ורג' סיאופסיס, ו-וסיליוס מרולאס, "הומולוגיה מתמשכת קוונטית לסדרות זמן", arXiv: 2211.04465.
[6] סיימון אפרס, סיאנטן סן ודניאל סבו, "אלגוריתם קלאסי (פשוט) להערכת מספרי בטי", arXiv: 2211.09618.
[7] סם מקארדל, אנדראש גיליין ומריו ברטה, "אלגוריתם קוונטי יעיל לניתוח נתונים טופולוגי עם פחות קיוביטים באופן אקספוננציאלי", arXiv: 2209.12887.
[8] אנדרו ולאסיץ' ואנה פאם, "הבנת המיפוי של נתוני מקודד באמצעות יישום של ניתוח טופולוגי קוונטי", arXiv: 2209.10596.
הציטוטים לעיל הם מ- מודעות SAO / NASA (עודכן לאחרונה בהצלחה 2022-12-07 16:42:14). הרשימה עשויה להיות שלמה מכיוון שלא כל בעלי האתרים מספקים נתוני ציטוט ראויים ומלאים.
לא ניתן היה להביא נתונים מצוטטים על ידי קרוסרף במהלך ניסיון אחרון 2022-12-07 16:42:12: לא ניתן היה להביא נתונים שהובאו עבור 10.22331 / q-2022-12-07-873 מקרוסרף. זה נורמלי אם ה- DOI נרשם לאחרונה.
מאמר זה מתפרסם בקוונטים תחת התקציב ייחוס Creative Commons 4.0 הבינלאומי (CC BY 4.0) רישיון. זכויות יוצרים נשארות עם בעלי זכויות היוצרים המקוריים כמו המחברים או מוסדותיהם.
