論文の概要: Online Shadow Tomography Matching the Classical Bounds

• arxiv url: http://arxiv.org/abs/2607.29686v1
• Date: Fri, 31 Jul 2026 17:59:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-03 14:29:40.841491
• Title: Online Shadow Tomography Matching the Classical Bounds
• Title（参考訳）: 古典的境界に一致するオンラインシャドウトモグラフィー
• Abstract要約: emphOnline Shadow Tomography では、未知の$d$次元量子状態 $$ のコピーが与えられる。 各$A(t)$が与えられた後、$Tr(A(t))$を$pm $に見積もる必要があります。 % オフラインの場合、$A(1), ldots, A(m)$は前もって与えられるが、これもよく研究されている問題である。
• 参考スコア（独自算出の注目度）: 13.458467420475507
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In \emph{Online Shadow Tomography}, we are given copies of an unknown $d$-dimensional quantum state $ρ$, an adversary (adaptively) proposes a sequence of bounded observables $A^{(1)},\ldots,A^{(m)}$, and after each $A^{(t)}$ is given we must estimate $\Tr(A^{(t)}ρ)$ to within $\pm ε$. This is the direct quantum generalization of the classical problem of \emph{Adaptive Data Analysis}. %The ``offline'' case, in which $A^{(1)}, \ldots, A^{(m)}$ are given upfront, is also a well-studied problem. The main goal is to minimize the number of copies, $n$, required. Prior results for online Shadow Tomography were suboptimal in all three parameters $m, d, ε$, lagging behind the best known and classical rates~\cite{bassily2021algorithmic}, for which there is some evidence of optimality. In this work, we finally close this gap, giving a pair of algorithms matching the classical rates. The bound on the left is the first to achieve $o(\log^2 m)$-dependence together with $\poly(\log(d)/\eps)$; moreover, it improves all three exponents even in the \emph{Offline} Shadow Tomography setting. The bound on the right is known to be optimal among bounds independent of~$d$, and improves the best prior result by a $\sqrt{m} \log m$ factor. The key to our proof is a new framework for quantifying post-measurement damage, based on the quantum Efron--Stein decomposition.
• Abstract（参考訳）: emph{Online Shadow Tomography} では、未知の$d$-次元量子状態 $ρ$ のコピーが与えられ、(適応的に)逆元が有界な可観測値 $A^{(1)},\ldots,A^{(m)}$ の列を提案し、各$A^{(t)}$ が与えられた後、$\Tr(A^{(t)ρ)$ を$\pm ε$ 内で推定しなければならない。 これは、古典的問題である \emph{Adaptive Data Analysis} の直接量子一般化である。 % `offline'' の場合、$A^{(1)}, \ldots, A^{(m)}$ が前もって与えられる場合もよく研究される問題である。 主なゴールは、必要なコピー数、$n$を最小化することである。 オンラインシャドウ・トモグラフィーの以前の結果は、3つのパラメータ$m, d, ε$のすべてで最適であり、最もよく知られた古典的レート—\cite{bassily2021algorithmic} に遅れを取っていた。 この研究で、私たちは最終的にこのギャップを閉じ、古典的なレートと一致するアルゴリズムのペアを与えました。 左のバウンダリは$o(\log^2 m)$-dependenceを$\poly(\log(d)/\eps)$と共に達成した最初のものである。 右上の境界は~$d$とは独立な境界の中で最適であることが知られており、$\sqrt{m} \log m$ factor によって最優先の結果を改善する。 我々の証明の鍵は、量子Efron-Stein分解に基づいて、測定後の損傷を定量化する新しい枠組みである。

関連論文リスト

• 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)
• Linear Bandits on Ellipsoids: Minimax Optimal Algorithms [5.678465386088928]
  作用の集合が楕円体であるような計算線形帯域を考える。 この問題に対して、最初の既知のミニマックス最適アルゴリズムを提供する。 実行には、時間$O(dT + d2 log(T/d) + d3)$とメモリ$O(d2)$のみが必要である。
  論文  参考訳（メタデータ） (2025-02-24T14:12:31Z)
• Improved Regret in Stochastic Decision-Theoretic Online Learning under Differential Privacy [17.711455925206298]
  HuとMehta(2024年)は、オープンな問題を提起した:$varepsilon$-differential privacyの下で、決定論的オンライン学習($K$アクションと$T$ラウンドを含む)の最適なインスタンス依存率は何ですか?
  論文  参考訳（メタデータ） (2025-02-16T05:13:51Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• 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)
• Optimal and Efficient Algorithms for Decentralized Online Convex Optimization [51.00357162913229]
  分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。 我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。 我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
  論文  参考訳（メタデータ） (2024-02-14T13:44:16Z)
• On Accelerated Perceptrons and Beyond [17.479295705933698]
  RosenblattのPerceptronアルゴリズムは、$n$の線形分離可能なデータポイントを正しく分類する線形しきい値関数を見つけるのに使うことができる。 基本的な結果は、Perceptron が $Omega(sqrtlog n/gamma)$ iterations の後に収束するということである。 最近、より洗練されたアルゴリズムでこの速度を2乗係数で$Omega(sqrtlog n/gamma)$に改善する研究がいくつかある。
  論文  参考訳（メタデータ） (2022-10-17T19:12:30Z)
• Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs [111.75736569611159]
  線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。 我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。 これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
  論文  参考訳（メタデータ） (2022-05-23T17:59:18Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。 経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
  論文  参考訳（メタデータ） (2021-03-25T18:52:17Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• No quantum speedup over gradient descent for non-smooth convex optimization [22.16973542453584]
  ブラックボックスアクセスは(必ずしも滑らかではない)関数 $f:mathbbRn から mathbbR$ とその (サブ) 階数へのアクセスである。 私たちのゴールは、$epsilon$-approximate minimum of $f$ を、真極小から少なくとも$R$ の距離から始めることにある。 下界で使われる関数族はランダム化アルゴリズムでは難しいが、$O(GR/epsilon)$量子クエリで解くことができる。
  論文  参考訳（メタデータ） (2020-10-05T06:32:47Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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