Інститут теоретичної фізики Юкавы, Кіотський університет, Кітасіракава Ойвакечо, Сакіоку, Кіото 606-8502, Японія
Вам цей документ цікавий чи ви хочете обговорити? Скайте або залиште коментар на 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] Петро Бубеник та ін. Статистичний топологічний аналіз даних з використанням персистентних ландшафтів. Й. Мах. вчитися. Res., 16 (1): 77–102, 2015. 10.5555/2789272.2789275.
https: / / doi.org/ 10.5555 / 2789272.2789275
[6] Фредерік Шазаль і Бертран Мішель. Вступ до топологічного аналізу даних: фундаментальні та практичні аспекти для спеціалістів із обробки даних. Frontiers in artificial intelligence, 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] Алекс Коул і Гері Шиу. Топологічний аналіз даних для рядкового ландшафту. 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 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] Роберт Х. Діке. Когерентність у процесах спонтанного випромінювання. 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] Арам В. Харроу, Авінатан Хасидім і Сет Ллойд. Квантовий алгоритм для лінійних систем рівнянь. Physical Review Letters, 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] Рю Хаякава, Томоюкі Моріме та Сугуру Тамакі. Дрібнозерниста квантова перевага на основі ортогональних векторів, найкоротших шляхів із 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] Хе-Лян Хуан, Сі-Лін Ван, Пітер П Роде, І-Хан Луо, Ю-Вей Чжао, Чан Лю, Лі Лі, Най-Ле Лю, Чао-Ян Лу та Цзянь-Вей Пан. Демонстрація топологічного аналізу даних на квантовому процесорі. Оптика, 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] Пратюш Пранав, Герберт Едельсбруннер, Ріен Ван де Вейгарт, Герт Вегтер, Майкл Кербер, Бернард Дж. Т. Джонс і Матійс Вінтраекен. Топологія космічної мережі в термінах постійних чисел Бетті. Monthly Notices of the Royal Astronomical Society, 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 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] Ларрі Вассерман. Топологічний аналіз даних. Annual Review of Statistics and It Application, 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] Alexander Schmidhuber і Seth Lloyd, “Complexity-Teoretic Limitations on Quantum Algorithms for Topological Data Analysis”, 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.
Вищезазначені цитати від 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 на 4.0) ліцензія. Авторське право залишається за оригінальними власниками авторських прав, такими як автори або їх установи.
