Fugu-MT 論文翻訳(概要): The Keyl-Werner algorithm is not optimal for spectrum estimation

論文の概要: The Keyl-Werner algorithm is not optimal for spectrum estimation

arxiv url: http://arxiv.org/abs/2607.27117v1
Date: Wed, 29 Jul 2026 16:46:05 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-30 21:06:25.745337
Title: The Keyl-Werner algorithm is not optimal for spectrum estimation
Title（参考訳）: Keyl-Wernerアルゴリズムはスペクトル推定に最適ではない
Abstract要約: 我々は,全変動距離において,$$ to constant error の固有値を推定するアルゴリズムを提案する。これは、Kel-Wernerアルゴリズムによるスペクトル推定の最初の改良である。
参考スコア（独自算出の注目度）: 1.4842441810416076
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We give an algorithm which, given $n = O(d^2 \cdot (\log\log(d)/\log(d))^2)$ copies of $ρ$, estimates the eigenvalues of $ρ$ to constant error in total variation distance. Thus, we can learn the eigenvalues of a quantum state with fewer copies than the $Θ(d^2)$ needed to run full state tomography. This is the first improvement to spectrum estimation over the influential Keyl-Werner algorithm, which uses $n = Θ(d^2)$ copies, thereby resolving a question raised by Keyl and Werner in 2001 and refuting a 2016 conjecture of Wright. Our main technical tool is a new tomography guarantee, where the error of tomography in a particular direction $|w\rangle$ scales with $\langle w | ρ|w\rangle$ for all directions simultaneously. From this stronger "relative-error" bound, we recover better algorithms for principal component analysis in Bures distance and tomography in $χ^2$-divergence as corollaries.
Abstract（参考訳）: 我々は、$ρ$のコピーとして$n = O(d^2 \cdot (\log\log(d)/\log(d))^2)$を与えられたアルゴリズムを与える。したがって、完全な状態トモグラフィーを実行するのに必要な$(d^2)$よりも少ないコピーで量子状態の固有値を学ぶことができる。これは、2001年にキールとワーナーが提起した質問を解消し、2016年のライト予想を否定する、影響力のあるキール・ワーナーアルゴリズムに対するスペクトル推定の最初の改善である。我々の主要な技術ツールは、新しいトモグラフィー保証であり、特定の方向のトモグラフィーの誤差を$|w\rangle$と$\langle w | ρ|w\rangle$で同時にスケールする。この強い「相対エラー」境界から、バーズ距離とトモグラフィーにおける主成分分析のためのより良いアルゴリズムを、コロリとして$ ^2$-divergence で回収する。

関連論文リスト

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)
Accelerated Evolving Set Processes for Local PageRank Computation [75.54334100808022]
この研究は、パーソナライズされたPageRank計算を高速化するために、ネストした進化したセットプロセスに基づく新しいフレームワークを提案する。このような局所化手法の時間複雑性は、PPRベクトルの$epsilon$-approximationを得るために$mintildemathcalO(R2/epsilon2), tildemathcalO(m)$によって上界となることを示す。
論文参考訳（メタデータ） (2025-10-09T09:47:40Z)
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)
Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism [5.4971134662997025]
SVTを多次元ベクトルに一般化する新しい一般化スパースベクトル法を定式化する。アプリケーションとして、我々は以前よりもバウンダリが良い多くの重要なグラフ問題を解く。我々は、$O(epsilon-1log n)$加法誤差と$O(n)$ラウンドでの乗算誤差のない$k$コア分解に対して、厳密なローカルエッジDPアルゴリズムを与える。
論文参考訳（メタデータ） (2025-08-04T08:26:58Z)
Beating full state tomography for unentangled spectrum estimation [4.162538161344671]
スペクトル推定のための最もよく知られたアルゴリズムは、完全な状態トモグラフィーと同じくらい多くのコピーを必要とする。これは、アンタングル計測の設定ではそうではないことを示す。そこで本研究では,スペクトル推定のサンプル複雑性が全状態トモグラフィーでのみ改善できることを示す。
論文参考訳（メタデータ） (2025-04-03T17:29:12Z)
Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文参考訳（メタデータ） (2023-09-20T21:41:59Z)
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)
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)
Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文参考訳（メタデータ） (2020-09-18T02:18:44Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)

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