ความซับซ้อนของเครื่องเวกเตอร์ที่รองรับควอนตัม

ความซับซ้อนของเครื่องเวกเตอร์ที่รองรับควอนตัม

โหนดต้นทาง: 3057476

จาน เกนติเน็ตต้า1,2, อาร์เน่ ทอมเซ่น3,2, เดวิด ซัทเทอร์2และสเตฟาน เวอร์เนอร์2

1สถาบันฟิสิกส์ École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Europe – ซูริก
3ภาควิชาฟิสิกส์ ETH ซูริก

พบบทความนี้ที่น่าสนใจหรือต้องการหารือ? Scite หรือแสดงความคิดเห็นใน SciRate.

นามธรรม

เครื่องเวกเตอร์สนับสนุนควอนตัมใช้วงจรควอนตัมเพื่อกำหนดฟังก์ชันเคอร์เนล แสดงให้เห็นว่าแนวทางนี้ให้การเร่งความเร็วแบบเอ็กซ์โพเนนเชียลที่พิสูจน์ได้เมื่อเปรียบเทียบกับอัลกอริธึมคลาสสิกที่รู้จักสำหรับชุดข้อมูลบางชุด การฝึกโมเดลดังกล่าวสอดคล้องกับการแก้ปัญหาการหาค่าเหมาะที่สุดแบบนูนไม่ว่าจะผ่านสูตรผสมเบื้องต้นหรือสูตรคู่ เนื่องจากธรรมชาติของความน่าจะเป็นของกลศาสตร์ควอนตัม อัลกอริธึมการฝึกอบรมจึงได้รับผลกระทบจากความไม่แน่นอนทางสถิติ ซึ่งมีผลกระทบสำคัญต่อความซับซ้อน เราแสดงให้เห็นว่าปัญหาสองประการสามารถแก้ไขได้ในการประเมินวงจรควอนตัม $O(M^{4.67}/varepsilon^2)$ โดยที่ $M$ หมายถึงขนาดของชุดข้อมูลและ $varepsilon$ คือความแม่นยำของโซลูชันเมื่อเทียบกับค่าที่เหมาะสมที่สุด เป็นผลมาจากค่าความคาดหวังที่แน่นอนซึ่งหาได้ในทางทฤษฎีเท่านั้น เราพิสูจน์ภายใต้สมมติฐานที่มีแรงจูงใจเชิงประจักษ์ว่าปัญหาเคอร์เนลไลซ์เบื้องต้นสามารถแก้ไขได้ใน $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ การประเมินโดยใช้ลักษณะทั่วไปของคลาสสิกที่รู้จัก อัลกอริธึมที่เรียกว่า Pegasos ผลการทดลองที่ตามมาแสดงให้เห็นว่าความซับซ้อนในการวิเคราะห์เหล่านี้มีความเข้มงวดมาก นอกจากนี้ เรายังตรวจสอบการประมาณความแปรผันของเครื่องจักรเวคเตอร์ที่รองรับควอนตัม และแสดงให้เห็นว่าการฝึกศึกษาสำนึกของพวกมันบรรลุการขยายขนาดที่ดีขึ้นอย่างมากในการทดลองของเรา

เครื่องเวกเตอร์สนับสนุนควอนตัมเป็นตัวเลือกสำหรับการแสดงให้เห็นถึงความได้เปรียบของควอนตัมในอนาคตอันใกล้นี้สำหรับปัญหาการจำแนกประเภท แนวคิดก็คือว่าฟังก์ชันเคอร์เนล (หวังว่าจะมีประโยชน์) นั้นได้มาจากวงจรควอนตัมที่มีประสิทธิภาพ ซึ่งยากในการประเมินแบบคลาสสิก เนื่องจากธรรมชาติของความน่าจะเป็นของกลศาสตร์ควอนตัม ฟังก์ชันเคอร์เนลจึงได้รับผลกระทบจากความไม่แน่นอนทางสถิติ ในงานนี้ เราวิเคราะห์อย่างเข้มงวดว่าความไม่แน่นอนนี้ (หรือที่เรียกว่าสัญญาณรบกวนช็อต) ส่งผลกระทบต่อความซับซ้อนในการคำนวณโดยรวมในการแก้ปัญหาการจำแนกประเภทอย่างไร

