Độ phức tạp của máy vectơ hỗ trợ lượng tử

Độ phức tạp của máy vectơ hỗ trợ lượng tử

Dấu thời gian: ngày 11 tháng 2024 năm 9 08:XNUMX sáng
Nút nguồn: 3057476

Gian Gentinetta1,2, Arne Thomsen3,2, David Sutter2và Stefan Woerner2

1Viện Vật lý, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Châu Âu – Zurich
3Khoa Vật lý, ETH Zurich

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

Máy vectơ hỗ trợ lượng tử sử dụng các mạch lượng tử để xác định hàm hạt nhân. Người ta đã chứng minh rằng phương pháp này mang lại khả năng tăng tốc theo cấp số nhân có thể chứng minh được so với bất kỳ thuật toán cổ điển nào đã biết đối với một số tập dữ liệu nhất định. Việc huấn luyện các mô hình như vậy tương ứng với việc giải quyết vấn đề tối ưu hóa lồi thông qua công thức cơ bản hoặc kép của nó. Do tính chất xác suất của cơ học lượng tử, các thuật toán huấn luyện bị ảnh hưởng bởi độ không đảm bảo về mặt thống kê, điều này có tác động lớn đến độ phức tạp của chúng. Chúng tôi chứng minh rằng vấn đề kép có thể được giải quyết trong các đánh giá mạch lượng tử $O(M^{4.67}/varepsilon^2)$, trong đó $M$ biểu thị kích thước của tập dữ liệu và $varepsilon$ độ chính xác của giải pháp so với lý tưởng là kết quả của các giá trị kỳ vọng chính xác mà chỉ có thể đạt được trên lý thuyết. Chúng tôi chứng minh theo một giả định có động cơ thực nghiệm rằng vấn đề nguyên thủy được nhân hóa có thể được giải quyết theo cách khác trong các đánh giá $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ bằng cách sử dụng khái quát hóa của một phương pháp cổ điển đã biết thuật toán có tên Pegasos. Các kết quả thực nghiệm kèm theo cho thấy sự phức tạp trong phân tích này về cơ bản là chặt chẽ. Ngoài ra, chúng tôi điều tra phép tính gần đúng biến thiên đối với các máy vectơ hỗ trợ lượng tử và chỉ ra rằng quá trình đào tạo heuristic của chúng đạt được khả năng mở rộng quy mô tốt hơn đáng kể trong các thử nghiệm của chúng tôi.

