สถาบัน Yukawa สำหรับฟิสิกส์เชิงทฤษฎี, มหาวิทยาลัยเกียวโต, Kitashirakawa Oiwakecho, Sakyoku, Kyoto 606-8502, Japan
พบบทความนี้ที่น่าสนใจหรือต้องการหารือ? Scite หรือแสดงความคิดเห็นใน SciRate.
นามธรรม
การวิเคราะห์ข้อมูลเชิงทอพอโลยี (TDA) เป็นสาขาใหม่ของการวิเคราะห์ข้อมูล ขั้นตอนสำคัญของ TDA คือการคำนวณหมายเลข Betti ที่คงอยู่ อัลกอริทึมแบบคลาสสิกที่มีอยู่สำหรับ TDA นั้นถูกจำกัด หากเราต้องการเรียนรู้จากคุณสมบัติโทโพโลยีมิติสูง เนื่องจากจำนวนของความเรียบง่ายมิติสูงเพิ่มขึ้นอย่างทวีคูณในขนาดของข้อมูล ในบริบทของการคำนวณควอนตัม ก่อนหน้านี้ได้แสดงให้เห็นว่ามีอัลกอริทึมควอนตัมที่มีประสิทธิภาพสำหรับการประมาณจำนวน Betti แม้ในมิติที่สูง อย่างไรก็ตาม หมายเลข Betti นั้นกว้างน้อยกว่าหมายเลข Betti ถาวร และไม่มีอัลกอริทึมควอนตัมใดที่สามารถประมาณค่า Betti ถาวรของมิติข้อมูลโดยพลการได้
บทความนี้แสดงอัลกอริทึมควอนตัมแรกที่สามารถประเมินจำนวน Betti ถาวร ($ normalized$) ของมิติโดยพลการ อัลกอริทึมของเรามีประสิทธิภาพสำหรับคอมเพล็กซ์ที่เรียบง่าย เช่น คอมเพล็กซ์ Vietoris-Rips และแสดงให้เห็นถึงการเร่งความเร็วแบบทวีคูณเหนืออัลกอริทึมแบบคลาสสิกที่รู้จัก
► ข้อมูล BibTeX
► ข้อมูลอ้างอิง
[1] เมห์เม็ต เอ อักตัส, เอสรา อักบาส และอาเหม็ด เอล ฟัตมาอุย ความคล้ายคลึงกันของการคงอยู่ของเครือข่าย: วิธีการและการประยุกต์ใช้ วิทยาศาสตร์เครือข่ายประยุกต์ 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 การเตรียมการที่ชัดเจนของรัฐดิ๊ก ใน International Symposium on Fundamentals of Computation Theory, หน้า 126–139. สปริงเกอร์ 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 และ Alain Tapp การขยายและการประมาณค่าแอมพลิจูดควอนตัม คณิตศาสตร์ร่วมสมัย, 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] เฟรเดริก ชาซาล และเบอร์ทรานด์ มิเชล บทนำเกี่ยวกับการวิเคราะห์ข้อมูลเชิงทอพอโลยี: แง่มุมพื้นฐานและการปฏิบัติสำหรับนักวิทยาศาสตร์ข้อมูล พรมแดนด้านปัญญาประดิษฐ์ 4 ปี 2021 10.3389/frai.2021.667963
https://doi.org/10.3389/frai.2021.667963
[7] Ho Yee Cheung, Tsz Chiu Kwok และ Lap Chi Lau อัลกอริทึมอันดับเมทริกซ์และแอปพลิเคชันที่รวดเร็ว วารสาร 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] 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:ปริมาณ-ph/0410184
[11] เอโดอาร์โด ดิ นาโปลี, เอริก โปลิซซี และ ยูเซฟ ซาด การประมาณค่าลักษณะเฉพาะอย่างมีประสิทธิภาพนับในช่วงเวลา พีชคณิตเชิงเส้นตัวเลขพร้อมแอปพลิเคชัน 23 (4): 674–692, 2016 10.1002/nla.2048
https://doi.org/10.1002/nla.2048
[12] โรเบิร์ต เอช ดิกเก การเชื่อมโยงกันในกระบวนการฉายรังสีที่เกิดขึ้นเอง การทบทวนร่างกาย 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] Herbert Edelsbrunner, David Letscher และ Afra Zomorodian การคงอยู่ของทอพอโลยีและการทำให้เข้าใจง่าย ใน Proceedings 41st Annual symposium on Foundations of Computer Science, หน้า 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] โจเอล ฟรีดแมน. การคำนวณหมายเลข betti ผ่าน combinatorial laplacians อัลกอริทึม, 21 (4): 331–346, 1998. 10.1007/PL00009218
https://doi.org/10.1007/PL00009218
[17] โรเบิร์ต กริสต์. บาร์โค้ด: โทโพโลยีถาวรของข้อมูล แถลงการณ์ของ American Mathematical Society, 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 และ Nathan Wiebe การแปลงค่าควอนตัมเอกพจน์และอื่น ๆ : การปรับปรุงเลขยกกำลังสำหรับเลขคณิตควอนตัมเมทริกซ์ ในรายงานการประชุม ACM SIGACT Symposium on Theory of Computing ประจำปีครั้งที่ 51 หน้า 193–204 ปี 2019 10.1145/3313276.3316366
https://doi.org/10.1145/3313276.3316366
[19] แซม กันน์ และนีลส์ คอร์เนรัป ทบทวนอัลกอริทึมควอนตัมสำหรับหมายเลข betti พิมพ์ล่วงหน้า 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 และ 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 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] Yong He, Ming-Xing Luo, E Zhang, Hong-Ke Wang และ Xiao-Feng Wang การสลายตัวของ n-qubit toffoli gate ที่มีความซับซ้อนของวงจรเชิงเส้น 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 และ Jian-Wei Pan การสาธิตการวิเคราะห์ข้อมูลเชิงทอพอโลยีบนตัวประมวลผลควอนตัม ออพติกา 5 (2): 193–198 2018 10.1364/OPTICA.5.000193
https://doi.org/10.1364/OPTICA.5.000193
[25] เล็กเฮงลิ้ม. Hodge laplacians บนกราฟ SIAM Review, 62 (3): 685–715, 2020. 10.1137/18M1223101.
https://doi.org/10.113718M1223101
[26] Lin Lin, Yousef Saad และ Chao Yang ความหนาแน่นสเปกตรัมโดยประมาณของเมทริกซ์ขนาดใหญ่ SIAM review, 58 (1): 34–65, 2016. 10.1137/130934283.
https://doi.org/10.1137/130934283
[27] เซธ ลอยด์, ซิลวาโน การ์เนโรเน และเปาโล ซานาร์ดี อัลกอริธึมควอนตัมสำหรับการวิเคราะห์ทอพอโลยีและเรขาคณิตของข้อมูล การสื่อสารตามธรรมชาติ, 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] RHAJ ไมเยอร์ การทำคลัสเตอร์โดยใช้ควอนตัมคงค้างแบบถาวร วิทยานิพนธ์มหาบัณฑิต, 2019.
[30] Facundo Mémoli, Zhengchao Wan และ Yusu Wang Lalacians ถาวร: คุณสมบัติ อัลกอริทึม และความหมาย SIAM Journal on Mathematics of Data Science, 4 (2): 858–884, 2022 10.1137/21M1435471
https://doi.org/10.113721M1435471
[31] Niels Neumann และ Sterre den Breeijen ข้อจำกัดของการจัดกลุ่มโดยใช้ควอนตัมคงรูป พิมพ์ล่วงหน้า 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 และ Heather A. Harrington แผนงานสำหรับการคำนวณความคล้ายคลึงกันแบบถาวร 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] Pratyush Pranav, Herbert Edelsbrunner, Rien Van de Weygaert, Gert Vegter, Michael Kerber, Bernard JT Jones และ Mathijs Wintraecken โทโพโลยีของเว็บจักรวาลในแง่ของหมายเลขเบตติถาวร ประกาศประจำเดือนของ 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 และ 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] อาบู บาการ์ ซิดดิก ซาเดีย ฟาริด และมูฮัมหมัด ทาฮีร์ หลักฐานของ bijection สำหรับระบบจำนวนเชิงผสม พิมพ์ล่วงหน้า 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] Shashanka Ubaru, Ismail Yunus Akhalwaya, Mark S Squillante, Kenneth L. Clarkson และ Lior Horesh การวิเคราะห์ข้อมูลโทโพโลยีเชิงควอนตัมด้วยความลึกเชิงเส้นและการเร่งความเร็วแบบเอ็กซ์โปเนนเชียล พิมพ์ล่วงหน้า 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 กราฟสเปกตรัมถาวร วารสารนานาชาติสำหรับวิธีการทางตัวเลขในวิศวกรรมชีวการแพทย์ 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] Kelin Xia และ Guo-Wei Wei การวิเคราะห์ความคล้ายคลึงกันแบบถาวรของโครงสร้างโปรตีน ความยืดหยุ่น และการพับ วารสารนานาชาติสำหรับวิธีการทางตัวเลขในวิศวกรรมชีวการแพทย์ 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, “ข้อจำกัดทางทฤษฎีเชิงความซับซ้อนเกี่ยวกับอัลกอริทึมควอนตัมสำหรับการวิเคราะห์ข้อมูลทอพอโลยี”, arXiv: 2209.14286.
[2] Bernardo Ameneyro, Vasileios Maroulas และ George Siopsis, “Quantum Persistent Homology”, 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, “Quantum Persistent Homology for Time Series”, arXiv: 2211.04465.
[6] Simon Apers, Sayantan Sen และ Dániel Szabó, “อัลกอริทึมคลาสสิก (แบบง่าย) สำหรับการประมาณค่า Betti”, arXiv: 2211.09618.
[7] Sam McArdle, András Gilyén และ Mario Berta, “อัลกอริธึมควอนตัมที่คล่องตัวสำหรับการวิเคราะห์ข้อมูลเชิงทอพอโลยีที่มี qubits น้อยลงแบบทวีคูณ”, arXiv: 2209.12887.
[8] Andrew Vlasic และ Anh Pham, “Understanding the Mapping of Encode Data Through An Implementation of Quantum Topological Analysis”, arXiv: 2209.10596.
การอ้างอิงข้างต้นมาจาก are อบต./นาซ่าโฆษณา (ปรับปรุงล่าสุดสำเร็จ 2022-12-07 16:42:14 น.) รายการอาจไม่สมบูรณ์เนื่องจากผู้จัดพิมพ์บางรายไม่ได้ให้ข้อมูลอ้างอิงที่เหมาะสมและครบถ้วน
ไม่สามารถดึงข้อมูล Crossref อ้างโดย data ระหว่างความพยายามครั้งล่าสุด 2022-12-07 16:42:12 น.: ไม่สามารถดึงข้อมูลที่อ้างถึงสำหรับ 10.22331/q-2022-12-07-873 จาก Crossref นี่เป็นเรื่องปกติหาก DOI ได้รับการจดทะเบียนเมื่อเร็วๆ นี้
บทความนี้เผยแพร่ใน Quantum ภายใต้ the ครีเอทีฟคอมมอนส์แบบแสดงที่มา 4.0 สากล (CC BY 4.0) ใบอนุญาต ลิขสิทธิ์ยังคงอยู่กับผู้ถือลิขสิทธิ์ดั้งเดิม เช่น ผู้เขียนหรือสถาบันของพวกเขา
