Kompleksitas mesin vektor dukungan kuantum

Kompleksitas mesin vektor dukungan kuantum

Stempel Waktu: 11 Januari 2024 9
Node Sumber: 3057476

Gian Gentinetta1,2, Arne Thomsen3,2, David Sutter2, dan Stefan Woerner2

1Institut Fisika, École Polytechnique Fédérale de Lausanne
2IBM Quantum, IBM Research Eropa – Zurich
3Departemen Fisika, ETH Zurich

Apakah makalah ini menarik atau ingin dibahas? Scite atau tinggalkan komentar di SciRate.

Abstrak

Mesin vektor dukungan kuantum menggunakan sirkuit kuantum untuk menentukan fungsi kernel. Telah terbukti bahwa pendekatan ini menawarkan percepatan eksponensial yang dapat dibuktikan dibandingkan dengan algoritma klasik yang dikenal untuk kumpulan data tertentu. Pelatihan model tersebut berhubungan dengan penyelesaian masalah optimasi cembung baik melalui formulasi primal atau ganda. Karena sifat mekanika kuantum yang probabilistik, algoritme pelatihan dipengaruhi oleh ketidakpastian statistik, yang berdampak besar pada kompleksitasnya. Kami menunjukkan bahwa masalah ganda dapat diselesaikan dalam evaluasi rangkaian kuantum $O(M^{4.67}/varepsilon^2)$, dengan $M$ menunjukkan ukuran kumpulan data dan $varepsilon$ akurasi solusi dibandingkan dengan ideal dihasilkan dari nilai ekspektasi yang tepat, yang hanya dapat diperoleh secara teori. Kami membuktikan berdasarkan asumsi yang dimotivasi secara empiris bahwa masalah primal yang dikernelisasi dapat diselesaikan secara alternatif dalam evaluasi $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ dengan menggunakan generalisasi dari pendekatan klasik yang diketahui algoritma yang disebut Pegasos. Hasil empiris yang menyertainya menunjukkan kompleksitas analitis ini sangat ketat. Selain itu, kami menyelidiki perkiraan variasional terhadap mesin vektor dukungan kuantum dan menunjukkan bahwa pelatihan heuristiknya mencapai penskalaan yang jauh lebih baik dalam eksperimen kami.

Gambar unggulan: Estimasi nilai kernel $k(mathbf{x}_i, mathbf{x}_j)$, dengan $mathcal{E}(mathbf{x}_i)$ menunjukkan kesatuan yang diparametrikan oleh data $mathbf{x }_i$. Jumlah tembakan diberikan oleh $R$ yang mengontrol keakuratan estimasi kernel.

Ringkasan populer

Mesin vektor dukungan kuantum adalah kandidat untuk menunjukkan keunggulan kuantum dalam waktu dekat untuk masalah klasifikasi. Idenya adalah bahwa fungsi kernel (semoga bermanfaat) diberikan oleh rangkaian kuantum efisien yang secara klasik sulit untuk dievaluasi. Karena sifat probabilistik mekanika kuantum, fungsi kernel tersebut dipengaruhi oleh ketidakpastian statistik. Dalam karya ini, kami menganalisis dengan cermat bagaimana ketidakpastian ini (juga disebut shot noise) berdampak pada kompleksitas komputasi secara keseluruhan untuk memecahkan masalah klasifikasi.

► data BibTeX

► Referensi

[1] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, dan S. Lloyd. Pembelajaran mesin kuantum. Alam, 549(7671):195–202, 2017. DOI: 10.1038/​nature23474.
https: / / doi.org/ 10.1038 / nature23474

[2] V. Havlíček, AD Córcoles, K. Temme, AW Harrow, A. Kandala, JM Chow, dan JM Gambetta. Pembelajaran yang diawasi dengan ruang fitur yang disempurnakan secara kuantum. Alam, 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, dan S. Woerner. Kekuatan jaringan saraf kuantum. Ilmu Komputasi Alam, 1(Juni), 2020. DOI: 10.1038/​s43588-021-00084-1.
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

