量子サポートベクターマシンの複雑さ

量子サポートベクターマシンの複雑さ

タイムスタンプ：11年2024月9日午前08時XNUMX分
ソースノード： 3057476

ジャン・ゲンティネッタ1,2, アルネ・トムセン3,2, デビッド・サッター2、およびStefan Woerner2

1ローザンヌ連邦エコール工科大学物理学研究所
2IBM Quantum、IBM Research Europe – チューリッヒ
3チューリッヒ工科大学物理学科

この論文を興味深いと思うか、議論したいですか？ SciRateを引用するかコメントを残す.

抽象

量子サポート ベクター マシンは、量子回路を使用してカーネル関数を定義します。このアプローチは、特定のデータセットに対して既知の古典的なアルゴリズムと比較して、証明可能な指数関数的な高速化を実現することが示されています。このようなモデルのトレーニングは、一次定式化または双対定式化のいずれかを介して凸最適化問題を解くことに対応します。量子力学の確率的性質により、トレーニング アルゴリズムは統計的不確実性の影響を受け、それがアルゴリズムの複雑さに大きな影響を与えます。 $O(M^{4.67}/varepsilon^2)$ 量子回路評価で双対問題を解決できることを示します。ここで、$M$ はデータセットのサイズを示し、$varepsilon$ は理想と比較した解の精度を示します。正確な期待値から結果が得られますが、これは理論的にのみ得られます。経験的に動機づけられた仮定の下で、カーネル化された主問題は、既知の古典的な問題の一般化を採用することによって $O(min { M^2/varepsilon^6, , 1/varepsilon^{10} })$ 評価でも解決できることを証明します。 Pegasosと呼ばれるアルゴリズム。付随する実験結果は、これらの分析の複雑さが本質的に厳しいことを示しています。さらに、量子サポート ベクター マシンの変分近似を調査し、そのヒューリスティック トレーニングが実験で大幅に優れたスケーリングを達成することを示します。

注目の画像: カーネル値 $k(mathbf{x}_i, mathbf{x}_j)$ の推定、ここで $mathcal{E}(mathbf{x}_i)$ はデータ $mathbf{x によってパラメータ化されたユニタリーを示します}_i$。ショットの数は、カーネル推定の精度を制御する $R$ によって与えられます。

人気の要約

量子サポート ベクター マシンは、近い将来、分類問題に対する量子の利点を実証する候補です。その考え方は、（うまくいけば役に立つ）カーネル関数は、古典的に評価するのが難しい効率的な量子回路によって与えられるということです。量子力学の確率的性質により、このようなカーネル関数は統計的不確実性の影響を受けます。この研究では、この不確実性 (ショット ノイズとも呼ばれます) が、分類問題を解決するための全体的な計算の複雑さにどのような影響を与えるかを厳密に分析します。

►BibTeXデータ

►参照

【1] J. ビアモンテ、P. ウィテック、N. パンコッティ、P. レベントロスト、N. ウィーブ、および S. ロイド。量子機械学習。 Nature、549(7671):195–202、2017。DOI: 10.1038/ nature23474。
https：/ / doi.org/ 10.1038 / nature23474

【2] V. ハブリチェク、A. D. コルコレス、K. テンメ、A. W. ハロー、A. カンダラ、J. M. チョウ、J. M. ガンベッタ。量子強化特徴空間を使用した教師あり学習。 Nature、567(7747):209–212、2019。DOI: 10.1038/ s41586-019-0980-2。
https:/​/​doi.org/​10.1038/​s41586-019-0980-2

【3] A. アッバス、D. サッター、C. ズファル、A. ルッキ、A. フィガリ、S. ヴェルナー。量子ニューラル ネットワークの力。 Nature Computational Science、1(2020 月)、10.1038 年。DOI: 43588/ s021-00084-1-XNUMX。
https:/​/​doi.org/​10.1038/​s43588-021-00084-1

【4] Y. リュー、S. アルナーチャラム、K. テメ。教師あり機械学習における厳密かつ堅牢な量子高速化。 Nature Physics、2021。DOI: 10.1038/ s41567-021-01287-z。
https：/ / doi.org/ 10.1038 / s41567-021-01287-z

【5] S・アーロンソン。詳細の閲覧。 Nature Physics、11(4):291–293、2015。DOI: 10.1038/nphys3272。
https：/ / doi.org/ 10.1038 / nphys3272