Hình ảnh nổi bật: Ước tính giá trị hạt nhân $k(mathbf{x} _i, mathbf{x__j)$, trong đó $mathcal{E}(mathbf{x} _i)$ biểu thị một tham số đơn nhất được tham số hóa bởi dữ liệu $mathbf{x _i$. Số lần chụp được đưa ra bởi $R$, nó kiểm soát độ chính xác của ước tính hạt nhân.

Tóm tắt phổ biến

Máy vectơ hỗ trợ lượng tử là ứng cử viên để chứng minh lợi thế lượng tử trong tương lai gần cho các vấn đề phân loại. Ý tưởng là một hàm hạt nhân (hy vọng là hữu ích) được đưa ra bởi một mạch lượng tử hiệu quả mà về mặt kinh điển rất khó đánh giá. Do tính chất xác suất của cơ học lượng tử nên các hàm hạt nhân bị ảnh hưởng bởi độ bất định thống kê. Trong công việc này, chúng tôi phân tích chặt chẽ mức độ không chắc chắn này (còn gọi là nhiễu bắn) ảnh hưởng đến độ phức tạp tính toán tổng thể để giải quyết vấn đề phân loại.

► Dữ liệu BibTeX

► Tài liệu tham khảo

[1] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe và S. Lloyd. Học máy lượng tử. Thiên nhiên, 549(7671):195–202, 2017. DOI: 10.1038/​nature23474.
https: / / doi.org/ 10.1038 / thiên nhiên23474

[2] V. Havlíček, AD Córcoles, K. Temme, AW Harrow, A. Kandala, JM Chow và JM Gambetta. Học tập có giám sát với không gian tính năng được tăng cường lượng tử. Thiên nhiên, 567(7747):209–212, 2019. DOI: 10.1038/​s41586-019-0980-2.
https:/​/​doi.org/​10.1038/​s41586-019-0980-2

[3] A. Abbas, D. Sutter, C. Zoufal, A. Lucchi, A. Figalli và S. Woerner. Sức mạnh của mạng lưới thần kinh lượng tử. Khoa học tính toán tự nhiên, ngày 1 (tháng 2020), năm 10.1038. DOI: 43588/​s021-00084-1-XNUMX.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] Y. Liu, S. Arunachalam và K. Temme. Tăng tốc lượng tử một cách nghiêm ngặt và mạnh mẽ trong học máy có giám sát. Vật lý Tự nhiên, 2021. DOI: 10.1038/​s41567-021-01287-z.
https: / / doi.org/ 10.1038 / s41567-021-01287-z

[5] S. Aaronson. Đọc bản in đẹp. Vật lý Tự nhiên, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https: / / doi.org/ 10.1038 / nphys3272

[6] E. Đường. Một thuật toán cổ điển lấy cảm hứng từ lượng tử cho các hệ thống khuyến nghị. 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 máy tính, STOC 2019, trang 217–228, New York, NY, Hoa Kỳ, 2019. Hiệp hội Máy tính. DOI: 10.1145/​3313276.3316310.
https: / / doi.org/ 10.1145 / 3313276.3316310

[7] N.-H. Chia, A. Gilyén, T. Li, H.-H. Lin, E. Tang và C. Wang. Khung số học ma trận xếp hạng thấp tuyến tính dựa trên lấy mẫu để giải lượng tử học máy lượng tử, trang 387–400. Hiệp hội Máy tính, New York, NY, Hoa Kỳ, 2020. Có sẵn trực tuyến: https://​/​doi.org/​10.1145/​3357713.3384314.
https: / / doi.org/ 10.1145 / 3357713.3384314

[8] T. Li, S. Chakrabarti và X. Wu. Các thuật toán lượng tử tuyến tính để đào tạo các bộ phân loại tuyến tính và dựa trên hạt nhân. Trong Hội nghị quốc tế về học máy, trang 3815–3824. PMLR, 2019.

[9] S. Thanasilp, S. Wang, M. Cerezo và Z. Holmes. Nồng độ theo cấp số nhân và khả năng không thể huấn luyện trong các phương pháp hạt nhân lượng tử, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https: / / doi.org/ 10.48550 / ARXIV.2208.11060

[10] S. Shalev-Shwartz và N. Srebro. Tối ưu hóa SVM: Sự phụ thuộc nghịch đảo vào kích thước tập huấn luyện. Kỷ yếu của Hội nghị quốc tế lần thứ 25 về Học máy, trang 928–935, 2008.

[11] A. Thomsen. So sánh mạng lưới thần kinh lượng tử và máy vectơ hỗ trợ lượng tử. Luận văn thạc sĩ, ETH Zurich, 2021-09-06. DOI: 20.500.11850/​527559.

[12] BE Boser, IM Guyon và VN Vapnik. Thuật toán đào tạo cho bộ phân loại ký quỹ tối ưu. Trong Kỷ yếu của Hội thảo thường niên lần thứ năm về Lý thuyết học tính toán, COLT '92, trang 144–152, New York, NY, Hoa Kỳ, 1992. Hiệp hội Máy tính. DOI: 10.1145/​130385.130401.
https: / / doi.org/ 10.1145 / 130385.130401

[13] C. Cortes và V. Vapnik. Mạng vectơ hỗ trợ. Trong Học máy, trang 273–297, 1995.

[14] VN Vapnik. Bản chất của lý thuyết học thống kê. Springer Science+Business Media, LLC, 2000.

[15] F. Pedregosa và cộng sự. Scikit-learn: Học máy bằng Python. Tạp chí Nghiên cứu Học máy, 12(85):2825–2830, 2011. Có sẵn trực tuyến: http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html

[16] S. Boyd và L. Vandenberghe. Tối ưu hoá trực quan. Nhà xuất bản Đại học Cambridge, 2004.

[17] S. Shalev-Shwartz, Y. Singer, N. Srebro và A. Cotter. Pegasos: Bộ giải gradient phụ ước tính cơ bản cho SVM. Lập trình toán học, 127(1):3–30, 2011. DOI: 10.1007/​s10107-010-0420-4.
https:/​/​doi.org/​10.1007/​s10107-010-0420-4

[18] MDS Anis và cộng sự. Qiskit: Khung nguồn mở cho điện toán lượng tử, 2021. DOI: 10.5281/​zenodo.2573505.
https: / / doi.org/ 10.5281 / zenodo.2573505

[19] P. Rebentrost, M. Mohseni và S. Lloyd. Máy vectơ hỗ trợ lượng tử để phân loại dữ liệu lớn Thư Đánh giá Vật lý, 113(3):1–5, 2014. DOI: 10.1103/​PhysRevLett.113.130503.
https: / / doi.org/ 10.1103 / PhysRevLett.113.130503

[20] J. Kübler, S. Buchholz và B. Schölkopf. Độ lệch quy nạp của hạt nhân lượng tử. Trong M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang và JW Vaughan, biên tập viên, Những tiến bộ trong Hệ thống xử lý thông tin thần kinh, tập 34, trang 12661–12673. Curran Associates, Inc., 2021. Có sẵn trực tuyến: 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é và C. Ciuti. Máy hạt nhân lượng tử ồn ào. Vật lý. Rev. A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

[22] CJC Burges và CJC Burges. Hướng dẫn về việc hỗ trợ các máy véctơ để nhận diện mẫu. Khai thác dữ liệu và khám phá tri thức, 2:121–167, 1998. Có sẵn trực tuyến: https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -machines-for-pattern-nhận dạng/​.
https://​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector-machines-for-pattern-recognition/​

[23] M. Cerezo, A. Sone, T. Volkoff, L. Cincio và PJ Coles. Các cao nguyên cằn cỗi phụ thuộc vào hàm chi phí trong các mạch lượng tử được tham số hóa nông. Truyền thông Thiên nhiên, 12(1):1791, 2021. DOI: 10.1038/​s41467-021-21728-w.
https: / / doi.org/ 10.1038 / s41467-021-21728-w

[24] Belis, Vasilis, González-Castillo, Samuel, Reissel, Christina, Vallecorsa, Sofia, Combarro, Elías F., Dissertori, Günther, và Reiter, Florentin. Phân tích Higgs với máy phân loại lượng tử. Hội nghị Web EPJ, 251:03070, 2021. DOI: 10.1051/​epjconf/​202125103070.
https: / / doi.org/ 10.1051 / epjconf / 202125103070

[25] M. Cerezo, A. Arrasmith, R. Babbush, SC Benjamin, S. Endo, K. Fujii, JR McClean, K. Mitarai, X. Yuan, L. Cincio và PJ Coles. Các thuật toán lượng tử biến thiên. Tạp chí Tự nhiên Vật lý, 3(9):625–644, 2021. DOI: 10.1038/​s42254-021-00348-9.
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[26] R. McGibborn và cộng sự. quadprog: Bộ giải lập trình bậc hai (python). https://​/​github.com/​quadprog/​quadprog, 2022.
https://​/​github.com/​quadprog/​quadprog

[27] Y. Nesterov. Bài giảng giới thiệu về Tối ưu hóa lồi: Một khóa học cơ bản. Tối ưu hóa ứng dụng. Springer, 2004. DOI: 10.1007/​978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] J. Spall. Tổng quan về phương pháp nhiễu loạn đồng thời để tối ưu hóa hiệu quả. Thông báo Kỹ thuật APL của John Hopkins, 19(4), trang 482–492, 1998.

