Yukawa Institute for Theoretical Physics, Kyoto University, Kitashirakawa Oiwakecho, Sakyoku, Kyoto 606-8502, Jepang
Apakah makalah ini menarik atau ingin dibahas? Scite atau tinggalkan komentar di SciRate.
Abstrak
Analisis data topologi (TDA) adalah bidang analisis data yang muncul. Langkah kritis TDA adalah menghitung angka Betti yang persisten. Algoritma klasik yang ada untuk TDA terbatas jika kita ingin belajar dari fitur topologi dimensi tinggi karena jumlah simplis dimensi tinggi tumbuh secara eksponensial dalam ukuran data. Dalam konteks perhitungan kuantum, sebelumnya telah ditunjukkan bahwa terdapat algoritma kuantum yang efisien untuk memperkirakan bilangan Betti bahkan dalam dimensi tinggi. Namun, angka Betti kurang umum dibandingkan dengan angka Betti persisten, dan tidak ada algoritme kuantum yang dapat memperkirakan angka Betti persisten dari dimensi arbitrer.
Makalah ini menunjukkan algoritme kuantum pertama yang dapat memperkirakan angka Betti persisten ($ yang dinormalisasi $) dari dimensi arbitrer. Algoritme kami efisien untuk kompleks sederhana seperti kompleks Vietoris-Rips dan menunjukkan percepatan eksponensial dibandingkan algoritme klasik yang dikenal.
► data BibTeX
► Referensi
[1] Mehmet E Aktas, Esra Akbas, and Ahmed El Fatmaoui. Homologi ketekunan jaringan: metode dan aplikasi. Ilmu Jaringan Terapan, 4 (1): 1–28, 2019. 10.1007/s41109-019-0179-3.
https://doi.org/10.1007/s41109-019-0179-3
[2] Jonathan Ariel Barmak dan Elias Gabriel Minian. Jenis homotopi yang kuat, saraf dan kolaps. Geometri Diskrit & Komputasi, 47 (2): 301–328, 2012. 10.1007/s00454-011-9357-5.
https://doi.org/10.1007/s00454-011-9357-5
[3] Andreas Bärtschi dan Stephan Eidenbenz. Persiapan deterministik dari keadaan dicke. Dalam International Symposium on Fundamentals of Computation Theory, halaman 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, dan Alain Tapp. Amplifikasi dan estimasi amplitudo kuantum. Matematika Kontemporer, 305: 53–74, 2002. 10.1090 / conm / 305/05215.
https: / / doi.org/ 10.1090 / conm / 305/05215
[5] Peter Bubenik dkk. Analisis data topologi statistik menggunakan lanskap persistensi. J.Mach. Mempelajari. Res., 16 (1): 77–102, 2015. 10.5555/2789272.2789275.
https: / / doi.org/ 10.5555 / 2789272.2789275
[6] Frédéric Chazal dan Bertrand Michel. Pengantar analisis data topologi: aspek fundamental dan praktis untuk ilmuwan data. Frontiers in artificial intelligence, 4, 2021. 10.3389/frai.2021.667963.
https:///doi.org/10.3389/frai.2021.667963
[7] Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau. Algoritma dan aplikasi peringkat matriks cepat. Jurnal ACM (JACM), 60 (5): 1–25, 2013. 10.1145/2528404.
https: / / doi.org/ 10.1145 / 2528404
[8] David Cohen-Steiner, Herbert Edelsbrunner, dan John Harer. Stabilitas diagram persistensi. Geometri diskrit & komputasi, 37 (1): 103–120, 2007. 10.1007/s00454-006-1276-5.
https://doi.org/10.1007/s00454-006-1276-5
[9] Alex Cole dan Gary Shiu. Analisis data topologi untuk lanskap string. Jurnal Fisika Energi Tinggi, 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, and David Petrie Moulton. Sirkuit penambahan pembawa riak kuantum baru. 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] Edoardo Di Napoli, Eric Polizzi, and Yousef Saad. Estimasi jumlah nilai eigen yang efisien dalam suatu interval. Aljabar Linear Numerik dengan Aplikasi, 23 (4): 674–692, 2016. 10.1002/nla.2048.
https:///doi.org/10.1002/nla.2048
[12] Robert H Dike. Koherensi dalam proses radiasi spontan. Tinjauan fisik, 93 (1): 99, 1954. 10.1103/PhysRev.93.99.
https: / / doi.org/ 10.1103 / PhysRev.93.99
[13] Herbert Edelsbrunner dan John Harer. Topologi komputasi: pengantar. American Mathematical Soc., 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, dan Afra Zomorodian. Persistensi dan penyederhanaan topologi. Dalam Prosiding simposium tahunan ke-41 tentang dasar-dasar ilmu komputer, halaman 454–463. IEEE, 2000/s10.1007-00454-002-2885.
https://doi.org/10.1007/s00454-002-2885-2
[15] Herbert Edelsbrunner, John Harer, dkk. Homologi persisten-survei. Matematika kontemporer, 453: 257–282, 2008. 10.1090/conm/453/08802.
https: / / doi.org/ 10.1090 / conm / 453/08802
[16] Joel Friedman. Menghitung nomor betti melalui laplacian kombinatorial. Algorithmica, 21 (4): 331–346, 1998. 10.1007/PL00009218.
https: / / doi.org/ 10.1007 / PL00009218
[17] Robert Grist. Barcode: topologi data yang persisten. Buletin Masyarakat Matematika Amerika, 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, dan Nathan Wiebe. Transformasi nilai singular kuantum dan seterusnya: peningkatan eksponensial untuk aritmatika matriks kuantum. Dalam Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, halaman 193-204, 2019. 10.1145/3313276.3316366.
https: / / doi.org/ 10.1145 / 3313276.3316366
[19] Sam Gunn dan Niels Kornerup. Tinjau algoritma kuantum untuk angka betti. pracetak 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, and Seth Lloyd. Algoritma kuantum untuk sistem persamaan linier. Surat tinjauan fisik, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
[21] Ryu Hayakawa. Algoritma kuantum untuk angka betti persisten dan analisis data topologi. pracetak 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, and Suguru Tamaki. Supremasi kuantum berbutir halus berdasarkan vektor ortogonal, jalur terpendek 3-jumlah dan semua pasangan. pracetak 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, dan Xiao-Feng Wang. Dekomposisi gerbang toffoli n-qubit dengan kompleksitas rangkaian linier. International Journal of Theoretical Physics, 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, and Jian-Wei Pan. Demonstrasi analisis data topologi pada prosesor kuantum. Optica, 5 (2): 193–198, 2018. 10.1364/OPTICA.5.000193.
https: / / doi.org/ 10.1364 / OPTICA.5.000193
[25] Lek-Heng Lim. Hodge laplacians pada grafik. Tinjauan SIAM, 62 (3): 685–715, 2020. 10.1137/18M1223101.
https: / / doi.org/ 10.1137 / 18M1223101
[26] Lin Lin, Yousef Saad, dan Chao Yang. Mendekati kerapatan spektral matriks besar. Tinjauan SIAM, 58 (1): 34–65, 2016. 10.1137/130934283.
https: / / doi.org/ 10.1137 / 130934283
[27] Seth Lloyd, Silvano Garnerone, dan Paolo Zanardi. Algoritma kuantum untuk analisis data topologi dan geometris. Komunikasi alam, 7 (1): 1–7, 2016. 10.1038/ncomms10138.
https:///doi.org/10.1038/ncomms10138
[28] John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang. Penyatuan besar algoritma kuantum. PRX Quantum, 2 (4): 040203, 2021. 10.1103/PRXQuantum.2.040203.
https: / / doi.org/ 10.1103 / PRXQuantum.2.040203
[29] RHAJ Meijer. Pengelompokan menggunakan homologi persisten kuantum. tesis master, 2019.
[30] Facundo Memoli, Zhengchao Wan, and Yusu Wang. Laplacia persisten: Properti, algoritme, dan implikasi. Jurnal SIAM tentang Matematika Ilmu Data, 4 (2): 858–884, 2022. 10.1137/21M1435471.
https: / / doi.org/ 10.1137 / 21M1435471
[31] Niels Neumann dan Sterre den Breeijen. Keterbatasan pengelompokan menggunakan homologi persisten kuantum. pracetak 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, dan Heather A Harrington. Peta jalan untuk perhitungan homologi persisten. Ilmu Data 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, and Mathijs Wintraecken. Topologi web kosmik dalam hal angka betti yang persisten. Pemberitahuan Bulanan Royal Astronomical Society, 465 (4): 4281–4310, 2017. 10.1093/mnras/stw2862.
https:///doi.org/10.1093/mnras/stw2862
[34] Chi Seng Pun, Si Xian Lee, and Kelin Xia. Pembelajaran mesin berbasis homologi yang persisten: survei dan studi komparatif. Tinjauan Kecerdasan Buatan, halaman 1–45, 2022. 10.1007/s10462-022-10146-z.
https: / / doi.org/ 10.1007 / s10462-022-10146-z
[35] Patrick Ral. Algoritme kuantum koheren yang lebih cepat untuk estimasi fase, energi, dan amplitudo. Quantum, 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, dan Muhammad Tahir. Bukti bijeksi untuk sistem bilangan kombinatorial. pracetak 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, dan Anna Wienhard. Menemukan perilaku mirip diri sendiri dalam dinamika banyak-tubuh kuantum melalui homologi persisten. 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, and Lior Horesh. Analisis data topologi kuantum dengan kedalaman linier dan percepatan eksponensial. pracetak 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, dan Guo-Wei Wei. Grafik spektral persisten. Jurnal internasional untuk metode numerik dalam teknik biomedis, 36 (9): e3376, 2020. 10.1002/cnm.3376.
https:///doi.org/10.1002/cnm.3376
[40] Larry Wasserman. Analisis data topologi. Tinjauan Tahunan Statistik dan Penerapannya, 5: 501–532, 2018. 10.1146/annurev-statistics-031017-100045.
https:///doi.org/10.1146/annurev-statistics-031017-100045
[41] Kelin Xia dan Guo-Wei Wei. Analisis homologi gigih dari struktur protein, fleksibilitas, dan pelipatan. Jurnal internasional untuk metode numerik dalam teknik biomedis, 30 (8): 814–844, 2014. 10.1002/cnm.2655.
https:///doi.org/10.1002/cnm.2655
[42] Afra Zomorodian dan Gunnar Carlsson. Menghitung homologi persisten. Geometri Diskrit & Komputasi, 33 (2): 249–274, 2005. 10.1007/s00454-004-1146-y.
https: / / doi.org/ 10.1007 / s00454-004-1146-y
Dikutip oleh
[1] Alexander Schmidhuber dan Seth Lloyd, "Keterbatasan Teori Kompleksitas pada Algoritma Kuantum untuk Analisis Data Topologi", arXiv: 2209.14286.
[2] Bernardo Ameneyro, Vasileios Maroulas, dan George Siopsis, “Homologi Persisten Kuantum”, 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, dan Ryan Babbush, “Mengukur Keuntungan Kuantum dalam Analisis Data Topologi”, arXiv: 2209.13581.
[4] Iordanis Kerenidis dan Anupam Prakash, “Pembelajaran mesin kuantum dengan status subruang”, arXiv: 2202.00054.
[5] Bernardo Ameneyro, George Siopsis, dan Vasileios Maroulas, "Homologi Persisten Kuantum untuk Deret Waktu", arXiv: 2211.04465.
[6] Simon Apers, Sayantan Sen, dan Dániel Szabó, “Algoritme klasik (sederhana) untuk memperkirakan angka Betti”, arXiv: 2211.09618.
[7] Sam McArdle, András Gilyén, dan Mario Berta, "Algoritme kuantum yang disederhanakan untuk analisis data topologi dengan qubit yang lebih sedikit secara eksponensial", arXiv: 2209.12887.
[8] Andrew Vlasic dan Anh Pham, “Memahami Pemetaan Enkode Data Melalui Implementasi Analisis Topologi Kuantum”, arXiv: 2209.10596.
Kutipan di atas berasal dari SAO / NASA ADS (terakhir berhasil diperbarui, 2022-12-07 16:42:14). Daftar ini mungkin tidak lengkap karena tidak semua penerbit menyediakan data kutipan yang cocok dan lengkap.
Tidak dapat mengambil Crossref dikutip oleh data selama upaya terakhir 2022-12-07 16:42:12: Tidak dapat mengambil data yang dikutip oleh untuk 10.22331 / q-2022-12-07-873 dari Crossref. Ini normal jika DOI terdaftar baru-baru ini.
Makalah ini diterbitkan dalam Quantum di bawah Creative Commons Attribution 4.0 Internasional (CC BY 4.0) lisensi. Hak cipta tetap berada pada pemegang hak cipta asli seperti penulis atau lembaganya.