【6] E.タン。量子にインスピレーションを得た、レコメンデーション システム用の古典的なアルゴリズム。コンピューティング理論に関する第 51 回年次 ACM SIGACT シンポジウム議事録、STOC 2019、217 ～ 228 ページ、ニューヨーク、ニューヨーク、米国、2019 年。コンピューティング機械協会。 DOI: 10.1145/ 3313276.3316310。
https：/ / doi.org/ 10.1145 / 3313276.3316310

【7] N.-H.チア、A. ギレン、T. リー、H.-H.リン、E. タン、C. ワン。逆量子化量子機械学習のためのサンプリングベースのサブ線形低ランク行列演算フレームワーク (387 ～ 400 ページ)。 Association for Computing Machinery、米国ニューヨーク州ニューヨーク、2020年。オンラインで入手可能: https:/ / doi.org/ 10.1145/ 3357713.3384314。
https：/ / doi.org/ 10.1145 / 3357713.3384314

【8] T. リー、S. チャクラバルティ、X. ウー。線形およびカーネルベースの分類器をトレーニングするためのサブ線形量子アルゴリズム。機械学習に関する国際会議、3815 ～ 3824 ページ。 PMLR、2019年。

【9] S.タナシルプ、S.ワン、M.セレッソ、Z.ホームズ。量子カーネル法における指数集中と非訓練可能性、2022 年。DOI: 10.48550/ARXIV.2208.11060。
https：/ / doi.org/ 10.48550 / ARXIV.2208.11060

【10] S.シャレフ＝シュワルツとN.スレブロ。 SVM の最適化: トレーニング セットのサイズへの逆依存。第 25 回機械学習国際会議議事録、928 ～ 935 ページ、2008 年。

【11] A.トムセン。量子ニューラル ネットワークと量子サポート ベクター マシンの比較。修士論文、チューリッヒ工科大学、2021-09-06。 DOI: 20.500.11850/527559。

【12] B.E.ボーザー、I.M.ガイヨン、V.N.ヴァプニク。最適マージン分類器のトレーニング アルゴリズム。計算学習理論に関する第 92 回年次ワークショップ議事録、COLT '144、152 ～ 1992 ページ、ニューヨーク、ニューヨーク州、米国、10.1145 年。Association for Computing Machinery。 DOI: 130385.130401/ XNUMX。
https：/ / doi.org/ 10.1145 / 130385.130401

【13] C.コルテスとV.ヴァプニク。サポートベクター ネットワーク。 『機械学習』、273 ～ 297 ページ、1995 年。

【14] V.N.ヴァプニク。統計的学習理論の性質。シュプリンガー サイエンス + ビジネス メディア、LLC、2000 年。

【15] F.ペドレゴサら。 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] S.ボイドとL.ヴァンデンバーグ。凸型最適化。ケンブリッジ大学出版局、2004 年。

【17] S. シャレフ＝シュワルツ、Y. シンガー、N. スレブロ、A. コッター。 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.アニスら。 Qiskit: 量子コンピューティングのためのオープンソース フレームワーク、2021。DOI: 10.5281/ zenodo.2573505。
https：/ / doi.org/ 10.5281 / zenodo.2573505

【19] P. レベントロスト、M. モーセニ、S. ロイド。ビッグデータ分類用の量子サポート ベクター マシン。 Physical Review Letters、113(3):1–5、2014 年。DOI: 10.1103/PhysRevLett.113.130503。
https：/ / doi.org/ 10.1103 / PhysRevLett.113.130503

【20] J. キューブラー、S. ブッフホルツ、B. シェルコップ。量子カーネルの誘導バイアス。 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. ヘイロー、Z. リ、Z. デニス、A. ル ボワテ、C. シウティ。ノイズの多い量子カーネル マシン。物理学。 Rev. A、106:052421、2022。DOI: 10.1103/PhysRevA.106.052421。
https：/ / doi.org/ 10.1103 / PhysRevA.106.052421

【22] C.J.C.バージェスとC.J.C.バージェス。パターン認識のためのサポート ベクター マシンのチュートリアル。 Data Mining and Knowledge Discovery、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] M.セレッソ、A.曽根、T.ヴォルコフ、L.シンシオ、P.J.コールズ。浅いパラメータ化された量子回路におけるコスト関数に依存する不毛なプラトー。 Nature Communications、12(1):1791、2021。DOI: 10.1038/ s41467-021-21728-w。
https：/ / doi.org/ 10.1038 / s41467-021-21728-w

