論文の概要: New Bounds on Quantum Sample Complexity of Measurement Classes
- arxiv url: http://arxiv.org/abs/2408.12683v1
- Date: Thu, 22 Aug 2024 18:43:13 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-26 16:48:16.013368
- Title: New Bounds on Quantum Sample Complexity of Measurement Classes
- Title（参考訳）: 測定クラスの量子サンプル複雑度に関する新しい知見
- Authors: Mohsen Heidari, Wojciech Szpankowski,
- Abstract要約: 本稿では量子状態からの古典的推論のための量子教師あり学習について研究する。
学習の難しさは、よく知られたほぼ正しい(PAC)量子対して、サンプルの複雑さによって測定される
- 参考スコア（独自算出の注目度）: 18.531114735719274
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies quantum supervised learning for classical inference from quantum states. In this model, a learner has access to a set of labeled quantum samples as the training set. The objective is to find a quantum measurement that predicts the label of the unseen samples. The hardness of learning is measured via sample complexity under a quantum counterpart of the well-known probably approximately correct (PAC). Quantum sample complexity is expected to be higher than classical one, because of the measurement incompatibility and state collapse. Recent efforts showed that the sample complexity of learning a finite quantum concept class $\mathcal{C}$ scales as $O(|\mathcal{C}|)$. This is significantly higher than the classical sample complexity that grows logarithmically with the class size. This work improves the sample complexity bound to $O(V_{\mathcal{C}^*} \log |\mathcal{C}^*|)$, where $\mathcal{C}^*$ is the set of extreme points of the convex closure of $\mathcal{C}$ and $V_{\mathcal{C}^*}$ is the shadow-norm of this set. We show the tightness of our bound for the class of bounded Hilbert-Schmidt norm, scaling as $O(\log |\mathcal{C}^*|)$. Our approach is based on a new quantum empirical risk minimization (ERM) algorithm equipped with a shadow tomography method.
- Abstract（参考訳）: 本稿では量子状態からの古典的推論のための量子教師あり学習について研究する。
このモデルでは、学習者はトレーニングセットとしてラベル付き量子サンプルのセットにアクセスすることができる。
目的は、目に見えないサンプルのラベルを予測する量子測度を見つけることである。
学習の難易度は、よく知られたほぼ正しい(PAC)量子対のサンプル複雑性によって測定される。
量子サンプルの複雑さは、測定の不整合性と状態崩壊のため、古典的なものよりも高いと期待されている。
最近の研究により、有限量子概念クラス $\mathcal{C}$ を学ぶ際のサンプルの複雑さが$O(|\mathcal{C}|)$としてスケールされることが示されている。
これは、クラスサイズと対数的に増加する古典的なサンプルの複雑さよりもはるかに高い。
この研究は、サンプル複雑性を$O(V_{\mathcal{C}^*} \log |\mathcal{C}^*|)$に限定し、$\mathcal{C}^*$は、凸閉包の極点の集合である$\mathcal{C}$と$V_{\mathcal{C}^*}$は、この集合の影ノルムである。
我々は、有界ヒルベルト・シュミットノルムのクラスに対する境界の厳密性を示し、$O(\log |\mathcal{C}^*|)$としてスケールする。
提案手法は,シャドウトモグラフィー法を用いた新しい量子経験的リスク最小化(ERM)アルゴリズムに基づいている。
関連論文リスト
- Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。
我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文 参考訳（メタデータ） (2024-06-25T06:07:20Z) - Quantum State Learning Implies Circuit Lower Bounds [2.2667044928324747]
状態トモグラフィー、擬似ランダム性、量子状態、回路下界の接続を確立する。
わずかに自明な量子状態トモグラフィーアルゴリズムでさえも量子状態合成に関する新しい言明に繋がることを示した。
論文 参考訳（メタデータ） (2024-05-16T16:46:27Z) - Proper vs Improper Quantum PAC learning [3.292420364429101]
本稿では,サンプリング複雑性を伴う量子クーポンコレクタ問題に対するアルゴリズムを提案する。
両学習モードにおける古典的クーポンコレクタ問題と,そのサンプルの複雑性が一致することを証明した。
パディングがより一般的に、古典的な学習行動から量子環境へと持ち上げられることを願っています。
論文 参考訳（メタデータ） (2024-03-05T19:49:44Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Heisenberg-limited quantum phase estimation of multiple eigenvalues with
few control qubits [1.6328866317851185]
量子位相推定の単一制御量子ビット変種は、系の固有状態を準備できない場合にも、ハイゼンベルク極限を達成することができることを示す。
本稿では,行列鉛筆法を用いてハイゼンベルク限定スケーリングを実現できることを示す。
論文 参考訳（メタデータ） (2021-07-09T18:00:10Z) - Learning k-qubit Quantum Operators via Pauli Decomposition [11.498089180181365]
現在の量子系の量子ビット容量の制限により、量子サンプルの複雑さを$k$-qubit量子作用素で調べる。
我々は、$k$-qubitの量子演算の量子サンプルの複雑さが、その量子演算の古典的なサンプルの複雑さに匹敵することを示した。
論文 参考訳（メタデータ） (2021-02-10T01:20:55Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。