[4] Y. Liu, S. Arunachalam, dan K. Temme. Percepatan kuantum yang ketat dan kuat dalam pembelajaran mesin yang diawasi. Fisika Alam, 2021. DOI: 10.1038/​s41567-021-01287-z.
https: / / doi.org/ 10.1038 / s41567-021-01287-z

[5] S.Aaronson. Baca cetakan kecilnya. Fisika Alam, 11(4):291–293, 2015. DOI: 10.1038/​nphys3272.
https://​/​doi.org/​10.1038/​nphys3272

[6] E.Tang. Algoritme klasik yang terinspirasi kuantum untuk sistem rekomendasi. Dalam Prosiding Simposium ACM SIGACT Tahunan ke-51 tentang Teori Komputasi, STOC 2019, halaman 217–228, New York, NY, AS, 2019. Asosiasi Mesin Komputasi. 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, dan C. Wang. Kerangka Kerja Aritmatika Matriks Tingkat Rendah Sublinear Berbasis Pengambilan Sampel untuk Dequantizing Quantum Machine Learning, halaman 387–400. Association for Computing Machinery, New York, NY, USA, 2020. Tersedia online: https:/​/​doi.org/​10.1145/​3357713.3384314.
https: / / doi.org/ 10.1145 / 3357713.3384314

[8] T.Li, S. Chakrabarti, dan X.Wu. Algoritma kuantum sublinear untuk melatih pengklasifikasi linier dan berbasis kernel. Dalam Konferensi Internasional tentang Pembelajaran Mesin, halaman 3815–3824. PMLR, 2019.

[9] S. Thanasilp, S. Wang, M. Cerezo, dan Z. Holmes. Konsentrasi eksponensial dan ketidakterlatihan dalam metode kernel kuantum, 2022. DOI: 10.48550/​ARXIV.2208.11060.
https://​/​doi.org/​10.48550/​ARXIV.2208.11060

[10] S. Shalev-Shwartz dan N. Srebro. Optimasi SVM: Ketergantungan terbalik pada ukuran set pelatihan. Prosiding Konferensi Internasional ke-25 tentang Pembelajaran Mesin, halaman 928–935, 2008.

[11] A.Thomsen. Membandingkan jaringan saraf kuantum dan mesin vektor dukungan kuantum. Tesis Master, ETH Zurich, 2021-09-06. DOI: 20.500.11850/​527559.

[12] JADILAH Boser, IM Guyon, dan VN Vapnik. Algoritma Pelatihan untuk Pengklasifikasi Margin Optimal. Dalam Prosiding Lokakarya Tahunan Kelima tentang Teori Pembelajaran Komputasi, COLT '92, halaman 144–152, New York, NY, AS, 1992. Asosiasi Mesin Komputasi. DOI: 10.1145/​130385.130401.
https: / / doi.org/ 10.1145 / 130385.130401

[13] C. Cortes dan V. Vapnik. Jaringan dukungan-vektor. Dalam Pembelajaran Mesin, halaman 273–297, 1995.

[14] VN Vapnik. Sifat Teori Pembelajaran Statistik. Springer Sains + Media Bisnis, LLC, 2000.

[15] F.Pedregosa dkk. Scikit-learn: Pembelajaran Mesin dengan Python. Jurnal Penelitian Pembelajaran Mesin, 12(85):2825–2830, 2011. Tersedia online: http://​/​jmlr.org/​papers/​v12/​pedregosa11a.html.
http:/​/​jmlr.org/​papers/​v12/​pedregosa11a.html

[16] S. Boyd dan L. Vandenberghe. Optimasi Cembung. Pers Universitas Cambridge, 2004.

[17] S. Shalev-Shwartz, Y. Singer, N. Srebro, dan A. Cotter. Pegasos: Estimasi primal pemecah sub-gradien untuk SVM. Pemrograman Matematika, 127(1):3–30, 2011. DOI: 10.1007/​s10107-010-0420-4.
https:/​/​doi.org/​10.1007/​s10107-010-0420-4

[18] MDS Anis dkk. Qiskit: Kerangka Sumber Terbuka untuk Komputasi Kuantum, 2021. DOI: 10.5281/​zenodo.2573505.
https: / / doi.org/ 10.5281 / zenodo.2573505

