論文の概要: Shadow Tomography Against Adversaries

• arxiv url: http://arxiv.org/abs/2512.05451v1
• Date: Fri, 05 Dec 2025 06:06:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-13 22:40:56.91487
• Title: Shadow Tomography Against Adversaries
• Title（参考訳）: 広告主に対するシャドウトモグラフィー
• Authors: Maryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia, Chia-Ying Lin, Yuhan Liu, Aadil Oufkir, Yu-Ching Shen,
• Abstract要約: すべての非適応型シャドウトモグラフィーアルゴリズムは、可観測値の選択に対して$varepsilon=tildeO(max_iin[M]|O_i|_HS)$の誤差を発生させなければならないことを示す。 我々は,無限コピーでも可観測性を選択するために,$varepsilon=tildeO(minsqrtM, sqrtd)$の誤差を実現するアルゴリズムを設計する。
• 参考スコア（独自算出の注目度）: 31.34964957208756
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study single-copy shadow tomography in the adversarial robust setting, where the goal is to learn the expectation values of $M$ observables $O_1, \ldots, O_M$ with $\varepsilon$ accuracy, but $γ$-fraction of the outcomes can be arbitrarily corrupted by an adversary. We show that all non-adaptive shadow tomography algorithms must incur an error of $\varepsilon=\tildeΩ(γ\min\{\sqrt{M}, \sqrt{d}\})$ for some choice of observables, even with unlimited copies. Unfortunately, the classical shadows algorithm by [HKP20] and naive algorithms that directly measure each observable suffer even more. We design an algorithm that achieves an error of $\varepsilon=\tilde{O}(γ\max_{i\in[M]}\|O_i\|_{HS})$, which nearly matches our worst-case error lower bound for $M\ge d$ and guarantees better accuracy when the observables have stronger structure. Remarkably, the algorithm only needs $n=\frac{1}{γ^2}\log(M/δ)$ copies to achieve that error with probability at least $1-δ$, matching the sample complexity of the classical shadows algorithm that achieves the same error without corrupted measurement outcomes. Our algorithm is conceptually simple and easy to implement. Classical simulation for fidelity estimation shows that our algorithm enjoys much stronger robustness than [HKP20] under adversarial noise. Finally, based on a reduction from full-state tomography to shadow tomography, we prove that for rank $r$ states, both the near-optimal asymptotic error of $\varepsilon=\tilde{O}(γ\sqrt{r})$ and copy complexity $\tilde{O}(dr^2/\varepsilon^2)=\tilde{O}(dr/γ^2)$ can be achieved for adversarially robust state tomography, closing the large gap in [ABCL25] where optimal error can only be achieved using pseudo-polynomial number of copies in $d$.
• Abstract（参考訳）: 対向ロバスト環境では単一コピーのシャドウトモグラフィーを研究し、目的は、$M$observables $O_1, \ldots, O_M$ with $\varepsilon$ accuracy, but $γ$-fraction of the outcomes can be arbitrarily corrupted by an adversary。 すべての非適応型シャドウトモグラフィアルゴリズムは、無限コピーであっても可観測性の選択に対して$\varepsilon=\tildeΩ(γ\min\{\sqrt{M}, \sqrt{d}\})$の誤差を発生させなければならないことを示す。 残念ながら、[HKP20]による古典的なシャドウアルゴリズムと、各観測可能度を直接測定するナイーブアルゴリズムは、さらに苦しむ。 我々は、$\varepsilon=\tilde{O}(γ\max_{i\in[M]}\|O_i\|_{HS})$の誤差を達成するアルゴリズムを設計する。 注目すべきは、このアルゴリズムは、少なくとも1-δ$の確率でその誤差を達成するために$n=\frac{1}{γ^2}\log(M/δ)$コピーしか必要とせず、測定結果が破損することなく同じ誤差を達成する古典的シャドウズアルゴリズムのサンプル複雑性と一致することである。 私たちのアルゴリズムは概念的にはシンプルで実装も簡単です。 有限性推定の古典的シミュレーションにより,我々のアルゴリズムは[HKP20]よりも強い強靭性を有することが示された。 最後に、フルステートトモグラフィーからシャドウトモグラフィーへの還元に基づいて、階数$r$状態に対して、$\varepsilon=\tilde{O}(γ\sqrt{r})$とコピー複雑性$\tilde{O}(dr^2/\varepsilon^2)=\tilde{O}(dr/γ^2)$の近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近近距離誤差が逆強固状態トモグラフィーに対して達成できることを証明し、最適な誤差が$d$の擬似ポノミカル数でのみ達成できることを証明した。

関連論文リスト

• The debiased Keyl's algorithm: a new unbiased estimator for full state tomography [1.4302622916198997]
  完全状態トモグラフィーのための最初の推定器であるデバイアスド・キールのアルゴリズムについて述べる。 我々は、$n = O(rd/varepsilon2)$コピーが、最適な距離誤差である$varepsilon$をトレースするためにランク-r$混合状態を学ぶのに十分であることを示す。 さらに、$n = O(rd/varepsilon2)$コピーは、より困難なBures距離で$varepsilon$の誤りを学習するのに十分であることを示す。
  論文  参考訳（メタデータ） (2025-10-09T05:07:12Z)
• Optimal lower bounds for quantum state tomography [0.9969485010222057]
  in mathbbCd times d$ up to error $varepsilon$ in trace distance において、$n = Omega(rd/varepsilon2)$コピーは階数 $r$ mixed state $rho を学ぶために必要であることを示す。 我々の証明における重要な技術的要素は、プロジェクタートモグラフィーのアルゴリズムで、トレース距離で$varepsilon$の誤差を学習するアルゴリズムを、より厳密なBuresで$O(varepsilon)$の誤差を学習するアルゴリズムに変換することである。
  論文  参考訳（メタデータ） (2025-10-09T02:36:48Z)
• Optimal high-precision shadow estimation [22.01044188849049]
  正式には、未知の混合状態$rhoinmathbbCdtimes d$のコピーを$O(log(m)/epsilon2)$に測定するプロトコルを提供します。 次元還元により、$epsilon$と$d$を再スケールして、$epsilon le O(d-1/2)$の政権に還元できることを示す。
  論文  参考訳（メタデータ） (2024-07-18T19:42:49Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• 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)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Quantum tomography using state-preparation unitaries [0.22940141855172028]
  ユニタリへのアクセスが与えられると、$d$次元の量子状態の古典的記述を近似的に得るアルゴリズムを記述する。 状態の$varepsilon$-$ell$-approximationを得るには、$widetildeTheta(d/varepsilon)$ Unitaryのアプリケーションが必要です。 我々は、ランク=r$混合状態のシュターテン$q$最適推定値を得るための効率的なアルゴリズムを与える。
  論文  参考訳（メタデータ） (2022-07-18T17:56:18Z)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• 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)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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