► ข้อมูล BibTeX

► ข้อมูลอ้างอิง

[1] เจ. เบียมอนเต้, พี. วิตเทค, เอ็น. แพนคอตติ, พี. รีเบนทรอสต์, เอ็น. วีบ และเอส. ลอยด์ การเรียนรู้ของเครื่องควอนตัม ธรรมชาติ, 549(7671):195–202, 2017. DOI: 10.1038/​nature23474.
https://doi.org/10.1038/​nature23474

[2] วี. ฮาฟลิเชค, เอ. ดี. กอร์โคลส์, เค. เทมเม, เอ. ดับเบิลยู. แฮร์โรว์, เอ. กันดาลา, เจ. เอ็ม. โชว และเจ. เอ็ม. แกมเบตตา การเรียนรู้ภายใต้การดูแลด้วยช่องว่างคุณลักษณะที่ปรับปรุงด้วยควอนตัม ธรรมชาติ 567(7747):209–212, 2019. DOI: 10.1038/s41586-019-0980-2.
https:/​/​doi.org/​10.1038/​s41586-019-0980-2

[3] เอ. อับบาส, ดี. ซัทเทอร์, ซี. ซูฟาล, เอ. ลุคคี่, เอ. ฟิกัลลี และเอส. โวเออร์เนอร์ พลังของโครงข่ายประสาทเทียมควอนตัม วิทยาศาสตร์คอมพิวเตอร์ธรรมชาติ 1(มิถุนายน) 2020 DOI: 10.1038/s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] วาย. หลิว, ส. อรุณาชาลัม และเค. เทมมี่. การเร่งความเร็วควอนตัมที่เข้มงวดและแข็งแกร่งในการเรียนรู้ของเครื่องภายใต้การดูแล ฟิสิกส์ธรรมชาติ 2021 DOI: 10.1038/s41567-021-01287-z.
https://doi.org/10.1038/​s41567-021-01287-z

[5] เอส. แอรอนสัน. อ่านพิมพ์ดีด. ฟิสิกส์ธรรมชาติ, 11(4):291–293, 2015 DOI: 10.1038/nphys3272
https://doi.org/10.1038/​nphys3272

[6] อี. ถัง. อัลกอริธึมคลาสสิกที่ได้รับแรงบันดาลใจจากควอนตัมสำหรับระบบการแนะนำ ใน รายงานการประชุมสัมมนา ACM SIGACT Symposium ประจำปีครั้งที่ 51 เกี่ยวกับทฤษฎีคอมพิวเตอร์, STOC 2019, หน้า 217–228, นิวยอร์ก, นิวยอร์ก, สหรัฐอเมริกา, 2019 สมาคมเครื่องจักรคอมพิวเตอร์ ดอย: 10.1145/​3313276.3316310.
https://doi.org/10.1145/​3313276.3316310

[7] น.-H. Chia, A. Gilyén, T. Li, H.-H. หลิน อี. ถัง และซี. หวัง กรอบงานเมทริกซ์เลขคณิตระดับต่ำเชิงเส้นแบบซับลิเนียร์สำหรับการสุ่มตัวอย่างสำหรับการเรียนรู้ของเครื่องควอนตัมเชิงควอนตัม หน้า 387–400 Association for Computing Machinery, New York, NY, USA, 2020. เข้าถึงออนไลน์: https://​/​doi.org/​10.1145/​3357713.3384314.
https://doi.org/10.1145/​3357713.3384314

