論文の概要: A Quantum Algorithm for Computing All Eigenvalues and Eigenstates of Sparse Hermitian Matrices
- arxiv url: http://arxiv.org/abs/2611.16610v1
- Date: Thu, 12 Nov 2026 10:48:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.447777
- Title: A Quantum Algorithm for Computing All Eigenvalues and Eigenstates of Sparse Hermitian Matrices
- Title(参考訳): スパースエルミート行列のすべての固有値と固有状態を計算するための量子アルゴリズム
- Abstract要約: 我々は,それぞれの固有値の集合として定義されるスパースエルミート行列のスペクトルを決定する量子アルゴリズムを開発し,各固有値に対して,対応する固有ベクトルを固有空間の量子状態として準備する。
固有値は、所定の精度でバイナリ文字列として表現され、対応する固有ベクトルは量子状態として保持され、古典的な文字列を再構築する必要がなくなる。
- 参考スコア(独自算出の注目度): 3.530759252061682
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Computation of eigenvalues and eigenvectors of a sparse Hermitian matrix is a fundamental problem in algebra, arising both as a problem of independent interest and as a key subroutine in a wide range of computational and scientific applications. In this work, we develop a quantum algorithm that determines the spectrum of a sparse Hermitian matrix, defined as the set of its distinct eigenvalues, and for each eigenvalue, prepares a corresponding eigenvector as a quantum state in its eigenspace. The eigenvalues are represented as binary strings with a prescribed precision, while the corresponding eigenvectors are kept as quantum states, eliminating the need to reconstruct their classical counterparts. The algorithm instead enables estimation of expectation values $\braket{x|M|x}$, where $\ket{x}$ is a prepared eigenstate and $M$ is an observable. For an $n \times n$ $s$-sparse Hermitian matrix $H$, dense methods based on Householder tridiagonalization and QR iteration compute all eigenvalues and eigenvectors in $\mathcal{O}(n^3)$ time. Exploiting sparsity, the Lanczos method computes all eigenvalues in $\mathcal{O}(n^2 s)$ time in exact arithmetic, but recovering all eigenvectors still requires $\mathcal{O}(n^3)$ time. In contrast, our algorithm runs in time $\tilde{\mathcal{O}}(n s^2 \log^2 n / Δ_{\min})$, where $Δ_{\min}$ denotes the minimum spectral gap of the normalized matrix. For inverse gaps up to $Δ_{\min}^{-1} = \mathcal{O}(n)$, the most favorable scaling for $n$ distinct eigenvalues, attained by nearly uniformly spaced spectra such as those of perfect-state-transfer spin chains and the Sylvester-Kac matrix, and for sparsity up to $s = o(\sqrt{n}/\log n)$, the proposed algorithm achieves an improved asymptotic runtime over the classical $\mathcal{O}(n^3)$ approach for computing all eigenvalues and eigenvectors, under standard sparse-access assumptions.
- Abstract(参考訳): スパースエルミート行列の固有値と固有ベクトルの計算は代数の基本的な問題であり、独立利害問題と、幅広い計算および科学応用におけるキーサブルーチンとして生じる。
本研究では,それぞれの固有値の集合として定義されるスパースエルミート行列のスペクトルを決定する量子アルゴリズムを開発し,各固有値に対して,対応する固有ベクトルを固有空間の量子状態として準備する。
固有値は、所定の精度でバイナリ文字列として表現され、対応する固有ベクトルは量子状態として保持され、古典的な文字列を再構築する必要がなくなる。
代わりにアルゴリズムは期待値 $\braket{x|M|x}$ を推定できるが、$\ket{x}$ は準備された固有状態であり、$M$ は観測可能である。
a $n \times n$$s$-sparse Hermitian matrix $H$, dense method based on Householder tridiagonalization and QR iteration では、すべての固有値と固有ベクトルを $\mathcal{O}(n^3)$ time で計算する。
Lanczos法は、全ての固有値を正確な算術で$\mathcal{O}(n^2 s)$時間で計算するが、すべての固有ベクトルを復元するには$\mathcal{O}(n^3)$時間が必要である。
対照的に、我々のアルゴリズムは時間$\tilde{\mathcal{O}}(n s^2 \log^2 n / Δ_{\min})$で実行され、$Δ_{\min}$は正規化行列の最小スペクトルギャップを表す。
逆ギャップを$Δ_{\min}^{-1} = \mathcal{O}(n)$とすると、完全状態遷移スピンチェインやシルベスター・カック行列のようなほぼ均一に空間化されたスペクトルによって得られる$n$の異なる固有値に対する最も好ましいスケーリングと、古典的な$\mathcal{O}(n^3)$のスパース条件の下での全ての固有値と固有ベクトルの計算に対するアプローチは、より改良された漸近的実行を達成できる。
関連論文リスト
- Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。
我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
論文 参考訳(メタデータ) (2026-09-30T17:51:21Z) - Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
行列連鎖乗法は、科学計算、機械学習、グラフ解析における問題である。
我々は、$K$行列の$mathcalW$を回路深さの量子状態にエンコードする量子サブルーチンであるemphTwo-Tower Matrixを提案する。
論文 参考訳(メタデータ) (2026-07-14T18:42:40Z) - Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。
この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
論文 参考訳(メタデータ) (2025-08-28T17:04:18Z) - A quantum algorithm for estimating the determinant [4.369550829556577]
このアルゴリズムは、$n×n$正のスパース行列の行列式を精度$epsilon$ in time $cal O(log n/epsilon3)$と推定する。
量子スペクトルサンプリングアルゴリズムは、$sum_j f(lambda_j)$とすると、$lambda_j$は行列固有値である。
論文 参考訳(メタデータ) (2025-04-15T10:32:36Z) - Quantum Eigensolver for Non-Normal Matrices via Ground State Energy Estimation [0.4511923587827302]
大規模な固有値問題は、古典的コンピュータにとって大きな課題となっている。
本稿では,少なくとも1-p_rm fail$の確率で,固有値の推定値を加算誤差$epsilon$内に出力する量子アルゴリズムを提案する。
我々のアルゴリズムはこのスケーリングを実現する最初の一般固有値アルゴリズムである。
論文 参考訳(メタデータ) (2025-02-25T11:43:47Z) - Exponential quantum advantages for practical non-Hermitian eigenproblems [9.59420259768862]
我々は一般の非エルミート固有値問題に対処する量子アルゴリズムを開発した。
本手法は,ファジィ量子固有値検出器と分別・対数戦略を組み合わせることで,関連する固有値の効率よく分離する。
自発的な$PT$対称性の破れの検出、リウヴィリアのギャップの推定、古典マルコフ過程の解析における幅広い応用について論じる。
論文 参考訳(メタデータ) (2024-01-22T16:29:08Z) - 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) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳(メタデータ) (2020-11-12T16:29:45Z) - Rodeo Algorithm for Quantum Computing [0.0]
量子ハミルトニアンの固有ベクトルを生成できる量子計算アルゴリズムを提案する。
固有状態生成の速度は、推定や断熱進化の速度よりも指数関数的に速い。
論文 参考訳(メタデータ) (2020-09-09T04:12:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。