Институт теоретической физики Юкавы, Университет Киото, Киташиракава Оивакэчо, Сакёку, Киото 606-8502, Япония
Находите эту статью интересной или хотите обсудить? Scite или оставить комментарий на SciRate.
Абстрактные
Топологический анализ данных (TDA) — новая область анализа данных. Важнейшим шагом TDA является вычисление постоянных чисел Бетти. Существующие классические алгоритмы для TDA ограничены, если мы хотим учиться на многомерных топологических функциях, потому что количество многомерных симплексов растет экспоненциально в размере данных. В контексте квантовых вычислений ранее было показано, что существует эффективный квантовый алгоритм для оценки чисел Бетти даже в больших размерностях. Однако числа Бетти менее общие, чем постоянные числа Бетти, и не существует квантовых алгоритмов, которые могут оценивать постоянные числа Бетти произвольной размерности.
В этой статье показан первый квантовый алгоритм, который может оценивать ($нормализованные$) персистентные числа Бетти произвольной размерности. Наш алгоритм эффективен для симплициальных комплексов, таких как комплекс Виеториса-Рипса, и демонстрирует экспоненциальное ускорение по сравнению с известными классическими алгоритмами.
► Данные 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] Джонатан Ариэль Бармак и Элиас Габриэль Миниан. Сильные гомотопические типы, нервы и коллапсы. Дискретная и вычислительная геометрия, 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] Питер Бубеник и др. Статистический топологический анализ данных с использованием персистентных ландшафтов. Дж. Мах. Учиться. Рез., 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 quant-ph/0410184, 2004. 10.48550/arXiv.quant-ph/0410184.
https:///doi.org/10.48550/arXiv.quant-ph/0410184
Arxiv: колич-фот / 0410184
[11] Эдоардо Ди Наполи, Эрик Полицци и Юсеф Саад. Эффективная оценка количества собственных значений в интервале. Численная линейная алгебра с приложениями, 23 (4): 674–692, 2016. 10.1002/nla.2048.
https:///doi.org/10.1002/nla.2048
[12] Роберт Дике. Когерентность в процессах спонтанного излучения. Physical Review, 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] Джоэл Фридман. Вычисление чисел Бетти с помощью комбинаторных лапласианов. Algorithmica, 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] Андраш Гильен, Юань Су, Гуан Хао Лоу и Натан Вибе. Квантовое преобразование сингулярных значений и не только: экспоненциальные улучшения квантовой матричной арифметики. В материалах 51-го ежегодного симпозиума ACM SIGACT по теории вычислений, стр. 193–204, 2019 г. 10.1145/3313276.3316366.
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 arXiv:2111.00433v1, 2021. 10.48550/arXiv.2111.00433.
https:///doi.org/10.48550/arXiv.2111.00433
Arxiv: 2111.00433v1
[22] Рю Хаякава, Томоюки Моримаэ и Сугуру Тамаки. Детальное квантовое превосходство, основанное на ортогональных векторах, кратчайших путях с тремя суммами и всеми парами. Препринт arXiv arXiv:3, 1902.08382. 2019/arXiv.10.48550.
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 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] Сет Ллойд, Сильвано Гарнероне и Паоло Дзанарди. Квантовые алгоритмы топологического и геометрического анализа данных. Nature Communications, 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] РАЙ Мейер. Кластеризация с использованием квантовой устойчивой гомологии. Кандидатская диссертация, 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-г
[35] Патрик Ролл. Более быстрые когерентные квантовые алгоритмы для оценки фазы, энергии и амплитуды. Quantum, 5: 566, 2021. 10.22331/q-2021-10-19-566.
https://doi.org/10.22331/q-2021-10-19-566
[36] Абу Бакар Сиддик, Саадия Фарид и Мухаммад Тахир. Доказательство биекции для комбинаторной системы счисления. Препринт arXiv 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. URL https:///scipost.org/10.21468/SciPostPhys.11.3.060.
https: / / doi.org/ 10.21468 / SciPostPhys.11.3.060
[38] Шашанка Убару, Исмаил Юнус Ахалвая, Марк С. Сквилланте, Кеннет Л. Кларксон и Лиор Хореш. Квантовый топологический анализ данных с линейной глубиной и экспоненциальным ускорением. Препринт arXiv arXiv:2108.02811, 2021. 10.48550/arXiv.2108.02811.
https:///doi.org/10.48550/arXiv.2108.02811
Arxiv: 2108.02811
[39] Руи Ван, Дук Зуй Нгуен и Го-Вэй Вэй. Постоянный спектральный график. Международный журнал численных методов в биомедицинской инженерии, 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] Афра Зомородян и Гуннар Карлссон. Вычисление стойкой гомологии. Discrete & Computational Geometry, 33 (2): 249–274, 2005. 10.1007/s00454-004-1146-y.
https: / / doi.org/ 10.1007 / s00454-004-1146-й
Цитируется
[1] Александр Шмидхубер и Сет Ллойд, «Теоретико-сложные ограничения квантовых алгоритмов для топологического анализа данных», Arxiv: 2209.14286.
[2] Бернардо Аменейро, Василиос Марулас и Джордж Сиопсис, «Квантовая постоянная гомология», Arxiv: 2202.12965.
[3] Доминик В. Берри, Юань Су, Каспер Гюрик, Робби Кинг, Жоао Бассо, Александр Дель Торо Барба, Абхишек Раджпут, Натан Вибе, Ведран Дунько и Райан Баббуш, «Количественная оценка квантовых преимуществ в топологическом анализе данных», Arxiv: 2209.13581.
[4] Иорданис Керенидис и Анупам Пракаш, «Квантовое машинное обучение с подпространственными состояниями», Arxiv: 2202.00054.
[5] Бернардо Аменейро, Джордж Сиопсис и Василиос Марулас, «Квантовая постоянная гомология для временных рядов», Arxiv: 2211.04465.
[6] Саймон Аперс, Саянтан Сен и Даниэль Сабо, «(Простой) классический алгоритм для оценки чисел Бетти», Arxiv: 2211.09618.
[7] Сэм МакАрдл, Андраш Гильен и Марио Берта, «Упрощенный квантовый алгоритм для топологического анализа данных с экспоненциально меньшим количеством кубитов», Arxiv: 2209.12887.
[8] Эндрю Власик и Ан Фам, «Понимание отображения данных кодирования с помощью реализации квантово-топологического анализа», Arxiv: 2209.10596.
Приведенные цитаты из САО / НАСА 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) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.
