論文の概要: Polynomial-time exact diagonalization via sparse guided eigenwalks
- arxiv url: http://arxiv.org/abs/2606.23967v1
- Date: Mon, 22 Jun 2026 21:47:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-24 22:16:48.69582
- Title: Polynomial-time exact diagonalization via sparse guided eigenwalks
- Title（参考訳）: スパース誘導固有ウォークによる多項式時間精密対角化
- Authors: Zachary E. Chin, Mario Motta, Javier Robledo Moreno, Antonio Mezzacapo, Isaac L. Chuang, William Kirby,
- Abstract要約: エルミート行列のスパース固有ベクトルの支持を求める固有ウォーク問題を導入する。
すべてのスパース固有ベクトルに対して、グラフに強く局所化された同じ固有値を持つスパース固有ベクトルが存在することを証明している。
結果は、ハミルトニアンの縮退性、局所性、スペクトル幅、スペクトルギャップに関する仮定を伴わない。
- 参考スコア（独自算出の注目度）: 2.8221337927464547
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Computing quantum ground states is generically difficult, but additional structure can sometimes allow diagonalization to be recast as a more feasible problem. For example, when the desired ground state is sparse in a given basis, diagonalization can be facilitated via graph search. We make this reformulation precise by introducing the eigenwalk problem, which seeks the support of a sparse eigenvector of a Hermitian matrix by exploring the graph induced by its nonzero entries. However, it is not obvious whether the relevant support vertices must always be efficiently reachable by a search on the graph. To resolve this question, we prove that for every sparse eigenvector, there exists a (possibly different) sparse eigenvector with the same eigenvalue whose support is tightly localized in the graph, with diameter scaling only linearly in the sparsity and independently of the total number of vertices. As a consequence, if a $2^n$-dimensional, ${\rm poly}(n)$-sparse Hamiltonian has an $\mathcal{O}(1)$-sparse extremal eigenvector and one support element is known, then an exact eigenvector with the same eigenvalue can be computed classically in ${\rm poly}(n)$ time. The same conclusion follows when the $\mathcal{O}(1)$-sparse eigenvector is non-extremal, provided that it is sparser than every eigenvector with a different eigenvalue. These results hold with no assumptions on the degeneracy, locality, spectral width, or spectral gap of the Hamiltonian, and the underlying support-localization principle also extends to problems beyond exact diagonalization, such as sparse principal component analysis.
- Abstract（参考訳）: 量子基底状態の計算は一般に難しいが、追加の構造により、より現実的な問題として対角化が再キャストされることがある。
例えば、所定ベースで所望の基底状態がスパースである場合、グラフ探索により対角化を容易にすることができる。
我々は、エルミート行列のスパース固有ベクトルの支持を求める固有ウォーク問題を導入することにより、この修正を正確にする。
しかし、関連するサポート頂点が常にグラフ上の探索によって効率的に到達可能でなければならないかどうかは明らかではない。
この問題を解決するために、すべてのスパース固有ベクトルに対して、(おそらく異なる)スパース固有ベクトルが存在することを証明する。
その結果、$2^n$-次元、${\rm poly}(n)$-sparse Hamiltonian が$\mathcal{O}(1)$-sparse extremal eigenvector を持ち、一つのサポート要素が知られているなら、同じ固有値を持つ正確な固有ベクトルは ${\rm poly}(n)$ time で古典的に計算できる。
同じ結論は、$\mathcal{O}(1)$-sparse 固有ベクトルが非極大であるとき、異なる固有ベクトルを持つすべての固有ベクトルよりもスペーサーである。
これらの結果は、ハミルトニアンの縮退性、局所性、スペクトル幅、スペクトルギャップに関する仮定がなく、基礎となる支持局在化原理は、スパース主成分分析のような正確な対角化を超えた問題にも及んでいる。
関連論文リスト
- Complex Interpolation of Matrices with an application to Multi-Manifold Learning [12.540068560688958]
A1-x Bx$ for $0 leq x leq 1$ のスペクトル特性について検討する。
A$ と $Bx|$ の「共通構造」の存在は、この観点で調べることができる。
これらの結果から,多視点データにおける共通かつ別個の潜在構造を識別する多次元学習フレームワークの理論的正当化がもたらされる。
論文 参考訳（メタデータ） (2026-04-15T17:40:37Z) - Exponential quantum advantages for practical non-Hermitian eigenproblems [9.59420259768862]
我々は一般の非エルミート固有値問題に対処する量子アルゴリズムを開発した。
本手法は,ファジィ量子固有値検出器と分別・対数戦略を組み合わせることで,関連する固有値の効率よく分離する。
自発的な$PT$対称性の破れの検出、リウヴィリアのギャップの推定、古典マルコフ過程の解析における幅広い応用について論じる。
論文 参考訳（メタデータ） (2024-01-22T16:29:08Z) - Re-Analyze Gauss: Bounds for Private Matrix Approximation via Dyson
Brownian Motion [28.431572772564518]
対称行列 $M$ とベクトル $lambda$ が与えられたとき、行列によって$M$ を近似するガウス機構のフロベニウス距離ユーティリティ上の新しい境界を示す。
私たちのバウンダリは、$lambda$と$M$の固有値のギャップの両方に依存します。
論文 参考訳（メタデータ） (2022-11-11T18:54:01Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Sign and Basis Invariant Networks for Spectral Graph Representation
Learning [75.18802152811539]
SignNetとBasisNetは、すべての必須対称性に不変な新しいニューラルアーキテクチャであり、したがって、原則化された方法で固有空間のコレクションを処理する。
我々のネットワークは理論的にはグラフ表現学習に強い -- 任意のスペクトルグラフ畳み込みを近似することができる。
実験により、スペクトルグラフフィルタの学習とグラフ位置エンコーディングの学習のためのネットワークの強みが示された。
論文 参考訳（メタデータ） (2022-02-25T23:11:59Z) - Improved analysis of randomized SVD for top-eigenvector approximation [16.905540623795467]
そこで本研究では,無作為なSVDアルゴリズムであるcitethalko2011finding を新たに解析し,興味のある場合の厳密な境界を導出する。
特に、これは任意の反復数を持つランダム化SVDに対して$R(hatmathbfu)$の非自明な境界を与える最初の作品である。
論文 参考訳（メタデータ） (2022-02-16T11:12:07Z) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳（メタデータ） (2021-09-06T14:21:43Z) - Minimax Estimation of Linear Functions of Eigenvectors in the Face of
Small Eigen-Gaps [95.62172085878132]
固有ベクトル摂動解析は様々な統計データ科学の応用において重要な役割を果たす。
未知の固有ベクトルの任意の線型関数の摂動を特徴付ける統計理論の一組を開発する。
自然の「プラグイン」推定器に固有の非無視バイアス問題を緩和するために,非バイアス推定器を開発する。
論文 参考訳（メタデータ） (2021-04-07T17:55:10Z) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。
最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。
本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-10-25T18:12:50Z) - Tackling small eigen-gaps: Fine-grained eigenvector estimation and
inference under heteroscedastic noise [28.637772416856194]
ノイズの観測から、固有ベクトル推定と低ランク行列の推測に2つの根本的な課題が生じる。
未知固有ベクトルに対する推定と不確実性定量化手法を提案する。
未知固有値に対する信頼区間を構築するための最適手順を確立する。
論文 参考訳（メタデータ） (2020-01-14T04:26:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。