مؤسسه فیزیک نظری یوکاوا، دانشگاه کیوتو، کیتاشیراکاوا اویواکچو، ساکیوکو، کیوتو 606-8502، ژاپن
این مقاله را جالب می دانید یا می خواهید بحث کنید؟ SciRate را ذکر کنید یا در SciRate نظر بدهید.
چکیده
تجزیه و تحلیل داده های توپولوژیکی (TDA) یک حوزه نوظهور تجزیه و تحلیل داده ها است. مرحله مهم TDA محاسبه اعداد Betti پایدار است. اگر بخواهیم از ویژگی‌های توپولوژیکی با ابعاد بالا یاد بگیریم، الگوریتم‌های کلاسیک موجود برای TDA محدود هستند، زیرا تعداد ساده‌سازی‌های با ابعاد بالا به طور تصاعدی در اندازه داده‌ها افزایش می‌یابد. در زمینه محاسبات کوانتومی، قبلا نشان داده شده است که یک الگوریتم کوانتومی کارآمد برای تخمین اعداد بتی حتی در ابعاد بالا وجود دارد. با این حال، اعداد بتی کمتر از اعداد بتی پایدار هستند، و هیچ الگوریتم کوانتومی وجود ندارد که بتواند اعداد بتی پایدار ابعاد دلخواه را تخمین بزند.
این مقاله اولین الگوریتم کوانتومی را نشان می‌دهد که می‌تواند اعداد بتی پایدار ($normalized$) ابعاد دلخواه را تخمین بزند. الگوریتم ما برای مجتمع‌های ساده مانند مجتمع Vietoris-Rips کارآمد است و سرعت نمایی را نسبت به الگوریتم‌های کلاسیک شناخته‌شده نشان می‌دهد.
► داده های BibTeX
◄ مراجع
[1] مهمت ای آکتاش، اسرا اکباس و احمد الفتماوی. همسانی تداوم شبکه ها: روش ها و کاربردها علوم شبکه کاربردی، 4 (1): 1–28، 2019. 10.1007/s41109-019-0179-3.
https://doi.org/10.1007/s41109-019-0179-3
[2] جاناتان آریل بارمک و الیاس گابریل مینیان. انواع هموتوپی قوی، اعصاب و فروپاشی. هندسه گسسته و محاسباتی، 47 (2): 301-328، 2012. 10.1007/s00454-011-9357-5.
https://doi.org/10.1007/s00454-011-9357-5
[3] آندریاس بارتشی و استفان آیدنبنز آماده سازی قطعی حالات دیک. در سمپوزیوم بین المللی مبانی نظریه محاسبات، صفحات 126-139. Springer, 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] پیتر بوبنیک و همکاران تجزیه و تحلیل داده های توپولوژیکی آماری با استفاده از مناظر پایدار جی. ماخ. فرا گرفتن. Res., 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] هو یی چونگ، تز چیو کوک و لپ چی لاو. الگوریتم ها و برنامه های کاربردی رتبه بندی سریع ماتریس. مجله 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] الکس کول و گری شیو. تجزیه و تحلیل داده های توپولوژیکی برای چشم انداز رشته. مجله فیزیک انرژی بالا، 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] ادواردو دی ناپولی، اریک پولیزی و یوسف سعد. تخمین کارآمد شمارش مقادیر ویژه در یک بازه زمانی. جبر خطی عددی با کاربردها، 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. IEEE، 463. 2000/s10.1007-00454-002-2885.
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] جوئل فریدمن. محاسبه اعداد بتی از طریق لاپلاسیان های ترکیبی الگوریتمیکا، 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] آندراس گیلین، یوان سو، گوانگ هائو لو، و ناتان ویبه. تبدیل مقدار تکین کوانتومی و فراتر از آن: بهبودهای نمایی برای محاسبات ماتریس کوانتومی در مجموعه مقالات پنجاه و یکمین سمپوزیوم سالانه ACM SIGACT در نظریه محاسبات، صفحات 51-193، 204. 2019/10.1145.
https://doi.org/10.1145/3313276.3316366
[19] سم گان و نیلز کورنراپ بررسی یک الگوریتم کوانتومی برای اعداد بتی پیش چاپ arXiv 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] ریو هایاکاوا، تومویوکی موریما و سوگورو تاماکی. برتری کوانتومی ریز دانه بر اساس بردارهای متعامد، کوتاه ترین مسیرهای 3 مجموع و تمام جفت. پیش چاپ arXiv arXiv:1902.08382، 2019. 10.48550/arXiv.1902.08382.
https://doi.org/10.48550/arXiv.1902.08382
arXiv: 1902.08382
[23] یونگ هی، مینگ-زینگ لو، ای ژانگ، هونگ-که وانگ و شیائو-فنگ وانگ. تجزیه دروازه های توفولی n-کیوبیت با پیچیدگی مدار خطی. مجله بین المللی فیزیک نظری، 56 (7): 2350-2361، 2017. 10.1007/s10773-017-3389-4.
https://doi.org/10.1007/s10773-017-3389-4
[24] هی لیانگ هوانگ، شی لین وانگ، پیتر پی روده، یی هان لو، یو وی ژائو، چانگ لیو، لی لی، نای لیو، چائو یانگ لو و جیان وی پان. نمایش تجزیه و تحلیل داده های توپولوژیکی بر روی یک پردازنده کوانتومی. Optica, 5 (2): 193–198, 2018. 10.1364/OPTICA.5.000193.
https://doi.org/10.1364/OPTICA.5.000193
[25] لک هنگ لیم. لاپلاسیان هاج روی نمودارها. بررسی SIAM، 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] فاکوندو ممولی، ژنگ چائو وان و یوسو وانگ. لاپلاسیان های پایدار: ویژگی ها، الگوریتم ها و مفاهیم SIAM Journal on Mathematics of Data Science, 4 (2): 858-884, 2022. 10.1137/21M1435471.
https://doi.org/10.1137/21M1435471
[31] نیلز نویمان و استر دن بریژن. محدودیت های خوشه بندی با استفاده از همسانی پایدار کوانتومی پیش چاپ arXiv 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] پراتیوش پراناو، هربرت ادلسبرونر، رین وان د وایگارت، گرت وگتر، مایکل کربر، برنارد جی تی جونز و ماتیج وینتراکن. توپولوژی وب کیهانی از نظر اعداد بتی پایدار. اعلامیه های ماهانه انجمن سلطنتی نجوم، 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] شاشانکا اوبارو، اسماعیل یونس آخالوایا، مارک اس اسکیلانته، کنت ال کلارکسون و لیور هورش. تجزیه و تحلیل داده های توپولوژیکی کوانتومی با عمق خطی و سرعت نمایی. 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] کلین شیا و گو-وی وی. تجزیه و تحلیل همولوژی پایدار ساختار پروتئین، انعطاف پذیری و تاخوردگی. مجله بین المللی برای روش های عددی در مهندسی زیست پزشکی، 30 (8): 814-844، 2014. 10.1002/cnm.2655.
https://doi.org/10.1002/cnm.2655
[42] افرا زمردیان و گونار کارلسون. محاسبه همسانی پایدار هندسه گسسته و محاسباتی، 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] دومینیک دبلیو بری، یوان سو، کاسپر گیوریک، رابی کینگ، جوآئو باسو، الکساندر دل تورو باربا، آبیشک راجپوت، ناتان ویبه، ودران دانکو و رایان بابوش، "کمی سازی مزیت کوانتومی در تجزیه و تحلیل داده های توپولوژیکی". arXiv: 2209.13581.
[4] یوردانیس کرنیدیس و آنوپام پراکاش، "یادگیری ماشین کوانتومی با حالات زیرفضایی"، arXiv: 2202.00054.
[5] برناردو آمنیرو، جورج سیوپسیس، و واسیلیوس مارولاس، «همسانی پایدار کوانتومی برای سری‌های زمانی»، arXiv: 2211.04465.
[6] Simon Apers، Sayantan Sen و Dániel Szabó، "یک الگوریتم کلاسیک (ساده) برای تخمین اعداد بتی" arXiv: 2211.09618.
[7] سام مک‌آردل، آندراس گیلین، و ماریو برتا، «یک الگوریتم کوانتومی کارآمد برای تجزیه و تحلیل داده‌های توپولوژیکی با نمایی کمتر» arXiv: 2209.12887.
[8] اندرو ولاسیک و آن فام، "درک نگاشت داده های رمزگذاری شده از طریق اجرای تحلیل توپولوژیکی کوانتومی"، arXiv: 2209.10596.
نقل قول های بالا از SAO/NASA Ads (آخرین به روز رسانی با موفقیت 2022-12-07 16:42:14). فهرست ممکن است ناقص باشد زیرا همه ناشران داده های استنادی مناسب و کاملی را ارائه نمی دهند.
واکشی نشد داده های استناد شده متقاطع در آخرین تلاش 2022-12-07 16:42:12: داده های استناد شده برای 10.22331/q-2022-12-07-873 از Crossref دریافت نشد. اگر DOI اخیراً ثبت شده باشد، طبیعی است.
این مقاله در Quantum تحت عنوان منتشر شده است Creative Commons Attribution 4.0 International (CC BY 4.0) مجوز. حق چاپ نزد دارندگان حق چاپ اصلی مانند نویسندگان یا مؤسسات آنها باقی می ماند.