[29] G. Gentinetta, A. Thomsen, D. Sutter và S. Woerner. Mã cho bản thảo “Sự phức tạp của máy vectơ hỗ trợ lượng tử”. 2022. DOI: https://​/​doi.org/​10.5281/​zenodo.6303725.
https: / / doi.org/ 10.5281 / zenodo.6303725

[30] T. Hubregtsen, D. Wierichs, E. Gil-Fuster, P.-JHS Derks, PK Faehrmann và JJ Meyer. Đào tạo hạt nhân nhúng lượng tử trên máy tính lượng tử ngắn hạn. Vật lý. Rev. A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

[31] R. Latała. Một số ước lượng chuẩn của ma trận ngẫu nhiên. Kỷ yếu của Hiệp hội Toán học Hoa Kỳ, 133(5):1273–1282, 2005. DOI: 10.1090/​s0002-9939-04-07800-1.
https:/​/​doi.org/​10.1090/​s0002-9939-04-07800-1

[32] R. Vershynin. Giới thiệu về phân tích không tiệm cận của ma trận ngẫu nhiên. Cảm biến nén: Lý thuyết và ứng dụng, trang 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https: / / doi.org/ 10.1017 / CBO9780511794308.006

[33] T. Hofmann, B. Schölkopf và AJ Smola. Các phương pháp hạt nhân trong học máy. Biên niên sử Thống kê, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https: / / doi.org/ 10.1214 / 009053607000000677

