論文の概要: Optimal high-precision shadow estimation

• arxiv url: http://arxiv.org/abs/2407.13874v1
• Date: Thu, 18 Jul 2024 19:42:49 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-22 19:32:58.920398
• Title: Optimal high-precision shadow estimation
• Title（参考訳）: 最適高精度影推定
• Authors: Sitan Chen, Jerry Li, Allen Liu,
• Abstract要約: 正式には、未知の混合状態$rhoinmathbbCdtimes d$のコピーを$O(log(m)/epsilon2)$に測定するプロトコルを提供します。 次元還元により、$epsilon$と$d$を再スケールして、$epsilon le O(d-1/2)$の政権に還元できることを示す。
• 参考スコア（独自算出の注目度）: 22.01044188849049
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give the first tight sample complexity bounds for shadow tomography and classical shadows in the regime where the target error is below some sufficiently small inverse polynomial in the dimension of the Hilbert space. Formally we give a protocol that, given any $m\in\mathbb{N}$ and $\epsilon \le O(d^{-12})$, measures $O(\log(m)/\epsilon^2)$ copies of an unknown mixed state $\rho\in\mathbb{C}^{d\times d}$ and outputs a classical description of $\rho$ which can then be used to estimate any collection of $m$ observables to within additive accuracy $\epsilon$. Previously, even for the simpler task of shadow tomography -- where the $m$ observables are known in advance -- the best known rates either scaled benignly but suboptimally in all of $m, d, \epsilon$, or scaled optimally in $\epsilon, m$ but had additional polynomial factors in $d$ for general observables. Intriguingly, we also show via dimensionality reduction, that we can rescale $\epsilon$ and $d$ to reduce to the regime where $\epsilon \le O(d^{-1/2})$. Our algorithm draws upon representation-theoretic tools recently developed in the context of full state tomography.
• Abstract（参考訳）: ヒルベルト空間の次元において、ターゲット誤差が十分小さい逆多項式以下である状態において、シャドウトモグラフィと古典的影に対する最初の厳密なサンプル複雑性境界を与える。 正式には、$m\in\mathbb{N}$と$\epsilon \le O(d^{-12})$が与えられたとき、未知の混合状態$\rho\in\mathbb{C}^{d\times d}$のコピーを$O(\log(m)/\epsilon^2)$に測定し、$\rho$の古典的な記述を出力し、$m$の可観測物のコレクションを加算精度$\epsilon$内で見積もることができる。 以前は、より単純なシャドウトモグラフィーのタスク --$m$オブザーバブルが事前に知られている -- に対して、最もよく知られたレートは、$m, d, \epsilon$のすべてで、直にスケールするか、あるいは$\epsilon, m$で最適にスケールするか、あるいは一般的なオブザーバブルに対して$d$で追加の多項式係数を持つかのいずれかであった。 興味深いことに、次元還元によっても、$\epsilon$と$d$を再スケールして、$\epsilon \le O(d^{-1/2})$の政権に還元できることが示される。 提案アルゴリズムは,最近,フルステートトモグラフィの文脈で開発された表現理論ツールに基づく。

関連論文リスト

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Resource-efficient shadow tomography using equatorial stabilizer measurements [0.0]
  equatorial-stabilizer-based shadow-tomography schemes can estimated $M$ observables using $mathcalO(log(M), mathrmpoly(n), 1/varepsilon2)$ sample copy. 我々は、ランダムな純状態とマルチキュービットグラフ状態を持つ理論的に派生したシャドウ・トモグラフィー・サンプリングの複雑さを数値的に検証する。
  論文  参考訳（メタデータ） (2023-11-24T17:33:44Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。 巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。 我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
  論文  参考訳（メタデータ） (2023-01-04T04:15:40Z)
• Sample-optimal classical shadows for pure states [0.0]
  我々は、結合測定と独立測定の両方の設定において、純粋な状態に対する古典的なシャドウタスクを考察する。 独立測定では、$mathcal O(sqrtBd epsilon-1 + epsilon-2)$ sufficeを示す。
  論文  参考訳（メタデータ） (2022-11-21T19:24:17Z)
• Quantum tomography using state-preparation unitaries [0.22940141855172028]
  ユニタリへのアクセスが与えられると、$d$次元の量子状態の古典的記述を近似的に得るアルゴリズムを記述する。 状態の$varepsilon$-$ell$-approximationを得るには、$widetildeTheta(d/varepsilon)$ Unitaryのアプリケーションが必要です。 我々は、ランク=r$混合状態のシュターテン$q$最適推定値を得るための効率的なアルゴリズムを与える。
  論文  参考訳（メタデータ） (2022-07-18T17:56:18Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Sparse sketches with small inversion bias [79.77110958547695]
  逆バイアスは、逆の共分散に依存する量の推定を平均化するときに生じる。 本研究では、確率行列に対する$(epsilon,delta)$-unbiased estimatorという概念に基づいて、逆バイアスを解析するためのフレームワークを開発する。 スケッチ行列 $S$ が密度が高く、すなわちサブガウスのエントリを持つとき、$(epsilon,delta)$-unbiased for $(Atop A)-1$ は $m=O(d+sqrt d/ のスケッチを持つ。
  論文  参考訳（メタデータ） (2020-11-21T01:33:15Z)
• Faster Binary Embeddings for Preserving Euclidean Distances [9.340611077939828]
  本稿では, 高速で, 距離保存可能なバイナリ埋め込みアルゴリズムを提案し, データセット $mathcalTsubseteqmathbbRn$ を立方体 $pm 1m$ のバイナリシーケンスに変換する。 我々の手法は高速かつメモリ効率が良く、時間複雑性は$O(m)$、空間複雑性は$O(m)$である。
  論文  参考訳（メタデータ） (2020-10-01T22:41:41Z)

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

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