[19] P. Rebentrost, M. Mohseni, dan S. Lloyd. Mesin vektor dukungan kuantum untuk klasifikasi data besar. Surat Tinjauan Fisik, 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, dan B. Schölkopf. Bias induktif inti kuantum. Dalam M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, dan JW Vaughan, editor, Advances in Neural Information Processing Systems, volume 34, halaman 12661–12673. Curran Associates, Inc., 2021. Tersedia online: 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é, dan C. Ciuti. Mesin kernel kuantum yang berisik. Fis. Rev.A, 106:052421, 2022. DOI: 10.1103/​PhysRevA.106.052421.
https: / / doi.org/ 10.1103 / PhysRevA.106.052421

[22] CJC Burges dan CJC Burges. Tutorial tentang Mesin Vektor Dukungan untuk Pengenalan Pola. Penambangan Data dan Penemuan Pengetahuan, 2:121–167, 1998. Tersedia online: https:/​/​www.microsoft.com/​en-us/​research/​publication/​a-tutorial-on-support-vector -mesin-untuk-pengenalan-pola/​.
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, dan PJ Coles. Dataran tinggi tandus yang bergantung pada fungsi biaya di sirkuit kuantum berparametri dangkal. Komunikasi Alam, 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, dan Reiter, Florentin. Analisis Higgs dengan pengklasifikasi kuantum. Konferensi 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, dan PJ Coles. Algoritma kuantum variasi. Tinjauan Alam Fisika, 3(9):625–644, 2021. DOI: 10.1038/​s42254-021-00348-9.
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

[26] R. McGibborn dkk. quadprog: Pemecah pemrograman kuadrat (python). https:/​/​github.com/​quadprog/​quadprog, 2022.
https://​/​github.com/​quadprog/​quadprog

[27] Y.Nesterov. Kuliah Pengantar Optimasi Cembung: Kursus Dasar. Optimasi Terapan. Springer, 2004. DOI: 10.1007/​978-1-4419-8853-9.
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

[28] J. Spall. Gambaran Umum Metode Perturbasi Simultan untuk Optimasi yang Efisien. Intisari Teknis John Hopkins APL, 19(4), halaman 482–492, 1998.

[29] G. Gentinetta, A. Thomsen, D. Sutter, dan S. Woerner. Kode untuk manuskrip “Kompleksitas mesin vektor dukungan kuantum”. 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, dan JJ Meyer. Melatih kernel penyematan kuantum pada komputer kuantum jangka pendek. Fis. Rev.A, 106:042431, 2022. DOI: 10.1103/​PhysRevA.106.042431.
https: / / doi.org/ 10.1103 / PhysRevA.106.042431

[31] R. Latała. Beberapa perkiraan norma matriks acak. Prosiding American Mathematical Society, 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. Pengantar analisis matriks acak non-asimtotik. Penginderaan Terkompresi: Teori dan Aplikasi, halaman 210–268, 2009. DOI: 10.1017/​CBO9780511794308.006.
https: / / doi.org/ 10.1017 / CBO9780511794308.006

[33] T. Hofmann, B. Schölkopf, dan AJ Smola. Metode kernel dalam pembelajaran mesin. Sejarah Statistik, 36(3):1171–1220, 2008. DOI: 10.1214/​009053607000000677.
https: / / doi.org/ 10.1214 / 009053607000000677

[34] JW Daniel. Stabilitas penyelesaian program kuadrat pasti. Pemrograman Matematika, 5(1):41–53, 1973. DOI: 10.1007/​BF01580110.
https: / / doi.org/ 10.1007 / BF01580110

Dikutip oleh

