論文の概要: Classical and quantum spectral density estimation under local graph access

• arxiv url: http://arxiv.org/abs/2608.22769v2
• Date: Tue, 25 Aug 2026 01:46:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-26 14:09:34.122393
• Title: Classical and quantum spectral density estimation under local graph access
• Title（参考訳）: 局所グラフアクセスによる古典的および量子スペクトル密度推定
• Authors: Rong-Hua Li, Meihao Liao, Yichun Yang,
• Abstract要約: 局所アクセスモデルに基づく非重み付きグラフの正規化隣接行列のスペクトル密度推定について検討した。 We give a $widetilde O(eps-3)$-query algorithm that the spectrum density with Wasserstein-1 error at least $eps$。 グラフが十分に大きいとき、$widetilde(eps-4/3)$ quantum lower boundを証明します。
• 参考スコア（独自算出の注目度）: 13.320652433896122
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study spectral density estimation for the normalized adjacency matrix of an unweighted graph under local access model. Previously, Cohen-Steiner et al. [KDD 2018] proposed an algorithm for $\varepsilon$-approximate spectral density estimation in the Wasserstein-1 distance, using $2^{O(1/\varepsilon)}$ local queries to the graph. In this paper, we prove that every constant-success estimator with Wasserstein--$1$ error at most $\eps$ requires $2^{Ω(1/\eps)}$ queries, showing that the Cohen-Steiner algorithm is optimal up to constant in the exponent. This resolves the open problem left by previous researches Jin et al. [COLT 2023] and Peng et al. [COLT 2026]. We then turn to quantum local access model. We give an $\widetilde O(\eps^{-3})$-query algorithm estimating the spectral density with Wasserstein-1 error at most $\eps$. Finally, we prove a $\widetildeΩ(\eps^{-4/3})$ quantum lower bound when the graph is sufficiently large. As a result, quantum local access model changes the dependence on $\eps$ from exponential to polynomial.
• Abstract（参考訳）: 局所アクセスモデルに基づく非重み付きグラフの正規化隣接行列のスペクトル密度推定について検討した。 以前は Cohen-Steiner et al [KDD 2018] は、Wasserstein-1 距離における$\varepsilon$-approximate スペクトル密度推定のアルゴリズムを提案しており、このグラフへの局所クエリは $2^{O(1/\varepsilon)$である。 本稿では,Wasserstein を用いた任意の定数確率推定器を最大で 1$ の誤差は 2^{Ω(1/\eps)} のクエリを必要とすることを証明し,コーエン=スカイナーアルゴリズムが指数の定数まで最適であることを示す。 これにより、以前の研究であるJin et al [COLT 2023] と Peng et al [COLT 2026] の未解決問題が解決される。 次に、量子局所アクセスモデルに目を向けます。 We give a $\widetilde O(\eps^{-3})$-query algorithm that the spectrum density with Wasserstein-1 error at most $\eps$。 最後に、グラフが十分に大きいとき、$\widetildeΩ(\eps^{-4/3})$ 量子下界を証明する。 その結果、量子局所アクセスモデルは指数関数から多項式への$\eps$への依存を変化させる。

関連論文リスト

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• Faster Spectral Density Estimation and Sparsification in the Nuclear Norm [28.368253322669336]
  我々は,新しいグラフスペーシフィケーションの概念を導入し,これを核スペーシフィケーションと呼ぶ。 また,本手法はスペクトル密度推定のための最初の決定論的アルゴリズムを導出することを示した。
  論文  参考訳（メタデータ） (2024-06-11T17:50:20Z)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。 我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。 教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
  論文  参考訳（メタデータ） (2023-08-16T06:46:37Z)
• Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
  我々は、ワッサーシュタイン1距離において精度$epsilon$に近似できない$[-1,1]$に分布が存在することを示す。 正規化グラフ隣接行列のスペクトルに対する$epsilon$-accurate近似を一定の確率で計算することはできない。
  論文  参考訳（メタデータ） (2023-07-02T05:03:38Z)
• 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)
• Detection of $d_{1}\otimes d_{2}$ Dimensional Bipartite Entangled State: A Graph Theoretical Approach [1.5762281194023464]
  構成されたユニタリ写像$phi$はその純度に関して量子状態を特徴付けることを示す。 密度行列の最小固有値と連結部分グラフのエッジの重みの間の不等式を導出し、d_1 otimes d_2$次元二部量子状態の絡み合いを検出する。
  論文  参考訳（メタデータ） (2022-02-28T17:13:27Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。 十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。 ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
  論文  参考訳（メタデータ） (2021-11-29T19:26:28Z)
• Spectral density estimation with the Gaussian Integral Transform [91.3755431537592]
  スペクトル密度作用素 $hatrho(omega)=delta(omega-hatH)$ は線形応答論において中心的な役割を果たす。 スペクトル密度を近似する近似量子アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2020-04-10T03:14:38Z)

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

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