論文の概要: 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（参考訳）: スペクトル推定はトモグラフィーと同じくらい硬い
• Authors: Marco Fanizza, Ryan O'Donnell, Chirag Wadhwa,
• 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 を有界にすることで不明瞭性が得られる; 非ゼロの高次項とハールランドムユニタリーの関数の集中もまた、典型的なスペクトル、エントロピー、ランクにおける分離を暗示し、我々の下界を証明している。

関連論文リスト

• 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)
• 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)
• Tight Exponential Analysis for Smoothing the Max-Relative Entropy and for Quantum Privacy Amplification [56.61325554836984]
  最大相対エントロピーとその滑らかなバージョンは、量子情報理論の基本的な道具である。 我々は、精製された距離に基づいて最大相対エントロピーを滑らかにする量子状態の小さな変化の崩壊の正確な指数を導出する。
  論文  参考訳（メタデータ） (2021-11-01T16:35:41Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)

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

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