京都大学汤河理论物理研究所，北京都，北kyo川大和町606-8502，日本
觉得本文有趣或想讨论？ 在SciRate上发表评论或发表评论.
抽象
拓扑数据分析（TDA）是数据分析的一个新兴领域。 TDA 的关键步骤是计算持久的 Betti 数字。 如果我们想从高维拓扑特征中学习，现有的 TDA 经典算法是有限的，因为高维单纯形的数量随着数据的大小呈指数增长。 在量子计算的背景下，先前已经表明存在一种有效的量子算法，即使在高维中也能估计 Betti 数。 然而，Betti 数不如持久 Betti 数通用，并且还没有可以估计任意维度的持久 Betti 数的量子算法。
本文展示了第一个可以估计任意维度的 ($normalized$) 持久 Betti 数的量子算法。 我们的算法对于诸如 Vietoris-Rips 复形的单纯复形是有效的，并且展示了比已知经典算法更高的指数加速。
►BibTeX数据
►参考
[1] Mehmet E Aktas、Esra Akbas 和 Ahmed El Fatmaoui。 网络的持久性同源性：方法和应用。 应用网络科学，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。 强同伦类型、紧张和崩溃。 离散与计算几何，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 状态的确定性准备。 在国际计算理论基础研讨会上，第 126-139 页。 施普林格，2019/ 10.1007-978-3-030-25027_0。
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] 彼得布贝尼克等人。 使用持久性景观的统计拓扑数据分析。 J.马赫。 学。 研究，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] 张何以仪、郭慈超和刘立志。 快速矩阵秩算法和应用。 ACM 杂志 (JACM)，60 (5): 1–25, 2013. 10.1145/2528404。
https：/ / doi.org/10.1145/ 2528404
[8] David Cohen-Steiner、Herbert Edelsbrunner 和 John Harer。 持久性图的稳定性。 离散与计算几何，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。 弦景观的拓扑数据分析。 高能物理学报, 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。 区间内特征值计数的有效估计。 数值线性代数及其应用，23 (4): 674–692, 2016. 10.1002/ nla.2048。
https:// / doi.org/ 10.1002/ nla.2048
[12] 罗伯特·H·迪克。 自发辐射过程的相干性。 物理评论，93 (1): 99, 1954. 10.1103/ PhysRev.93.99。
https：/ / doi.org/ 10.1103 / PhysRev.93.99
[13] 赫伯特·埃德尔斯布伦纳和约翰·哈勒。 计算拓扑：介绍。 美国数学学会，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 等人。 持久同源性调查。 当代数学, 453: 257–282, 2008. 10.1090/ conm/ 453/ 08802。
https：/ ‐ / doi.org/10.1090/conm/453/08802
[16] 乔尔·弗里德曼。 通过组合拉普拉斯算子计算 betti 数。 算法, 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、袁苏、Guang Hao Low 和 Nathan Wiebe。 量子奇异值变换及超越：量子矩阵算术的指数改进。 在第 51 届年度 ACM SIGACT 计算理论研讨会论文集上，第 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/ arXiv.10.48550。
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] 早川龙。 用于持久 betti 数和拓扑数据分析的量子算法。 arXiv 预印本 arXiv:2111.00433v1, 2021/ arXiv.10.48550。
https://doi.org/10.48550/arXiv.2111.00433
arXiv：2111.00433v1
[22] Ryu Hayakawa、Tomoyuki Morimae 和 Suguru Tamaki。 基于正交向量、3 和和所有对最短路径的细粒度量子霸权。 arXiv 预印本 arXiv:1902.08382, 2019/ arXiv.10.48550。
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。 具有线性电路复杂性的 n-qubit toffoli 门的分解。 国际理论物理学杂志，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。 在量子处理器上演示拓扑数据分析。 光学, 5 (2): 193–198, 2018. 10.1364/ OPTICA.5.000193。
https：///doi.org/10.1364/OPTICA.5.000193
[25] Lek-Heng Lim。 图上的霍奇拉普拉斯算子。 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] Seth Lloyd、Silvano Garnerone 和 Paolo Zanardi。 用于数据拓扑和几何分析的量子算法。 自然通讯，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 量子，2 (4)：040203，2021/ PRXQuantum.10.1103。
https：/ / doi.org/ 10.1103 / PRXQuantum.2.040203
[29] 拉吉梅杰。 使用量子持久同源性聚类。 硕士论文, 2019.
[30] Facundo Mémoli、Zhengchao Wan 和 Yusu Wang。 持久性拉普拉斯算子：属性、算法和含义。 SIAM 数据科学数学杂志，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/ arXiv.10.48550。
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 数据科学，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 数字方面的拓扑结构。 皇家天文学会月刊，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] 帕特里克·拉尔。 用于相位、能量和振幅估计的更快的相干量子算法。 量子，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/ arXiv.10.48550。
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. 网址 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/arXiv.10.48550。
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] 柯林夏和郭薇薇。 蛋白质结构、柔韧性和折叠的持久同源性分析。 国际生物医学工程数值方法杂志, 30 (8): 814–844, 2014. 10.1002/ cnm.2655.
https:// / doi.org/ 10.1002/ cnm.2655
[42] Afra Zomorodian 和 Gunnar Carlsson。 计算持久同源性。 离散与计算几何，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、Vasileios Maroulas 和 George Siopsis，“量子持久同源性”， 的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，“量化拓扑数据分析中的量子优势”， 的arXiv：2209.13581.
[4] Iordanis Kerenidis 和 Anupam Prakash，“具有子空间状态的量子机器学习”， 的arXiv：2202.00054.
[5] Bernardo Ameneyro、George Siopsis 和 Vasileios Maroulas，“时间序列的量子持久同源性”， 的arXiv：2211.04465.
[6] Simon Apers、Sayantan Sen 和 Dániel Szabó，“用于估计 Betti 数的（简单）经典算法”， 的arXiv：2211.09618.
[7] Sam McArdle、András Gilyén 和 Mario Berta，“用于拓扑数据分析的简化量子算法，量子位呈指数级减少”， 的arXiv：2209.12887.
[8] Andrew Vlasic 和 Anh Pham，“通过实施量子拓扑分析了解编码数据的映射”， 的arXiv：2209.10596.
以上引用来自 SAO / NASA广告 （最近成功更新为2022-12-07 16:42:14）。 该列表可能不完整，因为并非所有发布者都提供合适且完整的引用数据。
无法获取 Crossref引用的数据 在上一次尝试2022-12-07 16:42:12期间：无法从Crossref获取10.22331 / q-2022-12-07-873的引用数据。 如果DOI是最近注册的，这是正常的。
该论文发表在《量子》杂志上 国际知识共享署名署名4.0（CC BY 4.0） 执照。 版权归原始版权持有者所有，例如作者或其所在机构。