[8] ที. ลี, ส. จักระบาร์ติ และเอ็กซ์. วู. อัลกอริธึมควอนตัมซับลิเนียร์สำหรับการฝึกตัวแยกประเภทเชิงเส้นและเคอร์เนล ในการประชุมนานาชาติเรื่อง Machine Learning หน้า 3815–3824 พีเอ็มแอลอาร์, 2019.

[9] ส.ธนศิลป์, ส.วัง, เอ็ม. เซเรโซ และซี. โฮล์มส์. ความเข้มข้นแบบเอ็กซ์โพเนนเชียลและการฝึกไม่ได้ในวิธีเคอร์เนลควอนตัม 2022 DOI: 10.48550/​ARXIV.2208.11060
https://doi.org/​10.48550/​ARXIV.2208.11060

[10] เอส. ชาเลฟ-ชวาตซ์ และ เอ็น. สเรโบร การเพิ่มประสิทธิภาพ SVM: การพึ่งพาแบบผกผันกับขนาดชุดการฝึก การดำเนินการของการประชุมนานาชาติเรื่อง Machine Learning ครั้งที่ 25 หน้า 928–935, 2008

[11] อ. ทอมเซ่น. การเปรียบเทียบเครือข่ายประสาทควอนตัมกับเครื่องเวกเตอร์ที่รองรับควอนตัม วิทยานิพนธ์ระดับปริญญาโท, ETH Zurich, 2021-09-06 ดอย: 20.500.11850/​527559.

[12] พ.ศ. โบเซอร์, ไอ. เอ็ม. กายอน และ วี. เอ็น. วาปนิค อัลกอริธึมการฝึกอบรมสำหรับตัวแยกประเภทมาร์จิ้นที่เหมาะสมที่สุด ใน Proceedings of the Fifth Annual Workshop on Computational Learning Theory, COLT ’92, หน้า 144–152, New York, NY, USA, 1992. Association for Computing Machinery. ดอย: 10.1145/130385.130401.
https://doi.org/10.1145/​130385.130401

[13] ซี. คอร์เตส และ วี. วาปนิค เครือข่ายสนับสนุนเวกเตอร์ ใน Machine Learning หน้า 273–297, 1995

[14] วี.เอ็น. วาปนิค. ธรรมชาติของทฤษฎีการเรียนรู้เชิงสถิติ Springer Science+Business Media, LLC, 2000

[15] F. Pedregosa และคณะ Scikit-learn: การเรียนรู้ของเครื่องใน Python Journal of Machine Learning Research, 12(85):2825–2830, 2011. เข้าถึงออนไลน์: http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html
http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html

[16] เอส. บอยด์ และแอล. แวนเดนเบิร์ก. การเพิ่มประสิทธิภาพนูน สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์, 2004

[17] เอส. ชาเลฟ-ชวาตซ์, วาย. ซิงเกอร์, เอ็น. สเรโบร และเอ. คอตเตอร์ Pegasos: ตัวแก้ปัญหาการไล่ระดับสีย่อยเบื้องต้นโดยประมาณสำหรับ SVM การเขียนโปรแกรมทางคณิตศาสตร์ 127(1):3–30 ปี 2011 DOI: 10.1007/s10107-010-0420-4
https:/​/​doi.org/​10.1007/​s10107-010-0420-4

[18] M.D.S. Anis และคณะ Qiskit: กรอบงานโอเพ่นซอร์สสำหรับคอมพิวเตอร์ควอนตัม ปี 2021 DOI: 10.5281/​zenodo.2573505
https://doi.org/10.5281/​zenodo.2573505

[19] พี. รีเบนทรอสต์, เอ็ม. โมห์เซนี และเอส. ลอยด์ เครื่องเวกเตอร์สนับสนุนควอนตัมสำหรับการจำแนกข้อมูลขนาดใหญ่ จดหมายทบทวนทางกายภาพ, 113(3):1–5, 2014. DOI: 10.1103/​PhysRevLett.113.130503.
https://doi.org/​10.1103/​PhysRevLett.113.130503

