論文の概要: Pretty good shadow tomography

• arxiv url: http://arxiv.org/abs/2610.06781v1
• Date: Mon, 05 Oct 2026 17:44:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 22:51:31.289289
• Title: Pretty good shadow tomography
• Title（参考訳）: 良いシャドウトモグラフィー
• Abstract要約: O(log(m) log(m/) / varepsilon2)$の入力状態をコピーするシャドウトモグラフィーアルゴリズムを提供する。 既知の前者から引き出されたランダムな状態に対して、$O(log(m)/varepsilon2)$コピーのかなり良い測定は、前者のごく一部を除いて、常にエラーを保証します。 かなり良い測定は前者のランダム性に対する成功を増幅するが、測定のランダム性に対する成功を増幅するものではない。
• 参考スコア（独自算出の注目度）: 1.3834643970559857
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give a shadow tomography algorithm that uses $O(\log(m) \log(m/δ) / \varepsilon^2)$ copies of the input state. Specifically, given a quantum state $ρ$ and observables $O_1,\ldots,O_m$, the algorithm outputs estimates of $\mathrm{tr}(O_iρ)$ for all $i\in[m]$ that are all accurate to within $\pm\varepsilon$, except with probability at most $δ$. The key idea is to work in the average-case setting: for a random state drawn from a known prior, a pretty good measurement on $O(\log(m)/\varepsilon^2)$ copies gives a constant-error guarantee on all but a small fraction of the prior. Boosting this guarantee gives an average-case shadow tomography algorithm, and the minimax principle then (non-constructively) implies the existence of a measurement with the same worst-case guarantee. We also identify an obstruction to further improvement with this approach. While pretty good measurements amplify success over the randomness of the prior, they do not amplify success over the randomness of measurement. This issue appears to be inherent, and gives rise to the remaining $\log(m)$ factor separating the complexity of the quantum problem from its classical counterpart.
• Abstract（参考訳）: 入力状態のコピーとして$O(\log(m) \log(m/δ) / \varepsilon^2) を用いるシャドウトモグラフィーアルゴリズムを提案する。 具体的には、量子状態 $ρ$ とオブザーバブル $O_1,\ldots,O_m$ が与えられたとき、アルゴリズムは、最大$δ$の確率を除いて全ての$i\in[m]$に対して$\mathrm{tr}(O_iρ)$の見積もりを出力する。 既知の事前から引き出されたランダムな状態に対して、$O(\log(m)/\varepsilon^2)$コピーのかなり良い測定値が、前者のごく一部を除いて、常にエラーを保証します。 この保証を高めることで、平均ケースのシャドウトモグラフィーアルゴリズムが得られ、ミニマックスの原理は(非構成的に)同じ最悪ケースの保証を持つ測定の存在を示唆する。 このアプローチでさらに改善するための障害も特定します。 かなり良い測定は前者のランダム性に対する成功を増幅するが、測定のランダム性に対する成功を増幅するものではない。 この問題は本質的に成り立っていて、量子問題の複雑性を古典的な問題と区別する$\log(m)$因子が生じる。

関連論文リスト

• A Simple Algorithm for Best Separable State [5.5559749120901385]
  本研究では,無絡状態上での量子測定の最大受容確率を求める最適分離状態問題 (BSS) について検討する。 古典的な意味での目標は、$langle(x otimes y), M (x otimes y)rangle$ over unit vectors $x,y$ where $0 preceq M preceq I$である。
  論文  参考訳（メタデータ） (2026-08-10T19:04:15Z)
• Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach [2.956729394666618]
  シャドウトモグラフィーの高精度化過程における試料の複雑さについて検討した。 我々は、$O(mathrmpolylog(d))$$のコピー数に一度に作用するアダプティブな測定値を使用する。
  論文  参考訳（メタデータ） (2026-02-04T19:00:00Z)
• Shadow Tomography Against Adversaries [31.34964957208756]
  すべての非適応型シャドウトモグラフィーアルゴリズムは、可観測値の選択に対して$varepsilon=tildeO(max_iin[M]|O_i|_HS)$の誤差を発生させなければならないことを示す。 我々は,無限コピーでも可観測性を選択するために,$varepsilon=tildeO(minsqrtM, sqrtd)$の誤差を実現するアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2025-12-05T06:06:07Z)
• Dimension Independent and Computationally Efficient Shadow Tomography [0.0]
  シャドウトモグラフィーアルゴリズムは$n=Theta(sqrtmlog m/epsilon2)$サンプルを使用し、$m$の測定と追加エラー$epsilon$について説明する。 これは、ナイーブなアプローチを改善する、これまで知られていたすべてのアルゴリズムとは対照的である。
  論文  参考訳（メタデータ） (2024-11-03T03:07:35Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Quantum tomography using state-preparation unitaries [0.22940141855172028]
  ユニタリへのアクセスが与えられると、$d$次元の量子状態の古典的記述を近似的に得るアルゴリズムを記述する。 状態の$varepsilon$-$ell$-approximationを得るには、$widetildeTheta(d/varepsilon)$ Unitaryのアプリケーションが必要です。 我々は、ランク=r$混合状態のシュターテン$q$最適推定値を得るための効率的なアルゴリズムを与える。
  論文  参考訳（メタデータ） (2022-07-18T17:56:18Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• 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)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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