[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, dan Fernando GSL Brandão, “Algoritme kuantum: Survei aplikasi dan kompleksitas ujung ke ujung”, arXiv: 2310.03011, (2023).

[2] Maria Schuld dan Nathan Killoran, “Apakah Keunggulan Quantum adalah Tujuan yang Tepat untuk Pembelajaran Mesin Quantum?”, PRX Kuantum 3 3, 030101 (2022).

[3] Mohammad Hassan Hassanshahi, Marcin Jastrzebski, Sarah Malik, dan Ofer Lahav, “Mesin vektor dukungan yang ditingkatkan kuantum untuk klasifikasi galaksi”, Teknik dan Instrumen RAS 2 1, 752 (2023).

[4] Kuan-Cheng Chen, Xiaotian Xu, Henry Makhanov, Hui-Hsuan Chung, dan Chen-Yu Liu, “Mesin Vektor Dukungan yang Ditingkatkan Kuantum untuk Klasifikasi Bintang Skala Besar dengan Akselerasi GPU”, arXiv: 2311.12328, (2023).

[5] Supanut Thanasilp, Samson Wang, M. Cerezo, dan Zoë Holmes, "Konsentrasi eksponensial dan ketidakterlatihan dalam metode kernel kuantum", arXiv: 2208.11060, (2022).

[6] Kouhei Nakaji, Hiroyuki Tezuka, dan Naoki Yamamoto, “Jaringan saraf hibrid kuantum-klasik dalam rezim kernel tangen saraf”, Sains dan Teknologi Kuantum 9 1, 015022 (2024).

[7] Yaswitha Gujju, Atsushi Matsuo, dan Rudy Raymond, “Pembelajaran Mesin Kuantum pada Perangkat Kuantum Jangka Pendek: Keadaan Teknik yang Diawasi dan Tidak Diawasi Saat Ini untuk Aplikasi Dunia Nyata”, arXiv: 2307.00908, (2023).

[8] Raoul Heese, Thore Gerlach, Sascha Mücke, Sabine Müller, Matthias Jakobs, dan Nico Piatkowski, “Menjelaskan Sirkuit Kuantum dengan Nilai Shapley: Menuju Pembelajaran Mesin Kuantum yang Dapat Dijelaskan”, arXiv: 2301.09138, (2023).

[9] Julien Gacon, Jannes Nys, Riccardo Rossi, Stefan Woerner, dan Giuseppe Carleo, “Variasional Evolusi Waktu Kuantum tanpa Tensor Geometris Kuantum”, arXiv: 2303.12839, (2023).

[10] Gian Gentinetta, David Sutter, Christa Zoufal, Bryce Fuller, dan Stefan Woerner, “Penyelarasan Kernel Quantum dengan Penurunan Gradien Stochastic”, arXiv: 2304.09899, (2023).

[11] Philippa Duckett, Gabriel Facini, Marcin Jastrzebski, Sarah Malik, Sebastien Rettie, dan Tim Scanlon, “Merekonstruksi segmen jalur partikel bermuatan dengan mesin vektor dukungan yang ditingkatkan kuantum”, arXiv: 2212.07279, (2022).

[12] Travis L. Scholten, Derrick Perry, Joseph Washington, Jennifer R. Glick, dan Thomas Ward, “Model untuk Runtime Eksekusi Sirkuit Dan Implikasinya terhadap Kernel Kuantum Pada Ukuran Kumpulan Data Praktis”, arXiv: 2307.04980, (2023).

[13] Samantha V. Barron, Daniel J. Egger, Elijah Pelofske, Andreas Bärtschi, Stephan Eidenbenz, Matthis Lehmkuehler, dan Stefan Woerner, “Batas yang dapat dibuktikan untuk nilai ekspektasi bebas noise yang dihitung dari sampel yang berisik”, arXiv: 2312.00733, (2023).

[14] M. Emre Sahin, Benjamin CB Symons, Pushpak Pati, Fayyaz Minhas, Declan Millar, Maria Gabrani, Jan Lukas Robertus, dan Stefano Mensa, “Optimasi Parameter yang Efisien untuk Penyelarasan Kernel Kuantum: Pendekatan Sub-sampling dalam Pelatihan Variasi” , arXiv: 2401.02879, (2024).

Kutipan di atas berasal dari SAO / NASA ADS (terakhir berhasil diperbarui, 2024-01-12 02:12:22). Daftar ini mungkin tidak lengkap karena tidak semua penerbit menyediakan data kutipan yang cocok dan lengkap.

On Layanan dikutip-oleh Crossref tidak ada data tentang karya mengutip ditemukan (upaya terakhir 2024-01-12 02:12:21).

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.

Stempel Waktu:

Lebih dari Jurnal Kuantum