[20] เจ. คุบเลอร์, เอส. บุคโฮลซ์ และบี. โชลคอปฟ์ อคติแบบอุปนัยของเมล็ดควอนตัม ใน M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang และ J. W. Vaughan บรรณาธิการ Advances in Neural Information Processing Systems เล่มที่ 34 หน้า 12661–12673 Curran Associates, Inc., 2021 มีจำหน่ายทางออนไลน์: https://​/​proceedings.neurips.cc/​paper_files/​paper/​2021/​file/​69adc1e107f7f7d035d7baf04342e1ca-Paper.pdf
https:/​/​proceedings.neurips.cc/​paper_files/​paper/​2021/​file/​69adc1e107f7f7d035d7baf04342e1ca-Paper.pdf

[21] V. Heyraud, Z. Li, Z. Denis, A. Le Boité และ C. Ciuti เครื่องเคอร์เนลควอนตัมที่มีเสียงดัง ฟิสิกส์ รายได้ A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https://doi.org/10.1103/​PhysRevA.106.052421

[22] ซี.เจ.ซี. เบอร์จส์ และ ซี.เจ.ซี. เบอร์เจส บทช่วยสอนเกี่ยวกับเครื่องเวกเตอร์ที่รองรับสำหรับการจดจำรูปแบบ การทำเหมืองข้อมูลและการค้นพบความรู้, 2:121–167, 1998 มีให้ทางออนไลน์: https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -เครื่องจักรสำหรับการรับรู้รูปแบบ/​.
https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector-machines-for-pattern-recognition/​

[23] เอ็ม. เซเรโซ, เอ. โซน, ที. โวลคอฟฟ์, แอล. ซินซิโอ และพี. เจ. โคลส์ ฟังก์ชันต้นทุนขึ้นอยู่กับที่ราบสูงแห้งแล้งในวงจรควอนตัมแบบพาราเมตริกแบบตื้น การสื่อสารทางธรรมชาติ 12(1):1791, 2021. DOI: 10.1038/s41467-021-21728-w.
https://doi.org/​10.1038/​s41467-021-21728-w

[24] เบลิส, วาซิลิส, กอนซาเลซ-กัสติลโล, ซามูเอล, ไรส์เซล, คริสตินา, วัลเลกอร์ซา, โซเฟีย, คอมบาร์โร, เอลีอัส เอฟ., ดิสเซิตอรี, กุนเธอร์ และไรเตอร์ ฟลอเรนติน การวิเคราะห์ฮิกส์ด้วยตัวแยกประเภทควอนตัม EPJ Web Conf., 251:03070, 2021. DOI: 10.1051/​epjconf/​202125103070.
https://doi.org/​10.1051/​epjconf/​202125103070

[25] เอ็ม. เซเรโซ, เอ. อาร์ราสมิธ, อาร์. แบบบุช, เอส. ซี. เบนจามิน, เอส. เอนโด, เค. ฟูจิอิ, เจ. อาร์. แมคคลีน, เค. มิทาไร, เอ็กซ์. หยวน, แอล. ซินซิโอ และพี. เจ. โคลส์ อัลกอริธึมควอนตัมแปรผัน ฟิสิกส์บทวิจารณ์ธรรมชาติ, 3(9):625–644, 2021. DOI: 10.1038/s42254-021-00348-9.
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[26] อาร์. แมคกิบบอร์น และคณะ quadprog: โปรแกรมแก้ปัญหาการเขียนโปรแกรมกำลังสอง (หลาม) https://​/​github.com/​quadprog/​quadprog, 2022.
https://​/​github.com/​quadprog/​quadprog

[27] Y. Nesterov การบรรยายเบื้องต้นเกี่ยวกับการเพิ่มประสิทธิภาพนูน: หลักสูตรพื้นฐาน การเพิ่มประสิทธิภาพประยุกต์ สปริงเกอร์, 2004. DOI: 10.1007/​978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] เจ. สปอล. ภาพรวมของวิธีการก่อกวนพร้อมกันเพื่อการเพิ่มประสิทธิภาพที่มีประสิทธิภาพ ข้อมูลทางเทคนิคของ John Hopkins APL, 19(4), หน้า 482–492, 1998