[34] JW Daniel. Tính ổn định của nghiệm của chương trình bậc hai xác định. Lập trình toán học, 5(1):41–53, 1973. DOI: 10.1007/​BF01580110.
https: / / doi.org/ 10.1007 / BF01580110

Trích dẫn

[1] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, và Fernando GSL Brandão, “Thuật toán lượng tử: Khảo sát về các ứng dụng và độ phức tạp từ đầu đến cuối”, arXiv: 2310.03011, (2023).

[2] Maria Schuld và Nathan Killoran, “Lợi thế lượng tử có phải là mục tiêu phù hợp cho việc học máy lượng tử không?”, PRX lượng tử 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik và Ofer Lahav, “Một máy vectơ hỗ trợ tăng cường lượng tử để phân loại thiên hà”, Kỹ thuật và dụng cụ RAS 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung và Chen-Yu Liu, “Máy vectơ hỗ trợ tăng cường lượng tử để phân loại sao quy mô lớn với khả năng tăng tốc GPU”, arXiv: 2311.12328, (2023).

[5] Supanut Thanasilp, Samson Wang, M. Cerezo và Zoë Holmes, “Nồng độ hàm mũ và tính không thể huấn luyện trong các phương pháp hạt nhân lượng tử”, arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka và Naoki Yamamoto, “Mạng lưới thần kinh lai lượng tử-cổ điển trong chế độ hạt nhân tiếp tuyến thần kinh”, Khoa học và Công nghệ Lượng tử 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo và Rudy Raymond, “Học máy lượng tử trên các thiết bị lượng tử ngắn hạn: Hiện trạng các kỹ thuật được giám sát và không giám sát cho các ứng dụng trong thế giới thực”, arXiv: 2307.00908, (2023).

[8] Raoul Heese, Thore Gerlach, Sascha Mücke, Sabine Müller, Matthias Jakobs và Nico Piatkowski, “Giải thích mạch lượng tử bằng các giá trị Shapley: Hướng tới việc học máy lượng tử có thể giải thích được”, arXiv: 2301.09138, (2023).

[9] Julien Gacon, Jannes Nys, Riccardo Rossi, Stefan Woerner và Giuseppe Carleo, “Sự tiến hóa theo thời gian lượng tử biến thiên không có Tensor hình học lượng tử”, arXiv: 2303.12839, (2023).

[10] Gian Gentinetta, David Sutter, Christa Zoufal, Bryce Fuller và Stefan Woerner, “Sự liên kết hạt nhân lượng tử với độ dốc giảm dần ngẫu nhiên”, arXiv: 2304.09899, (2023).

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie và Tim Scanlon, “Tái tạo các phân đoạn theo dõi hạt tích điện bằng máy vectơ hỗ trợ tăng cường lượng tử”, arXiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick và Thomas Ward, “Mô hình về thời gian chạy thực thi mạch và ý nghĩa của nó đối với hạt nhân lượng tử ở các kích thước tập dữ liệu thực tế”, arXiv: 2307.04980, (2023).

[13] Samantha V. Barron, Daniel J. Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler và Stefan Woerner, “Các giới hạn có thể chứng minh được cho các giá trị kỳ vọng không có tiếng ồn được tính toán từ các mẫu nhiễu”, arXiv: 2312.00733, (2023).

[14] M. Emre Sahin, Benjamin CB Symons, Pushpak Pati, Fayyaz Minhas, Declan Millar, Maria Gabrani, Jan Lukas Robertus và Stefano Mensa, “Tối ưu hóa tham số hiệu quả để căn chỉnh hạt nhân lượng tử: Phương pháp lấy mẫu phụ trong đào tạo biến phân” , arXiv: 2401.02879, (2024).

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 2024 / 01-12 02:12:22). 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 đủ.

On Dịch vụ trích dẫn của Crossref không có dữ liệu về các công việc trích dẫn được tìm thấy (lần thử cuối cùng 2024 / 01-12 02:12:21).

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ọ.

Dấu thời gian:

Thêm từ Tạp chí lượng tử