論文の概要: On the Role of Entanglement and Statistics in Learning
- arxiv url: http://arxiv.org/abs/2306.03161v1
- Date: Mon, 5 Jun 2023 18:16:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-07 19:00:53.988378
- Title: On the Role of Entanglement and Statistics in Learning
- Title（参考訳）: 学習における絡み合いと統計の役割について
- Authors: Srinivasan Arunachalam, Vojtech Havlicek, Louis Schatzki
- Abstract要約: 我々は,絡み合った,分離可能な,統計的に測定された学習モデルと学習モデルとの関係を理解することを進める。
我々は、QSQ学習と量子学習を交絡測定で指数関数的に分離するクラスC$を示す。
我々は,純度テスト,シャドウトモグラフィ,アベリア隠れ部分群問題,次数2$関数,植込み双斜め状態,クリフォード深度回路の出力状態について,超ポリノミカルQSQの下界を証明した。
- 参考スコア（独自算出の注目度）: 4.984601297028256
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this work we make progress in understanding the relationship between
learning models with access to entangled, separable and statistical
measurements in the quantum statistical query (QSQ) model. To this end, we show
the following results.
$\textbf{Entangled versus separable measurements.}$ The goal here is to learn
an unknown $f$ from the concept class $C\subseteq \{f:\{0,1\}^n\rightarrow
[k]\}$ given copies of $\frac{1}{\sqrt{2^n}}\sum_x \vert x,f(x)\rangle$. We
show that, if $T$ copies suffice to learn $f$ using entangled measurements,
then $O(nT^2)$ copies suffice to learn $f$ using just separable measurements.
$\textbf{Entangled versus statistical measurements}$ The goal here is to
learn a function $f \in C$ given access to separable measurements and
statistical measurements. We exhibit a class $C$ that gives an exponential
separation between QSQ learning and quantum learning with entangled
measurements (even in the presence of noise). This proves the "quantum
analogue" of the seminal result of Blum et al. [BKW'03]. that separates
classical SQ and PAC learning with classification noise.
$\textbf{QSQ lower bounds for learning states.}$ We introduce a quantum
statistical query dimension (QSD), which we use to give lower bounds on the QSQ
learning. With this we prove superpolynomial QSQ lower bounds for testing
purity, shadow tomography, Abelian hidden subgroup problem, degree-$2$
functions, planted bi-clique states and output states of Clifford circuits of
depth $\textsf{polylog}(n)$.
$\textbf{Further applications.}$ We give and $\textit{unconditional}$
separation between weak and strong error mitigation and prove lower bounds for
learning distributions in the QSQ model. Prior works by Quek et al. [QFK+'22],
Hinsche et al. [HIN+'22], and Nietner et al. [NIS+'23] proved the analogous
results $\textit{assuming}$ diagonal measurements and our work removes this
assumption.
- Abstract（参考訳）: 本研究では,量子統計クエリ(QSQ)モデルにおいて,絡み合った,分離可能な,統計的に測定された学習モデル間の関係を理解する。
この目的のために、以下の結果を示す。
分離可能な測定値に対して$\textbf{entangled。
c\subseteq \{f:\{0,1\}^n\rightarrow [k]\}$ $\frac{1}{\sqrt{2^n}}\sum_x \vert x,f(x)\rangle$.} ここでの目標は、未知の$f$を、$\frac{1}{\sqrt{2^n}}\sum_x \vert x,f(x)\rangle$という概念クラスから学ぶことである。
もし$t$が、絡み合った測定値を使って$f$を学ぶのに十分であれば、$o(nt^2)$は、分離可能な測定値だけで$f$を学ぶのに十分である。
$\textbf{Entangled versus statistics Measurement} ここでのゴールは、分離可能な測定と統計測定へのアクセスを与えられた関数 $f \in C$ を学ぶことである。
qsq学習と(ノイズが存在する場合でも)絡み合った測定値を持つ量子学習を指数関数的に分離するクラス$c$を示す。
これはblum et alの独創的な結果の「量子アナログ」を証明している。
[BKW'03]。
これは古典的なSQとPAC学習を分類ノイズで分離する。
学習状態の上限は$\textbf{qsq である。
量子統計クエリーディメンション(QSD)を導入し、QSQ学習の下位境界を与える。
これにより、純度、シャドウトモグラフィ、アベリア隠れ部分群問題、次数2$の関数、植込み双斜め状態、深さ$\textsf{polylog}(n)$のクリフォード回路の出力状態をテストするための超多項式QSQの下界を証明できる。
$\textbf{Further アプリケーション。
弱いエラーと強いエラーの軽減を分離し、qsqモデルにおける学習分布の限界を低く証明します。
Quekらによる以前の作品。
qfk+'22] ヒンシュなどです
[hin+'22] と nietner 等。
NIS+'23]は類似の結果を$\textit{assuming}$ 対角測定で証明し、我々の研究はこの仮定を取り除いた。
関連論文リスト
- Space-bounded quantum interactive proof systems [2.623117146922531]
空間有界量子対話型証明システムの2つのモデル、$sf QIPL$と$sf QIP_rm UL$を紹介する。
$sf QIP_rm UL$モデルは、検証動作をユニタリ回路に制限する。対照的に、$sf QIPL$は検証動作ごとに、対数的に多くの中間測定を可能にする。
論文 参考訳（メタデータ） (2024-10-31T14:11:08Z) - A computational transition for detecting correlated stochastic block models by low-degree polynomials [13.396246336911842]
一対のランダムグラフにおける相関性の検出は、近年広く研究されている基本的な統計的および計算上の問題である。
一対の相関ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon;s)$ を共通の親ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon;s)$ からサブサンプリングする。
隣接部のエントリーのエンスロー度に基づくテストに焦点をあてる
論文 参考訳（メタデータ） (2024-09-02T06:14:05Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。
SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Statistical Query Lower Bounds for Learning Truncated Gaussians [43.452452030671694]
この問題のSQアルゴリズムの複雑さは、$dmathrmpoly (1/epsilon)$であり、クラス$mathcalC$が単純である場合でも、$mathrmpoly(d/epsilon)が情報理論的に十分であることを示す。
論文 参考訳（メタデータ） (2024-03-04T18:30:33Z) - Estimation and Inference in Distributional Reinforcement Learning [28.253677740976197]
サイズ$widetilde Oleft(frac|mathcalS||mathcalA|epsilon2 (1-gamma)4right)$ suffices to ensure the Kolmogorov metric and total variation metric between $hatetapi$ and $etapi$ is below $epsilon$ with high probability。
以上の結果から,多種多様な統計的汎関数の統計的推測への統一的アプローチがもたらされた。
論文 参考訳（メタデータ） (2023-09-29T14:14:53Z) - Learning (Very) Simple Generative Models Is Hard [45.13248517769758]
我々は,$mathbbRdtobbRd'$の出力座標が$mathrmpoly(d)$ニューロンを持つ一層ReLUネットワークである場合でも,リアルタイムアルゴリズムが問題を解決可能であることを示す。
我々の証明の鍵となる要素は、コンパクトに支持されたピースワイズ線形関数$f$をニューラルネットワークで束ねたスロープで構築することであり、$mathcalN(0,1)$のプッシュフォワードは$mathcalのすべての低度モーメントと一致する。
論文 参考訳（メタデータ） (2022-05-31T17:59:09Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - On the Power of Multitask Representation Learning in Linear MDP [61.58929164172968]
本稿では,線形マルコフ決定過程(MDP)におけるマルチタスク表現学習の統計的メリットについて分析する。
簡単な最小二乗アルゴリズムが $tildeO(H2sqrtfrackappa MathcalC(Phi)2 kappa dNT+frackappa dn) というポリシーを学ぶことを証明した。
論文 参考訳（メタデータ） (2021-06-15T11:21:06Z) - Tightening the Dependence on Horizon in the Sample Complexity of
Q-Learning [59.71676469100807]
この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。
計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
論文 参考訳（メタデータ） (2021-02-12T14:22:05Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。