[29] จี. เกนติเนตตา, เอ. ทอมเซ่น, ดี. ซัทเทอร์ และเอส. เวอร์เนอร์ รหัสสำหรับต้นฉบับ "ความซับซ้อนของเครื่องเวกเตอร์สนับสนุนควอนตัม" 2022. DOI: https://​/​doi.org/​10.5281/​zenodo.6303725.
https://doi.org/10.5281/​zenodo.6303725

[30] ที. ฮูเบรกเซ่น, ดี. วีริคส์, อี. กิล-ฟูสเตอร์, พี.-เจ. เอช.เอส. เดิร์กส์, พี.เค. เฟร์มานน์ และเจ.เจ. เมเยอร์ การฝึกอบรมการฝังเคอร์เนลควอนตัมบนคอมพิวเตอร์ควอนตัมระยะสั้น ฟิสิกส์ รายได้ A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https://doi.org/10.1103/​PhysRevA.106.042431

[31] ร. ลาตาลา. การประมาณค่าบรรทัดฐานบางประการของเมทริกซ์สุ่ม การดำเนินการของสมาคมคณิตศาสตร์อเมริกัน 133(5):1273–1282, 2005 DOI: 10.1090/s0002-9939-04-07800-1
https:/​/​doi.org/​10.1090/​s0002-9939-04-07800-1

[32] อาร์. เวอร์ชินิน ข้อมูลเบื้องต้นเกี่ยวกับการวิเคราะห์แบบไม่เชิงเส้นกำกับของเมทริกซ์สุ่ม Compressed Sensing: Theory and Applications, หน้า 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https://doi.org/10.1017/​CBO9780511794308.006

[33] ที. ฮอฟมันน์, บี. ชอลคอปฟ์ และเอ. เจ. สโมลา วิธีการเคอร์เนลในการเรียนรู้ของเครื่อง พงศาวดารสถิติ, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https://doi.org/10.1214/​009053607000000677

[34] เจ.ดับบลิว.แดเนียล. ความเสถียรของคำตอบของโปรแกรมกำลังสองแน่นอน การเขียนโปรแกรมทางคณิตศาสตร์ 5(1):41–53, 1973. DOI: 10.1007/​BF01580110.
https://doi.org/​10.1007/​BF01580110

อ้างโดย

[1] อเล็กซานเดอร์ เอ็ม. ดัลเซลล์, แซม แม็กอาร์เดิล, มาริโอ เบอร์ทา, เพรเซมีสลาฟ เบียเนียส, ชี-ฟาง เฉิน, อันดราส กิลีเยน, คอนเนอร์ ที. ฮานน์, ไมเคิล เจ. คาสตอรี่อาโน, เอมิล ที. คาบิบูลลิน, อเล็กซานเดอร์ คูบิกา, แกรนท์ ซอลตัน, แซมสัน หวัง และ Fernando GSL Brandão, “อัลกอริทึมควอนตัม: การสำรวจแอปพลิเคชันและความซับซ้อนตั้งแต่ต้นทางถึงปลายทาง”, arXiv: 2310.03011, (2023).

[2] Maria Schuld และ Nathan Killoran, “Quantum Advantage เป็นเป้าหมายที่เหมาะสมสำหรับการเรียนรู้เครื่องควอนตัมหรือไม่”, PRX ควอนตัม 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik และ Ofer Lahav, “เครื่องเวกเตอร์สนับสนุนที่ปรับปรุงด้วยควอนตัมสำหรับการจำแนกกาแลคซี”, เทคนิคและเครื่องมือ RAS 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung และ Chen-Yu Liu, “เครื่องเวกเตอร์สนับสนุนควอนตัมที่ปรับปรุงแล้วสำหรับการจำแนกดาวฤกษ์ขนาดใหญ่ด้วยการเร่งความเร็วของ GPU”, arXiv: 2311.12328, (2023).

