Viện Vật lý Lý thuyết Yukawa, Đại học Kyoto, Kitashirakawa Oiwakecho, Sakyoku, Kyoto 606-8502, Nhật Bản
Tìm bài báo này thú vị hay muốn thảo luận? Scite hoặc để lại nhận xét về SciRate.
Tóm tắt
Phân tích dữ liệu tôpô (TDA) là một lĩnh vực phân tích dữ liệu mới nổi. Bước quan trọng của TDA là tính toán số Betti liên tục. Các thuật toán cổ điển hiện tại cho TDA bị hạn chế nếu chúng ta muốn học từ các đặc điểm tôpô chiều cao vì số lượng đơn giản chiều cao tăng theo cấp số nhân theo kích thước của dữ liệu. Trong bối cảnh tính toán lượng tử, trước đây người ta đã chứng minh rằng tồn tại một thuật toán lượng tử hiệu quả để ước tính số Betti ngay cả ở các chiều cao. Tuy nhiên, số Betti ít tổng quát hơn số Betti liên tục và không có thuật toán lượng tử nào có thể ước tính số Betti liên tục có kích thước tùy ý.
Bài viết này trình bày thuật toán lượng tử đầu tiên có thể ước tính số lượng Betti liên tục ($ chuẩn hóa $) có kích thước tùy ý. Thuật toán của chúng tôi hiệu quả đối với các phức hợp đơn giản như phức hợp Vietoris-Rips và thể hiện tốc độ tăng theo cấp số nhân so với các thuật toán cổ điển đã biết.
► Dữ liệu BibTeX
► Tài liệu tham khảo
[1] Mehmet E Aktas, Esra Akbas và Ahmed El Fatmaoui. Tương đồng bền bỉ của mạng: phương pháp và ứng dụng. Khoa học mạng ứng dụng, 4 (1): 1–28, 2019. 10.1007/s41109-019-0179-3.
https://doi.org/10.1007/s41109-019-0179-3
[2] Jonathan Ariel Barmak và Elias Gabriel Minian. Các loại đồng luân mạnh mẽ, thần kinh và sụp đổ. Hình học rời rạc và tính toán, 47 (2): 301–328, 2012. 10.1007/s00454-011-9357-5.
https://doi.org/10.1007/s00454-011-9357-5
[3] Andreas Bärtschi và Stephan Eidenbenz. Sự chuẩn bị tất định của các trạng thái Dicke. Trong Hội nghị chuyên đề quốc tế về nguyên tắc cơ bản của lý thuyết tính toán, trang 126–139. Springer, 2019. 10.1007/978-3-030-25027-0_9.
https://doi.org/10.1007/978-3-030-25027-0_9
[4] Gilles Brassard, Peter Hoyer, Michele Mosca và Alain Tapp. Khuếch đại và ước lượng biên độ lượng tử. Toán học đương đại, 305: 53–74, 2002. 10.1090 / conm / 305/05215.
https: / / doi.org/ 10.1090 / conm / 305/05215
[5] Peter Bubenik và cộng sự. Phân tích dữ liệu tôpô thống kê bằng cách sử dụng cảnh quan bền vững. J. Mach. Học hỏi. Nghị quyết, 16 (1): 77–102, 2015. 10.5555/2789272.2789275.
https: / / doi.org/ 10.5555 / 2789272.2789275
[6] Frédéric Chazal và Bertrand Michel. Giới thiệu về phân tích dữ liệu tôpô: các khía cạnh cơ bản và thực tiễn dành cho các nhà khoa học dữ liệu. Biên giới trong trí tuệ nhân tạo, ngày 4 năm 2021. 10.3389/frai.2021.667963.
https:///doi.org/10.3389/frai.2021.667963
[7] Ho Yee Cheung, Tsz Chiu Kwok và Lập Chi Lau. Các thuật toán và ứng dụng xếp hạng ma trận nhanh. Tạp chí của ACM (JACM), 60 (5): 1–25, 2013. 10.1145/2528404.
https: / / doi.org/ 10.1145 / 2528404
[8] David Cohen-Steiner, Herbert Edelsbrunner và John Harer. Tính ổn định của biểu đồ bền vững Hình học rời rạc và tính toán, 37 (1): 103–120, 2007. 10.1007/s00454-006-1276-5.
https://doi.org/10.1007/s00454-006-1276-5
[9] Alex Cole và Gary Shiu. Phân tích dữ liệu tôpô cho cảnh quan chuỗi. Tạp chí Vật lý Năng lượng Cao, 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 và David Petrie Moulton. Một mạch cộng mang gợn sóng lượng tử mới. arXiv bản in trước 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 và Yousef Saad. Ước tính hiệu quả số lượng giá trị riêng trong một khoảng. Đại số tuyến tính số có ứng dụng, 23 (4): 674–692, 2016. 10.1002/nla.2048.
https:///doi.org/10.1002/nla.2048
[12] Robert H Dicke. Sự kết hợp trong các quá trình bức xạ tự phát. Đánh giá vật lý, 93 (1): 99, 1954. 10.1103/PhysRev.93.99.
https: / / doi.org/ 10.1103 / PhysRev93.99
[13] Herbert Edelsbrunner và John Harer. Cấu trúc liên kết tính toán: giới thiệu. Hiệp hội Toán học Hoa Kỳ, 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 và Afra Zomorodian. Sự bền bỉ và đơn giản hóa cấu trúc liên kết. Trong Kỷ yếu hội nghị chuyên đề thường niên lần thứ 41 về nền tảng của khoa học máy tính, trang 454–463. IEEE, 2000. 10.1007/s00454-002-2885-2.
https://doi.org/10.1007/s00454-002-2885-2
[15] Herbert Edelsbrunner, John Harer và cộng sự. Tương đồng dai dẳng-một cuộc khảo sát. Toán học đương đại, 453: 257–282, 2008. 10.1090/conm/453/08802.
https: / / doi.org/ 10.1090 / conm / 453/08802
[16] Joel Friedman. Tính toán số lượng betti thông qua laplacians tổ hợp. Algorithmica, 21 (4): 331–346, 1998. 10.1007/PL00009218.
https: / / doi.org/ 10.1007 / PL00009218
[17] Robert Grist. Mã vạch: cấu trúc liên kết liên tục của dữ liệu. Bản tin của Hiệp hội Toán học Hoa Kỳ, 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 và Nathan Wiebe. Biến đổi giá trị kỳ dị lượng tử và hơn thế nữa: cải tiến theo cấp số nhân cho số học ma trận lượng tử. Trong Kỷ yếu của Hội nghị chuyên đề ACM SIGACT thường niên lần thứ 51 về Lý thuyết điện toán, trang 193–204, 2019. 10.1145/3313276.3316366.
https: / / doi.org/ 10.1145 / 3313276.3316366
[19] Sam Gunn và Niels Kornerup. Xem xét thuật toán lượng tử cho số betti. bản in trước arXiv arXiv:1906.07673, 2019. 10.48550/arXiv.1906.07673.
https: / / doi.org/ 10.48550 / arXiv.1906.07673
arXiv: 1906.07673
[20] Aram W Harrow, Avinatan Hassidim và Seth Lloyd. Thuật toán lượng tử cho hệ phương trình tuyến tính. Thư đánh giá vật lý, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
[21] Ryu Hayakawa. Thuật toán lượng tử cho số lượng betti liên tục và phân tích dữ liệu tôpô. bản in trước arXiv 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 và Suguru Tamaki. Ưu thế lượng tử chi tiết dựa trên các vectơ trực giao, đường đi ngắn nhất tổng 3 và tất cả các cặp. bản in trước arXiv arXiv:1902.08382, 2019. 10.48550/arXiv.1902.08382.
https: / / doi.org/ 10.48550 / arXiv.1902.08382
arXiv: 1902.08382
[23] Yong He, Ming-Xing Luo, E Zhang, Hong-Ke Wang và Xiao-Feng Wang. Sự phân hủy của cổng toffoli n-qubit với độ phức tạp của mạch tuyến tính. Tạp chí Vật lý Lý thuyết Quốc tế, 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 và Jian-Wei Pan. Trình diễn phân tích dữ liệu tôpô trên bộ xử lý lượng tử. Optica, 5 (2): 193–198, 2018. 10.1364/OPTICA.5.000193.
https: / / doi.org/ 10.1364 / OPTICA.5.000193
[25] Lê Hằng Lâm. Hodge laplacians trên đồ thị. Tạp chí SIAM, 62 (3): 685–715, 2020. 10.1137/18M1223101.
https: / / doi.org/ 10.1137 / 18M1223101
[26] Lin Lin, Yousef Saad và Chao Yang. Xấp xỉ mật độ phổ của ma trận lớn. Tạp chí SIAM, 58 (1): 34–65, 2016. 10.1137/130934283.
https: / / doi.org/ 10.1137 / 130934283
[27] Seth Lloyd, Silvano Garnerone và Paolo Zanardi. Các thuật toán lượng tử để phân tích cấu trúc liên kết và hình học của dữ liệu. Truyền thông tự nhiên, 7 (1): 1–7, 2016. 10.1038/ncomms10138.
https: / / doi.org/ 10.1038 / ncomms10138
[28] John M Martyn, Zane M Rossi, Andrew K Tan và Isaac L Chuang. Sự thống nhất lớn của các thuật toán lượng tử. PRX Quantum, 2 (4): 040203, 2021. 10.1103/PRXQuantum.2.040203.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
[29] RHAJ Meijer. Phân cụm bằng cách sử dụng tương đồng lượng tử liên tục. Luận văn thạc sĩ, 2019.
[30] Facundo Mémoli, Zhengchao Wan, và Yusu Wang. Người laplacian dai dẳng: Thuộc tính, thuật toán và ý nghĩa. Tạp chí SIAM về Toán học của Khoa học Dữ liệu, 4 (2): 858–884, 2022. 10.1137/21M1435471.
https: / / doi.org/ 10.1137 / 21M1435471
[31] Niels Neumann và Sterre den Breeijen. Hạn chế của việc phân cụm bằng cách sử dụng tương đồng lượng tử liên tục. bản in trước arXiv arXiv:1911.10781, 2019. 10.48550/arXiv.1911.10781.
https: / / doi.org/ 10.48550 / arXiv.1911.10781
arXiv: 1911.10781
[32] Nina Otter, Mason A Porter, Ulrike Tillmann, Peter Grindrod và Heather A Harrington. Lộ trình tính toán sự tương đồng liên tục. Khoa học dữ liệu 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 và Mathijs Wintraecken. Cấu trúc liên kết của mạng vũ trụ về số lượng betti liên tục. Thông báo hàng tháng của Hiệp hội Thiên văn Hoàng gia, 465 (4): 4281–4310, 2017. 10.1093/mnras/stw2862.
https:///doi.org/10.1093/mnras/stw2862
[34] Chi Seng Pun, Si Xian Lee và Kelin Xia. Học máy dựa trên tính tương đồng liên tục: một cuộc khảo sát và nghiên cứu so sánh. Đánh giá về Trí tuệ Nhân tạo, trang 1–45, 2022. 10.1007/s10462-022-10146-z.
https: / / doi.org/ 10.1007 / s10462-022-10146-z
[35] Patrick Rall. Các thuật toán lượng tử mạch lạc nhanh hơn để ước tính pha, năng lượng và biên độ. Lượng tử, 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 và Muhammad Tahir. Chứng minh song ánh cho hệ thống số tổ hợp. bản in trước arXiv arXiv:1601.05794, 2016. 10.48550/arXiv.1601.05794.
https: / / doi.org/ 10.48550 / arXiv.1601.05794
arXiv: 1601.05794
[37] Daniel Spitz, Jürgen Berges, Markus Oberthaler và Anna Wienhard. Tìm kiếm hành vi tự tương tự trong động lực học nhiều vật thể lượng tử thông qua sự tương đồng bền bỉ. 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] Shashanka Ubaru, Ismail Yunus Akhalwaya, Mark S Squillante, Kenneth L Clarkson và Lior Horesh. Phân tích dữ liệu tôpô lượng tử với độ sâu tuyến tính và tăng tốc theo cấp số nhân. bản in trước arXiv 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. Đồ thị phổ liên tục. Tạp chí quốc tế về phương pháp số trong kỹ thuật y sinh, 36 (9): e3376, 2020. 10.1002/cnm.3376.
https:///doi.org/10.1002/cnm.3376
[40] Larry Wasserman. Phân tích dữ liệu topo. Đánh giá hàng năm về thống kê và ứng dụng của nó, 5: 501–532, 2018. 10.1146/annurev-statistics-031017-100045.
https:///doi.org/10.1146/annurev-statistics-031017-100045
[41] Kelin Xia và Guo-Wei Wei. Phân tích tương đồng liên tục về cấu trúc, tính linh hoạt và khả năng gấp nếp của protein. Tạp chí quốc tế về phương pháp số trong kỹ thuật y sinh, 30 (8): 814–844, 2014. 10.1002/cnm.2655.
https:///doi.org/10.1002/cnm.2655
[42] Afra Zomorodian và Gunnar Carlsson. Tính toán tương đồng liên tục. Hình học rời rạc và tính toán, 33 (2): 249–274, 2005. 10.1007/s00454-004-1146-y.
https: / / doi.org/ 10.1007 / s00454-004-1146-y
Trích dẫn
[1] Alexander Schmidhuber và Seth Lloyd, “Những hạn chế về mặt lý thuyết phức tạp đối với các thuật toán lượng tử để phân tích dữ liệu tôpô”, arXiv: 2209.14286.
[2] Bernardo Ameneyro, Vasileios Maroulas và George Siopsis, “Sự tương đồng liên tục lượng tử”, 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 và Ryan Babbush, “Định lượng lợi thế lượng tử trong phân tích dữ liệu cấu trúc liên kết”, arXiv: 2209.13581.
[4] Iordanis Kerenidis và Anupam Prakash, “Máy học lượng tử với các trạng thái không gian con”, arXiv: 2202.00054.
[5] Bernardo Ameneyro, George Siopsis và Vasileios Maroulas, “Sự tương đồng liên tục lượng tử cho chuỗi thời gian”, arXiv: 2211.04465.
[6] Simon Apers, Sayantan Sen và Dániel Szabó, “Thuật toán cổ điển (đơn giản) để ước tính số Betti”, arXiv: 2211.09618.
[7] Sam McArdle, András Gilyén và Mario Berta, “Một thuật toán lượng tử được sắp xếp hợp lý để phân tích dữ liệu tôpô với số qubit ít hơn theo cấp số nhân”, arXiv: 2209.12887.
[8] Andrew Vlasic và Anh Pham, “Tìm hiểu về ánh xạ dữ liệu mã hóa thông qua việc triển khai phân tích cấu trúc liên kết lượng tử”, arXiv: 2209.10596.
Các trích dẫn trên là từ SAO / NASA ADS (cập nhật lần cuối thành công 2022 / 12-07 16:42:14). Danh sách có thể không đầy đủ vì không phải tất cả các nhà xuất bản đều cung cấp dữ liệu trích dẫn phù hợp và đầy đủ.
Không thể tìm nạp Crossref trích dẫn bởi dữ liệu trong lần thử cuối cùng 2022 / 12-07 16:42:12: Không thể tìm nạp dữ liệu được trích dẫn cho 10.22331 / q-2022 / 12-07-873 từ Crossref. Điều này là bình thường nếu DOI đã được đăng ký gần đây.
Bài viết này được xuất bản trong Lượng tử dưới Creative Commons Ghi công 4.0 Quốc tế (CC BY 4.0) giấy phép. Bản quyền vẫn thuộc về chủ sở hữu bản quyền gốc như các tác giả hoặc tổ chức của họ.
