論文の概要: Provable Advantage in Quantum PAC Learning

• arxiv url: http://arxiv.org/abs/2309.10887v1
• Date: Tue, 19 Sep 2023 19:26:20 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-21 18:05:15.199427
• Title: Provable Advantage in Quantum PAC Learning
• Title（参考訳）: 量子PAC学習における確率的アドバンテージ
• Authors: Wilfred Salmon, Sergii Strelchuk, Tom Gur
• Abstract要約: PAC学習者は量子学習において汎用的な優位性を得ることができることを示す。 多相性因子は古典的な学習サンプルの複雑さよりも正方形の改善である。
• 参考スコア（独自算出の注目度）: 3.291862617649511
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We revisit the problem of characterising the complexity of Quantum PAC learning, as introduced by Bshouty and Jackson [SIAM J. Comput. 1998, 28, 1136-1153]. Several quantum advantages have been demonstrated in this setting, however, none are generic: they apply to particular concept classes and typically only work when the distribution that generates the data is known. In the general case, it was recently shown by Arunachalam and de Wolf [JMLR, 19 (2018) 1-36] that quantum PAC learners can only achieve constant factor advantages over classical PAC learners. We show that with a natural extension of the definition of quantum PAC learning used by Arunachalam and de Wolf, we can achieve a generic advantage in quantum learning. To be precise, for any concept class $\mathcal{C}$ of VC dimension $d$, we show there is an $(\epsilon, \delta)$-quantum PAC learner with sample complexity \[ O\left(\frac{1}{\sqrt{\epsilon}}\left[d+ \log(\frac{1}{\delta})\right]\log^9(1/\epsilon)\right). \] Up to polylogarithmic factors, this is a square root improvement over the classical learning sample complexity. We show the tightness of our result by proving an $\Omega(d/\sqrt{\epsilon})$ lower bound that matches our upper bound up to polylogarithmic factors.
• Abstract（参考訳）: 我々は、Bshouty と Jackson (SIAM J. Comput. 1998, 28 1136-1153) によって導入された量子PAC学習の複雑さを特徴づける問題を再考する。 それらは特定の概念クラスに適用され、典型的にはデータを生成する分布が知られている場合にのみ機能する。 一般の場合、Arunachalam と de Wolf [JMLR, 19 (2018) 1-36] により、量子PAC学習者は古典的なPAC学習者よりも定数係数の利点しか得られないことを示した。 Arunachalam と de Wolf が用いた量子PAC学習の定義を自然に拡張することで、量子学習における汎用的な優位性を実現できることを示す。 正確には、VC 次元 $d$ の任意の概念クラス $\mathcal{C}$ に対して、サンプル複雑性 \[O\left(\frac{1}{\sqrt{\epsilon}}\left[d+ \log(\frac{1}{\delta})\right]\log^9(1/\epsilon)\right を持つ$(\epsilon, \delta)$-quantum PAC 学習者が存在することを示す。 ]多対数因子を考えると、これは古典的学習サンプルの複雑さよりも二乗根の改善である。 この結果の厳密性は、上界を多対数因子に一致する$\Omega(d/\sqrt{\epsilon})$下界を証明することによって示される。

関連論文リスト

• New Bounds on Quantum Sample Complexity of Measurement Classes [18.531114735719274]
  本稿では量子状態からの古典的推論のための量子教師あり学習について研究する。 学習の難しさは、よく知られたほぼ正しい(PAC)量子対して、サンプルの複雑さによって測定される
  論文  参考訳（メタデータ） (2024-08-22T18:43:13Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Proper vs Improper Quantum PAC learning [3.292420364429101]
  本稿では,サンプリング複雑性を伴う量子クーポンコレクタ問題に対するアルゴリズムを提案する。 両学習モードにおける古典的クーポンコレクタ問題と,そのサンプルの複雑性が一致することを証明した。 パディングがより一般的に、古典的な学習行動から量子環境へと持ち上げられることを願っています。
  論文  参考訳（メタデータ） (2024-03-05T19:49:44Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• A Quadratic Sample Complexity Reduction for Agnostic Learning via Quantum Algorithms [0.0]
  我々は,$O(mboxlog(frac1delta)/epsilon)を$epsilon,deltarightarrow 0arrowとして新しいサンプル複雑性上限を求める。 一般学習の場合、学習速度の量子スピードアップは、$epsilon-1$の2乗である。
  論文  参考訳（メタデータ） (2023-10-24T07:39:16Z)
• Optimal lower bounds for Quantum Learning via Information Theory [3.093890460224435]
  我々は、PACとモデルの両方において、情報理論的アプローチにより、量子サンプルの複雑さに対して最適な下界を導出する。 次に、確率論から古典的な問題であるクーポンコレクタ問題(英語版)の量子アナログに目を向ける。 量子クーポンコレクター問題のすべての側面は、関連するグラム行列のスペクトルの性質について研究する。
  論文  参考訳（メタデータ） (2023-01-05T18:55:04Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Exponential separations between learning with and without quantum memory [17.763817187554096]
  量子システムと力学の学習特性を学習するための量子メモリのパワーについて検討する。 多くの最先端の学習アルゴリズムは、追加の外部量子メモリへのアクセスを必要とする。 このトレードオフは、幅広い学習問題に固有のものであることを示す。
  論文  参考訳（メタデータ） (2021-11-10T19:03:49Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。 正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
  論文  参考訳（メタデータ） (2020-06-22T17:53:54Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。