[5] Supanut Thanasilp, Samson Wang, M. Cerezo, and Zoë Holmes, “Exponential Concentration and Untrainability in quantum kernel method”, arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka และ Naoki Yamamoto, “เครือข่ายประสาทไฮบริดควอนตัมคลาสสิกในระบอบเคอร์เนลแทนเจนต์ประสาท”, วิทยาศาสตร์และเทคโนโลยีควอนตัม 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo และ Rudy Raymond, “การเรียนรู้ของเครื่องควอนตัมบนอุปกรณ์ควอนตัมระยะใกล้: สถานะปัจจุบันของเทคนิคที่ได้รับการดูแลและไม่ได้รับการดูแลสำหรับการใช้งานในโลกแห่งความเป็นจริง”, arXiv: 2307.00908, (2023).

[8] Raoul Heese, Thore Gerlach, Sascha Mücke, Sabine Müller, Matthias Jakobs และ Nico Piatkowski, “การอธิบายวงจรควอนตัมด้วยค่า Shapley: สู่การเรียนรู้เครื่องควอนตัมที่อธิบายได้”, arXiv: 2301.09138, (2023).

[9] Julien Gacon, Jannes Nys, Riccardo Rossi, Stefan Woerner และ Giuseppe Carleo, “วิวัฒนาการเวลาควอนตัมที่หลากหลายโดยไม่มีเทนเซอร์เรขาคณิตควอนตัม”, arXiv: 2303.12839, (2023).

[10] Gian Gentinetta, David Sutter, Christa Zoufal, Bryce Fuller และ Stefan Woerner, “การจัดตำแหน่งเคอร์เนลควอนตัมพร้อม Stochastic Gradient Descent”, arXiv: 2304.09899, (2023).

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie และ Tim Scanlon, "การสร้างส่วนติดตามอนุภาคที่มีประจุขึ้นใหม่ด้วยเครื่องเวกเตอร์รองรับที่ปรับปรุงด้วยควอนตัม", arXiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick และ Thomas Ward, “แบบจำลองสำหรับรันไทม์การดำเนินการวงจรและผลกระทบของเคอร์เนลควอนตัมที่ขนาดชุดข้อมูลเชิงปฏิบัติ”, arXiv: 2307.04980, (2023).

[13] Samantha V. Barron, Daniel J. Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler และ Stefan Woerner, “ขอบเขตที่พิสูจน์ได้สำหรับค่าความคาดหวังที่ปราศจากเสียงรบกวนซึ่งคำนวณจากตัวอย่างที่มีเสียงดัง”, arXiv: 2312.00733, (2023).

(14) M. Emre Sahin, Benjamin C. B. Symons, Pushpak Pati, Fayyaz Minhas, Declan Millar, Maria Gabrani, Jan Lukas Robertus และ Stefano Mensa, "การเพิ่มประสิทธิภาพพารามิเตอร์ที่มีประสิทธิภาพสำหรับการจัดตำแหน่งเคอร์เนลควอนตัม: วิธีการสุ่มตัวอย่างย่อยในการฝึกอบรมรูปแบบต่างๆ" , arXiv: 2401.02879, (2024).

การอ้างอิงข้างต้นมาจาก are อบต./นาซ่าโฆษณา (ปรับปรุงล่าสุดสำเร็จ 2024-01-12 02:12:22 น.) รายการอาจไม่สมบูรณ์เนื่องจากผู้จัดพิมพ์บางรายไม่ได้ให้ข้อมูลอ้างอิงที่เหมาะสมและครบถ้วน

On บริการอ้างอิงของ Crossref ไม่พบข้อมูลอ้างอิงงาน (ความพยายามครั้งสุดท้าย 2024-01-12 02:12:21)

ประทับเวลา:

เพิ่มเติมจาก วารสารควอนตัม