論文の概要: Spectrum Estimation is Almost as Hard as Tomography
- arxiv url: http://arxiv.org/abs/2607.29680v1
- Date: Fri, 31 Jul 2026 17:57:03 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-03 14:29:40.840591
- Title: Spectrum Estimation is Almost as Hard as Tomography
- Title（参考訳）: スペクトル推定はトモグラフィーと同じくらい硬い
- Abstract要約: 定位全変分誤差に対するスペクトル推定のために、サンプルの複雑さを$(d2-)$以下で証明する。
私たちのハードインスタンスは、Haar-randomプロジェクターのサンドイッチ製品から作られています。
- 参考スコア（独自算出の注目度）: 1.7205106391379026
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the sample complexity of estimating and testing fundamental unitarily invariant properties of unknown quantum states; namely, the tasks of spectrum estimation, von Neumann entropy estimation, and rank-testing. For $d$-dimensional states, and for every $γ>0$, we prove a sample complexity lower bound of $Ω(d^{2-γ})$ for spectrum estimation to constant sorted total-variation error, entropy estimation to constant additive error, and rank-testing to constant trace distance. Our hard instances are constructed from sandwiched products of Haar-random projectors, suitably normalized using a novel technique that lets us derive explicit expressions for high-order tensor moments of the resultant states. These moments can be expressed as symmetric functions of Jucys--Murphy elements of the symmetric group algebra. To show that two such mixtures are indistinguishable, we analyze the log-likelihood ratio and perform moment-matching, i.e., we set its low-order Jucys--Murphy components to zero. Indistinguishability is then obtained by bounding an $f$-divergence through the high-order components; the non-zero high-order terms and concentration of functions of Haar-random unitaries also imply separations in typical spectra, entropies, and ranks, proving all our lower bounds.
- Abstract（参考訳）: 未知の量子状態の基本的な単位不変性、すなわちスペクトル推定、フォン・ノイマンエントロピー推定、ランクテストのタスクを推定し、検証するサンプル複雑性について検討する。
$d$次元状態と、すべての$γ>0$に対して、定数ソートされた全偏差誤差へのスペクトル推定、定数加法誤差へのエントロピー推定、および定数トレース距離へのランクテストに対して、$Ω(d^{2-γ})$のサンプル複雑性の低い境界を証明する。
我々のハードインスタンスは、Haar-randomプロジェクターのサンドイッチ製品から構築され、その結果の高次テンソルモーメントに対する明示的な表現を導出する新しい技術を用いて、適切に正規化されている。
これらのモーメントは、対称群代数のジューシー-マーフィー要素の対称函数として表すことができる。
そのような2つの混合が区別できないことを示すために、ログ類似率を分析し、モーメントマッチング、すなわち、低階のジューシー-マーフィー成分をゼロに設定する。
その結果、高次成分を通して$f$-divergence を有界にすることで不明瞭性が得られる; 非ゼロの高次項とハールランドムユニタリーの関数の集中もまた、典型的なスペクトル、エントロピー、ランクにおける分離を暗示し、我々の下界を証明している。
関連論文リスト
- Uniqueness and Cramér-Rao Efficiency of Quantum U-Statistics [8.156494881838947]
本研究では,独立コピーからの量子状態のスカラー値関数の非バイアス推定について検討する。
偏りのない置換不変な推定器の中で、量子U統計は任意の数のコピーに対するユニークな拡張であることを示す。
論文 参考訳（メタデータ） (2026-09-08T13:37:19Z) - Spectral Convergence of Random Feature Method in Multiple Dimensions [5.361030050051251]
我々はまず,ソボレフ,ゲブリー,超分析,帯域制限クラスにおける多次元目標に対するランダム特徴法(RFM)のスペクトル収束性を示す。
この分析は一般的なメカニズムを特定しており、高精度なスペクトル近似が重篤な条件付けを引き起こすのと同じである。
論文 参考訳（メタデータ） (2026-09-03T06:01:00Z) - Time-series Random Process Complexity Ranking Using a Bound on Conditional Differential Entropy [0.8666096694354596]
Fangらによって確立された情報理論予測誤差境界に基づいて構築する。
条件付き微分エントロピー textbf$h(X_k mid X_k-1,...,X_k-m)$ は次ステップ予測誤差の行列式の関数によって上界となることを示す。
論文 参考訳（メタデータ） (2025-10-23T13:36:04Z) - Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。
我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。
また、異なるアンサンブルを区別する新しい問題も分析できます。
論文 参考訳（メタデータ） (2024-04-29T14:33:24Z) - Sampling and estimation on manifolds using the Langevin diffusion [45.57801520690309]
離散化マルコフ過程に基づく$mu_phi $の線形汎函数の2つの推定器を検討する。
誤差境界は、本質的に定義されたランゲヴィン拡散の離散化を用いてサンプリングと推定のために導出される。
論文 参考訳（メタデータ） (2023-12-22T18:01:11Z) - Random Lindblad operators obeying detailed balance [0.18899300124593646]
我々は、与えられた定常状態$sigma$ of size$N$に対して量子詳細バランス条件を満たすランダムリンドブラッド作用素$cal L$の異なるアンサンブルを導入する。
同様の普遍性は、ランダムなデイビーズ生成器のアンサンブルにスーパーデコヒーレンスを適用して得られる詳細なバランスに合うコルモゴロフ生成器に対して成り立つことを示す。
論文 参考訳（メタデータ） (2023-04-06T09:38:16Z) - Extremal jumps of circuit complexity of unitary evolutions generated by random Hamiltonians [0.0]
有限次元ヒルベルト空間におけるランダムに選択された強い相互作用を持つハミルトニアンの時間発展によって生じるユニタリの回路複雑性について検討する。
私たちは、$exp(-it H)$の複雑さが驚くべき振る舞いを示すことを証明しています -- 自明な(ゼロ)複雑さを持つユニタリからなるアイデンティティの近傍を逃れるために必要となる、同じ時間スケールで最大許容値に達する確率が高いのです。
論文 参考訳（メタデータ） (2023-03-30T17:05:06Z) - Near-Optimal Non-Parametric Sequential Tests and Confidence Sequences
with Possibly Dependent Observations [44.71254888821376]
我々は、一般的な非データ生成プロセスの下で、最初のタイプIエラーと予測リジェクション時間保証を提供する。
本研究では, 平均処理効果など, 方程式を推定することによって定義されるパラメータの推測に, 結果を適用する方法を示す。
論文 参考訳（メタデータ） (2022-12-29T18:37:08Z) - Clipped Stochastic Methods for Variational Inequalities with
Heavy-Tailed Noise [64.85879194013407]
単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。
この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。
さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
論文 参考訳（メタデータ） (2022-06-02T15:21:55Z) - Tight Exponential Analysis for Smoothing the Max-Relative Entropy and
for Quantum Privacy Amplification [56.61325554836984]
最大相対エントロピーとその滑らかなバージョンは、量子情報理論の基本的な道具である。
我々は、精製された距離に基づいて最大相対エントロピーを滑らかにする量子状態の小さな変化の崩壊の正確な指数を導出する。
論文 参考訳（メタデータ） (2021-11-01T16:35:41Z) - Mean-Square Analysis with An Application to Optimal Dimension Dependence
of Langevin Monte Carlo [60.785586069299356]
この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。
我々の理論解析は数値実験によってさらに検証される。
論文 参考訳（メタデータ） (2021-09-08T18:00:05Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。