論文の概要: Optimal Shadow Estimation with Minimal Measurement Settings
- arxiv url: http://arxiv.org/abs/2606.20003v1
- Date: Thu, 18 Jun 2026 09:40:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-19 18:23:39.771949
- Title: Optimal Shadow Estimation with Minimal Measurement Settings
- Title（参考訳）: 最小測定設定による最適影推定
- Authors: Zhiyao Yang, Datong Chen, Huangjun Zhu,
- Abstract要約: シャドウ推定はランダム化測定から量子特性を予測するための強力なフレームワークである。
最悪のケース推定には$(d2)$baseが必要で、平均ケースのパフォーマンスは$(d)$ basesしか必要としない。
- 参考スコア（独自算出の注目度）: 3.398964351541323
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Shadow estimation is a powerful framework for predicting quantum properties from randomized measurements. While $3$-design protocols achieve optimal worst-case performance, the minimal number of measurement bases required for such optimality has remained open. Here we prove that $Θ(d^2)$ measurement bases are both necessary and sufficient for worst-case optimal shadow estimation and construct an explicit basis family. In stark contrast, any state $2$-design already suffices for average-case optimality: the mean squared shadow norm of normalized observables is bounded by a universal constant, and we prove strong concentration for Haar-random states, yielding constant sample complexity for generic pure-state fidelity estimation. Easily implementable $2$-designs -- from mutually unbiased bases, cyclic measurements, or shallow $\mathcal{O}(\log n)$-depth circuits -- enable optimal average-case protocols with remarkably simple measurement strategies. Our results establish a fundamental complexity separation: worst-case estimation requires $Θ(d^2)$ bases, whereas average-case performance requires only $Θ(d)$ bases, with broad implications for quantum information theory and near-term experiments.
- Abstract（参考訳）: シャドウ推定はランダム化測定から量子特性を予測するための強力なフレームワークである。
3ドルの設計プロトコルは最適な最悪の性能を達成するが、そのような最適性に必要な測定基準の最小限は未解決のままである。
ここでは、最低ケースの最適影推定と明示的な基底族の構築には、$(d^2)$測定基底が必要かつ十分であることを示す。
スターク対照的に、平均ケース最適性に対して既に2ドルの設計が十分である: 正規化可観測体の平均二乗影ノルムは普遍定数で有界であり、Haar-random状態に対して強い濃度を証明し、一般的な純粋状態の忠実度推定に一定のサンプル複雑性をもたらす。
相互にバイアスのないベースや循環測定、浅い$\mathcal{O}(\log n)$-depth 回路など、簡単に実装可能な2ドルの設計は、極めて単純な測定戦略で最適な平均ケースプロトコルを実現する。
最悪の場合の推定には$s(d^2)$basesが必要であるのに対し、平均ケースのパフォーマンスは$s(d)$basesしか必要とせず、量子情報理論や短期実験に広く影響する。
関連論文リスト
- Optimal algorithmic complexity of inference in quantum kernel methods [0.815557531820863]
量子カーネル法は、教師あり学習において量子優位性を達成するための主要な候補の一つである。
標準アプローチでは、各項をサンプリングによって独立に見積もっており、クエリの複雑さは$O(NlVertrVert2/varepsilon2)$である。
単一可観測体の期待値として全推論和を符号化したクエリ-最適組合せを提案する。
この結果から,クエリ最適化アルゴリズムと,ハードウェア能力による戦略選択の両立が期待できる。
論文 参考訳（メタデータ） (2026-04-16T16:45:02Z) - Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Strict Optimality of Frequency Estimation Under Local Differential Privacy [0.0]
本稿では、局所的な差分プライバシー下での周波数推定精度の厳密な最適性を確立する。
周波数推定器は, 対称かつ極端な構成であり, 最適化された値に等しい一定のサポートサイズで, 最大精度を実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2026-03-12T04:16:22Z) - An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
量子ビット効率の最適化を幾何学的問題として再検討する。
局所一貫性問題は、Sherali-Adams level-2 polytope $mathrmSA(2)$とちょうど一致する。
論文 参考訳（メタデータ） (2025-11-11T15:38:57Z) - Fast quantum measurement tomography with dimension-optimal error bounds [0.6144680854063935]
本稿では,古典的コプロセッシングコストに光を当てた2段階の量子計測トモグラフィープロトコルを提案する。
最悪ケース距離でエラー$epsilon$を達成するには$mathcalO(d3 L ln(d)/epsilon2)$サンプルが必要である。
また, 磁束可変トランスモン量子ビットを用いた雑音型超伝導量子コンピュータで行った経験的性能研究を補完する。
論文 参考訳（メタデータ） (2025-07-06T18:35:07Z) - A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。