【24] ベリス、ヴァシリス、ゴンサレス＝カスティージョ、サミュエル、ライセル、クリスティーナ、バジェコルサ、ソフィア、コンバーロ、エリアス・F.、ディセルトーリ、ギュンター、ライター、フロレンティン。量子分類器を使用したヒッグス分析。 EPJ Web Conf.、251:03070、2021。DOI: 10.1051/epjconf/202125103070。
https：/ / doi.org/ 10.1051 / epjconf / 202125103070

【25] M. セレッソ、A. アラスミス、R. バブシュ、S. C. ベンジャミン、S. 遠藤、K. 藤井、J. R. マクリーン、K. 御手洗、X. ユアン、L. シンシオ、および P. J. コールズ。変分量子アルゴリズム。 Nature Reviews Physics、3(9):625–644、2021。DOI: 10.1038/ s42254-021-00348-9。
https:/​/​doi.org/​10.1038/​s42254-021-00348-9

【26] R.マクギボーンら。 quadprog: 二次計画法ソルバー (Python)。 https:/ / github.com/ quadprog/ quadprog、2022 年。
https:/ / github.com/ quadprog/ quadprog

【27] Y.ネステロフ。凸最適化の入門講義: 基礎コース。応用最適化。 Springer、2004 年。DOI: 10.1007/ 978-1-4419-8853-9。
https:/​/​doi.org/​10.1007/​978-1-4419-8853-9

【28] J.スポール。効率的な最適化のための同時摂動法の概要。ジョン・ホプキンス APL テクニカル・ダイジェスト、19(4)、482 ～ 492 ページ、1998 年。

【29] G. ゲンティネッタ、A. トムセン、D. サッター、S. ヴェルナー。原稿「量子サポート ベクター マシンの複雑さ」のコード。 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.-J. H. S. ダークス、P. K. ファーマン、J. J. マイヤー。近い将来の量子コンピューター上での量子埋め込みカーネルのトレーニング。物理学。 Rev. A、106:042431、2022。DOI: 10.1103/PhysRevA.106.042431。
https：/ / doi.org/ 10.1103 / PhysRevA.106.042431

【31] R.ラタワ。ランダム行列のノルムの推定。アメリカ数学協会議事録、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. バーシャニン。ランダム行列の非漸近解析の紹介。圧縮センシング: 理論と応用、210 ～ 268 ページ、2009 年。DOI: 10.1017/CBO9780511794308.006。
https：/ / doi.org/ 10.1017 / CBO9780511794308.006

【33] T. ホフマン、B. シェルコップ、A. J. スモラ。機械学習におけるカーネルメソッド。 『統計年報』、36(3):1171–1220、2008 年。DOI: 10.1214/ 009053607000000677。
https：/ / doi.org/ 10.1214 / 009053607000000677

【34] J・W・ダニエル。定二次プログラムの解の安定性。数学的プログラミング、5(1):41–53、1973。DOI: 10.1007/BF01580110。
https：/ / doi.org/ 10.1007 / BF01580110

によって引用

[1] Alexander M. Dalzell、Sam McArdle、Mario Berta、Przemyslaw Bienias、Chi-Fang Chen、András Gilyen、Connor T. Hann、Michael J. Kastoryano、Emil T. Khabiboulline、Aleksander Kubica、Grant Salton、Samson Wang、およびFernando GSL Brandão、「量子アルゴリズム: アプリケーションとエンドツーエンドの複雑さの調査」、 arXiv：2310.03011, (2023).

[2] Maria Schuld と Nathan Killoran、「量子アドバンテージは量子機械学習の正しい目標ですか?」 PRX Quantum 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、Zoë Holmes、「量子カーネル法における指数集中と訓練不可能性」、 arXiv：2208.11060, (2022).

[6] 中路公平、手塚裕之、山本直樹、「ニューラルタンジェントカーネル領域における量子古典ハイブリッドニューラルネットワーク」、 量子科学技術9 1、015022（2024）.

[7] Yaswitha Gujju、松尾 篤、および 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、「確率的勾配降下法による量子カーネル アライメント」、 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 Aidenbenz、Mattis 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).

上記の引用は SAO / NASA ADS （最後に正常に更新された2024-01-12 02:12:22）。 すべての出版社が適切で完全な引用データを提供するわけではないため、リストは不完全な場合があります。

On Crossrefの被引用サービス 作品の引用に関するデータは見つかりませんでした（最後の試行2024-01-12 02:12:21）。

この論文は、 Creative Commons Attribution 4.0 International（CC BY 4.0） ライセンス。 著作権は、著者やその機関などの元の著作権者にあります。

タイムスタンプ：

より多くの 量子ジャーナル